【正文】 鎖的算法，該算法由于能用于銀行系統(tǒng)現(xiàn)金貸款的發(fā)放而得名。銀行家算法是在確保當(dāng)前系統(tǒng)安全的前提下推進(jìn)的。該論文在理解和分析了銀行家算法的核心思想以及狀態(tài)的本質(zhì)含義的前提下，對算法的實(shí)現(xiàn)在總體上進(jìn)行了設(shè)計(jì)，包括對算法分模塊設(shè)計(jì)，并對各個(gè)模塊的算法思想通過流程圖表示，分塊編寫代碼，并進(jìn)行測試，最后進(jìn)行程序的測試，在設(shè)計(jì)思路上嚴(yán)格按照軟件工程的思想執(zhí)行，確保了設(shè)計(jì)和實(shí)現(xiàn)的可行性。如此，尋求一種避免死鎖的方法便顯得很重要。因此，我們只需在當(dāng)前的有限資源下，找到一組合法的執(zhí)行順序，便能很好的避免死鎖。 死鎖 死鎖是進(jìn)程死鎖的簡稱，是指多個(gè)進(jìn)程循環(huán)等待它方占有的資源而無限期地僵持下去的局面。雖然進(jìn)程在運(yùn)行過程中會(huì)產(chǎn)生死鎖，但死鎖的發(fā)生也必須具備四個(gè)條件：（ 1）互斥條件；（ 2）請求與保持條件；（ 3）不剝奪條件；（ 4）環(huán)路與等待條件。目前，預(yù)防死鎖的方法可歸結(jié)為以下兩種： （ 1）預(yù)防死鎖。去破壞產(chǎn)生死鎖的四個(gè)條件中的一個(gè)或幾個(gè)條件，來預(yù)防發(fā)生死鎖。同樣是實(shí)現(xiàn)預(yù)防的策略但是他并不是實(shí)現(xiàn)采取各種限制措施去破壞產(chǎn)生死鎖的四個(gè)條件，而是在資源分配過程中，用某種方法去防止 系統(tǒng)進(jìn)入不安全的狀態(tài)，從而避免死鎖。這種方法并不須事先采取任何限制性措施，也不需檢查系統(tǒng)是否進(jìn)入不安全區(qū)，而是允許系統(tǒng)在運(yùn)行過程中發(fā)生死鎖。然后，采取適當(dāng)?shù)氖侄?，將死鎖清除掉。與檢測死鎖相配套，當(dāng)系統(tǒng)發(fā)生死鎖的時(shí)候，將進(jìn)程從死鎖中解除出來。但預(yù)防死鎖所施加的條件較嚴(yán)格，這往往會(huì)影響進(jìn)程的并發(fā)執(zhí)行，而避免死鎖所施加的限制條件則較寬松，這給進(jìn)程的運(yùn)行 提供了較寬松的環(huán)境，有利于進(jìn)程的并發(fā)執(zhí)行。所謂的安全狀態(tài)就是指系統(tǒng)按某種進(jìn)程順序（ P1， P2， …… ， Pn）（稱 P1， P2， …… ， Pn為安全序列），來為某種進(jìn)程分配資源，直至滿足每個(gè)進(jìn)程對資源的最大需求，使每個(gè)進(jìn)程都能夠順利完成。 銀行家算法 銀行家算法是最具有代表性的避免死鎖的算法，是由于該算法能用于銀行系統(tǒng)現(xiàn)金貸款的發(fā)放而得名。為保證資金的安全 ,銀行家規(guī)定： （ 1）當(dāng)一個(gè)顧客對資金的最大需求量不超過銀行家現(xiàn)有的資金時(shí)就可接納該顧客； （ 2）顧客可以分次貸款 ,但貸款的總數(shù)不能超過最大需求量； （ 3）當(dāng)銀行家現(xiàn)有的資金不能滿足顧客尚需的貸款數(shù)額時(shí) ,對顧客的貸款可推遲支付 ,但總能使顧客在有限的時(shí)間里得到貸款； （ 4）當(dāng)顧客得到所需的資金后 ,一定能在有限的時(shí)間里歸還所有的資金。當(dāng)進(jìn)程在執(zhí)行中繼續(xù)申請資源時(shí)，先測試該進(jìn)程已占用的資源數(shù)與本次申請的資源數(shù)之和是否超過了該進(jìn)程對資源的最大需求量。 那么，安全序列在銀行家算法中的實(shí)際意義在于：系統(tǒng)每次進(jìn)行資源分配后，如果對于系統(tǒng)中新的資源狀況，存在一個(gè)安全序列，則至少存在一條確保系統(tǒng)不 長治學(xué)院學(xué)士學(xué)位論文 (設(shè)計(jì) ) 3 會(huì)進(jìn)入 死鎖的路徑。 問題的關(guān)鍵在于安全性算法，即查找安全性序列。包括對進(jìn)程的存在有無檢查，請求向量的不合法檢查，試分配失敗后的數(shù)據(jù)恢復(fù)和重新接受進(jìn)程請求等。如圖 1 所示。 模塊調(diào)用關(guān)系 銀行家算法系統(tǒng)有四個(gè)模塊，各模塊之間的調(diào)用關(guān)系如圖 2 所示： 圖 2 模塊調(diào)用關(guān)系圖 各模塊之間的接口 系統(tǒng)的四個(gè)模塊用到三個(gè)接口。它們的功能介紹如下：Flag1： 試分配模塊 Attempt_Allocation 與安全性檢查 Safety_Algorithm 之間接口 Attempt_Allocation 通過檢查 flag 的真假了判斷是否執(zhí)行。 Flag2： Safety_Algorithm 與主模塊之間的接口，為真則調(diào)用打印函數(shù)，輸出主模塊 Main（） 初始化 Init_process（） 試分配 Attempt_Allocation（） 安全性檢查 Safety_Algorithm（） 長治學(xué)院學(xué)士學(xué)位論文（設(shè)計(jì)） 5 最終結(jié)果，否則調(diào)用恢復(fù)函數(shù)，恢復(fù)之前系統(tǒng)狀態(tài)。如果 Request[j]≥ Need[i,j]， 則認(rèn)為出錯(cuò)，進(jìn)入等待狀態(tài)。如果 Request[j]≥Available[j]， 則表示尚無足夠資源，進(jìn)程需要等待。檢查此次分配后系統(tǒng)是否處于安全狀態(tài)。否則，將本次的試探分配作廢，恢復(fù)原來 的資源分配。 圖 3 程序總流程圖 4 詳細(xì)設(shè)計(jì) Y Y Y N 開始 結(jié)束 申請資源 試探分配 安全性算法 進(jìn)程等待 正式分配 恢復(fù)程序 RENE? REAVE? 系統(tǒng)安全？ N N 銀行家算法避免死鎖的研究與實(shí)現(xiàn) 6 數(shù)據(jù)結(jié)構(gòu)選取分析 該算法中用到了較多的數(shù)據(jù)，基于程序的易實(shí)現(xiàn)和較好的結(jié)構(gòu)，決定采用結(jié)構(gòu)鏈表，以進(jìn)程為單位（結(jié)點(diǎn)）。否則，打印提示信息，接收其他請求向量； （ 4）再次調(diào)用安全性算法，檢查試分配以后的系統(tǒng)安全性，若安全打印安全性序列和當(dāng)前系統(tǒng)資源分布圖，并進(jìn)入新一輪的執(zhí)行。 長治學(xué)院學(xué)士學(xué)位論文（設(shè)計(jì)） 7 程序流圖 (1)系統(tǒng)以及進(jìn)程資源初始化 Init_process 的程序流程圖 首先，讀入當(dāng)前系統(tǒng)可用資源；然后，讀入進(jìn)程資源，建立進(jìn)程鏈表，輸入1 結(jié)束初始化；最后，打印當(dāng)前系統(tǒng)資源分配表。 圖 4 初始化 Init_process 的程序流程圖 (2)安全性算法的程序流程圖 首先，初識化 work,finish[]。最后，執(zhí)行安全檢查，并顯示檢查后結(jié)果，返回給 flag。 Y N N Y 開始 結(jié)束 初始化 int i,j=0。 輸入數(shù)據(jù) Break； [0]!=1 1 銀行家算法避免死鎖的研究與實(shí)現(xiàn) 8 圖 6 試分配的程序流程圖 圖 5 安全性算法的程序流程圖 (3)接受進(jìn)程請求，試分配的程序流程圖 首先， p 指針指向弧的結(jié)點(diǎn)。如圖 6 所示。如圖 7 所示。 i=0； i++。 i=0。 對不同情況進(jìn)行分析 P!=null? im？ Y N 開始 結(jié)束 Int num,i。 請求合法性檢驗(yàn) Printf(“請輸入請求向量 \”) Printf(“無此進(jìn)程！ \n”) 試分配，修改相關(guān)數(shù)據(jù) P==null？ 長治學(xué)院學(xué)士學(xué)位論文（設(shè)計(jì)） 9 圖 7 試分配后，安全性檢查的程序流程圖 5 程序分析測試 分模塊分析與測試 （ 1)初始化系統(tǒng)資源模塊 Init_process 的測試 圖 8 初始化系統(tǒng)資源模塊 Init_process 的測試 N Y i m？ m？ 恢復(fù)系統(tǒng)資源 i=0 i ++。 結(jié)束 銀行家算法避免死鎖的研究與實(shí)現(xiàn) 10 按提示輸入，以 1 結(jié)束整個(gè)初始化過程，并打印結(jié)果。如圖 8 所示。如圖 9 所示。如圖 11所示。如圖 13所示。 （ 1） 06： 結(jié)果： 無此進(jìn)程。 （ 3） 01： Request(1,0,2) 結(jié)果： 兩次安全性檢查都通過，并打印出最終結(jié)果。 （ 5） 00： Request(0,1,0) 結(jié)果： 兩次安全性檢查都通過，并打印出最終結(jié)果。 首先，我在網(wǎng)上收集了一些關(guān)于銀行家算法的資料，包括它的起源，以及在實(shí)際中多個(gè)領(lǐng)域的應(yīng)用，加深了對它的理解。首先需要初識化系統(tǒng)資源；其次，安全性檢查；再者，試分配；最后是試分配后的安全性檢查。譬如，死循環(huán)，邏輯關(guān)系的設(shè)計(jì)不當(dāng)，還有顯示效果不理想等等。在集成測試中，由于之前的模塊測試做的比較扎實(shí)，所以相對只是一些細(xì)節(jié)上的問題，很快也達(dá)到了預(yù)期的效果。 deadlock。 secure sequence 銀行家算法避免死鎖的研究與實(shí)現(xiàn) 14 致謝 在論文的寫作過程中遇到了無數(shù)的困難和障礙，都在同學(xué)和老師的幫助下度過了。另外，在校圖書館查找資料的時(shí)候，圖書館的老師也給我提供了很多方面的支持與幫助。 由于我的學(xué)術(shù)水平有限，所寫論文難免有不足之處，懇請各位老師批評和指正！