基于銀行家算法的研究和應用分析

（蘭州大學信息科學與工程學院 甘肅 730000）

1 基本概念

在銀行家的算法中，每個過程都需要預先確定其潛在的最大資源需求，盡管該過程可能能夠以少于該數量的速度進行。每個進程都必須保證，如果可以利用最大數量的資源，則它將完成其處理并將其資源返回給系統。

當進程進入等待狀態時會發生這種情況，因為該進程所請求的資源正由另一個等待該進程的資源持有，而該等待進程又在等待另一個資源。如果某個進程由于另一個進程正在使用該進程所請求的資源而無法無限期更改其狀態，則稱該系統處于死鎖狀態[1]。

大部分死鎖問題都和資源有關[2]。資源可分為可搶占資源和不可搶占資源。不可搶占資源是指一旦被進程占用，就無法被釋放給其他資源使用，除非占用的進程主動釋放；而可占用資源則相反，它可以被占用資源任意釋放，和被其他資源使用，可占用資源避免了死鎖的發生。

1.1多用戶操作系統與單用戶操作系統

根據在同一時間最多允許多少個用戶同時操作計算機，操作系統可分為單用戶操作系統和多用戶操作系統。同一時間內允許多個用戶同時操作計算機，稱為多用戶操作系統;反之，同一時間內最多只允許一個用戶操作計算機，則稱為單用戶操作系統。

1.2 安全狀態

假設系統中存在n個并發的進程，分別為P1，P2，…，Pn，每個進程完成后，必須將其資源返還給系統，以便下一個進程可以使用，使得n個進程都能順利完成資源分配，則該序列稱為安全序列，此時系統處于安全狀態。

只要保持系統時刻處于安全狀態，便可避免死鎖的發生。

1.3 死鎖產生的必要條件

（1）互斥，任一時刻只允許一個進程使用資源，即資源不能同時分配給多個進程。

（2）占有并等待，操作系統環境中某個資源的進程請求新的資源，而這些資源被其他進程所占有，無法釋放。

（3）循環等待，存在一個進程的封閉環路，其中每個進程占有環路中下一進程所需的至少一個資源。

（4）非搶占，是指資源不可剝奪，只能被占用它的進程主動釋放。

當死鎖發生時，以上四個條件必須同時滿足。

1.4 死鎖的解決辦法

1.4.1 死鎖的預防

間接防止三個必要條件的發生，或直接防止循環等待。具體方法為：一次請求所有資源，或資源剝奪，適用于狀態可以保存和恢復的資源，或資源按序申請，可以在編譯時進行檢查。

此方法的缺點是：需要預知資源需求，并且進程初始化時間會延長，因此效率會降低。

1.4.2 死鎖的避免

尋找可能的安全的運行順序，操作系統動態做出決定：如果當前資源分配滿足，否則導致死鎖。死鎖的避免需要知道未來進程資源請求，但是這一要求對于計算機來說很難實現。同時進程可能長時間阻塞。

避免策略是資源分配的保守方法[3]。當確定由于后續請求而不會發生死鎖時，它們通過允許系統僅根據分配進行轉換來控制狀態轉換。該策略是在進入預期狀態之前對其進行分析，以確定是否存在從每個狀態仍然可以執行的狀態開始的過渡序列。

具體有以下兩種方法：第一，拒絕進程啟動。如果進程資源請求可能導致死鎖，則不啟動進程。只有在當前所有進程以及此進程的最大資源請求得到滿足時進程才會啟動，所以我們考慮最壞的情況下，即所有進程同時提出最大申請時拒絕進程啟動。第二，拒絕資源分配。如果本次分配可能導致死鎖，則拒絕進程的增量資源請求。

1.4.3 死鎖的檢測

死鎖預防策略是非常保守的，不僅限制了對資源的訪問，同時對進程也有一定的限制。在任何可能的情況下，資源總是滿足進程的申請；定期檢測即每次資源請求時都需要檢測是否有死鎖情況的發生。這種方法的優點是：能夠盡早檢測，算法也相對簡單[4]。不足的地方在于，每次檢測是都需要占用相當長的處理器時間。

死鎖檢測算法：

（1）標記分配矩陣Allocation中對應行全為0的進程；

（2）初始化向量W為可用矩陣；

（3）找到未標記的進程Pi，其中進程滿足：Qik<=Wk(對于k從1 取值到m 成立)，如果找不到滿足條件的進程，則終止算法；

（4）如果找到進程Pi，將其分配矩陣向量加入W，即Wk=Wk+Aik，返回（3）。

此時，死鎖發生當且僅當存在未標記的進程，即未標記的進程可能會引發死鎖。

2 銀行家算法

2.1 算法數據結構

（1）可分配資源向量Available

含有m個元素的數組向量，其中的每一個元素代表一類可利用的資源數目。如果Available[j]=K，則表示系統中現有可分配的Rj類資源K個。

（2）最大需求矩陣Max[N，M]

一個n 行m 列的矩陣，它定義了系統中n個進程中的每一個進程對m類資源的最大需求。如果Max[i，j]=K，則表示進程Pi需要Rj類資源的最大需求量為K。

（3）分配矩陣Allocation[N，M]

一個n 行m 列的矩陣，它定義了每個進程已占用每種資源的數量。如果Allocation[i，j]=K，則表示進程Pi當前占有Rj類資源的數目為K。

（4）需求矩陣Need[N，M]

這也是一個n 行m 列的矩陣，表示每個進程申請的每種資源數目。如果Need[i，j]=K，則表示進程Pi正在申請Rj類資源K個。

三個矩陣之間存在以下關系：Need[i，j]=Max[i，j]-Allocation[i，j]。即，需求矩陣是最大需求量減去已分配的資源量。

2.2 進程申請資源的情況

假設Rij=(Cij-Aij)。設Ri是進程Pi的請求向量，如果Ri[j]=K，表示進程Pi 需要Rj類資源的個數為K。Ri 與Need的關系可能為以下3 種情況：

（1）Ri>Need[i]。這種情況表示該進程的資源需求已大于它所聲明的最大值。此時無法滿足該進程的申請。

（2）Ri=Need[i]。這種情況表示操作系統滿足該進程的全部申請的資源數。

（3）Ri

2.3 銀行家算法的描述

當進程Pi發出資源請求后，系統按下述步驟進行檢查[5]；

（1）如果Ri>Need[i]，便轉向步驟（2）；否則顯示出錯，系統認定為非法請求，因為它所需的資源數已超過它事先聲明的最大值。

（2）如果Ri≤Available，便轉向步驟（3）；否則，表示目前操作系統中沒有足夠資源進行分配，Pi須等待其他進程執行完釋放資源。

（3）假設系統將資源分配給進程Pi，則需修改幾個矩陣的值：

Available ：=Available-Ri；

Allocation ：=Allocation+Ri；

Needi：=Needi-Ri；

2.4 系統安全性算法步驟：

（1）設置2個向量：Work[i]表示資源向量和Finish[i]表示資源夠標識向量[6]。W 即資源向量，代表當前能夠提供給進程使用總數，F 代表有效向量，表示當前完成的進程返還給操作系統的資源總數。初始化假設Fi=false，滿足一定條件則置為true。

（2）當某個進程滿足條件Fi=false 以及（C-A）ij＜Vj，則跳轉到步驟（3），否則跳轉到步驟（4）。

（3）當進程Pi獲得資源后，順利執行操作，完成后釋放該進程分配得到的資源

Vj=Vj+Aij

Fi=true

繼續執行步驟（2）。

（4）如果所有進程的Fi=true都完成，則系統處于安全狀態，可以完成資源分配工作。只要有進程的有效向量為false 則說明此進程可能會有死鎖發生。

3 銀行家算法的應用

3.1 高校排課

排課系統是學校在完成高質量教學過程中必須要重視的問題。隨著學校招生人數增加和學生課程的豐富度逐年上升，而學校的資源又是有限的，用傳統的人工管理方式排課就顯得比較煩瑣，所以如何在短時間內排出整個學校的課程，讓教室和教師的資源都能得到充分利用，學生的課程負擔平衡，上完課后會及時歸還教室資源，就顯得尤為重要[7]。如果教務處安排不合理，就會陷入死鎖狀態，還可能會產生沖突，這樣的安排顯然就是不適用的。

算法的基本思想是：先安排選其中一門課的學生上課，等這批學生上完課后就會釋放資源，然后可以安排下一批學生進行上課，以此類推[8]。這樣選其他課程的學生就可以分配到足夠多的資源，從而老師和學校能夠正常完成教學目標。

3.2 網絡爬蟲資源分配[9]

將銀行家算法中核心的遞歸思想引入到請求集生成過程中，這是一種全局遞歸的思想。允許當前節點進入的條件是：測試每個納入請求級的數組是否合法。合法指的是當前節點進入之后是否可以保障下一個節點進入請求集。

當利用銀行家算法對網絡爬蟲資源時，能夠有效提高資源率并避免死鎖。

3.3 智能家居能源管理

目標是建立一個智能家居模型，它能夠根據預先定義的標準，決定哪些過程應該提供必要的資源。標準包括在預定的到期時間之前完成該過程，將分配的資源保持在某個閾值以下，并且標準易擴展，因此對任何其他資源的當前分配數量的額外限制可以施加到其中的任何一個。為了使過程更簡單，結果更加明了，假設如下：資源數量必須預先定義并保持不變；所有流程都預先確定每個流程需要多少資源；完成后，每個進程返回所有分配的資源，因此可以通過分配給其他進程來重新利用；且每個過程都在有限的時間內完成。

為了滿足所有性能要求，對銀行家算法進行了修改[10]。

引入離散化的概念。離散化是指將每個過程分成幾個子過程，每個子過程持續一個離散化周期，這樣可以滿足資源和過程數量恒定的假設。此外，假設在一個離散化周期內，資源數量恒定。同時我們將時間進行分片，選擇足夠小的時間片，隨著子過程數量的增加，時間片越小，系統越復雜。另一方面，時間片越小，與用戶的通信的時間就越短。

引入進程優先級。為了區分進程執行的緊急程度，引入進程的優先級[11]。假設將進程分為兩組，第一組由用戶進行管理，第二組由修改后的銀行家算法進行管理。第一組的過程具有最高優先級，同時每個進程都分配了默認優先級——第一組優先級為2，第二組優先級為0。優先級的高低代表開始執行時間的緊迫性，優先級越高，排隊等待執行的時間越短。除此之外，第一組進程的優先級是恒定的，如果沒有足夠的資源來立即執行這種類型的過程，請求將會被忽略。如果銀行家算法管理的進程的優先級增加到1，則表示該進程必須在這個特定的時間開始執行。如果優先級值超過1，進程將無法及時完成[12]。如果沒有足夠的資源來執行第二組的過程，則將第二組進程將被推遲，直到執行條件得到滿足。

動態調整需求矩陣。默認情況下，在開始時，所有定義的進程都需要給予低成本資源支持。根據流程的優先級和資源的可用性，每個進程的資源需求必須在每個時間片中進行調整。因為在最初的銀行家算法中，每個過程對所有必要資源的需求都存儲在需求矩陣中，這對應于需求矩陣的改變。由于所有當前進程的資源需求都存儲在矩陣需求中，所以矩陣會根據當前可用的資源、每個進程的優先級和管理策略的變化而變化。如果所選擇的管理策略是標準策略方法模擬，那么需求矩陣的值也會發生變化。

動態調整可分配矩陣。可分配資源存儲在可分配矩陣中，它的大小對應于資源的數量。可分配字眼矩陣包含當前可用資源的數量。首先，計算優先級高于或等于1的所有流程的總使用量[13]。然后將極限值和最大值進行比較。如果需求量大于極限值，可分配矩陣中的值將精確地增加到當下時間的需求量，以執行優先級高于或等于1的所有進程。如果對需求值大于最大值，可分配矩陣中的取值則會增加到最大值。計算完所有矩陣后，將資源分配給進程。即進程可以開始執行。

通過對以上條件的改進，算法考慮的角度更加全面和人性化，使得智能家居模型能夠帶給居住者更安全和舒適的體驗。在經典的銀行家算法中，會檢查將資源分配給進程是否會導致系統進入不安全狀態，即可能的死鎖。在這里省略了安全檢查，原因是智能住宅不會陷入算法意義上的死鎖狀態[14]。

3.4 制造系統

制造系統由一組不同的資源組成，如緩沖器、機器人機械手臂和自動駕駛車輛，需要對這些資源進行處理和控制，以執行特定的生產功能。控制制造系統的需求源于生產操作使用的資源數量有限，因此需要資源共享。控制策略需要考慮資源的優先級分配和避免死鎖狀態。設計控制器時要考慮三個主要問題：第一，操作的精確順序；第二如何避免死鎖；第三，在出現沖突情況下，如何分配進程優先級。離散事件控制器的本質基本上與其他控制器相似：基于系統的當前狀態和想要獲得的結果，控制器應該自主地決定采取哪些行動來實現目標，同時需要考慮要花費最少的能量[15]。

在處理制造系統的建模和控制時，有三種主要工具：Petri網，圖論方法和自動機。Petri網算法理論上非常強大，并且提供了較好的仿真結果，但是對于大規模系統，仍然存在復雜性較高的問題[16]。銀行家算法是一種死鎖避免策略，控制資源分配以確保系統始終是處于安全狀態的，并且其復雜度低于Petri網算法。矩陣模型與Petri網直接對應，將矩陣模型或相應的Petri網中給出的系統需求量轉換成銀行家算法所需的矩陣。在制造系統中，每個部分都有清晰的開始和結束的標志，即輸入和輸出標志，對應制造系統的一組操作和一組資源，為了獲得矩陣模型，可以以if-then 規則的形式描述系統進程。同時每個規則對應于表示為x的二進制邏輯狀態向量的一個分量。如果滿足部分規則的所有先決條件，則滿足特定規則，即向量x的相應元素從“相應設置為“置為。此時根據進程的開始和結束標志管理進程和分配資源。

可分配矩陣和需求矩陣的數值大小取決于系統結構和當前狀態，隨著系統的變化而變化。進程每次請求資源時，銀行家算法都會更新可分配矩陣和需求矩陣，并檢查這種分配是否處于安全狀態，檢查完畢后資源被一個接一個地順序分配給進程。如果所有進程都可以成功結束，而沒有處于死鎖狀態，則狀態是安全的。

盡管對于給定的系統，時間復雜性沒有問題，但是對于較大規模的系統，應該考慮使用稀疏矩陣對制造系統進行模擬，同時更新存儲器管理系統和算法[17]。

3.5 救援物資的分配

當災害發生后，如何對救援工作進行統籌安排，是一切工作的中心。為了讓受災群眾能夠及時獲得救援物資，需要一種合理的分配方式。銀行家算法利用了廣度優先搜索的策略，解決了有向圖中單個源點到其他頂點的最短路徑問題[18]。

首先利用GIS技術對受災情況有一個大致的分析和了解，通過受災區域的分口分布、受災持續時間等等估算受災損失程度，進一步利用銀行家算法與GIS相結合，使得受災物資運送到受災地點的時間最短[19]。

4 銀行家算法的實現實例

T0 時刻若出現下述資源分配情況：

（1）初始狀態

首先用最大需求矩陣減去分配矩陣得到每個進程的需求矩陣：

圖1 初始狀態

（2）P2 進程完成

我們可以觀察到，可分配矩陣小于P2 進程的需求矩陣，所以只能分配給P2 矩陣，注意進程執行完后，需要將資源返還給可分配向量，同時將關于P2 進程的其他矩陣清零。

圖2 P2 進程完成

（3）P1 進程完成

圖3 P1 進程完成

（4）P3 進程完成

圖4 P3 進程完成

（5）P4 進程完成

圖5 P4 進程完成

（6）總結：此時我們可以判斷，可以進行資源分配，且不會發生死鎖狀態。且實例存在安全序列P2->P1->P3->P4。

5 銀行家算法的改進[20]

在銀行家算法中，如果某些進程處于等待狀態，說明沒有合適的方法提供安全序列。

提出一種等待狀態處理算法提供一個安全的序列：它取決于需求矩陣needi=1，21e，分配矩陣Allocationi=1，21l和可用資源矩陣Available。

如果進程要等待狀態，則必須遵循以下步驟：

（1）needi和need（i+1到最后）進行比較。

（2）以最少的需求和最大限度地進行過程分配。

（3）如果可用資源矩陣Available

（4）Available=Available+Allocationi

（5）重復（1）至（4），直到進程將進入運行狀態。

6 總結

本文基于銀行家算法，對算法進行了分析，對應用進行了舉例說明。銀行家算法能夠合理安排已有資源，從而提高了資源利用率。不僅利用在高校排課中，同時在網絡爬蟲資源配置和家庭智能家居能源分配上也有一定的應用。在并發和分布式系統的資源分配算法中，我們還必須考慮多種資源類型。在銀行家算法的基礎上，不斷對算法進行研究和改進，就能有效避免死鎖的發生。