基于銀行家算法的安全序列分析

李坤芩 熊琰 王磊 田豐

（貴州商學院計算機與信息工程學院 貴州省貴陽市 550014）

操作系統調度算法有很多，如FCFS、SJF、RR 算法、銀行家算法等[1]。避免死鎖的最具代表性算法——銀行家算法，銀行能把資金貸給所有需要的客戶，不會發生不滿足的情況。在操作系統中，利用銀行家算法的思想來避免死鎖，即所有進程都必須保證能利用系統最大數量的資源，運行完成后將其資源釋放給系統。

1 安全序列

系統有兩種狀態，即安全和不安全。當系統處在安全狀態時，可以避免死鎖；當系統處在不安全狀態時，可能會發生死鎖的發生[1]。系統能夠按照某種進程推進順序（P1,P2,...,Pn）為所有進程分配其所需要的資源，使所有進程都能如期完成，則系統處于安全狀態，便不會進入死鎖狀態，（P1,P2,...,Pn）為安全序列[1]。如果系統不能找到一個安全序列，則系統處于不安全狀態[1]，有可能進入死鎖狀態。因此，避免死鎖的本質就是使系統不要進入不安全狀態。

2 銀行家算法的數據結構

算法中有Available、Max、Allocation 和Need 四個數據結構，還存在以下關系：Need=Max-Allocation，詳情如下：

（1）可分配資源向量Available，系統最后還剩下的可利用資源個數[2]。

（2）最大需求矩陣Max，某個進程一共需要的資源個數[2]。

（3）分配矩陣Allocation，某個進程已經占有的資源個數[2]。

（4）需求矩陣Need，某個進程還需要的資源個數[2]。

3 銀行家算法

假設系統中有進程M 個，當進程Pi 申請（Requesti）資源時，資源分配如下：

（1）如果Requesti≤Needi，則轉向第（2）步；反之出錯返回。

（2）如果Requesti≤Available，則轉向第（3）步；反之進程Pi等待。

（3）假定進程Pi得到資源分配并修改以下參數[3]：

Available=Available-Requesti

Allocationi=Allocationi+Requesti

Needi=Needi-Requesti

（4）安全性算法檢查：如果系統能找到安全序列，說明系統安全，可以順利進行[3]；反之進程Pi等待[3]。

4 安全性算法

（1）工作向量Work，初始值為Available 的值；Finish，初始值為False，如果存在充足的資源，那么Finishi的值為True。

（2）找到進程符合以下要求[1]：

Finishi=False

Needi≤Work

如果能找到符合以上條件的進程，則轉向下面的第（3）步，否則，轉向第（4）步。

（3）假設進程Pi獲得資源，修改以下參數：

Work=Work+Allocation

Finishi=True

繼續執行第（3）步；

（4）當所有進程的Finishi=True，表明安全；反之，表明不安全。

從銀行家算法和安全性算法可知，如果系統能找到一個安全序列，說明系統是安全的，才能分配資源。

5 銀行家算法的安全序列分析

系統中有3 種資源A、B、C 和5 個進程，A、B、C 種資源個數分別為17、5、20。T0時刻，系統資源分配表如表1所示。

請分析：

（1）在T0時刻系統是否安全？請寫出判斷過程。

（2）假如進程P2請求Request2(0,3,4)，將如何進行資源分配？請寫出判斷過程。

（3）在進程P2請求Request2(0,3,4) 后，進程P4再請求Request4(2,0,1)，將如何進行資源分配？請寫出判斷過程。

解：T0時刻，由題可知:

AvailableA=原有-分配=17-（2+4+4+2+3）=2，AvailableB=5-（1+0+0+0+1）=3，AvailableC=20-（2+2+5+4+4）=3，Need=Max-Allocation，Need1=（3，4，7），Need2=（1，3，4），Need3=（0，0，6），Need4=（2，2，1），Need5=（1，1，0），可得T0時刻資源分配表如表2所示。

（1）安全性算法分析如表3所示。

通過以上分析，{P4,P3,P2,P5,P1}是安全序列，系統安全。因為安全序列有很多個，因此安全序列號并不唯一。

（2）進程P2請求Request2(0,3,4)，分析如下：

①Request2(0,3,4)≤Need2(1,3,4)；

②Request2(0,3,4)>Available(2,3,3)，故系統不能將資源分配給它，此時P2必須等待。

（3）進程P2請求Request2(0,3,4)后，進程P4再請求Request4(2,0,1)，分析如下：

①Request4(2,0,1)≤Need4(2,2,1)；

②Request4(2,0,1)≤Available(2,3,3)；

③假定進程P2得到資源分配并修改以下參數：

Available=Available-Request4=(2,3,3)-(2,0,1)=(0,3,2)

表1：資源分配表

表3：安全性檢查

Allocation4=Allocation4+Request4=(2,0,4)+(2,0,1)=(4,0,5)

Need4=Need4-Request4=(2,2,1)-(2,0,1)=(0,2,0)

④安全性檢查：Available=（0,3,2），Work=Available=（0,3,2），找5 個進程中Need 小于Work 的進程，可以找到進程P4滿足Need4(0,2,0)≤Work，因此可以滿足P4的運行。P4運行結束后，系統的狀態如表4所示。

通過以上分析，{P4,P2,P3,P5,P1}是安全序列，系統安全，可以進行資源分配。

從以上的舉例可知，安全性算法檢查完成后，最后的Work+Allocation 資源個數還是和初始的資源個數一致。如果在安全性算法判斷Need≤Work 錯誤，選錯進程找到一個安全序列，最后資源個數也和初始的資源個數一致，但是找到的這個序列號是錯誤的。因此，在安全性算法時，需要注意這一點。

6 結束語

本文詳細介紹了避免死鎖的最具代表性算法——銀行家算法，并通過舉例講述了銀行家算法的安全序列需要注意的問題。通過分析，得出在安全性算法檢查時，要特別注意需求矩陣Need 和工作向量Work 的比較，必須選擇滿足Need≤Work 的進程，切勿選錯進程。