避免死鎖同樣屬于事先預防的政策，但是并不是事先采取某種限制措施來破壞死鎖的必要條件，而是在資源的動态配置設定過程中，防止系統進入不安全狀态，以避免發生死鎖。避免死鎖這種方法對資源的配置設定限制條件較弱（相比于預防死鎖），以期望獲得更好的系統性能。
關于安全狀态和不安全狀态的概念，可以參看這篇博文。
銀行家算法是我們的老朋友迪傑斯特拉為T.H.E系統設計的一種避免死鎖産生的算法。該算法最初是為銀行系統設計的，為了保證銀行在發放現金貸款時，不會發生不能滿足所有客戶需要的情況。
銀行家算法要求，每個新程序在進入系統時，它必須申明在運作過程中，可能需要每種資源類型的最大單元數目，其數目不應超過系統所擁有的的資源總量。當程序請求一組資源時，系統必須首先确定是否有足夠的資源配置設定給該程序。若有，在進一步的檢測将這些資源配置設定給程序後，是否會是系統處于不安全狀态；如果不會，才将資源配置設定給該程序，否則讓程序等待。
1.銀行家算法中的資料結構
為了實作銀行家算法，在系統中必須設定這樣四個資料結構，分别用來描述系統中可利用的資源、所有程序對資源的最大需求、系統中的資源配置設定、以及所有程序仍需要的資源情況。
- 可利用資源向量Available：這是一個含有m個元素的數組，其中的每一個元素代表一類可利用的資源數目，其初始值是系統中所配置的該類全部可用資源的數目，其數值随該類資源的配置設定和回收而動态地改變。如果Available[j]=K，則表示系統中現有Rj類資源K個；
- 最大需求矩陣Max：這是一個n×m的矩陣，它定義了系統中n個程序中的每一個程序對m類資源的最大需求。如果Max[i, j]=K，則表示程序Pi需要Rj類資源的最大數目為K；
- 配置設定矩陣Allocation：這也是一個n×m的矩陣，它定義了系統中每一類資源目前已配置設定給每一程序的資源數。如果Allocation[i, j]=K，則表示程序Pi目前已分得Rj類資源的數目為K；
- 需求矩陣Need：這也是一個n×m的矩陣，用以表示每一個程序尚需的各類資源數。如果Need[i, j]=K，則表示程序Pi還需要Rj類資源K個，方能完成其任務。
上述的三個矩陣Max、Allocation、Need存在下述關系：
N
e
d
[
i
,
j
]
=
M
a
x
−
A
l
o
c
t
n
Need[i, j] = Max[i, j] - Allocation[i, j]
Need[i,j]=Max[i,j]−Allocation[i,j]
2.銀行家算法
設Requesti是程序Pi的請求向量，如果Requesti[j]=K，表示程序Pi需要K個Rj類型的資源。當Pi發出資源請求Requesti(1,2,…,0)後（表示m類資源分别申請1,2,…,0個），系統按下述步驟進行檢查：
- 如果Requesti[j]<=Need[i, j]，（Requesti向量中的所有項都要判斷）便轉向步驟2；否則認為出錯，因為他所需要的資源數（已經持有的+此次申請的）已經超過它之前聲明的最大值。
- 如果Requesti[j]<=Available[i, j]，（Requesti向量中的所有項都要判斷）便轉向步驟3；否則表示目前OS中尚無足夠的資源滿足程序Pi的此次申請，Pi程序阻塞，需要等待資源釋放。
-
系統試探着把資源配置設定給程序Pi，并修改下面資料結構中的數值（Requesti向量中的所有項都要操作）：
Available[j] = Available[j] - Requesti[j]; //可用資源減去此次申請的資源
Allocation[i, j] = Allocation[i, j] + Requesti[j];//已經持有的資源加上此次申請的資源
Need[i, j] = Need[i, j] - Requesti[j];//仍需求資源減去此次申請的資源
- 系統執行安全性算法，檢查此次資源配置設定後系統是否處于安全狀态。若安全，才正式将資源配置設定給程序Pi，以完成本次配置設定；否則， 将本次的試探配置設定廢棄，恢複原來的資源配置設定狀态，讓程序Pi等待。
3.安全性算法
安全性算法是銀行家算法在第4步執行的子算法，用于檢查試探着把資源配置設定給程序Pi後OS的安全狀态。為了保證安全性檢查不影響Available、Max、Allocation和Need，其建立兩個向量（臨時變量）：
- 工作向量Work：表示系統可提供給程序繼續運作所需的各類資源數目，它含有m個元素(對應OS中的m類資源)，在執行安全算法開始時，Work=Available（Work初始化為Available）;
- 結束标志向量Finsh：表示系統是否有足夠的資源配置設定給所有程序，使之運作完成，它含有n個元素（對應OS中的程序數量n）。在執行安全算法開始時，Finsh中的所有位全為false，當有足夠資源配置設定給程序Pi時，再令Finish[i] = true。
安全性算法的執行步驟如下：
- 從程序集合中找到一個能滿足下述兩個條件的程序：①Finsh[i] == false;②Need[i, j]<=Work[j]，其中0=<j<m，即程序Pi所需的所有資源可以申請獲得；若找到，執行步驟2，否則執行步驟4。
- 當程序Pi獲得所需的所有資源後，可順利執行完畢，并釋放出配置設定給它的資源，是以需執行以下步驟：①Work[j] = Work[j] + Allocation[i, j]，其中0=<j<m，m為OS中的資源種類；②Finish[i] = true，表示程序Pi可以順利執行完畢；③跳轉到步驟1。
- 如果Finish向量中的所有位全部為true，即所有程序都可順利執行完畢，則表示系統處于安全狀态；否則，系統處于不安全狀态。
最後，将檢測結果傳回給步驟四，來決定此次資源請求是否配置設定。
安全性算法其實際目的就是看是否能找到一個安全序列，如果存在一個所有程序都可順利推進完成的安全序列，則表示此時OS是處于安全狀态，在這個狀态下不會産生死鎖
4.一個例子
下面我們通過一個例子來講解銀行家算法的執行過程。
例題：假定系統中有五個程序{P0, P1, P2, P3, P4}和三類資源{A, B, C}，各種資源的對應數量為10、5、7，在T0時刻的資源配置設定圖如下圖所示。
(1)請檢查T0時刻的安全性。
解：檢查T0時刻的安全性，其實際就是使用安全性算法檢測T0時刻OS的安全狀态。我們通過安全性檢查對T0時刻的資源配置設定狀況進行分析：首先執行算法步驟1，因為此時所有的程序Finish全為false，且程序P1與P3的需求向量都小于Work向量，是以我們選取程序P1（選取哪個程序皆可，安全序列不唯一），并依次執行步驟2、3，完成後Work={5, 3, 2}，轉為執行步驟1…
經過安全性算法分析，分析過程如下圖所示，OS在T0時刻存在一個安全序列{P1, P3, P4, P2, P0}，故系統是安全的。
(2)在T0時刻，程序P0送出請求向量Request0(0, 3, 0)，OS是否可以把資源配置設定給程序P0?
解：P0請求資源，系統按照銀行家算法進行檢查：
①Request0(0, 3, 0) <=Need0(7, 4, 3);
②Request0(0, 3, 0)<=Available(3, 3, 2);
③系統先假定可為程序P0配置設定資源，并修改相關資料：
Available = Available(3, 3, 2) - Request0(0, 3, 0) = (3, 0, 2);
Allocation0= Allocation0(0, 1, 0) + Request0(0, 3, 0) = (0, 4, 0);
Need0 = Need0(7, 4, 3) - Request0(0, 3, 0) = (7, 1, 3);
目前資源配置設定表如下所示:
④進行安全性檢查，可用資源Available(3, 0, 2)已經不能滿足任何程序的需要，故系統進入不安全狀态，程序P0請求的資源不能配置設定。
5.總結
銀行家算法是一個非常經典的算法，也是死鎖避免算法中的最具代表性的算法，其思想是非常值得我們學習的。死鎖處理的四種方法：預防死鎖、避免死鎖、檢測死鎖、解除死鎖。其中預防死鎖最為複雜，需要為OS設定各種定律、準則，較難實作，且較為影響系統的性能，最主要的就是并發效率下降；避免死鎖可以讓OS不必遵循特定的準則，是以給OS施加的限制較小，設計者也希望能通過此獲得更好的系統性能，但是因為需要程序提前申明所需的最大資源，是以程序在進入系統前需要先對自身所需資源的進行一個最壞情況下的預估（要滿足運作，必定是>=實際需要的，否則因為銀行家算法在第一步就給卡死就非常冤了），但是這樣，也必定會影響系統的并發，進而影響系統性能；死鎖的檢測和解除，是采用的“鴕鳥政策”，我不關心你會不會發生死鎖，OS定時進行死鎖檢測，發現後進行解除，通過這種方式，反而可以獲得更好的并發，因為在銀行家算法中，許多情況下，不安全狀态并不一定會轉換為死鎖。
但是OS選取何種方法，也是需要根據自身設計的一個目的來標明，沒有哪個方法一定比哪個好。
又到了分隔線以下，本文到此就結束了，本文内容全部都是由部落客自己進行整理并結合自身的了解進行總結，如果有什麼錯誤，還請批評指正。
如有興趣，還可以檢視我的其他幾篇部落格，都是OS的幹貨，原創不易，喜歡的話還請點贊、評論加關注_。