基于銀行家算法的資源調度研究與實現

劉 璇

（貴陽信息科技學院 信息工程系，貴陽 550025）

0 引 言

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

1 死鎖

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

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

圖1 進程資源申請圖Fig.1 Process resource application diagram

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

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

2 銀行家算法

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

2.1 銀行家算法中的數據結構

假定系統中有個并發進程，，…，P，類資源，，…，R。在銀行家算法中需定義1個向量和4個矩陣。

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

（2）最大需求矩陣Max［］［］：表示系統中的個進程，每個進程對類資源的最大需求量。如：Max［］［］，表示進程P需要R類資源的數量為個。

（3）分配矩陣［］［］：表示系統中各進程已占用的各類資源數。如：［］［］，表示進程P已獲得R類資源的數量為個。

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

上述3個矩陣之間存在如下關系：

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

（5）請求矩陣［］［］：表示每個進程當前申請分配各類資源數。如：［］［］，表示進程P需要個R類的資源。

2.2 銀行家算法描述

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

（1）當［］［］［］［］時，不能進行資源分配。因為進程P所申請的資源數已超過其最大需求量，進程P出錯。

（2）當［］［］［］時，不能分配資源，進程P進入等待狀態。

（3）除以上兩種情況外，系統可給予分配，但是需要修改相應的數據結構為：

（4）檢測系統安全性。調用安全性算法檢查系統安全狀態，如果檢測結果為安全狀態，則給進程P分配所申請資源；否則進程P不能分配資源，并修改進程為等待資源狀態，恢復下列數據結構后返回。

2.3 安全性算法

安全性算法是銀行家算法的子算法（如22節中步驟4）。為了保證安全性檢查，在不影響、Max、和的狀態下，需新建兩個向量（臨時變量）、的數據結構，用以檢驗系統的安全狀態。

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

安全性檢測算法實現步驟如下：

對工作向量和完成向量進行初始化：

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

從進程集合中尋找滿足條件：［］、［］［］≤［］的一個進程。若滿足條件，則表明系統當前資源能滿足進程P的所有資源申請，轉去執行步驟3；否則表示系統不能滿足當前所有進程的資源申請，則執行步驟4。

當進程P分配到資源后，將繼續執行直至完成整個進程。之后，釋放所占用的全部資源，轉回步驟2繼續調度下一個可滿足資源申請的進程。此時工作向量和完成向量調整如下：

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

執行安全性算法的本質，就是找到一個符合當前系統資源的安全序列。如果該序列存在，則系統所有進程都可順利往前推進。系統按照該序列調度進程，系統就不會產生死鎖現象，使操作系統處于安全狀態。

3 算法建模

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

3.1 銀行家算法模塊

銀行家算法模塊主要是通過對進程所申請資源的、、向量之間關系進行判斷，判斷系統當前資源能否滿足該進程，能否對該進程進行資源分配。實現過程如下：

（1）如果滿足≤條件，表示進程申請的資源數小于等于該進程運行所需的所有資源數，則轉向步驟（2）繼續判斷；否則，系統出錯。

（2）如果≤條件成立，表示進程所申請的資源數小于或等于當前系統可用資源數，滿足該進程提出的申請，則分配資源給進程；否則，進程處于阻塞態。

（3）系統執行安全性算法。

3.2 安全性算法模塊

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

（1）設置兩個向量

①工作向量：，表示系統可用的各類資源數，其初值與相等；

②完成向量：表示系統是否有足夠資源滿足進程，表示有，表示沒有。

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

（3）給進程P分配所申請資源，進程執行完成時回收所有資源。；［］；轉（2）。

（4）若所有進程都使得［］，則表示系統處于安全狀態；反之系統處于不安全狀態。

4 設計與實現

設計中尋找安全序列的部分使用循環結構完成，通過分別處理循環的終止條件確定系統是否安全。若滿足條件［］的值為，并且［，］小于或等于［］時，說明系統處于安全狀態，此時將［］向量置為。循環中設置一個變量來累加計數，當該變量與進程數量相等時，說明已將［］向量全部置為，則終止循環。

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

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

資源分配過程關鍵代碼如下：

程序運行結果截圖如圖3所示。

圖3 程序運行結果Fig.3 Program running result diagram

5 結束語

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