銀行家算法計算過程「什麼是銀行家算法c」

1、銀行家算法介紹

銀行家算法是最著名的死鎖避免算法。當進程首次申請資源時，要測試該進程對資源的最大需求量，如果系統現存的資源可以滿足它的最大需求量時，則按當前的申請量分配資源，否則，推遲分配。

2、數據結構描述

2.1、可利用資源矢量Avaiable

含有m個元素的數組，其中的每一個元素代表一類可用的資源數目。Available[j]=k，則表示系統中現有Rj類資源K個。

2.2、最大需求矩陣Max

為n×m矩陣，定義了系統中n個進程中的每一個進程對m類資源的最大需求。Max[i,j]=K，則表示進程i需要Rj類資源最大數目為K

2.3、分配矩陣Allocation

為n×m矩陣，定義了系統中每一類資源當前已分配給每一進程的資源數。Allocation[i,j]=K，則表示進程i當前已分配得Rj類資源的數目為K。

2.4、需求矩陣Need

為n×m矩陣，表示每個進程尚需的各類資源數，Need[i,j]=K，則表示進程i還需要Rj類資源數目為K

3、銀行家算法描述

3.1、銀行家算法

設Request i是進程Pi的請求矢量，如果Request i[j]=K，表示進程Pi需要Rj類資源K個。當Pi發出資源請求後，系統按下述步驟進行檢測：

1、如果Request i[j] ≤Need[i，j]，便轉向步驟2，否則認為出錯，因為它所需的資源數超過了它所宣布的最大值。
2、如果Request i[j] ≤Available[i，j]，便轉向步驟3，否則，表示尚無足夠資源，Pi須等待
3、系統試探着把資源分配給進程Pi，並修改下面數據結構中的數值：
			Available[j]=Availabe[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.2、安全性算法

1.設置兩個矢量。

• 工作矢量Work；它表示系統可提供給進程繼續運行所需的各類資源數目，它含有m個元素，在執行安全算法開始時，Work=Available；
• Finish：它表示系統是否有足夠的資源分配給進程，使之運行完成。開始時Finish[i]=false；當有足夠資源分配給進程Pi時，再令Finish[i]=true;

2.從進程集合中找到一個能滿足下述條件的進程：

• Finish[i]=false;
• Need[i,j]=Work[j];

若找到，執行下一步驟，否則，執行步驟4

3.當進程Pi獲得資源後，可順利執行，直至完成，並釋放分配給它的資源，共應執行：

• Work[j]=Work[j]+Allocation[i,j];
• Finish[i]=true;
• go to step (2)

4.如果所有進程的Finish[i]=true滿足，則表示系統處於安全狀態；否則系統將處於不安全狀態

4、銀行家算法舉例

假設系統中有5個進程{P0，P1，P2，P3，P4}和三類資源{A，B，C}，各種資源的數量分別為10、5、7，在T0時刻資源分配情況見下表：

T0時刻資源分配情況

利用安全性算法對T0時刻資源分配進行分析，由下表可知，在T0時刻存在着一個安全序列{P1，P3，P4，P2，P0}，故系統是安全的。

P1請求資源：P1發出請求矢量Request 1(1,0,2)系統按銀行家算法檢查：

Request 1(1,0,2)≤Need 1(1,2,2)
Request 1(1,0,2)≤Available1(3,3,2)
系統先假定可為P1分配資源，並修改Available 1、Allocation 1和Need 1矢量，由此形成的資源變化情況可見下表。
再利用安全性檢查此時系統是否安全。

P4請求資源：P4發出請求矢量Request 4(3,3,0)，系統按銀行家算法進行檢查：

Request 4(3,3,0)≤Need 4(4,3,1)
Request 4(3,3,0)＞Available(2,3,0)，讓P4等待

P0請求資源：P0發出請求矢量Request 0(0,2,0)，系統按銀行家算法進行檢查：

Request 0(0,2,0)≤Need 0(7,4,3)
Request 0(0,2,0)≤Available(2,3,0)

系統暫時假定可為P0分配資源，並修改有關數據，如下表

進行安全性檢查，可以資源Available(2,1,0)已不能滿足任何進程需要，故系統進入不安全狀態，此時系統不分配資源。