Posted on 2007-03-21 19:00
kk 閱讀(5376)
評論(5) 編輯 收藏 引用 所屬分類:
Algorithm
銀行家算法是著名的操作系統用來解決死鎖問題的算法。
它是如何實現解決死鎖問題的呢？
今天稍微學習了一下，就稍微說一下其原理吧，免得忘了。其實原理很簡單！
???? Banker algorithm
最重要的一點是：保證操作系統的安全狀態！這也是操作系統判斷是否分配給一個進程資源的標準！那什么是安全狀態？舉個小例子，進程
P
需要申請
8
個資源（假設都是一樣的），已經申請了
5
個資源，還差
3
個資源。若這個時候操作系統還剩下
2
個資源。很顯然，這個時候操作系統無論如何都不能再分配資源給進程
P
了，因為即使全部給了他也不夠，還很可能會造成死鎖。若這個時候操作系統還有
3
個資源，無論
P
這一次申請幾個資源，操作系統都可以滿足他，因為操作系統可以保證
P
不死鎖，只要他不把剩余的資源分配給別人，進程
P
就一定能順利完成任務。
?
為什么銀行家算法是可行的呢？這里需要嚴格的證明一下。我這里就簡單得說一下吧。不管任何時候，操作系統分配資源的時候都可以保證當前接受資源的進程不會陷入死鎖，因為操作系統總是可以滿足該進程需要的資源的。
假設有
n
個進程
{p1, p2, p3, … pn}
，最后一個分配到資源的是
pi
，
pi
還需要
mi
個資源，假設此時操作系統還有
m
個資源剩余。那么很顯然
m>=mi
！而且如果之后操作系統又把資源分配給其他進程了，假設是
pj
，
pj
還需要
mj
個資源，同理可知
m>=mj
！也就是說在所有的進程中，還需要的資源數總是有小于
m
的！這樣就可以保證資源數永遠不會為
0
，即使可能暫時性為
0
。另外，還需要保證資源數不會減少！而且，所有已經分配到資源的進程總有一天會歸還它所擁有的資源！根據操作系統再分配的時候的狀態即可判定。
胡說八道了一通。。。不知有沒有把問題講明白了，還是越講越糊涂？
GL & HF