基于銀行家算法的資源調(diào)度研究與實現(xiàn)

劉 璇

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

0 引 言

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

1 死鎖

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

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

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

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

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

2 銀行家算法

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

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

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

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

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

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

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

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

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

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

2.2 銀行家算法描述

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

（1）當(dāng)［］［］［］［］時，不能進(jìn)行資源分配。因為進(jìn)程P所申請的資源數(shù)已超過其最大需求量，進(jìn)程P出錯。

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

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

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

2.3 安全性算法

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

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

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

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

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

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

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

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

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

3 算法建模

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

3.1 銀行家算法模塊

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

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

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

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

3.2 安全性算法模塊

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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