作業系統死鎖銀行家演算法
作業系統中死鎖是可以通過銀行家演算法避免的。下面由小編為大家整理了作業系統的死鎖銀行家演算法的相關知識,希望對大家有幫助!
詳解
死鎖既然不好,我們就可以利用銀行家演算法避免死鎖。
1.銀行家演算法中的資料結構
***1*** 可利用資源向量Available。這是一個含有m個元素的陣列,其中的每一個元素代表一類可利用的資源數目,其初始值是系統中所配置的該類全部可用資源的數目,其數值隨該類資源的分配和回收而動態地改變。如果Available[j]=K,則表示系統中現有Rj類資源K個。
***2*** 最大需求矩陣Max。這是一個n×m的矩陣,它定義了系統中n個程序中的每一個程序對m類資源的最大需求。如果Max[i,j]=K,則表示程序i需要Rj類資源的最大數目為K。
***3*** 分配矩陣Allocation。這也是一個n×m的矩陣,它定義了系統中每一類資源當前已分配給每一程序的資源數。如果Allocation[i,j]=K,則表示程序i當前已分得R j類資源的數目為K。
***4*** 需求矩陣Need。這也是一個n×m的矩陣,用以表示每一個程序尚需的各類資源數。如果Need[i,j]=K,則表示程序i還需要R j類資源K個,方能完成其任務。
上述三個矩陣間存在下述關係:
Need[i, j]=Max[i, j]-Allocation[i, j]
2.銀行家演算法
設Request i是程序Pi的請求向量,如果Request i[j]=K,表示程序P i需要K個R j型別的資源。當P i發出資源請求後,系統按下述步驟進行檢查:
***1*** 如果Request i[j]≤Need[i,j],便轉向步驟***2***;否則認為出錯,因為它所需要的資源數已超過它所宣佈的最大值。
***2*** 如果Request i[j]≤Available[j],便轉向步驟***3***;否則,表示尚無足夠資源,Pi須等待。
***3*** 系統試探著把資源分配給程序P i,並修改下面資料結構中的數值:
Available[j]:= Available[j]-Request i[j];
Allocation[i,j]:= Allocation[i,j]+Request i[j];
Need[i,j]:= Need[i,j]-Request i[j];
***4*** 系統執行安全性演算法,檢查此次資源分配後系統是否處於安全狀態。若安全,才正式將資源分配給程序Pi,以完成本次分配;否則,將本次的試探分配作廢,恢復原來的資源分配狀態,讓程序Pi等待。
3.安全性演算法
系統所執行的安全性演算法可描述如下:
***1*** 設定兩個向量:
① 工作向量Work,它表示系統可提供給程序繼續執行所需的各類資源數目,它含有m個元素,在執行安全演算法開始時,Work:=Available。
② Finish,它表示系統是否有足夠的資源分配給程序,使之執行完成。開始時先做Finish[i]:=false;當有足夠資源分配給程序時,再令Finish[i]:=true。
***2*** 從程序集合中找到一個能滿足下述條件的程序:
① Finish[i]=false;
② Need[i,j]≤Work[j];若找到,執行步驟***3***,否則,執行步驟***4***。
***3*** 當程序Pi獲得資源後,可順利執行,直至完成,並釋放出分配給它的資源,故應執行:
Work[j]:= Work[j]+Allocation[i,j];
Finish[i]:=true;
go to step ***2***;
***4*** 如果所有程序的Finish[i]=true都滿足,則表示系統處於安全狀態;否則,系統處於不安全狀態。
作業系統死鎖檢測演算法