劉 璇

（貴陽(yáng)信息科技學(xué)院 信息工程系，貴陽(yáng) 550025）

0 引 言

在現(xiàn)代操作系統(tǒng)中，利用多道進(jìn)程的并發(fā)執(zhí)行來(lái)提高資源的利用率和吞吐量，為用戶程序提供了良好的運(yùn)行環(huán)境，但同時(shí)也帶來(lái)一些新問(wèn)題。由于計(jì)算機(jī)系統(tǒng)資源是有限的，并且部分資源還具有獨(dú)占和排他的特性。計(jì)算機(jī)系統(tǒng)中打印機(jī)的數(shù)量、計(jì)算機(jī)的內(nèi)存容量、輸入輸出設(shè)備等的數(shù)量均是有限的，進(jìn)程在申請(qǐng)這些資源時(shí)只能互斥的使用。如多個(gè)進(jìn)程同時(shí)申請(qǐng)同一臺(tái)打印機(jī)時(shí)，進(jìn)程之間會(huì)發(fā)生互相搶奪，由于打印機(jī)數(shù)量有限，只能有一個(gè)進(jìn)程得到滿足，如果分配不合理，將會(huì)造成死鎖。

1 死鎖

死鎖（Deadlock）是指計(jì)算機(jī)系統(tǒng)中存在多個(gè)進(jìn)程，在執(zhí)行過(guò)程中，相互競(jìng)爭(zhēng)資源或在進(jìn)程之間進(jìn)行某些數(shù)據(jù)傳遞、申請(qǐng)等而造成的一種互相等待的現(xiàn)象。若無(wú)外界因素的干擾，多個(gè)進(jìn)程都將無(wú)法繼續(xù)推進(jìn)，所有進(jìn)程都處于互相等待狀態(tài)，此時(shí)系統(tǒng)產(chǎn)生死鎖。

由于資源的使用是互斥的，假設(shè)當(dāng)某個(gè)進(jìn)程提出申請(qǐng)資源時(shí)，此資源正在被別的進(jìn)程所占用，在不可剝奪條件下，若無(wú)外力協(xié)助，該進(jìn)程得不到資源的滿足。假設(shè)每個(gè)進(jìn)程都在等待被其它進(jìn)程占用的資源，而其它進(jìn)程也缺少資源，進(jìn)程在執(zhí)行完畢前不可能主動(dòng)放棄資源，這就陷入一種死循環(huán)狀態(tài)，所有進(jìn)程都在互相等待一種不可能發(fā)生的情況。計(jì)算機(jī)系統(tǒng)中，如果系統(tǒng)的資源分配策略不當(dāng)，更常見(jiàn)的可能是程序員寫(xiě)的程序有錯(cuò)誤等，則會(huì)導(dǎo)致進(jìn)程因競(jìng)爭(zhēng)資源不當(dāng)而產(chǎn)生死鎖的現(xiàn)象。如有進(jìn)程、、和資源A、B、C，3個(gè)進(jìn)程所占有的資源和申請(qǐng)的資源如圖1所示。

圖1 進(jìn)程資源申請(qǐng)圖Fig.1 Process resource application diagram

圖中進(jìn)程占用A資源同時(shí)申請(qǐng)B資源；進(jìn)程占用進(jìn)程申請(qǐng)的B資源，同時(shí)申請(qǐng)C資源；進(jìn)程占用進(jìn)程申請(qǐng)的C資源，同時(shí)申請(qǐng)進(jìn)程占用的A資源。由此可見(jiàn)，3個(gè)進(jìn)程之間申請(qǐng)的資源和占有的資源形成一個(gè)封閉的環(huán)狀，在資源不可剝奪情況下，3個(gè)進(jìn)程都在等待別的進(jìn)程釋放自己所需的資源，而別的進(jìn)程沒(méi)有執(zhí)行完畢，不可能釋放資源，此時(shí)進(jìn)程陷入永久等待，任何一個(gè)進(jìn)程都得不到滿足，都不會(huì)執(zhí)行完畢，都不會(huì)釋放資源，這就是一種典型的陷入死鎖狀態(tài)。

計(jì)算機(jī)系統(tǒng)產(chǎn)生死鎖的最主要原因是系統(tǒng)資源有限，進(jìn)程對(duì)資源的競(jìng)爭(zhēng)產(chǎn)生了死鎖，所以并發(fā)進(jìn)程對(duì)分配資源的順序就會(huì)有一定要求，若能合理的推進(jìn)順序，則能在很大程度上降低系統(tǒng)產(chǎn)生死鎖的概率。

2 銀行家算法

1965年，Dijkstra根據(jù)銀行系統(tǒng)現(xiàn)金貸款發(fā)放思想，提出了避免系統(tǒng)陷入死鎖的算法，將其命名為銀行家算法（Bankers algorithm）。該算法首先檢測(cè)進(jìn)程申請(qǐng)的資源數(shù)量系統(tǒng)是否能滿足；通過(guò)與系統(tǒng)現(xiàn)存可用資源數(shù)進(jìn)行對(duì)比分析，若申請(qǐng)資源數(shù)小于等于可用資源數(shù)，說(shuō)明當(dāng)前資源能夠滿足該進(jìn)程，可進(jìn)行資源分配；若大于，則說(shuō)明當(dāng)前資源不能進(jìn)行資源分配，否則系統(tǒng)產(chǎn)生死鎖。若在進(jìn)程的執(zhí)行過(guò)程中還需繼續(xù)申請(qǐng)資源，則要判斷本次申請(qǐng)資源數(shù)和已占有資源數(shù)之和是否大于進(jìn)程的最大資源數(shù)，若大于，拒絕分配；若小于，還需繼續(xù)檢測(cè)系統(tǒng)當(dāng)前可用資源能否滿足進(jìn)程的此次申請(qǐng)；若能滿足進(jìn)程申請(qǐng)，給予分配，否則拒絕分配。

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

假定系統(tǒng)中有個(gè)并發(fā)進(jìn)程，，…，P，類(lèi)資源，，…，R。在銀行家算法中需定義1個(gè)向量和4個(gè)矩陣。

（1）系統(tǒng)可用資源向量［］：表示系統(tǒng)中各類(lèi)可用資源數(shù)量。初始值是系統(tǒng)中類(lèi)資源全部可用數(shù)量，該值隨資源的分配與回收動(dòng)態(tài)變化。如：［］，表示系統(tǒng)中現(xiàn)有可用類(lèi)資源的數(shù)量為個(gè)。

（2）最大需求矩陣Max［］［］：表示系統(tǒng)中的個(gè)進(jìn)程，每個(gè)進(jìn)程對(duì)類(lèi)資源的最大需求量。如：Max［］［］，表示進(jìn)程P需要R類(lèi)資源的數(shù)量為個(gè)。

（3）分配矩陣［］［］：表示系統(tǒng)中各進(jìn)程已占用的各類(lèi)資源數(shù)。如：［］［］，表示進(jìn)程P已獲得R類(lèi)資源的數(shù)量為個(gè)。

（4）需求矩陣［］［］：表示每個(gè)進(jìn)程所需的各類(lèi)資源數(shù)。如：［］［］，表示進(jìn)程P還需要分配R類(lèi)資源個(gè)即可執(zhí)行完畢。

上述3個(gè)矩陣之間存在如下關(guān)系：

［］［］Max［］［］［］［］

（5）請(qǐng)求矩陣［］［］：表示每個(gè)進(jìn)程當(dāng)前申請(qǐng)分配各類(lèi)資源數(shù)。如：［］［］，表示進(jìn)程P需要個(gè)R類(lèi)的資源。

2.2 銀行家算法描述

設(shè)是進(jìn)程的請(qǐng)求向量，如果［］，表示進(jìn)程P需要個(gè)類(lèi)型的資源。當(dāng)進(jìn)程P發(fā)出資源請(qǐng)求（1，2，…，0）后（表示類(lèi)資源分別申請(qǐng)1，2，…，0個(gè)），系統(tǒng)按以下步驟進(jìn)行檢測(cè)，判斷是否進(jìn)行資源分配。

（1）當(dāng)［］［］［］［］時(shí)，不能進(jìn)行資源分配。因?yàn)檫M(jìn)程P所申請(qǐng)的資源數(shù)已超過(guò)其最大需求量，進(jìn)程P出錯(cuò)。

（2）當(dāng)［］［］［］時(shí)，不能分配資源，進(jìn)程P進(jìn)入等待狀態(tài)。

（3）除以上兩種情況外，系統(tǒng)可給予分配，但是需要修改相應(yīng)的數(shù)據(jù)結(jié)構(gòu)為：

（4）檢測(cè)系統(tǒng)安全性。調(diào)用安全性算法檢查系統(tǒng)安全狀態(tài)，如果檢測(cè)結(jié)果為安全狀態(tài)，則給進(jìn)程P分配所申請(qǐng)資源；否則進(jìn)程P不能分配資源，并修改進(jìn)程為等待資源狀態(tài)，恢復(fù)下列數(shù)據(jù)結(jié)構(gòu)后返回。

2.3 安全性算法

安全性算法是銀行家算法的子算法（如22節(jié)中步驟4）。為了保證安全性檢查，在不影響、Max、和的狀態(tài)下，需新建兩個(gè)向量（臨時(shí)變量）、的數(shù)據(jù)結(jié)構(gòu)，用以檢驗(yàn)系統(tǒng)的安全狀態(tài)。

其中，工作向量［］表示系統(tǒng)可分配給進(jìn)程使用的各類(lèi)資源數(shù)（有類(lèi)資源），其初始值與相等；完成向量［］表示系統(tǒng)是否有足夠的資源分配給所有待分配資源的進(jìn)程。若［］［］，則表示系統(tǒng)資源量不滿足；反之可以滿足。

安全性檢測(cè)算法實(shí)現(xiàn)步驟如下：

對(duì)工作向量和完成向量進(jìn)行初始化：

工作向量初始值與相等，中的所有位全為。當(dāng)有足夠資源分配給進(jìn)程P時(shí)，再令［］。

從進(jìn)程集合中尋找滿足條件：［］、［］［］≤［］的一個(gè)進(jìn)程。若滿足條件，則表明系統(tǒng)當(dāng)前資源能滿足進(jìn)程P的所有資源申請(qǐng)，轉(zhuǎn)去執(zhí)行步驟3；否則表示系統(tǒng)不能滿足當(dāng)前所有進(jìn)程的資源申請(qǐng)，則執(zhí)行步驟4。

當(dāng)進(jìn)程P分配到資源后，將繼續(xù)執(zhí)行直至完成整個(gè)進(jìn)程。之后，釋放所占用的全部資源，轉(zhuǎn)回步驟2繼續(xù)調(diào)度下一個(gè)可滿足資源申請(qǐng)的進(jìn)程。此時(shí)工作向量和完成向量調(diào)整如下：

對(duì)于任意（1，2，…，），都使得［］的值為真，則系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。

執(zhí)行安全性算法的本質(zhì)，就是找到一個(gè)符合當(dāng)前系統(tǒng)資源的安全序列。如果該序列存在，則系統(tǒng)所有進(jìn)程都可順利往前推進(jìn)。系統(tǒng)按照該序列調(diào)度進(jìn)程，系統(tǒng)就不會(huì)產(chǎn)生死鎖現(xiàn)象，使操作系統(tǒng)處于安全狀態(tài)。

3 算法建模

算法建模分為兩個(gè)模塊：銀行家算法模塊和安全性算法模塊。用戶通過(guò)輸入數(shù)據(jù)，分別對(duì)可利用資源矩陣、最大需求矩陣Max、分配矩陣、需求矩陣賦初值。采用C語(yǔ)言編程實(shí)現(xiàn)。

3.1 銀行家算法模塊

銀行家算法模塊主要是通過(guò)對(duì)進(jìn)程所申請(qǐng)資源的、、向量之間關(guān)系進(jìn)行判斷，判斷系統(tǒng)當(dāng)前資源能否滿足該進(jìn)程，能否對(duì)該進(jìn)程進(jìn)行資源分配。實(shí)現(xiàn)過(guò)程如下：

（1）如果滿足≤條件，表示進(jìn)程申請(qǐng)的資源數(shù)小于等于該進(jìn)程運(yùn)行所需的所有資源數(shù)，則轉(zhuǎn)向步驟（2）繼續(xù)判斷；否則，系統(tǒng)出錯(cuò)。

（2）如果≤條件成立，表示進(jìn)程所申請(qǐng)的資源數(shù)小于或等于當(dāng)前系統(tǒng)可用資源數(shù)，滿足該進(jìn)程提出的申請(qǐng)，則分配資源給進(jìn)程；否則，進(jìn)程處于阻塞態(tài)。

（3）系統(tǒng)執(zhí)行安全性算法。

3.2 安全性算法模塊

安全性算法模塊主要是對(duì)系統(tǒng)的安全性進(jìn)行檢測(cè)，通過(guò)遍歷所有進(jìn)程P，對(duì)完成向量的值進(jìn)行判斷，從而判斷系統(tǒng)是否處于安全隊(duì)列。實(shí)現(xiàn)過(guò)程如下：

（1）設(shè)置兩個(gè)向量

①工作向量：，表示系統(tǒng)可用的各類(lèi)資源數(shù)，其初值與相等；

②完成向量：表示系統(tǒng)是否有足夠資源滿足進(jìn)程，表示有，表示沒(méi)有。

（2）若［］≤，則執(zhí)行（3）；否則執(zhí)行（4）（為資源類(lèi)別）

（3）給進(jìn)程P分配所申請(qǐng)資源，進(jìn)程執(zhí)行完成時(shí)回收所有資源。；［］；轉(zhuǎn)（2）。

（4）若所有進(jìn)程都使得［］，則表示系統(tǒng)處于安全狀態(tài)；反之系統(tǒng)處于不安全狀態(tài)。

4 設(shè)計(jì)與實(shí)現(xiàn)

設(shè)計(jì)中尋找安全序列的部分使用循環(huán)結(jié)構(gòu)完成，通過(guò)分別處理循環(huán)的終止條件確定系統(tǒng)是否安全。若滿足條件［］的值為，并且［，］小于或等于［］時(shí)，說(shuō)明系統(tǒng)處于安全狀態(tài)，此時(shí)將［］向量置為。循環(huán)中設(shè)置一個(gè)變量來(lái)累加計(jì)數(shù)，當(dāng)該變量與進(jìn)程數(shù)量相等時(shí)，說(shuō)明已將［］向量全部置為，則終止循環(huán)。

對(duì)于不安全系統(tǒng)，不可將向量［］都置為，必定存在。由于需要不斷循環(huán)查找并嘗試分配，在尋求一個(gè)安全序列時(shí)，若在一輪的尋找中沒(méi)有一個(gè)可以安全執(zhí)行的進(jìn)程，則說(shuō)明往后也不存在安全的進(jìn)程，即可跳出循環(huán)，結(jié)束尋找。銀行家算法流程如圖2所示。

圖2 銀行家算法流程圖Fig.2 Banker algorithm flow chart

資源分配過(guò)程關(guān)鍵代碼如下：

程序運(yùn)行結(jié)果截圖如圖3所示。

圖3 程序運(yùn)行結(jié)果Fig.3 Program running result diagram

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

經(jīng)仿真實(shí)驗(yàn)得出，銀行家算法雖然無(wú)法從本質(zhì)上解決死鎖問(wèn)題，但是該算法可以提高多進(jìn)程并發(fā)算法的資源利用率，能預(yù)測(cè)當(dāng)前系統(tǒng)是否處于安全狀態(tài)，在避免死鎖的方面有較突出的表現(xiàn)。由于死鎖產(chǎn)生的根本原因是資源的數(shù)量不足，并且銀行家算法在計(jì)算過(guò)程中要不斷的檢測(cè)每個(gè)進(jìn)程占有資源、還需資源以及系統(tǒng)可用資源的情況，整個(gè)過(guò)程將耗費(fèi)大量時(shí)間。為此，相關(guān)問(wèn)題還有待進(jìn)一步探索研究。