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

李坤芩 熊琰 王磊 田豐

（貴州商學(xué)院計(jì)算機(jī)與信息工程學(xué)院 貴州省貴陽(yáng)市 550014）

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

1 安全序列

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

2 銀行家算法的數(shù)據(jù)結(jié)構(gòu)

算法中有Available、Max、Allocation 和Need 四個(gè)數(shù)據(jù)結(jié)構(gòu)，還存在以下關(guān)系：Need=Max-Allocation，詳情如下：

（1）可分配資源向量Available，系統(tǒng)最后還剩下的可利用資源個(gè)數(shù)[2]。

（2）最大需求矩陣Max，某個(gè)進(jìn)程一共需要的資源個(gè)數(shù)[2]。

（3）分配矩陣Allocation，某個(gè)進(jìn)程已經(jīng)占有的資源個(gè)數(shù)[2]。

（4）需求矩陣Need，某個(gè)進(jìn)程還需要的資源個(gè)數(shù)[2]。

3 銀行家算法

假設(shè)系統(tǒng)中有進(jìn)程M 個(gè)，當(dāng)進(jìn)程Pi 申請(qǐng)（Requesti）資源時(shí)，資源分配如下：

（1）如果Requesti≤Needi，則轉(zhuǎn)向第（2）步；反之出錯(cuò)返回。

（2）如果Requesti≤Available，則轉(zhuǎn)向第（3）步；反之進(jìn)程Pi等待。

（3）假定進(jìn)程Pi得到資源分配并修改以下參數(shù)[3]：

Available=Available-Requesti

Allocationi=Allocationi+Requesti

Needi=Needi-Requesti

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

4 安全性算法

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

（2）找到進(jìn)程符合以下要求[1]：

Finishi=False

Needi≤Work

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

（3）假設(shè)進(jìn)程Pi獲得資源，修改以下參數(shù)：

Work=Work+Allocation

Finishi=True

繼續(xù)執(zhí)行第（3）步；

（4）當(dāng)所有進(jìn)程的Finishi=True，表明安全；反之，表明不安全。

從銀行家算法和安全性算法可知，如果系統(tǒng)能找到一個(gè)安全序列，說(shuō)明系統(tǒng)是安全的，才能分配資源。

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

系統(tǒng)中有3 種資源A、B、C 和5 個(gè)進(jìn)程，A、B、C 種資源個(gè)數(shù)分別為17、5、20。T0時(shí)刻，系統(tǒng)資源分配表如表1所示。

請(qǐng)分析：

（1）在T0時(shí)刻系統(tǒng)是否安全？請(qǐng)寫出判斷過(guò)程。

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

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

解：T0時(shí)刻，由題可知:

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時(shí)刻資源分配表如表2所示。

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

通過(guò)以上分析，{P4,P3,P2,P5,P1}是安全序列，系統(tǒng)安全。因?yàn)榘踩蛄杏泻芏鄠€(gè)，因此安全序列號(hào)并不唯一。

（2）進(jìn)程P2請(qǐng)求Request2(0,3,4)，分析如下：

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

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

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

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

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

③假定進(jìn)程P2得到資源分配并修改以下參數(shù)：

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 個(gè)進(jìn)程中Need 小于Work 的進(jìn)程，可以找到進(jìn)程P4滿足Need4(0,2,0)≤Work，因此可以滿足P4的運(yùn)行。P4運(yùn)行結(jié)束后，系統(tǒng)的狀態(tài)如表4所示。

通過(guò)以上分析，{P4,P2,P3,P5,P1}是安全序列，系統(tǒng)安全，可以進(jìn)行資源分配。

從以上的舉例可知，安全性算法檢查完成后，最后的Work+Allocation 資源個(gè)數(shù)還是和初始的資源個(gè)數(shù)一致。如果在安全性算法判斷Need≤Work 錯(cuò)誤，選錯(cuò)進(jìn)程找到一個(gè)安全序列，最后資源個(gè)數(shù)也和初始的資源個(gè)數(shù)一致，但是找到的這個(gè)序列號(hào)是錯(cuò)誤的。因此，在安全性算法時(shí)，需要注意這一點(diǎn)。

6 結(jié)束語(yǔ)

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