「操作系統OS」避免死鎖的典型方法——銀行家演算法
死鎖是操作系統學科中的一個重要研究內容
所謂死鎖是指計算機系統和進程所處的一種狀態。即如果一組進程中的每一個進程都在等待僅由該組進程中的其他進程才能引發的事件，那麼該組進程是死鎖的（Deadlock）。
死鎖
目前處理死鎖的方法歸為四種
預防死鎖：預防死鎖是一種較易實現的方法，已被廣泛使用。
避免死鎖：最有代表性的避免死鎖的演算法就是 Dijkstra提出的銀行家演算法。
檢測死鎖：這種方法無需事先採取任何限制性措施，允許進程在進行過程中發生死鎖。
解除死鎖：當檢測到系統中已發生死鎖時，就採取措施，將進程從死鎖狀態中解脫出來。
利用銀行家演算法避免死鎖
銀行家演算法是避免死鎖的演算法。 銀行家通過發放貸款而獲取利潤 ,要獲取利潤必須按時收回貸款本金和利息 ,即貸款企業要按時還本付息 ,而只有各企業能不斷獲得所需資金最終完成項目才能還本付息。 要避免的情況是: 在某個時刻 ,各并行推進項目的企業均得到了一部分貸款 ,要使項目順利推進還需要貸款 ,而銀行家已經沒有多餘資金 ,從而導致各企業間循環等待對方釋放其佔有的資金而使項目中斷 ,造成一種僵滯局面 ,銀行家因收不回貸款而破產。
Advertisements
銀行家
操作系統的資源分配類似於銀行家貸款。 操作系統就像一個銀行家 ,系統臨界資源就像銀行家的貸款本金 ,併發進程就像需要貸款的企業。 因此可把銀行家規避風險的演算法引入操作系統的資源分配 ,解決資源分配中的死鎖問題。
銀行家演算法基本思想
在銀行家演算法中 ,為了決定是否對當前申請資源的進程進行資源分配 ,將系統狀態劃分為安全狀態和不安全狀態。若為當前申請資源的進程分配資源后系統進入安全狀態 ,則接受進程請求為其分配資源 ,否則拒絕進程請求不為其分配資源。
安全狀態: 從當前時刻起 ,若系統能按某種進程順序 ( P 0 ,P 1 ,… , P n )逐個分配所需全部剩餘資源 ,使各進程依次運行完畢 ,則稱此時刻系統處於安全狀態 ,上述進程序列稱為安全序列。 否則系統處於不安全狀態。
Advertisements
銀行家演算法中的數據結構
可利用資源向量 Available：這是一個含有m 個元素的數組, 其中每個元素代表一類可利用的資源數目, 初始值為系統中所配置的該類全部可用資源的數目，其數值隨該類資源的分配和回收而動態的改變。如果Available[j]=k，則表示系統中現有Rj 類資源k 個。
最大需求矩陣 Max :這是一個n*m 的矩陣, 定義了系統中的每個進程對m類資源的最大需求。若Max[i，j]=K ,表示進程 i需要Rj類資源的數目為K 。
分配矩陣Allocation:這也是一個n*m 的矩陣, 它定義了系統中每一類資源當前已分配給每一個進程的資源數。若Allocation [i，j]=K ,表示進程i當前已獲得 Rj 類資源的數目為 K 。
需求矩陣 Need:這也是一個 n*m 的矩陣, 用以表示每一個進程尚需的各類資源數。若N eed[i，j]=K ,表示進程i還需要Rj 類資源K 個，方能完成其任務 。
銀行家演算法
銀行家演算法
設Request i是進程Pi的請求向量，如果Request i[j] = K，表示進程Pi需要K個Rj類型的資源。當Pi發出資源請求后，系統按下述步驟進行檢查；
如果Request i[j]<=Need[i,j],便轉向步驟2；否則認為出錯，因為他所需要的資源數已超過它所宣布的最大值。
如果Request i[j]<=Available[j]，便轉向步驟3；否則表示尚無足夠資源，Pi需等待。
系統試探著把資源分配給進程Pj，並修改下列數據結構中的數值：
Available [ j ]= Available [ j ]— Requesti [ j ];
Allocation [ i , j ]= Allocation [ i , j ]+Requesti [ j ];
Need[i, j]= Need[i, j]— Requesti[j];
4. 系統執行安全性演算法 ,檢查此次資源分配后 ,系統是否處於安全狀態。 若安全 ,才正式將資源分配給進程 ,以完成本次分配; 否則將本次的試探分配作廢 ,恢復原來的資源分配狀態 ,讓進程 P i 等待。
安全性演算法
（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 都滿足 ,則表示系統處於安全狀態;否則系統處於不安全狀態。
例子我就不舉了，其實演算法很簡單，用起來也很方便。