基于銀行家算法的多進程算法資源配置策略研究

梁允（廣東電網有限責任公司河源供電局，廣東河源　514000）

?

基于銀行家算法的多進程算法資源配置策略研究

梁允
（廣東電網有限責任公司河源供電局，廣東河源514000）

摘要：系統資源不足會導致多進程算法進入不安全狀態，引發死鎖等問題，銀行家算法是避免死鎖的一種重要方法，能保證系統時刻都處于安全狀態。銀行家算法包括可利用資源向量、最大需求矩陣、分配矩陣、需求矩陣四類數據類型，包括試探分配、安全性檢查和資源分配等步驟。采用MFC編程，設計并實現了銀行家算法。通過軟件測試，證明軟件能夠有效避免死鎖，完成多個進程的資源分配。

關鍵詞：銀行家算法；死鎖；系統安全；多進程

當系統資源緊張時，多進程算法資源分配不足會導致發生死鎖，操作系統在對軟件、硬件資源管理時都有可能發生死鎖，死鎖發生時，發生死鎖的多進程算法進程無法繼續運行，必須釋放進程資源，采用新進程進行計算，因此造成多進程算法算法效率低下。避免死鎖算法以Dijkstra于1965年提出的銀行家算法最有代表性[1]，對多進程算法資源配置具有重要意義。

在避免死鎖的著名算法中，其中較為著名的是由Dijkstra在1965年提出的銀行家算法，它是以銀行的借貸系統的分配原則為理論背景，為判斷并保證T.H.E系統的安全運行為目的的一種算法。現已推廣到同一系統中，涉及多個單元向上級進行動態的資源申請及回收，都可以采取這種算法保證系統的穩定運行。

張菊等研究了基于銀行家算法的進程安全序列研究仿真，分析了銀行家算法的思想，給出了算法描述，并改進了銀行家算法[2]；侯剛研究了銀行家算法的基本原理并第一次在操作系統教材中揭示了銀行家算法的原理[3]；王繼奎、王會勇等研究了在銀行家算法思想指導下，同時深刻理解安全狀態的理論前提下，提出了一種針對系統的某一時刻搜索，所需要配置的進程安全序列算法，并利用面編程語言JAVA實現了該算法，該算法在分析全部安全序列的前提下，實現對系統資源的安全分配以及為系統的進程調度優化提供理論支持[4]；李婧、陳旺虎等分析了使用傳統的銀行家算法降低系統資源使用效率的主要原因是使用了事先聲明的全局最大資源需求量，提出了一種改進算法，該算法用廣義表表示每個進程的控制流程及其資源請求圖，可以減小銀行家算法對系統資源使用效率的影響[5]；彭志勇、賴曉風等利用該算法在高校排課系統中針對選修課程教室安排中的應用，并設計了一種排課的方案，從而使每個教室都能得到充分合理的安排，突出了銀行家算法相對其他算法在高校排課系統中的優勢[6]。

本文提出了基于銀行家算法的多進程算法資源分配策略，進一步促進了銀行家算法在多進程算法資源分配策略的應用，有效避免了多任務處理系統中死鎖的發生。

1　多進程算法資源分配存在問題

在允許多進程操作的系統中，由于允許通過多個進程的并行運行去改善系統，從而提高系統的工作量，但是可能發生多個進程循環等待它方占有資源，導致程序無限期地僵持下去，也就是所謂死鎖。如果沒有外力改變這個狀態，那么涉及到的進程都將永遠處于死鎖的狀態。其中死鎖狀態產生，一般是由于競爭資源和進程間在推進順序中所產生非法邏輯。因此只需在當前的有限資源下，構建一組合法的執行順序，這樣便能很好地避免死鎖的發生。銀行家算法起源于銀行系統的發放貸款，其本質狀態和計算機操作系統的資源分配相符。

要想避免死鎖，就必須考慮進程是否處于系統所要求的安全狀態，這樣就可以很好的規避死鎖。安全狀態指系統按照某種設定的安全進程順序為某種進程合理的提供資源分配，在此基礎上進而滿足每個進程對資源的最大需求，這樣就使的每個進程都能夠順利完成系統的任務。若在系統中，不存在或無法發現這樣的安全序列，那么就稱系統處于不安全狀態。

通過案例進行簡要說明，計算機有4個進程共享20個資源，進程P1、P2、P3、P4分別需要15個資源5個資源，8個資源和10個資源。在Tn時刻，P1，P2，P3，P4分別擁有8個、4個、4個、2個資源，且有2個空閑資源。Tn時刻是安全的，< P1，P2，P3，P4>為存在一個安全序列，只要系統按此序列分配，那么就可以安全地完成系統所需要的資源分配，保證系統的安全。

綜上，當進程向系統發出某種資源申請時，需要進行安全性檢查。分析系統中進程已分配資源數，當下進程的最大需求資源數及系統可配置資源數，在綜合分析后，根據分析結果決定判斷系統是否進行資源分配，進而避免系統進入不安全狀態。

2　銀行家算法

銀行家算法是避免死鎖的算法中頗具代表性的算法，其得名由于該算法思想來源于銀行系統現金貸款的發放。為了保證資金的安全，銀行家必須保證顧客對資金的總需求量不超過銀行家庫存的所有資金；若銀行家現有的資金少于顧客所需要的貸款需求時，對顧客的貸款進行推遲處理，同時也必須滿足，在有限的時間內，需處理顧客的貸款需求；同時若當顧客得到所需貸款后，也必須在有限的時間內，歸還所借取的貸款[8]。

2.1銀行家算法數據結構

存在四類數據類型。第1類數據類型稱為可利用資源向量，其中的每一個元素代表一類可利用資源的數量，其初始值為系統中該類資源的總量，隨著該類資源的分配和回收，使得資源處于動態變化，本文中用含有m個元素的一維數組Available表示。

第2類數據類型稱為最大需求矩陣，表示進程分別對應類資源的最大需求量，本文中用n×m的矩陣Max進行表示。

第3類數據類型稱為分配矩陣，表示每一類資源已分配給每一個進程的資源數量，本文中用n×m的矩陣Allocation表示。

第4類數據類型稱為需求矩陣，表示每一個進程尚需的各類資源數量，本文中用n×m的矩陣Need表示。

2.2銀行家算法流程

銀行家算法流程圖如圖1所示。

當進程Pi提出資源申請時，系統執行以下步驟：

（1）若Requesti≤Need(i，j)，跳轉到下一步，否則錯誤返回；

圖1　銀行家算法流程圖

（2）若Requesti≤Available，跳轉到下一步，否則進程等待；

（3）假設系統試分配及安全性檢查通過，則可以進行分配，分配算法為：

系統安全性檢查算法如圖2所示。

圖2　安全性檢查算法流程圖

首先，定義兩個狀態向量，工作向量(Work)和狀態向量(Finish)。Work向量表示系統可以提供給進程的資源量。執行算法時，Work的初值為系統可利用的資源量；Finish的狀態表示系統是否能夠進行資源分配，其初始狀態為false，當判斷足夠后，再令其為true。然后在從進程的集合中找到一個可以滿足狀態向量為false同時滿足需求向量小于工作向量進程，如果可以找到，則執行下一步，否則跳轉到最后一步，確定系統安全。此時當進程獲得資源后，可順利執行，當完成需要時，釋放所獲得的資源，繼續執行上一步。最后如果所有進程的都完成，表示系統處于安全狀態，否則系統處于一個不夠安全的狀態。

安全性檢查程序流程圖如圖3所示。

圖3　安全性檢查程序流程圖

3　銀行家算法的程序設計

本文采用Visual C++ 6.0設計Windows界面程序，程序設計語言為C++。界面分為三部分：參數輸入區域，資源分配區域和結果顯示區域。用戶在參數輸入區域輸入可利用資源、進程名稱、進程所需最大需求矩陣、進程的分配矩陣、等信息，單擊動態添加按鍵添加進程資源，單擊安全檢查，可以檢查當前所有進程對當前資源的申請是否安全，是否會使系統因資源不足或其他原因進入不安全狀態從而不能完成分配。如果進程申請資源安全，軟件則提示安全，否則提示不安全。

軟件可以支持最多10類資源進行分配，如圖4所示。可利用資源向量為[5，5，5，5，5，5，5，5，5，5]，輸入進程名稱process0，輸入pro?cess0最大需求矩陣為[1，1，2，1，1，1，1，1，1，1]，process0分配矩陣為[0，0，0，0，0，0，0，0，0，0]，需求矩陣為[1，1，2，1，1，1，1，1，1，1]，完成輸入之后單擊“動態添加”按鍵添加進程成功。單擊“安全檢查”按鍵，即提示系統狀態安全，可以執行分配操作。

開始執行分配，在進程名稱文本框輸入“process0”以及申請資源量。假設輸入的申請資源量為[1，1，1，1，1，1，1，1，1，1]，單擊“申請資源”，軟件彈出“資源分配后安全，可以分配”的消息提示框，表明輸入的資源量可以滿足申請要求并執行申請請求。單擊確認，進程process0已經分配資源為[1，1，1，1，1，1，1，1，1，1]，尚需分配資源為[0，0，1，0，0，0，0，0，0，0]，表明process0申請資源成功。此時系統可用資源數向量由原來的[5，5，5，5，5，5，5，5，5，5]變為[4，4，4，4，4，4，4，4，4，4]，系統為進程process0分配資源成功，如圖5所示。

圖4　軟件安全性檢查

圖5　進程資源分配

4　結論

由于銀行家算法需要不斷檢測每個進程對各類資源的占用和申請情況從而保證系統處于安全狀態，從而耗費了大量時間，目前大部分系統都沒有采用這個算法，也沒有任何關于死鎖的檢查。但銀行家算法在多進程算法資源配置策略中有重要的意義，可以大大提高多進程算法資源的利用率，并有效地預測系統的安全性，避免死鎖的發生。

參考文獻：

［1］彭媛.基于系統安全性的死鎖避免算法［J］.武漢生物工程學院學報，2006（1）：40-42.

［2］張菊.基于銀行家算法的進程安全序列仿真研究［J］.軟件，2012，33（2）：21-23.

［3］侯剛.深入解析銀行家算法［J］.濰坊學院學報，2006（3）：46-48.

［4］王繼奎，王會勇.基于銀行家算法的進程安全序列全搜索算法［J］.甘肅科學學報，2009 （2）：152-154.

［5］李婧，陳旺虎.基于廣義表的銀行家算法［J］.西北師范大學學報：自然科學版，2002（3）：30-33.

［6］彭志勇，賴曉鳳.銀行家算法在高校排課系統中的應用［J］.西昌學院學報：自然科學版，2011（6）：25-2.

(編輯：向飛)

The Research of Multi-Process Allocation Strategy Based on Banker Algorithm

LIANG Yun
（Heyuan Power Supply Bureau，Heyuan517000，China）

Abstract:Deadlock is the important affair of multi-user operating system. Insufficient system resource will cause the multi-process algorithm into unsafe state，lead to deadlock problem. Banker algorithm is an important method to avoid deadlock，guarantees the system always in safe state. There are four data structures in Banker algorithm: available resource vector，maximum demand matrix，allocation matrix and need matrix. Banker algorithm includes heuristic allocation，security check and resource allocation. In this paper，Banker algorithm is designed and implemented by MFC programming. According to the test results，it is proved that this software can avoid deadlock effectively and complete resource allocation for multi-processes.

Key words:Banker algorithm；deadlock；system safety；multi-process

作者簡介：梁允，男，1986年生，廣東河源人，碩士，工程師。研究領域：電力信息技術。

收稿日期：2015－08－11

DOI:10. 3969 / j. issn. 1009-9492. 2015. 11. 031

中圖分類號：TP39

文獻標識碼：A

文章編號：1009－9492 ( 2015 ) 11－0119－04