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