銀行家算法

銀行家算法是最有代表性的避免死鎖的算法。為實作銀行家算法，需要設定若幹個資料結構。

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目前已分得Rj類資源的數目為K。

（4）需求矩陣Need。這也是一個n*m的矩陣，用以表示每一個程序尚需的各類資源數。如果Need[i,j]=K，則表示程序i還需要Rj類資源K個，方能完成其任務。

上述三個矩陣間存在的關系：

　　　　　　　　Need[i,j]=Max[i,j]-Allocation[i,j]

2.銀行家算法

設Request(i)是程序P(i)的請求向量，如果Request(i)[j]=K，表示程序P(i)需要K個Rj類型的資源。當P（i）發出資源請求後，系統按下述步驟進行檢查：

（1）如果Request(i)[j]<=Need[i,j]，便轉向步驟（2）；否則認為出錯，因為它所需要的資源超出了它宣布的最大值。

（2）如果Request(i)[j]<=Avaiable[j]，便轉向步驟（3）；否則表示尚無足夠資源，P(i)須等待。

（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）系統執行安全性算法，檢查此資源配置設定後系統是否處于安全狀态。若安全，才正式将資源配置設定給程序P(i)，以完成本次配置設定；否則，将本次的試探配置設定廢棄，恢複原來的資源配置設定狀态，讓程序P(i)等待。

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）當程序P(i)獲得資源後，可順序執行，直至完成，并釋放出配置設定給它的資源，故應執行：

Work[j]=Work[j]+Allcation[i,j];

Finish[i]=true;

go to step 2;

（4）如果所有程序的Finish[i]=true都滿足，則表示系統處于安全狀态；否則，系統處于不安全狀态。