基于銀行家算法的多進(jìn)程算法資源配置策略研究

梁允（廣東電網(wǎng)有限責(zé)任公司河源供電局，廣東河源　514000）

?

基于銀行家算法的多進(jìn)程算法資源配置策略研究

梁允
（廣東電網(wǎng)有限責(zé)任公司河源供電局，廣東河源514000）

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

關(guān)鍵詞：銀行家算法；死鎖；系統(tǒng)安全；多進(jìn)程

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

在避免死鎖的著名算法中，其中較為著名的是由Dijkstra在1965年提出的銀行家算法，它是以銀行的借貸系統(tǒng)的分配原則為理論背景，為判斷并保證T.H.E系統(tǒng)的安全運(yùn)行為目的的一種算法?，F(xiàn)已推廣到同一系統(tǒng)中，涉及多個(gè)單元向上級(jí)進(jìn)行動(dòng)態(tài)的資源申請(qǐng)及回收，都可以采取這種算法保證系統(tǒng)的穩(wěn)定運(yùn)行。

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

本文提出了基于銀行家算法的多進(jìn)程算法資源分配策略，進(jìn)一步促進(jìn)了銀行家算法在多進(jìn)程算法資源分配策略的應(yīng)用，有效避免了多任務(wù)處理系統(tǒng)中死鎖的發(fā)生。

1　多進(jìn)程算法資源分配存在問題

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

要想避免死鎖，就必須考慮進(jìn)程是否處于系統(tǒng)所要求的安全狀態(tài)，這樣就可以很好的規(guī)避死鎖。安全狀態(tài)指系統(tǒng)按照某種設(shè)定的安全進(jìn)程順序?yàn)槟撤N進(jìn)程合理的提供資源分配，在此基礎(chǔ)上進(jìn)而滿足每個(gè)進(jìn)程對(duì)資源的最大需求，這樣就使的每個(gè)進(jìn)程都能夠順利完成系統(tǒng)的任務(wù)。若在系統(tǒng)中，不存在或無法發(fā)現(xiàn)這樣的安全序列，那么就稱系統(tǒng)處于不安全狀態(tài)。

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

綜上，當(dāng)進(jìn)程向系統(tǒng)發(fā)出某種資源申請(qǐng)時(shí)，需要進(jìn)行安全性檢查。分析系統(tǒng)中進(jìn)程已分配資源數(shù)，當(dāng)下進(jìn)程的最大需求資源數(shù)及系統(tǒng)可配置資源數(shù)，在綜合分析后，根據(jù)分析結(jié)果決定判斷系統(tǒng)是否進(jìn)行資源分配，進(jìn)而避免系統(tǒng)進(jìn)入不安全狀態(tài)。

2　銀行家算法

銀行家算法是避免死鎖的算法中頗具代表性的算法，其得名由于該算法思想來源于銀行系統(tǒng)現(xiàn)金貸款的發(fā)放。為了保證資金的安全，銀行家必須保證顧客對(duì)資金的總需求量不超過銀行家?guī)齑娴乃匈Y金；若銀行家現(xiàn)有的資金少于顧客所需要的貸款需求時(shí)，對(duì)顧客的貸款進(jìn)行推遲處理，同時(shí)也必須滿足，在有限的時(shí)間內(nèi)，需處理顧客的貸款需求；同時(shí)若當(dāng)顧客得到所需貸款后，也必須在有限的時(shí)間內(nèi)，歸還所借取的貸款[8]。

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

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

第2類數(shù)據(jù)類型稱為最大需求矩陣，表示進(jìn)程分別對(duì)應(yīng)類資源的最大需求量，本文中用n×m的矩陣Max進(jìn)行表示。

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

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

2.2銀行家算法流程

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

當(dāng)進(jìn)程Pi提出資源申請(qǐng)時(shí)，系統(tǒng)執(zhí)行以下步驟：

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

圖1　銀行家算法流程圖

（2）若Requesti≤Available，跳轉(zhuǎn)到下一步，否則進(jìn)程等待；

（3）假設(shè)系統(tǒng)試分配及安全性檢查通過，則可以進(jìn)行分配，分配算法為：

系統(tǒng)安全性檢查算法如圖2所示。

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

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

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

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

3　銀行家算法的程序設(shè)計(jì)

本文采用Visual C++ 6.0設(shè)計(jì)Windows界面程序，程序設(shè)計(jì)語言為C++。界面分為三部分：參數(shù)輸入?yún)^(qū)域，資源分配區(qū)域和結(jié)果顯示區(qū)域。用戶在參數(shù)輸入?yún)^(qū)域輸入可利用資源、進(jìn)程名稱、進(jìn)程所需最大需求矩陣、進(jìn)程的分配矩陣、等信息，單擊動(dòng)態(tài)添加按鍵添加進(jìn)程資源，單擊安全檢查，可以檢查當(dāng)前所有進(jìn)程對(duì)當(dāng)前資源的申請(qǐng)是否安全，是否會(huì)使系統(tǒng)因資源不足或其他原因進(jìn)入不安全狀態(tài)從而不能完成分配。如果進(jìn)程申請(qǐng)資源安全，軟件則提示安全，否則提示不安全。

軟件可以支持最多10類資源進(jìn)行分配，如圖4所示。可利用資源向量為[5，5，5，5，5，5，5，5，5，5]，輸入進(jìn)程名稱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]，完成輸入之后單擊“動(dòng)態(tài)添加”按鍵添加進(jìn)程成功。單擊“安全檢查”按鍵，即提示系統(tǒng)狀態(tài)安全，可以執(zhí)行分配操作。

開始執(zhí)行分配，在進(jìn)程名稱文本框輸入“process0”以及申請(qǐng)資源量。假設(shè)輸入的申請(qǐng)資源量為[1，1，1，1，1，1，1，1，1，1]，單擊“申請(qǐng)資源”，軟件彈出“資源分配后安全，可以分配”的消息提示框，表明輸入的資源量可以滿足申請(qǐng)要求并執(zhí)行申請(qǐng)請(qǐng)求。單擊確認(rèn)，進(jìn)程process0已經(jīng)分配資源為[1，1，1，1，1，1，1，1，1，1]，尚需分配資源為[0，0，1，0，0，0，0，0，0，0]，表明process0申請(qǐng)資源成功。此時(shí)系統(tǒng)可用資源數(shù)向量由原來的[5，5，5，5，5，5，5，5，5，5]變?yōu)閇4，4，4，4，4，4，4，4，4，4]，系統(tǒng)為進(jìn)程process0分配資源成功，如圖5所示。

圖4　軟件安全性檢查

圖5　進(jìn)程資源分配

4　結(jié)論

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

參考文獻(xiàn)：

［1］彭媛.基于系統(tǒng)安全性的死鎖避免算法［J］.武漢生物工程學(xué)院學(xué)報(bào)，2006（1）：40-42.

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

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

［4］王繼奎，王會(huì)勇.基于銀行家算法的進(jìn)程安全序列全搜索算法［J］.甘肅科學(xué)學(xué)報(bào)，2009 （2）：152-154.

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

［6］彭志勇，賴曉鳳.銀行家算法在高校排課系統(tǒng)中的應(yīng)用［J］.西昌學(xué)院學(xué)報(bào)：自然科學(xué)版，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

作者簡(jiǎn)介：梁允，男，1986年生，廣東河源人，碩士，工程師。研究領(lǐng)域：電力信息技術(shù)。

收稿日期：2015－08－11

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

中圖分類號(hào)：TP39

文獻(xiàn)標(biāo)識(shí)碼：A

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