銀行家演算法

銀行家演算法（英語：Banker's Algorithm）是一個避免死結的著名演算法，是由荷蘭電腦科學家艾茲赫爾·戴克斯特拉在1965年為T.H.E作業系統設計的一種避免死結產生的演算法。它以銀行借貸系統的分配策略為基礎，判斷並保證系統的安全執行。

背景

在銀行中，客戶申請貸款的數量是有限的，每個客戶在第一次申請貸款時要聲明完成該專案所需的最大資金量，在滿足所有貸款要求時，客戶應及時歸還。銀行家在客戶申請的貸款數量不超過自己擁有的最大值時，都應儘量滿足客戶的需要。在這樣的描述中，銀行家就好比作業系統，資金就是資源，客戶就相當於要申請資源的行程。

處理程式

      Allocation　　Max　　　Available
      ＡＢＣＤ　　  ＡＢＣＤ　　ＡＢＣＤ
 P1   ００１４　　  ０６５６　　１５２０　
 P2   １４３２　　  １９４２　
 P3   １３５４　  　１３５６
 P4   １０００　　  １７５０

我們會看到一個資源分配表，要判斷是否為安全狀態，首先先找出它的Need，Need即Max（最多需要多少資源）減去Allocation（原本已經分配出去的資源），計算結果如下：

   NEED
 ＡＢＣＤ
 ０６４２　
 ０５１０
 ０００２
 ０７５０

然後加一個全都為false的欄位

 FINISH
 false
 false
 false
 false

接下來找出need比available小的（千萬不能把它當成4位元數 他是4個不同的數）

   NEED　　  Available
 ＡＢＣＤ　　ＡＢＣＤ
 ０６４２　　１５２０
 ０５１０<-
 ０００２
 ０７５０

P2的需求小於能用的，所以組態給他再回收

  NEED　　   Available
 ＡＢＣＤ　　ＡＢＣＤ
 ０６４２　　１５２０
 ００００　＋１４３２
 ０００２－－－－－－－
 ０７５０　　２９５２

此時P2 FINISH的false要改成true（己完成）

 FINISH
 false
 true
 false
 false

接下來繼續往下找，發現P3的需求為0002，小於能用的2952，所以資源組態給他再回收

 　NEED　　    Available
 ＡＢＣＤ　　Ａ　Ｂ　Ｃ　Ｄ
 ０６４２　　２　９　５　２
 ００００　＋１　３　５　４
 ００００－－－－－－－－－－
 ０７５０　　３　12　10　6

依此類推，做完P4→P1，當全部的FINISH都變成true時，就是安全狀態。

安全和不安全的狀態

如果所有Process都可以完成並終止，則一個狀態（如上述範例）被認為是安全的。由於系統無法知道什麼時候一個過程將終止，或者之後它需要多少資源，系統假定所有行程將最終試圖取得其聲明的最大資源並在不久之後終止。在大多數情況下，這是一個合理的假設，因為系統不是特別關注每個行程執行了多久（至少不是從避免死結的角度）。此外，如果一個行程終止前沒有取得其能取得的最多的資源，它只是讓系統更容易處理。

基於這一假設，該演算法通過嘗試尋找允許每個行程獲得的最大資源並結束（把資源返還給系統）的行程請求的一個理想集合，來決定一個狀態是否是安全的。不存在這個集合的狀態都是不安全的。

虛擬碼（pseudo-code）

P - 行程的集合

Mp - 行程p的最大的請求數目

Cp - 行程p當前被分配的資源

A - 當前可用的資源

while (P != ∅) {
    found = FALSE;
    foreach (p ∈ P) {
        if (Mp − Cp ≤ A) {
             /* p可以獲得他所需的資源。假設他得到資源後執行；執行終止，並釋放所擁有的資源。*/
             A = A + Cp ;
             P = P − {p};
             found = TRUE;
        }
    }
    if (! found) return FAIL;
}
return OK;

參考文獻

書籍

• 《作業系統概念（Operating System Concepts）》第六版[1] （頁面存檔備份，存於網際網路檔案館）