畢業(yè)論文--銀行家算法避免死鎖的研究與實(shí)現(xiàn)

1、<p><b>　　長(zhǎng) 治 學(xué) 院</b></p><p>　　2013屆學(xué)士學(xué)位畢業(yè)論文</p><p>　　銀行家算法避免死鎖的研究與實(shí)現(xiàn)</p><p>　　學(xué) 號(hào)： 09407227 </p><p>　　姓 名： 王子丹 </p>

2、<p>　　指導(dǎo)教師： 陜粉麗 </p><p>　　專 業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù) </p><p>　　系 別： 計(jì)算機(jī)系 </p><p>　　完成時(shí)間：2013年5月</p><p>　　銀行家算法避免死鎖的研究與實(shí)現(xiàn)</p><p>　　專業(yè)：

3、計(jì)算機(jī)科學(xué)與技術(shù) 姓名：王子丹 學(xué)號(hào)：09407227</p><p><b>　　指導(dǎo)教師：陜粉麗</b></p><p>　　摘 要：Dijkstra的銀行家算法是最有代表性的避免死鎖的算法，該算法由于能用于銀行系統(tǒng)現(xiàn)金貸款的發(fā)放而得名。銀行家算法是在確保當(dāng)前系統(tǒng)安全的前提下推進(jìn)的。對(duì)進(jìn)程請(qǐng)求先進(jìn)行安全性檢查，來(lái)決定資源分配與否，從而確保系統(tǒng)的安全，有效的避

4、免了死鎖的發(fā)生。該論文在理解和分析了銀行家算法的核心思想以及狀態(tài)的本質(zhì)含義的前提下，對(duì)算法的實(shí)現(xiàn)在總體上進(jìn)行了設(shè)計(jì)，包括對(duì)算法分模塊設(shè)計(jì)，并對(duì)各個(gè)模塊的算法思想通過(guò)流程圖表示，分塊編寫代碼，并進(jìn)行測(cè)試，最后進(jìn)行程序的測(cè)試，在設(shè)計(jì)思路上嚴(yán)格按照軟件工程的思想執(zhí)行，確保了設(shè)計(jì)和實(shí)現(xiàn)的可行性。 </p><p>　　關(guān)鍵詞：銀行家算法；死鎖；避免死鎖；安全性序列</p><p><b&

5、gt;　　目 錄</b></p><p><b>　　1 前言1</b></p><p>　　1.1 課題背景1</p><p><b>　　1.2 死鎖1</b></p><p>　　1.3 系統(tǒng)安全狀態(tài)2</p><p>　　1.4 銀行家算法2&

6、lt;/p><p><b>　　2 需求分析3</b></p><p>　　2.1 問(wèn)題描述3</p><p>　　2.2 基本要求3</p><p>　　2.3 數(shù)據(jù)流模型3</p><p><b>　　3 概要設(shè)計(jì)4</b></p><p>

7、　　3.1 模塊的劃分4</p><p>　　3.2 模塊調(diào)用關(guān)系4</p><p>　　3.3 各模塊之間的接口4</p><p>　　3.4 程序流程圖5</p><p><b>　　4 詳細(xì)設(shè)計(jì)6</b></p><p>　　4.1 數(shù)據(jù)結(jié)構(gòu)選取分析6</p>&l

8、t;p>　　4.2 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)6</p><p>　　4.3 算法整體設(shè)計(jì)與調(diào)用6</p><p>　　4.4 程序流圖7</p><p>　　5 程序分析測(cè)試9</p><p>　　5.1 分模塊分析與測(cè)試9</p><p>　　5.2 集成測(cè)試11</p><p><

9、;b>　　6 結(jié)論12</b></p><p><b>　　參考文獻(xiàn)12</b></p><p><b>　　致謝14</b></p><p><b>　　附錄15</b></p><p>　　銀行家算法避免死鎖的研究與實(shí)現(xiàn)</p>&l

10、t;p><b>　　1 前言</b></p><p><b>　　1.1 課題背景</b></p><p>　　在多道程序系統(tǒng)中，雖可以借助多個(gè)進(jìn)程的并發(fā)執(zhí)行來(lái)改善系統(tǒng)的資源利用率，提高系統(tǒng)吞吐量，但可能發(fā)生一種危險(xiǎn)——死鎖。如此，尋求一種避免死鎖的方法便顯得很重要。死鎖產(chǎn)生的一般原因有兩點(diǎn)：競(jìng)爭(zhēng)資源和進(jìn)程間推進(jìn)順序非法。因此，我們只需在當(dāng)

11、前的有限資源下，找到一組合法的執(zhí)行順序，便能很好的避免死鎖。而銀行家算法起源于銀行系統(tǒng)的發(fā)放貸款，和計(jì)算機(jī)操作系統(tǒng)的資源分配完全符合，因此可以借鑒該算法的思想，設(shè)計(jì)出一種有效的算法程序，解決該問(wèn)題。</p><p><b>　　1.2 死鎖</b></p><p>　　死鎖是進(jìn)程死鎖的簡(jiǎn)稱，是指多個(gè)進(jìn)程循環(huán)等待它方占有的資源而無(wú)限期地僵持下去的局面。很顯然，如果沒(méi)有外

12、力的作用，那么死鎖涉及到的各個(gè)進(jìn)程都將永遠(yuǎn)處于封鎖狀態(tài)。雖然進(jìn)程在運(yùn)行過(guò)程中會(huì)產(chǎn)生死鎖，但死鎖的發(fā)生也必須具備四個(gè)條件：（1）互斥條件；（2）請(qǐng)求與保持條件；（3）不剝奪條件；（4）環(huán)路與等待條件。</p><p>　　為保證系統(tǒng)中諸進(jìn)程的正常運(yùn)行，應(yīng)事先采取必要的措施，來(lái)預(yù)防發(fā)生死鎖。目前，預(yù)防死鎖的方法可歸結(jié)為以下兩種：</p><p>　?。?）預(yù)防死鎖。它是通過(guò)設(shè)置某些限制條件。去

13、破壞產(chǎn)生死鎖的四個(gè)條件中的一個(gè)或幾個(gè)條件，來(lái)預(yù)防發(fā)生死鎖。</p><p>　　（2）避免死鎖。同樣是實(shí)現(xiàn)預(yù)防的策略但是他并不是實(shí)現(xiàn)采取各種限制措施去破壞產(chǎn)生死鎖的四個(gè)條件，而是在資源分配過(guò)程中，用某種方法去防止系統(tǒng)進(jìn)入不安全的狀態(tài)，從而避免死鎖。</p><p>　　（3）檢測(cè)死鎖。這種方法并不須事先采取任何限制性措施，也不需檢查系統(tǒng)是否進(jìn)入不安全區(qū)，而是允許系統(tǒng)在運(yùn)行過(guò)程中發(fā)生死鎖。通

14、過(guò)系統(tǒng)設(shè)置的檢測(cè)機(jī)構(gòu)，及時(shí)的檢測(cè)出死鎖的發(fā)生。然后，采取適當(dāng)?shù)氖侄?，將死鎖清除掉。</p><p>　?。?）解除死鎖。與檢測(cè)死鎖相配套，當(dāng)系統(tǒng)發(fā)生死鎖的時(shí)候，將進(jìn)程從死鎖中解除出來(lái)。</p><p>　　1.3 系統(tǒng)安全狀態(tài)</p><p>　　預(yù)防死鎖和解除死鎖都是通過(guò)施加條件限制，來(lái)預(yù)防發(fā)生死鎖。但預(yù)防死鎖所施加的條件較嚴(yán)格，這往往會(huì)影響進(jìn)程的并發(fā)執(zhí)行，而避免

15、死鎖所施加的限制條件則較寬松，這給進(jìn)程的運(yùn)行提供了較寬松的環(huán)境，有利于進(jìn)程的并發(fā)執(zhí)行。</p><p>　　要想避免死鎖，就必須考慮進(jìn)程是否處于安全狀態(tài)，只要處于安全狀態(tài)就可以避免死鎖。所謂的安全狀態(tài)就是指系統(tǒng)按某種進(jìn)程順序（P1，P2，……，Pn）（稱<P1，P2，……，Pn>為安全序列），來(lái)為某種進(jìn)程分配資源，直至滿足每個(gè)進(jìn)程對(duì)資源的最大需求，使每個(gè)進(jìn)程都能夠順利完成。但如果系統(tǒng)無(wú)法找到這樣一個(gè)安

16、全序列，則稱系統(tǒng)處于不安全狀態(tài)。</p><p><b>　　1.4 銀行家算法</b></p><p>　　銀行家算法是最具有代表性的避免死鎖的算法，是由于該算法能用于銀行系統(tǒng)現(xiàn)金貸款的發(fā)放而得名。我們可以把操作系統(tǒng)看作是銀行家，操作系統(tǒng)管理的資源相當(dāng)于銀行家管理的資金，進(jìn)程向操作系統(tǒng)請(qǐng)求分配資源相當(dāng)于用戶向銀行家貸款。為保證資金的安全,銀行家規(guī)定：</p&g

17、t;<p>　?。?）當(dāng)一個(gè)顧客對(duì)資金的最大需求量不超過(guò)銀行家現(xiàn)有的資金時(shí)就可接納該顧客；</p><p>　?。?）顧客可以分次貸款,但貸款的總數(shù)不能超過(guò)最大需求量；</p><p>　?。?）當(dāng)銀行家現(xiàn)有的資金不能滿足顧客尚需的貸款數(shù)額時(shí),對(duì)顧客的貸款可推遲支付,但總能使顧客在有限的時(shí)間里得到貸款；</p><p>　?。?）當(dāng)顧客得到所需的資金后

18、,一定能在有限的時(shí)間里歸還所有的資金。</p><p>　　操作系統(tǒng)按照銀行家制定的規(guī)則為進(jìn)程分配資源，當(dāng)進(jìn)程首次申請(qǐng)資源時(shí)，要測(cè)試該進(jìn)程對(duì)資源的最大需求量，如果系統(tǒng)現(xiàn)存的資源可以滿足它的最大需求量則按當(dāng)前的申請(qǐng)量分配資源，否則就推遲分配。當(dāng)進(jìn)程在執(zhí)行中繼續(xù)申請(qǐng)資源時(shí)，先測(cè)試該進(jìn)程已占用的資源數(shù)與本次申請(qǐng)的資源數(shù)之和是否超過(guò)了該進(jìn)程對(duì)資源的最大需求量。若超過(guò)則拒絕分配資源，若沒(méi)有超過(guò)則再測(cè)試系統(tǒng)現(xiàn)存的資源能否滿足

19、該進(jìn)程尚需的最大資源量，若能滿足則按當(dāng)前的申請(qǐng)量分配資源，否則也要推遲分配。</p><p>　　那么，安全序列在銀行家算法中的實(shí)際意義在于：系統(tǒng)每次進(jìn)行資源分配后，如果對(duì)于系統(tǒng)中新的資源狀況，存在一個(gè)安全序列，則至少存在一條確保系統(tǒng)不會(huì)進(jìn)入死鎖的路徑。</p><p><b>　　2 需求分析</b></p><p><b>　　2

20、.1 問(wèn)題描述</b></p><p>　　運(yùn)用銀行家算法避免死鎖的發(fā)生是在確保當(dāng)前系統(tǒng)安全的前提下推進(jìn)的，對(duì)進(jìn)程請(qǐng)求先進(jìn)行安全性檢查來(lái)決定資源分配與否，從而確保系統(tǒng)的安全，有效的避免了死鎖的發(fā)生。</p><p>　　問(wèn)題的關(guān)鍵在于安全性算法，即查找安全性序列。</p><p><b>　　2.2 基本要求</b></p&g

21、t;<p>　?。?）從鍵盤輸入當(dāng)前系統(tǒng)的資源信息，包括當(dāng)前可用資源，每個(gè)進(jìn)程對(duì)各類資源的最大需求量，每個(gè)進(jìn)程當(dāng)前已分配的各個(gè)資源量和每個(gè)進(jìn)程尚需要的各個(gè)資源量；</p><p>　?。?）輸入進(jìn)程請(qǐng)求，按照設(shè)計(jì)好的安全性算法進(jìn)行檢查，得到結(jié)果并輸出整個(gè)執(zhí)行過(guò)程的相關(guān)信息和最終結(jié)果；</p><p>　?。?）要求要有各種異常的處理，程序的可控制性和可連續(xù)性執(zhí)行。包括對(duì)進(jìn)程的

22、存在有無(wú)檢查，請(qǐng)求向量的不合法檢查，試分配失敗后的數(shù)據(jù)恢復(fù)和重新接受進(jìn)程請(qǐng)求等。 </p><p><b>　　2.3 數(shù)據(jù)流模型</b></p><p>　　用鍵盤輸入信息，對(duì)系統(tǒng)資源初始化，輸入進(jìn)程請(qǐng)求，用安全性算法進(jìn)行安全性檢查，系統(tǒng)安全的話就進(jìn)行試分配，再進(jìn)行安全性檢查；如果試分配失敗則恢復(fù)系統(tǒng)。如圖1所示。</p><p><b

23、>　　圖1 數(shù)據(jù)流模型</b></p><p><b>　　3 概要設(shè)計(jì)</b></p><p><b>　　3.1 模塊的劃分</b></p><p>　　由于該算法規(guī)模較小，所以選用結(jié)構(gòu)化的設(shè)計(jì)方法，將該系統(tǒng)劃為四塊，分別是：</p><p>　?。?）主模塊，處在整個(gè)系統(tǒng)的最

24、高層，負(fù)責(zé)組織調(diào)用其他模塊；</p><p>　?。?）初始化模塊，負(fù)責(zé)從鍵盤讀入系統(tǒng)資源和進(jìn)程狀態(tài)，并將系統(tǒng)初識(shí)資源分配狀態(tài)打??；</p><p>　　（3）試分配模塊，負(fù)責(zé)處理進(jìn)程請(qǐng)求和相應(yīng)的數(shù)據(jù)結(jié)構(gòu)的修改，以及特殊情況的處理；</p><p>　?。?）安全性檢查，負(fù)責(zé)試分配后的安全性檢查，以及系統(tǒng)不安全時(shí)的資源恢復(fù)。</p><p>

25、　　3.2 模塊調(diào)用關(guān)系</p><p>　　銀行家算法系統(tǒng)有四個(gè)模塊，各模塊之間的調(diào)用關(guān)系如圖2所示：</p><p>　　圖2 模塊調(diào)用關(guān)系圖</p><p>　　3.3 各模塊之間的接口</p><p>　　系統(tǒng)的四個(gè)模塊用到三個(gè)接口。分別為Flag1，pro，F(xiàn)lag2。它們的功能介紹如下：</p><p>　

26、　Flag1：試分配模塊Attempt_Allocation與安全性檢查Safety_Algorithm之間接口Attempt_Allocation通過(guò)檢查 flag的真假了判斷是否執(zhí)行。</p><p>　　Pro：一個(gè)地址，Safety_Algorithm返回給主模塊main的信息，不為NULL時(shí)表示試分配成功，否則系統(tǒng)轉(zhuǎn)入相應(yīng)異常處理。</p><p>　　Flag2：Safety_

27、Algorithm與主模塊之間的接口，為真則調(diào)用打印函數(shù)，輸出最終結(jié)果，否則調(diào)用恢復(fù)函數(shù)，恢復(fù)之前系統(tǒng)狀態(tài)。</p><p><b>　　3.4 程序流程圖</b></p><p>　　假設(shè)Request是進(jìn)程的請(qǐng)求向量，Need是需求向量，Available是可利用資源向量。如果Request[j]≥Need[i,j]，則認(rèn)為出錯(cuò)，進(jìn)入等待狀態(tài)。因?yàn)樗枰馁Y源數(shù)

28、已經(jīng)超得過(guò)最大值，否則判斷Request[j]，Available[j]。如果Request[j]≥Available[j]，則表示尚無(wú)足夠資源，進(jìn)程需要等待。接著，系統(tǒng)試探著把資源分配給進(jìn)程，系統(tǒng)執(zhí)行安全性算法。檢查此次分配后系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程，來(lái)完成分配。否則，將本次的試探分配作廢，恢復(fù)原來(lái)的資源分配。具體程序總流程圖如圖3所示。</p><p><b>　　圖3

29、程序總流程圖</b></p><p><b>　　4 詳細(xì)設(shè)計(jì)</b></p><p>　　4.1 數(shù)據(jù)結(jié)構(gòu)選取分析</p><p>　　該算法中用到了較多的數(shù)據(jù)，基于程序的易實(shí)現(xiàn)和較好的結(jié)構(gòu)，決定采用結(jié)構(gòu)鏈表，以進(jìn)程為單位（結(jié)點(diǎn)）。</p><p>　　4.2 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)</p><p

30、>　　typedef struct my_process</p><p><b>　　{</b></p><p>　　int num； </p><p>　　int Max[M]；</p><p>　　int Allocation[M]；</p><p>　　int

31、Need[M]；</p><p>　　struct my_process* next；</p><p><b>　　}process；</b></p><p>　　int Available[M]={0}；</p><p>　　int Request[M]={0}；</p><p>　　i

32、nt Record_work[N][M]={0}；</p><p>　　int Safety[N]={0}； </p><p>　　4.3 算法整體設(shè)計(jì)與調(diào)用</p><p>　　主函數(shù)void main（）主要分四大塊：</p><p>　　（1）首先需要初始化Init_process（process **head，int m，int* c

33、ount），存儲(chǔ)系統(tǒng)當(dāng)前狀態(tài)信息；</p><p>　　（2）調(diào)用安全算法Safety_Algorithm，檢測(cè)當(dāng)前系統(tǒng)安全狀態(tài)，若安全則進(jìn)行下一步，否則打印相關(guān)信息，程序退出；</p><p>　?。?）調(diào)用試分配函數(shù)Attempt_Allocation，進(jìn)行試分配，若試分配成功，修改相關(guān)數(shù)據(jù)結(jié)構(gòu)，打印當(dāng)前系統(tǒng)資源分布圖，轉(zhuǎn)下一步。否則，打印提示信息，接收其他請(qǐng)求向量；</p>

34、;<p>　?。?）再次調(diào)用安全性算法，檢查試分配以后的系統(tǒng)安全性，若安全打印安全性序列和當(dāng)前系統(tǒng)資源分布圖，并進(jìn)入新一輪的執(zhí)行。否則之前的試分配作廢，恢復(fù)試分配之前的數(shù)據(jù)結(jié)構(gòu)，輸出相關(guān)提示信息，接收下一個(gè)進(jìn)程請(qǐng)求。</p><p><b>　　4.4 程序流圖</b></p><p>　　(1)系統(tǒng)以及進(jìn)程資源初始化Init_process的程序流程圖

35、 </p><p>　　首先，讀入當(dāng)前系統(tǒng)可用資源；然后，讀入進(jìn)程資源，建立進(jìn)程鏈表，輸入-1結(jié)束初始化；最后，打印當(dāng)前系統(tǒng)資源分配表。如圖4所示。</p><p>　　圖4 初始化Init_process的程序流程圖 </p><p>　　(2)安全性算法的程序流程圖</p><p>　　首先，初識(shí)化work,finish[]。

36、然后，判斷異常情況，利用Reasonable函數(shù)找到當(dāng)前可執(zhí)行的進(jìn)程。最后，執(zhí)行安全檢查，并顯示檢查后結(jié)果，返回給flag。如圖5所示。</p><p>　　圖6 試分配的程序流程圖</p><p>　　圖5 安全性算法的程序流程圖 </p><p>　　(3)接受進(jìn)程請(qǐng)求，試分配的程序流程圖</p><

37、;p>　　首先，p指針指向弧的結(jié)點(diǎn)。如果為空，則輸出無(wú)此進(jìn)程，然后，輸入請(qǐng)求向量，檢查合法性，進(jìn)行試分配。如圖6所示。</p><p>　　(4)對(duì)試分配后的系統(tǒng)，進(jìn)行安全性檢查的程序流程圖</p><p>　　和圖5大致一樣，唯一一點(diǎn)在于當(dāng)找不到安全序列時(shí)，將本次試分配作廢，恢復(fù)該次試分配之前的數(shù)據(jù)結(jié)構(gòu)。如圖7所示。</p><p>　　圖7 試分配后，安全

38、性檢查的程序流程圖</p><p><b>　　5 程序分析測(cè)試</b></p><p>　　5.1 分模塊分析與測(cè)試</p><p>　?。?)初始化系統(tǒng)資源模塊Init_process的測(cè)試</p><p>　　圖8 初始化系統(tǒng)資源模塊Init_process的測(cè)試</p><p>　　按提

39、示輸入，以-1結(jié)束整個(gè)初始化過(guò)程，并打印結(jié)果。起初效果不理想，經(jīng)過(guò)一些調(diào)整后，顯示才比較理想。如圖8所示。</p><p>　　(2)試分配模塊Attempt_Allocation的測(cè)試</p><p>　　圖9 試分配模塊Attempt_Allocation的測(cè)試</p><p>　　試分配模塊，主要是在系統(tǒng)進(jìn)入第一次安全檢查后，對(duì)系統(tǒng)資源的一次嘗試性分配，試分配

40、完成后，相關(guān)的數(shù)據(jù)結(jié)構(gòu)被修改。如圖9所示。</p><p>　　(3)安全模塊Safety_Algorithm的調(diào)試</p><p>　　試分配前的安全算法，結(jié)果如果輸出一個(gè)安全性序列，并且經(jīng)過(guò)人工檢查該安全性序列，確實(shí)有效，則該模塊正確,如圖10所示；如果系統(tǒng)不安全，打印出相關(guān)信息，返回上一層。如圖11所示。</p><p>　　圖10 安全模塊Safety_Al

41、gorithm的調(diào)試的安全狀態(tài)</p><p>　　圖11 安全模塊Safety_Algorithm的調(diào)試的不安全狀態(tài)</p><p>　　試分配后的安全算法，結(jié)果如果輸出一個(gè)安全性序列，并且經(jīng)過(guò)人工檢查該安全性序列，確實(shí)有效，則該模塊正確，如圖12所示；否則，之前的試分配作廢，恢復(fù)試分配前的資源狀態(tài)。如圖13所示。</p><p>　　圖12 試分配后輸出一個(gè)安全

42、性序列</p><p>　　圖13 試分配后不安全狀態(tài)的資源恢復(fù)</p><p><b>　　5.2 集成測(cè)試</b></p><p>　　各模塊測(cè)試通過(guò)后，集成在一起測(cè)試，系統(tǒng)初始資源和模塊測(cè)試時(shí)保持一致，以下是測(cè)試用例以及結(jié)果，基本包括了該算法的所有情況。</p><p>　?。?）06：

43、 結(jié)果： 無(wú)此進(jìn)程。</p><p>　?。?）01： Request(2,0,2)結(jié)果： 系統(tǒng)不能滿足。</p><p>　?。?）01： Request(1,0,2)結(jié)果： 兩次安全性檢查都通過(guò)，并打印出最終結(jié)果。</p><p>　　（4）00： Request(0,2,0)結(jié)果： 試分配后，系統(tǒng)不安全，試分配作廢。</p>

44、<p>　?。?）00： Request(0,1,0)結(jié)果： 兩次安全性檢查都通過(guò)，并打印出最終結(jié)果。</p><p><b>　　6 結(jié)論</b></p><p>　　銀行家算法避免死鎖的研究與實(shí)現(xiàn)作為我的畢業(yè)設(shè)計(jì)。首先，我在網(wǎng)上收集了一些關(guān)于銀行家算法的資料，包括它的起源，以及在實(shí)際中多個(gè)領(lǐng)域的應(yīng)用，加深了對(duì)它的理解。之后，確定自己設(shè)計(jì)的算法分四大模

45、塊。首先需要初識(shí)化系統(tǒng)資源；其次，安全性檢查；再者，試分配；最后是試分配后的安全性檢查。</p><p>　　在程序測(cè)試中出現(xiàn)了很多問(wèn)題。譬如，死循環(huán)，邏輯關(guān)系的設(shè)計(jì)不當(dāng)，還有顯示效果不理想等等。但通過(guò)查閱書本，對(duì)算法細(xì)節(jié)重新建立正確的認(rèn)識(shí)后，再通過(guò)單步調(diào)試后，最終解決。在集成測(cè)試中，由于之前的模塊測(cè)試做的比較扎實(shí)，所以相對(duì)只是一些細(xì)節(jié)上的問(wèn)題，很快也達(dá)到了預(yù)期的效果。 </p><p>

46、;<b>　　參考文獻(xiàn)</b></p><p>　　[1] 嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)[M].北京:清華大學(xué)出社,2005. </p><p>　　[2] 湯小丹,梁紅兵,哲鳳屏等.計(jì)算機(jī)操作系統(tǒng)(第三版)[M].西安:西安電子科技大學(xué)出版社,2007.</p><p>　　[3] 譚浩強(qiáng).C語(yǔ)言程序設(shè)計(jì)[M].北京:清華大學(xué)出版社,

47、2006.</p><p>　　[4] 于帆,趙妮.程序設(shè)計(jì)基礎(chǔ)[M].北京:清華大學(xué)出版社,2006.</p><p>　　[5] 羅宇.操作系統(tǒng)課程[M].北京:設(shè)計(jì)機(jī)械工業(yè)出版社,2005.</p><p>　　[6] 黃水松,黃干平,曾平.計(jì)算機(jī)操作系統(tǒng)[M].武漢:武漢大學(xué)出版社,2003.</p><p>　　[7] 鞠時(shí)光.操作

48、系統(tǒng)原理[M].武漢:武漢理工大學(xué)出版社,2003.</p><p>　　[8] 何炎祥,熊前興.操作系統(tǒng)原理[M].武漢:華中科技大學(xué)出版社,2001.</p><p>　　[9] 張麗芬,劉美華.操作系統(tǒng)原理教程[M].北京:電子工業(yè)出版社,2004.</p><p>　　[10] 陳火.數(shù)據(jù)結(jié)構(gòu)與算法[M].廣東:中山大學(xué)出版社,2009.</p>

49、<p>　　[11] 鄭扣根.操作系統(tǒng)概念(第七版)[M].北京:高等教育出版社,1992.</p><p>　　[12] 趙莉,楊國(guó)梁,孫喁喁,徐飛.Java程序設(shè)計(jì)教程[M].西安:西安科技大學(xué)出版社,2009.</p><p>　　[13] 陳向群,向勇,王雷.Windows操作系統(tǒng)原理(第二版)[M].北京:北京機(jī)械工業(yè)出版社,2004.</p><

50、;p>　　Bankers Algorithm To Avoid Deadlock Research and Implementation</p><p>　　Major:Computer Science and technology Name: Wang Zidan </p><p>　　Student ID: 09407227 Supervis

51、or:Shan Fenli</p><p>　　Abstract:Bankers algorithm what Dijkstra put forward is the most representative of the algorithm to avoid deadlock, this algorithm can be used for the banking system because of its cas

52、h loans. Bankers algorithm is advancing in the premise of ensuring the system security. The first is that security check to process requests, to determine the allocation of resources or not, so as to ensure the safety of

53、 the system, to avoid deadlock.</p><p>　　This paper on the understanding and analysis of the essential meaning of bankers algorithm as well as the state of the core idea, the algorithm is implemented in the

54、overall design, including the module design of algorithm, and the algorithm of each module through a flow chart, block coding, and testing, the final program in the test, the design ideas on strictly according to the tho

55、ught of software engineering implementation, to ensure that the design and implementation of feasible, credible.</p><p>　　Keywords: bankers algorithm; deadlock; avoid deadlock; secure sequence</p><

56、;p><b>　　致謝</b></p><p>　　在論文的寫作過(guò)程中遇到了無(wú)數(shù)的困難和障礙，都在同學(xué)和老師的幫助下度過(guò)了。尤其要感謝我的論文指導(dǎo)老師——陜粉麗老師，她對(duì)我進(jìn)行了無(wú)私的指導(dǎo)和幫助，不厭其煩的幫助進(jìn)行論文的修改和改進(jìn)。另外，在校圖書館查找資料的時(shí)候，圖書館的老師也給我提供了很多方面的支持與幫助。在此向幫助和指導(dǎo)過(guò)我的各位老師表示最真誠(chéng)的感謝！ 此外，還要感謝我的同

57、學(xué)和朋友，在我寫論文的過(guò)程中給予我很多素材，還在論文的撰寫和排版的過(guò)程中提供熱情的幫助。 由于我的學(xué)術(shù)水平有限，所寫論文難免有不足之處，懇請(qǐng)各位老師批評(píng)和指正！</p><p><b>　　附錄</b></p><p><b>　　//銀行家算法</b></p><p>　　#include<stdio.h&

58、gt;</p><p>　　#include<stdlib.h></p><p>　　#include<string.h></p><p>　　#define M 3</p><p>　　#define N 10</p><p>　　#define D12 %5d%5d%5d%5d%5d%5d%

59、5d%5d%5d%5d%5d%5d </p><p>　　typedef struct my_process</p><p><b>　　{</b></p><p>　　int num;</p><p>　　int Max[M];</p><p>　　int Allocation[

60、M];</p><p>　　int Need[M];</p><p>　　struct my_process* next;</p><p><b>　　}process;</b></p><p>　　void Insret_Tail(process **head,process node) </

61、p><p><b>　　{</b></p><p>　　process* p=(process*)malloc(sizeof(process));</p><p>　　process* last=NULL;</p><p>　　memcpy(p,&node,sizeof(process)); </p&g

62、t;<p>　　p->next=NULL;</p><p>　　if(NULL==*head)</p><p><b>　　{</b></p><p><b>　　*head=p;</b></p><p><b>　　}</b></p><

63、;p>　　else </p><p><b>　　{</b></p><p>　　last=*head;</p><p>　　while(last->next!=NULL)</p><p><b>　　{</b></p><p>　　last=last-

64、>next;</p><p><b>　　}</b></p><p>　　last->next=p;</p><p>　　}</p><p><b>　　}</b></p><p>　　void Init_process(pro

65、cess **head,int m,int* count)</p><p><b>　　{</b></p><p>　　int i,j=0;</p><p>　　process node;</p><p>　　printf("請(qǐng)初始化一組進(jìn)程,進(jìn)程編號(hào)從P0開(kāi)始，輸入-1 結(jié)束輸入:\n");&l

66、t;/p><p><b>　　do</b></p><p><b>　　{</b></p><p>　　node.num=j++;</p><p>　　printf("請(qǐng)輸入第 %d個(gè)進(jìn)程信息 :\n",node.num);</p><p>　　printf(

67、"最大需求矩陣: ");</p><p>　　scanf("%d",&node.Max[P0]);</p><p>　　if(node.Max[P0]!=-1) </p><p><b>　　{</b></p><p>　　for(i=1;i<m

68、;i++)</p><p><b>　　{</b></p><p>　　scanf("%d",&node.Max[i]);</p><p><b>　　}</b></p><p>　　printf("分配矩陣: ");</p><p

69、>　　for(i=0;i<m;i++)</p><p><b>　　{</b></p><p>　　scanf("%d",&node.Allocation[i]);</p><p><b>　　}</b></p><p>　　printf("需求矩陣

70、: ");</p><p>　　for(i=0;i<m;i++)</p><p><b>　　{</b></p><p>　　scanf("%d",&node.Need[i]);</p><p><b>　　}</b></p><p&g

71、t;　　Insret_Tail(head,node);</p><p>　　(*count)++;</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><

72、p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　while(1);</b></p><p><b>　　}</b></p&g

73、t;<p>　　void Print(process *head,int *avail,int m)</p><p><b>　　{</b></p><p>　　process* p=NULL;</p><p><b>　　int i,j;</b></p><p><b>

74、;　　char ch;</b></p><p><b>　　p=head;</b></p><p>　　if(NULL==p)</p><p><b>　　{</b></p><p>　　printf("當(dāng)前無(wú)進(jìn)程 !\n"); </

75、p><p><b>　　exit(0);</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　printf("| Proce

76、ss | Max | |Allocation| | Need | |Available|\n\n");</p><p>　　printf("\t");</p><p>　　for(i=0;i<4;i++)</p><p><b>　　{</b></p>&l

77、t;p><b>　　ch='A';</b></p><p>　　for(j=0;j<m;j++)</p><p><b>　　{</b></p><p>　　printf("%4c",ch++);</p><p><b>　　}</b&

78、gt;</p><p>　　printf("\t");</p><p><b>　　}</b></p><p><b>　　puts("");</b></p><p>　　while(p!=NULL)</p><p><b>

79、　　{</b></p><p>　　printf("%8.2d",p->num);</p><p>　　for(j=0;j<m;j++)</p><p><b>　　{</b></p><p>　　printf("%4d",p->Max[j]);<

80、;/p><p><b>　　}</b></p><p>　　printf("\t");</p><p>　　for(j=0;j<m;j++)</p><p><b>　　{</b></p><p>　　printf("%4d",p-&

81、gt;Allocation[j]);</p><p><b>　　}</b></p><p>　　printf("\t");</p><p>　　for(j=0;j<m;j++)</p><p><b>　　{</b></p><p>　　print

82、f("%4d",p->Need[j]);</p><p><b>　　}</b></p><p>　　printf("\t");</p><p>　　for(j=0;j<m;j++)</p><p><b>　　{</b></p>&

83、lt;p>　　printf("%4d",avail[j]);</p><p><b>　　}</b></p><p>　　printf("\n");</p><p>　　p=p->next;</p><p><b>　　}</b></p>

84、;<p><b>　　puts("");</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　process* Location(process* head,int pro_num)</p>&l

85、t;p><b>　　{</b></p><p>　　process *p=NULL;</p><p><b>　　p=head;</b></p><p>　　if(NULL==p)</p><p><b>　　{</b></p><p>　　pri

86、ntf("error !\n");</p><p><b>　　return p;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p

87、><p>　　while(p!=NULL)</p><p><b>　　{</b></p><p>　　if(p->num==pro_num)</p><p><b>　　{</b></p><p><b>　　break;</b></p>

88、<p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　p=p->next;</p><p><b>　　}</b></p><p&g

89、t;<b>　　}</b></p><p>　　if(NULL==p)</p><p><b>　　{</b></p><p>　　printf("無(wú)此進(jìn)程 !\n");</p><p><b>　　return p;</b></p>

90、<p><b>　　}</b></p><p><b>　　else </b></p><p><b>　　{</b></p><p><b>　　return p;</b></p><p><b>　　}</b><

91、;/p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　process* Attempt_Allocation(process* head,int *request,int *avail,int m)</p><p><b>　　{</b&g

92、t;</p><p>　　int num,i;</p><p>　　process* p=NULL;</p><p>　　printf("請(qǐng)輸入進(jìn)程編號(hào): \n");</p><p>　　scanf("%d",&num);</p><p>　　p=Location(hea

93、d,num);</p><p>　　if(p==NULL)</p><p><b>　　{</b></p><p>　　printf("無(wú)此進(jìn)程!\n");</p><p><b>　　return p;</b></p><p><b>　　}&

94、lt;/b></p><p>　　printf("請(qǐng)輸入該進(jìn)程的請(qǐng)求向量: \n");</p><p>　　for(i=0;i<m;i++)</p><p><b>　　{</b></p><p>　　scanf("%d",&request[i]);</p

95、><p><b>　　}</b></p><p>　　for(i=0;i<m;i++)</p><p><b>　　{</b></p><p>　　if(request[i]<=p->Need[i])</p><p><b>　　{</b&g

96、t;</p><p><b>　　;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　printf("該請(qǐng)求系統(tǒng)不能

97、滿足 !\n");</p><p>　　return NULL;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　for(i=0;i<m;i++)</p><p><b>　　{</b>

98、</p><p>　　if(request[i]<=avail[i])</p><p><b>　　{</b></p><p><b>　　;</b></p><p><b>　　}</b></p><p><b>　　else</

99、b></p><p><b>　　{</b></p><p>　　printf("該請(qǐng)求系統(tǒng)不能滿足 !\n");</p><p>　　return NULL;</p><p><b>　　}</b></p><p><b>　　}<

100、;/b></p><p>　　for(i=0;i<m;i++) </p><p><b>　　{</b></p><p>　　avail[i]=avail[i] - request[i];</p><p>　　p->Allocation[i]=p->Alloc

101、ation[i] + request[i];</p><p>　　p->Need[i]=p->Need[i] - request[i];</p><p><b>　　}</b></p><p><b>　　return p;</b></p><p><b>　　}</b&

102、gt;</p><p>　　process* Reasonable(process* head,int*finish,int*work,int m,int n)</p><p><b>　　{</b></p><p>　　int i=0,j=0,count=0;</p><p>　　process* p=NULL;&

103、lt;/p><p><b>　　while(1)</b></p><p><b>　　{</b></p><p>　　if(finish[i]!=-1)</p><p><b>　　{</b></p><p>　　p=Location(head,finis

104、h[i]);</p><p>　　if(p!=NULL)</p><p><b>　　{</b></p><p>　　for(j=0;j<m;j++)</p><p><b>　　{</b></p><p>　　if(p->Need[j]>work[j]

105、)</p><p><b>　　{</b></p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b

106、></p><p><b>　　continue;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　if(j==m)</b></p><p><b>

107、;　　{</b></p><p><b>　　return p;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>&l

108、t;b>　　i++; </b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p&g

109、t;<b>　　{</b></p><p><b>　　i++; </b></p><p><b>　　}</b></p><p><b>　　if(i==n)</b></p><p><b>　　{</b></p>

110、<p>　　return NULL; </p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void Alter_Data(process* p,int* work,int* f

111、inish,int record[][M],int m) </p><p><b>　　{</b></p><p><b>　　int i;</b></p><p>　　for(i=0;i<m;i++)</p><p><b>　　{</b></p>&l

112、t;p>　　record[p->num][i]=work[i];</p><p>　　work[i]=work[i]+p->Allocation[i];</p><p><b>　　}</b></p><p>　　finish[p->num]=-1; </p><p><b>　　}

113、</b></p><p>　　int Safety_Algorithm(process* head,int *avail,int *safety,int Record[][M],int m,int n)</p><p><b>　　{</b></p><p>　　int *work=NULL;</p><p>

114、;　　int *finish=NULL;</p><p>　　process *p=NULL;</p><p>　　process *pro=NULL;</p><p>　　int i,count=0;</p><p>　　work=(int*)malloc(m*sizeof(int));</p><p>　　fi

115、nish=(int*)malloc(n*sizeof(int));</p><p>　　//safety=(int*)malloc(n*sizeof(int));</p><p><b>　　p=head;</b></p><p>　　for(i=0;i<m;i++)</p><p><b>　　{&

116、lt;/b></p><p>　　work[i]=avail[i];</p><p><b>　　}</b></p><p><b>　　i=0;</b></p><p>　　while(p!=NULL)</p><p><b>　　{</b>&

117、lt;/p><p>　　finish[i]=p->num;</p><p>　　p=p->next;</p><p><b>　　i++;</b></p><p><b>　　}</b></p><p><b>　　i=0;</b></p&

118、gt;<p>　　while(count<n)</p><p><b>　　{</b></p><p>　　pro=Reasonable(head,finish,work,m,n);</p><p>　　if(pro!=NULL){</p><p>　　Alter_Data(pro,

119、work,finish,Record,m);</p><p><b>　　count++;</b></p><p>　　safety[i]=pro->num; //</p><p><b>　　i++;</b></p><p><b>　　}</b></p>

120、;<p><b>　　else</b></p><p><b>　　{</b></p><p>　　printf("當(dāng)前系統(tǒng)處于不安全狀態(tài) !\n");</p><p>　　//remark=1;</p><p><b>　　break;</b&g

121、t;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　if(count==n)</p><p><b>　　{</b></p><p>　　printf("當(dāng)前系統(tǒng)處于安全狀態(tài),存在一個(gè)安全序

122、列 :\n");</p><p>　　for(i=0;i<n;i++)</p><p><b>　　{</b></p><p>　　printf("%d,",safety[i]); </p><p><b>　　}</b></p><p

123、><b>　　puts("");</b></p><p><b>　　}</b></p><p>　　free(finish);</p><p>　　free(work);</p><p>　　finish=NULL;</p><p>　　work=

124、NULL;</p><p>　　if(count==n)</p><p><b>　　{</b></p><p>　　return 1; </p><p><b>　　}</b></p><p><b>　　else</b></p>&l

125、t;p><b>　　{</b></p><p>　　return 0;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void Return_Source(process* p,int *request,int *a

126、vail,int m) </p><p><b>　　{</b></p><p><b>　　int i;</b></p><p><b>　　{</b></p><p>　　for(i=0;i<m;i++)</p><p><b>　

127、　{</b></p><p>　　p->Allocation[i]-=request[i];</p><p>　　p->Need[i]+=request[i];</p><p>　　avail[i]+=request[i];</p><p><b>　　}</b></p><p

128、><b>　　}</b></p><p><b>　　}</b></p><p>　　void Print_After_Safety(process *head,int *safety,int work[][M],int m,int n) </p><p><b>　　{</b></p&

129、gt;<p>　　process* p=NULL;</p><p><b>　　int i,j;</b></p><p><b>　　char ch;</b></p><p><b>　　p=head;</b></p><p>　　if(NULL==p)</

130、p><p><b>　　{</b></p><p><b>　　exit(0);</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b>

131、</p><p>　　printf("| Process | Work | | Need | |Allocation| |Work+Allocation| | Finish |\n\n");</p><p>　　printf("\t");</p><p>　　for(i=0;i&

132、lt;4;i++)</p><p><b>　　{</b></p><p><b>　　ch='A';</b></p><p>　　for(j=0;j<m;j++)</p><p><b>　　{</b></p><p>　　pri

133、ntf("%4c",ch++);</p><p><b>　　}</b></p><p>　　printf("\t");</p><p><b>　　}</b></p><p><b>　　puts("");</b>&

134、lt;/p><p>　　for(i=0;i<n;i++)</p><p><b>　　{</b></p><p><b>　　p=head;</b></p><p>　　while(p!=NULL)</p><p><b>　　{</b></p

135、><p>　　if(p->num==safety[i])</p><p>　　{printf("%8.2d",p->num);</p><p>　　for(j=0;j<m;j++)</p><p><b>　　{</b></p><p>　　printf(&qu

136、ot;%4d",work[p->num][j]);</p><p><b>　　}</b></p><p>　　printf("\t");</p><p>　　for(j=0;j<m;j++)</p><p><b>　　{</b></p>&

137、lt;p>　　printf("%4d",p->Need[j]);</p><p><b>　　}</b></p><p>　　printf("\t");</p><p>　　for(j=0;j<m;j++)</p><p><b>　　{</b&g

138、t;</p><p>　　printf("%4d",p->Allocation[j]);</p><p><b>　　}</b></p><p>　　printf("\t");</p><p>　　for(j=0;j<m;j++)</p><p>

139、;<b>　　{</b></p><p>　　printf("%4d",work[p->num][j]+p->Allocation[j]);</p><p><b>　　}</b></p><p>　　printf("\n");</p><p>&

140、lt;b>　　break;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　p=p->next;</p><p><b

141、>　　}</b></p><p><b>　　}</b></p><p><b>　　puts("");</b></p><p><b>　　}</b></p><p><b>　　}</b></p>&