銀行家算法---------概念&舉例

銀行家算法是一種用來避免作業系統死鎖出現的有效算法，是以在引入銀行家算法的解釋之前，有必要簡單介紹下死鎖的概念。

死鎖：是指兩個或兩個以上的程序在執行過程中，由于競争資源或者由于彼此通信而造成的一種阻塞的現象，若無外力作用，它們都将無法推進下去。此時稱系統處于死鎖狀态或系統産生了死鎖，這些永遠在互相等待的程序稱為死鎖程序。

死鎖的發生必須具備以下四個必要條件：

1）互斥條件：指程序對所配置設定到的資源進行排它性使用，即在一段時間内某資源隻由一個程序占用。如果此時還有其它程序請求資源，則請求者隻能等待，直至占有資源的程序用畢釋放。

2）請求和保持條件：指程序已經保持至少一個資源，但又提出了新的資源請求，而該資源已被其它程序占有，此時請求程序阻塞，但又對自己已獲得的其它資源保持不放。

3）不搶占條件：指程序已獲得的資源，在未使用完之前，不能被剝奪，隻能在使用完時由自己釋放。

4）循環等待條件：指在發生死鎖時，必然存在一個程序——資源的環形鍊，即程序集合{P0，P1，P2，···，Pn}中的P0正在等待一個P1占用的資源；P1正在等待P2占用的資源，……，Pn正在等待已被P0占用的資源。

避免死鎖算法中最有代表性的算法就是Dijkstra E.W 于1968年提出的銀行家算法，銀行家算法是避免死鎖的一種重要方法，防止死鎖的機構隻能確定上述四個條件之一不出現，則系統就不會發生死鎖。

為實作銀行家算法，系統必須設定若幹資料結構，同時要解釋銀行家算法，必須先解釋作業系統安全狀态和不安全狀态。

安全序列:是指一個程序式列{P1，…，Pn}是安全的，即對于每一個程序Pi(1≤i≤n），它以後尚需要的資源量不超過系統目前剩餘資源量與所有程序Pj (j < i )目前占有資源量之和。

安全狀态：如果存在一個由系統中所有程序構成的安全序列P1，…，Pn，則系統處于安全狀态。安全狀态一定是沒有死鎖發生。

不安全狀态：不存在一個安全序列。不安全狀态不一定導緻死鎖。

資料結構：

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]

銀行家算法:

設Request(i)是程序Pi的請求向量，如果Request(i)[j]=k，表示程序Pi需要K個R(j)類型的資源。當Pi發現資源請求後系統将進行下列步驟

(1)如果Request(i)[j] <= Need[i,j],邊轉向步驟2),否則認為出錯，因為它所請求的資源數已超過它所宣布的最大值。

(2)如果Request(i)[j] <= Available[i,j]，便轉向步驟3)，否則，表示尚無足夠資源，Pi需等待。

(3)系統試探着把資源配置設定給程序Pi，并需要修改下面資料結構中的數值；

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];

說了這麼多基本的概念，下面就讓我們通過實際案例來體會銀行算法吧。

銀行家算法之例:

解析:

從圖中資料我們可以利用銀行家算法的四個資料結構，來描述目前的系統狀态

Max	Allocation	Need	Available
A	B	C	A	B	C	A	B	C	A     B     C
P1	5	5	9	2	1	2	3	4	7	2     3      3
P2	5	3	6	4	2	1	3	4
P3	4	11	4	5	6
P4	4	2	5	2	4	2	2	1
P5	4	2	4	3	1	4	1	1

因為系統資源R=（17,5,20）而系統配置設定給這幾個線程的資源為Allocation=(15,2,17) 則可以求出Available=（2,3,3）

(1)在T0時刻，由于Availabel大于等于Need中 P5 所在行的向量，是以Availabel能滿足 P5 的運作，在 P5 運作後，系統的狀态變更為如下圖所示:

Work	Need	Allocation	Work+Allocation	finsh
A	B	C	A	B	C	A	B	C	A	B	C
P5	2	3	3	1	1	3	1	4	5	4	7	true
P4	5	4	7	2	2	1	2	4	7	4	11	true
P3	7	4	11	6	4	5	11	4	16	true
P2	11	4	16	1	3	4	4	2	15	4	18	true
P1	15	4	8	3	4	7	2	1	2	17	5	20	true

是以，在T0時刻，存在安全序列：P5，P4，P3，P2，P1（并不唯一）

(2)P2請求資源，P2送出請求向量Request(i)(0,3,4),系統根據銀行家算法進行檢查;

 ① P2 申請資源Reuqest(i)（0,3,4）<=Need中 P2 所在行向量Need(i)（1,3,4）

 ② P2 申請資源Reuqest(i)（0,3,4）>=可以利用資源向量Availabel（2,3,3），是以，該申請不給于配置設定

(3)P4請求資源，P4送出請求向量Request(i)(2,0,1),系統根據銀行家算法進行檢查;

2,0,1）<= Need(i)（2,2,1）

 ② Reuqest(i)（2,0,1 <= Availabel（2,3,3）

 ③對 P4 的申請（2,0,1）進行預配置設定後，系統的狀态為：

Max	Allocation	Need	Available
A	B	C	A	B	C	A	B	C	A    B   C
P1	5	5	9	2	1	2	3	4	7	0   3    2
P2	5	3	6	4	2	1	3	4
P3	4	11	4	5	6
P4	4	2	5	4	5	2
P5	4	2	4	3	1	4	1	1

可利用資源向量Availabel=（0,3,2），大于Need中 P4 所在行的向量（0,2,0），是以可以滿足 P4 的運作。P4 運作結束後，系統的狀态變為：

Work	Need	Allocation	Work+Allocation	finsh
A	B	C	A	B	C	A	B	C	A	B	C
P4	3	2	2	4	5	4	3	7	true
P5	4	3	7	1	1	3	1	4	7	4	11	true
P3	7	4	11	6	4	5	11	4	16	true
P2	11	4	16	1	3	4	4	2	15	4	18	true
P1	15	4	18	3	4	7	2	1	2	17	5	20	true

同理依次推導，可計算出存在安全序列P4，P5，P3，P2，P1(并不唯一）

(4)P1請求資源，P1送出請求向量Request(i)(0,2,0),系統根據銀行家算法進行檢查;

Request(i)(0,2,0)<= Need(i)（3,4,7）

Request(i)(0,2,0)<= Availabel（2,3,3）

 ③對 P1 的申請（0,2,0）進行預配置設定後，系統的狀态為：

Max	Allocation	Need	Available
A	B	C	A	B	C	A	B	C	A  B  C
P1	5	5	9	2	3	2	3	2	7	0  1  2
P2	5	3	6	4	2	1	3	4
P3	4	11	4	5	6
P4	4	2	5	2	4	2	2	1
P5	4	2	4	3	1	4	1	1

由于Availabel不大于等于 P1 到 P5 任一程序在Need中的需求向量，是以系統進行預配置設定後

處于不安全狀态，是以對于 P1 申請資源（0,2,0）不給予配置設定。

注意:因為(4)是建立在第(3)問的基礎上的是以Available=（0,3,2）-（0,2,0）=（0,1,2）