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