銀行家算法課程設(shè)計(jì)2

1、<p><b>　　摘 要</b></p><p>　　銀行家算法是最有代表性的避免死鎖的算法，該算法由于能用于銀行系統(tǒng)現(xiàn)金貸款的發(fā)放而得名。銀行家算法是在確保當(dāng)前系統(tǒng)安全的前提下推進(jìn)的。對(duì)進(jìn)程請(qǐng)求先進(jìn)行安全性檢查，來決定資源分配與否，從而確保系統(tǒng)的安全，有效的避免了死鎖的發(fā)生。</p><p>　　該設(shè)計(jì)在理解和分析了銀行家算法的核心思想以及狀態(tài)的本質(zhì)涵

2、義的前提下，對(duì)算法的實(shí)現(xiàn)在總體上進(jìn)行了設(shè)計(jì)，包括在對(duì)算法分模塊設(shè)計(jì)，并對(duì)各個(gè)模塊的算法思想通過流程圖表示，分塊編寫代碼，并進(jìn)行測(cè)試，最后進(jìn)行程序的測(cè)試，在設(shè)計(jì)思路上嚴(yán)格按照軟件工程的思想執(zhí)行，確保了設(shè)計(jì)和實(shí)現(xiàn)的可行，可信。 </p><p>　　關(guān)鍵詞：銀行家算法；死鎖；避免死鎖；安全性序列</p><p><b>　　目 錄</b></p>&l

3、t;p><b>　　1緒論1</b></p><p><b>　　1.1課題背景1</b></p><p>　　1.2 課題意義1</p><p>　　1.3 銀行家算法原理1</p><p><b>　　1.4 死鎖2</b></p><p

4、>　　1.5安全性序列2</p><p><b>　　2需求分析3</b></p><p>　　2.1 問題描述3</p><p>　　2.2 基本要求3</p><p>　　2.3死鎖的預(yù)防3</p><p><b>　　3 設(shè)計(jì)思路4</b></p

5、><p><b>　　3.1設(shè)計(jì)原理4</b></p><p><b>　　3.2設(shè)計(jì)目的4</b></p><p>　　3.3各模塊之間的調(diào)用圖4</p><p><b>　　4詳細(xì)設(shè)計(jì)5</b></p><p>　　4.1初始化程序設(shè)計(jì)5<

6、;/p><p>　　4.2銀行家算法設(shè)計(jì)5</p><p>　　4.3安全性檢查算法6</p><p><b>　　4.4流程圖7</b></p><p>　　5運(yùn)行調(diào)試及結(jié)果說明8</p><p><b>　　6總結(jié)11</b></p><p>

7、;<b>　　參考文獻(xiàn)12</b></p><p><b>　　致 謝13</b></p><p>　　附錄（源程序）：14</p><p><b>　　1緒論</b></p><p><b>　　1.1課題背景</b></p>&l

8、t;p>　　在多道程序系統(tǒng)中，雖可以借助多個(gè)進(jìn)程的并發(fā)執(zhí)行來改善系統(tǒng)的資源利用率，提高系統(tǒng)吞吐量，但可能發(fā)生一種危險(xiǎn)——死鎖，即多個(gè)進(jìn)程在運(yùn)行過程中因爭(zhēng)奪資源而造成的一種僵局，若無外力作用，將無法再向前推進(jìn)。如此，尋求一種避免死鎖的方法便顯得有為重要。死鎖的產(chǎn)生一般的原因有兩點(diǎn)：競(jìng)爭(zhēng)資源和進(jìn)程間推進(jìn)順序非法。因此，我們只需在當(dāng)前的有限資源下，找到一組合法的執(zhí)行順序，便能很好的避免死鎖，我們稱它為安全序列。而銀行家算法起源于銀行系統(tǒng)

9、的發(fā)放貸款，和計(jì)算機(jī)操作系統(tǒng)的資源分配完全符合，因此可以借鑒該算法的思想，設(shè)計(jì)出一種有效的算法程序，解決該問題。</p><p><b>　　1.2 課題意義</b></p><p>　?。?）運(yùn)用操作系統(tǒng)學(xué)過的知識(shí)和方法設(shè)計(jì)和實(shí)現(xiàn)，又是一次實(shí)戰(zhàn)演練，從而提高自己的分析問題，解決問題和動(dòng)手能力；</p><p>　?。?）通過整個(gè)算法的設(shè)計(jì)與實(shí)

10、現(xiàn)進(jìn)一步加深了對(duì)算法的理解和多道程序下的計(jì)算機(jī)系統(tǒng)資源分配現(xiàn)狀，為以后進(jìn)一步的學(xué)習(xí)打下了良好的基礎(chǔ)。</p><p>　　1.3 銀行家算法原理</p><p>　　為保證資金的安全,銀行家規(guī)定:</p><p>　　(1) 當(dāng)一個(gè)顧客對(duì)資金的最大需求量不超過銀行家現(xiàn)有的資金時(shí)就可接納該顧客;</p><p>　　(2) 顧客可以分歧貸款,但

11、貸款的總數(shù)不能超過最大需求量;</p><p>　　(3) 當(dāng)銀行家現(xiàn)有的資金不能滿足顧客尚需的貸款數(shù)額時(shí),對(duì)顧客的貸款可推遲支付,但總能使顧客在有限的時(shí)間里得到貸款;</p><p>　　(4) 當(dāng)顧客得到所需的全部資金后,一定能在有限的時(shí)間里歸還所有的資金,操作系統(tǒng)按照銀行家制定的規(guī)則為進(jìn)程分配資源，當(dāng)進(jìn)程首次申請(qǐng)資源時(shí)，要測(cè)試該進(jìn)程對(duì)資源的最大需求量，如果系統(tǒng)現(xiàn)存的資源可以滿足它的最

12、大需求量則按當(dāng)前的申請(qǐng)量分配資源，否則就推遲分配。當(dāng)進(jìn)程在執(zhí)行中繼續(xù)申請(qǐng)資源時(shí)，先測(cè)試該進(jìn)程已占用的資源數(shù)與本次申請(qǐng)的資源數(shù)之和是否超過了該進(jìn)程對(duì)資源的最大需求量。若超過則拒絕分配資源，若沒有超過則再測(cè)試系統(tǒng)現(xiàn)存的資源能否滿足該進(jìn)程尚需的最大資源量，若能滿足則按當(dāng)前的申請(qǐng)量分配資源，否則也要推遲分配。</p><p><b>　　1.4 死鎖</b></p><p>

13、　　死鎖是進(jìn)程死鎖的簡(jiǎn)稱，是由Dijkstra于1965年研究銀行家算法時(shí)首先提出來的。是指多個(gè)進(jìn)程循環(huán)等待它方占有的資源而無限期地僵持下去的局面。很顯然，如果沒有外力的作用，那麼死鎖涉及到的各個(gè)進(jìn)程都將永遠(yuǎn)處于封鎖狀態(tài)。</p><p>　　它是計(jì)算機(jī)操作系統(tǒng)乃至并發(fā)程序設(shè)計(jì)中最難處理的問題之一。實(shí)際上，死鎖問題不僅在計(jì)算機(jī)系統(tǒng)中存在，在我們?nèi)粘Ｉ钪兴矎V泛存在。</p><p>　　

14、在計(jì)算機(jī)系統(tǒng)中，涉及軟件，硬件資源都可能發(fā)生死鎖。例如：系統(tǒng)中只有一臺(tái)CD-ROM驅(qū)動(dòng)器和一臺(tái)打印機(jī)，某一個(gè)進(jìn)程占有了CD-ROM驅(qū)動(dòng)器，又申請(qǐng)打印機(jī)；另一進(jìn)程占有了打印機(jī)，還申請(qǐng)CD-ROM。結(jié)果，兩個(gè)進(jìn)程都被阻塞，永遠(yuǎn)也不能自行解除。</p><p><b>　　1.5安全性序列</b></p><p>　　安全序列的的實(shí)際意義在于：系統(tǒng)每次進(jìn)行資源分配后，如果對(duì)

15、于系統(tǒng)中新的資源狀況，存在一個(gè)安全序列，則至少存在一條確保系統(tǒng)不會(huì)進(jìn)入死鎖的路徑。按照該序列，銀行家可以實(shí)施一個(gè)有效的分配過程使得所有客戶得到滿足。</p><p>　　銀行家算法的核心在于安全序列的產(chǎn)生。安全序列正是一種安全的進(jìn)程推進(jìn)順序。</p><p><b>　　2需求分析</b></p><p><b>　　2.1 問題描述

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

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

18、理，程序的可控制性和可連續(xù)性執(zhí)行。包括對(duì)進(jìn)程的存在有無檢查，請(qǐng)求向量的不合法檢查，試分配失敗后的數(shù)據(jù)恢復(fù)和重新接受進(jìn)程請(qǐng)求等。</p><p><b>　　2.3死鎖的預(yù)防</b></p><p>　　出現(xiàn)死鎖有4個(gè)必要條件，只要確保至少一個(gè)必要條件不成立，就能預(yù)防死鎖發(fā)生。</p><p>　?。?）互斥。通常不能通過否定互斥條件來預(yù)防死鎖。

19、有些資源本身是非共享的。</p><p>　　（2）占有并等待。當(dāng)一個(gè)進(jìn)程申請(qǐng)一個(gè)資源時(shí)，它不能占有其他資源。執(zhí)行前申請(qǐng)并獲得所有資源申請(qǐng)其他資源之前，必須釋放其現(xiàn)在已分配的所有資源，缺點(diǎn)是資源利用率可能比較低，可能發(fā)生饑餓。</p><p>　?。?）非搶占。如果一個(gè)進(jìn)程占有資源并申請(qǐng)另一個(gè)不能立即分配的資源，那么其現(xiàn)已分配的資源都被搶占。通常應(yīng)用于其狀態(tài)可以保存和恢復(fù)的資源，如CPU寄

20、存器和內(nèi)存空間，不能適用于其他資源如打印機(jī)和磁帶驅(qū)動(dòng)器。</p><p><b>　　3 設(shè)計(jì)思路</b></p><p><b>　　3.1設(shè)計(jì)原理</b></p><p>　　我們可以把操作系統(tǒng)看作是銀行家，操作系統(tǒng)管理的資源相當(dāng)于銀行家管理的資金，進(jìn)程向操作系統(tǒng)請(qǐng)求分配資源相當(dāng)于用戶向銀行家貸款。操作系統(tǒng)按照銀行家制

21、定的規(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ù)之和是否超過了該進(jìn)程對(duì)資源的最大需求量。若超過則拒絕分配資源，若沒有超過則再測(cè)試系統(tǒng)現(xiàn)存的資源能否滿足該進(jìn)程尚需的最大資源量，若能滿足則按當(dāng)前的申請(qǐng)量分配資源，否則也要推遲分配。</p>&l

22、t;p><b>　　3.2設(shè)計(jì)目的</b></p><p>　　學(xué)生通過該題目的設(shè)計(jì)過程，掌握銀行家算法實(shí)現(xiàn)的原理、軟件開發(fā)方法。模擬實(shí)現(xiàn)銀行家算法，用銀行家算法實(shí)現(xiàn)資源分配并提高解決實(shí)際問題的能力。</p><p>　　3.3各模塊之間的調(diào)用圖</p><p>　　圖3.1各模塊之間的調(diào)用圖</p><p>&l

23、t;b>　　4詳細(xì)設(shè)計(jì)</b></p><p>　　4.1初始化程序設(shè)計(jì)</p><p>　　由用戶輸入數(shù)據(jù)，分別對(duì)可利用資源向量矩陣AVAILABLE、最大需求矩陣MAX、分配矩陣ALLOCATION、需求矩陣NEED賦值。</p><p>　　程序使用的全局變量：</p><p>　　#define MAXPROCESS

24、 50 /*最大進(jìn)程數(shù)*/ </p><p>　　#define MAXRESOURCE 100 /*最大資源數(shù)*/</p><p>　　int AVAILABLE[MAXRESOURCE]; /*可用資源數(shù)組*/</p><p>　　int MAX[MAX

25、PROCESS][MAXRESOURCE]; /*最大需求矩陣*/</p><p>　　int ALLOCATION[MAXPROCESS][MAXRESOURCE]; /*分配矩陣*/</p><p>　　int NEED[MAXPROCESS][MAXRESOURCE]; /*需求矩陣*/</p><p>　　int REQUEST[MAXP

26、ROCESS][MAXRESOURCE];//進(jìn)程需要資源數(shù)</p><p>　　int SUMMIT[MAXRESOURCE]={0} ; /*各種資源總量*/</p><p>　　int NEEDc[MAXRESOURCE]={0}; /*輔助向量*/</p><p>　　bool FINISH[MAXPROCESS];

27、 /*系統(tǒng)是否有足夠的資源分配*/</p><p>　　int p[MAXPROCESS]; /*記錄序列*/</p><p>　　int m,n; /*m個(gè)進(jìn)程,n個(gè)資源*/</p><p>　　4.2銀行家算法設(shè)計(jì)</p><p>　　在避免死鎖的方法中，所施加的限

28、制條件較弱，有可能獲得令人滿意的系統(tǒng)性能。在該方法中把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，只要能使系統(tǒng)始終都處于安全狀態(tài)，便可以避免發(fā)生死鎖。銀行家算法的基本思想是分配資源之前,判斷系統(tǒng)是否是安全的;若是,才分配。</p><p>　　設(shè)進(jìn)程cusneed提出請(qǐng)求REQUEST [i]，則銀行家算法按如下規(guī)則進(jìn)行判斷。</p><p>　　(1)如果REQUEST [cusneed] [i

29、]<= NEED[cusneed][i]，則轉(zhuǎn)(2)；否則，出錯(cuò)。</p><p>　　(2)如果REQUEST [cusneed] [i]<= AVAILABLE[cusneed][i]，則轉(zhuǎn)(3)；否則，出錯(cuò)。</p><p>　　(3)系統(tǒng)試探分配資源，修改相關(guān)數(shù)據(jù)：</p><p>　　AVAILABLE[i]-=REQUEST[cusneed]

30、[i];</p><p>　　ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];</p><p>　　NEED[cusneed][i]-=REQUEST[cusneed][i];</p><p>　　(4)系統(tǒng)執(zhí)行安全性檢查，如安全，則分配成立；否則試探險(xiǎn)性分配作廢，系統(tǒng)恢復(fù)原狀，進(jìn)程等待。</p><p&g

31、t;　　(5)對(duì)于某一進(jìn)程i，若對(duì)所有的j，有NEED[i][j]=0，則表此進(jìn)程資源分配完畢，應(yīng)將占用資源釋放。</p><p>　　4.3安全性檢查算法</p><p>　　(1)設(shè)置兩個(gè)工作向量Work=AVAILABLE;FINISH</p><p>　　(2)從進(jìn)程集合中找到一個(gè)滿足下述條件的進(jìn)程，</p><p>　　FINISH

32、==false;</p><p>　　NEED<=Work;</p><p>　　如找到，執(zhí)行(3)；否則，執(zhí)行(4)</p><p>　　(3)設(shè)進(jìn)程獲得資源，可順利執(zhí)行，直至完成，從而釋放資源。</p><p>　　Work+=ALLOCATION;</p><p>　　Finish=true;</p&

33、gt;<p><b>　　GOTO 2</b></p><p>　　(4)如所有的進(jìn)程Finish= true，則表示安全；否則系統(tǒng)不安全。</p><p><b>　　4.4流程圖</b></p><p>　　圖4.1程序設(shè)計(jì)流程圖</p><p>　　5運(yùn)行調(diào)試及結(jié)果說明</

34、p><p>　　初始化時(shí)若已分配資源多于最多所需資源則會(huì)報(bào)錯(cuò)，需重新輸入（如圖5.1所示）：</p><p><b>　　圖5.1為輸入報(bào)錯(cuò)</b></p><p>　　初始化后狀態(tài)顯示圖5.2</p><p><b>　　圖5.2為正確輸入</b></p><p>　　資源分配

35、時(shí)請(qǐng)求量超過需求量或現(xiàn)有資源數(shù)同樣會(huì)報(bào)錯(cuò)（如圖5.3）</p><p>　　圖5.3為超出需求量報(bào)錯(cuò)顯示</p><p>　　特殊情況：若申請(qǐng)資源數(shù)既不大于資源需求量，又不大于現(xiàn)有資源數(shù)，但仍有可能導(dǎo)致死鎖，如上圖所示。此時(shí)會(huì)顯示系統(tǒng)不安全，請(qǐng)求被拒絕。</p><p>　　圖5.4為拒絕分配資源</p><p>　　Sum=0，表某一進(jìn)程資

36、源分配完畢，資源釋放（請(qǐng)結(jié)合圖5.4）</p><p>　　圖5.5資源分配完畢資源釋放</p><p><b>　　6總結(jié)</b></p><p>　　本次設(shè)計(jì)中首先要解決的問題是對(duì)所做題目的理解。簡(jiǎn)單的文字描述總是生澀難懂，像銀行家算法這一問題，如果單看題目要求往往不知如何下手，更不要談下一步的設(shè)計(jì)過程。但倘若聯(lián)系實(shí)際生活中銀行貸款這一現(xiàn)象

37、，再來看問題時(shí)，一切開始顯得清晰，再加上老師的指點(diǎn)，便可以把自己究竟該作何工作搞清楚。這也給我一啟示，我們要解決的諸多問題都源自生活，若要解決它，聯(lián)系實(shí)際是個(gè)很不錯(cuò)的選擇。</p><p>　　明白了需求，下一個(gè)難點(diǎn)是如何通過軟件實(shí)現(xiàn)。我所做的銀行家算法這一題目，為了防止死鎖，需要進(jìn)行大量的判斷，這也導(dǎo)致了一個(gè)問題，即在進(jìn)行調(diào)試時(shí)，一旦出現(xiàn)問題，往往難以找到問題所在，針對(duì)這一問題，我編寫了一些監(jiān)測(cè)行（請(qǐng)參看源程序

38、），這樣能比較容易的找到問題的原因所在，這也是此次課程設(shè)計(jì)中在編程方面的一個(gè)收獲。</p><p>　　通過本次課程設(shè)計(jì)，我對(duì)軟件的開發(fā)的過程有了較為深入的了解，雖然只是對(duì)一個(gè)問題的簡(jiǎn)單模擬，但麻雀雖小五臟俱全，我對(duì)相關(guān)問題的解決已經(jīng)有了一定的認(rèn)識(shí)，對(duì)軟件技術(shù)這門課程也有了更為透徹的感悟。本次課程設(shè)計(jì)，鍛煉了我分析問題和解決問題的能力，為今后相關(guān)問題的解決積累了寶貴經(jīng)驗(yàn)，也增強(qiáng)了自己的耐心與自信，受益匪淺。<

39、;/p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1] 嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語言版).清華大學(xué)出版社.1999年 </p><p>　　[2] 湯小丹,梁紅兵,哲鳳屏,湯子嬴.計(jì)算機(jī)操作系統(tǒng)（第三版）.西安電子科技大學(xué)出版社；</p><p>　　[3] 湯子瀛,哲鳳屏.計(jì)算機(jī)操作系統(tǒng)[M].西安：

40、西安電子科技大學(xué)學(xué)出版社.1996年</p><p>　　[4] 王萬森.計(jì)算機(jī)操作系統(tǒng)原理[M].北京：高等教育出版社.2001年</p><p>　　[5] 周長林，左萬歷.計(jì)算機(jī)操作系統(tǒng)教程[M].北京：高等教育出版社.1994年</p><p>　　[6] 黃廷輝，王宇英.計(jì)算機(jī)操作系統(tǒng)實(shí)踐教程[M].北京：清華大學(xué)出版社. 2007年5月</p>

41、;<p>　　[7] 殷兆麟.計(jì)算機(jī)操作系統(tǒng)[M].北京：清華大學(xué)出版社.2007年3月</p><p>　　[8] 張堯?qū)W,史美林，張高.計(jì)算機(jī)操作系統(tǒng)教程[M].北京：清華大學(xué)出版社.1993年</p><p><b>　　致 謝</b></p><p>　　在這次操作系統(tǒng)銀行家算法實(shí)現(xiàn)程序設(shè)計(jì)中，我得到了馬生菊老師的認(rèn)真指

42、導(dǎo)和幫助，同時(shí)也感謝我的隊(duì)友劉城輝同學(xué)，因?yàn)樗盘岣吡宋以O(shè)計(jì)進(jìn)度和效率。我和劉城輝同學(xué)共同完成這次課程設(shè)計(jì)，在程序設(shè)計(jì)過程中難免會(huì)遇到各種問題，謝謝馬老師的耐心指導(dǎo)，謝謝同伴的包容，在這次課程設(shè)計(jì)中我感覺我有了很大的提高，我相信自己以后會(huì)做得更好。</p><p>　　通過本次設(shè)計(jì)，我的知識(shí)領(lǐng)域得到了進(jìn)一步擴(kuò)展，專業(yè)技能進(jìn)一步提高，同時(shí)增強(qiáng)了分析和解決實(shí)際問題的綜合能力。首先，我們要感謝學(xué)校給我們提供了此次課程設(shè)

43、計(jì)的機(jī)會(huì)，能讓我們?cè)谝黄饘W(xué)習(xí)與研究，讓我們有機(jī)會(huì)對(duì)所學(xué)的理論知識(shí)進(jìn)行實(shí)踐。</p><p>　　最后，在我設(shè)計(jì)完成后對(duì)程序的測(cè)試，并在同學(xué)與隊(duì)友的幫助下才得以完成沒有他們，也許就難以發(fā)現(xiàn)一些潛在的錯(cuò)誤，在此一并表示感謝。</p><p><b>　　附錄（源程序）：</b></p><p>　　#include <iostream>

44、</p><p>　　#include <windows.h> </p><p>　　#include <time.h> </p><p>　　using namespace std;</p><p>　　#define MAXPROCESS 50 /*最大進(jìn)程數(shù)*/ &

45、lt;/p><p>　　#define MAXRESOURCE 100 /*最大資源數(shù)*/</p><p>　　int AVAILABLE[MAXRESOURCE]; /*可用資源數(shù)組*/</p><p>　　int MAX[MAXPROCESS][MAXRESOURCE];

46、/*最大需求矩陣*/</p><p>　　int ALLOCATION[MAXPROCESS][MAXRESOURCE]; /*分配矩陣*/</p><p>　　int NEED[MAXPROCESS][MAXRESOURCE]; /*需求矩陣*/</p><p>　　int REQUEST[MAXPROCESS][MAXRESOURCE

47、]; /*進(jìn)程需要資源數(shù)*/</p><p>　　int SUMMIT[MAXRESOURCE]={0} ; /*各種資源總量*/</p><p>　　int NEEDc[MAXRESOURCE]={0}; /*輔助向量*/</p><p>　　bool FINISH[MAXPROCESS];

48、 /*系統(tǒng)是否有足夠的資源分配*/</p><p>　　int p[MAXPROCESS]; /*記錄序列*/</p><p>　　int m,n; /*m個(gè)進(jìn)程,n個(gè)資源*/</p><p>　　void Init();&l

49、t;/p><p>　　bool Safe();</p><p>　　void Bank();</p><p>　　void main()</p><p><b>　　{ </b></p><p>　　system("color 01f"); //設(shè)置當(dāng)前窗口的背景色和前景色 0

50、= 黑色 8 = 灰色 </p><p><b>　　Init();</b></p><p><b>　　Safe();</b></p><p><b>　　Bank();</b></p><p><b>　　}</b></p><p&

51、gt;　　void Init() /*初始化算法*/</p><p><b>　　{int i,j;</b></p><p>　　cout<<" "<<endl;</p><p>　　cout<<"

52、 銀行家算法模擬"<<endl;</p><p>　　cout<<" ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"<<endl;</p><p>　　cout<<"

53、 "<<endl;</p><p>　　cout<<" ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"<<endl;</p>

54、<p>　　cout<<" "<<endl;</p><p>　　cout<<" 算法簡(jiǎn)介："<<endl;</p><p>　　cout<<" 在避免死鎖的方法中，所施加的限制條件較弱，有可能獲得令人滿意"<<e

55、ndl;</p><p>　　cout<<" 的系統(tǒng)性能。在該方法中把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，只要"<<endl;</p><p>　　cout<<" 能使系統(tǒng)始終都處于安全狀態(tài)，便可以避免發(fā)生死鎖"<<endl;</p><p>　　cout&l

56、t;<" 銀行家算法的基本思想是分配資源之前,判斷系統(tǒng)是否是安全的;若是"<<endl;</p><p>　　cout<<" ,才分配。它是最具有代表性的避免死鎖的算法。"<<endl;</p><p>　　cout<<" "<<e

57、ndl;</p><p>　　cout<<" ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"<<endl;</p><p>　　cout<<" ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

58、~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"<<endl;</p><p>　　cout<<" "<<endl;</p><p>　　cout<<" 請(qǐng)稍候...6秒后跳入主界面" <<endl;</p&g

59、t;<p>　　Sleep(6000); </p><p>　　system("cls"); </p><p>　　cout<<" "<<endl;</p><p>　　cout <<" 運(yùn)行界面&

60、quot;<<endl; </p><p>　　cout<<">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

61、>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>"<<endl;</p><p>　　cout<<"

62、請(qǐng)輸入進(jìn)程的數(shù)目:"<<endl;</p><p><b>　　cin>>m;</b></p><p>　　cout<<"請(qǐng)輸入資源的種類:"<<endl;</p><p><b>　　cin>>n;</b></p>&

63、lt;p>　　cout<<"請(qǐng)輸入每個(gè)進(jìn)程最多所需的各資源數(shù),按照"<<m<<"x"<<n<<"矩陣輸入"<<endl;</p><p>　　for(i=0;i<m;i++)</p><p>　　for(j=0;j<n;j++)</p&

64、gt;<p>　　cin>>MAX[i][j];</p><p>　　cout<<"請(qǐng)輸入每個(gè)進(jìn)程已分配的各資源數(shù),也按照"<<m<<"x"<<n<<"矩陣輸入"<<endl;</p><p>　　for(i=0;i<m;i++

65、)</p><p><b>　　{</b></p><p>　　for(j=0;j<n;j++)</p><p><b>　　{</b></p><p>　　cin>>ALLOCATION[i][j];</p><p>　　NEED[i][j]=MAX[i]

66、[j]-ALLOCATION[i][j];</p><p>　　if(NEED[i][j]<0)</p><p><b>　　{</b></p><p>　　cout<<"您輸入的第"<<i+1<<"個(gè)進(jìn)程所擁有的第"<<j+1<<&quo

67、t;個(gè)資源數(shù)錯(cuò)誤,請(qǐng)重新輸入:"<<endl;</p><p><b>　　j--;</b></p><p><b>　　continue;</b></p><p><b>　　}</b></p><p><b>　　}</b><

68、;/p><p><b>　　}</b></p><p>　　for(j=0;j<n;j++) //已分配各資源總數(shù)</p><p><b>　　{</b></p><p>　　for(i=0;i<m;i++)</p><p>　　NEEDc[j]

69、=ALLOCATION[i][j]+NEEDc[j];</p><p><b>　　}</b></p><p>　　cout<<"請(qǐng)輸入各個(gè)資源現(xiàn)有的數(shù)目:"<<endl;</p><p>　　for(i=0;i<n;i++)</p><p><b>　　{&l

70、t;/b></p><p>　　cin>>AVAILABLE[i];</p><p><b>　　}</b></p><p>　　for(i=0;i<n;i++) //總資源數(shù)</p><p><b>　　{</b></p><p&g

71、t;　　SUMMIT[i]=AVAILABLE[i]+ NEEDc[i];</p><p><b>　　}</b></p><p>　　cout<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"<<endl;

72、</p><p>　　cout<<"初始化后狀態(tài)顯示:"<<endl;</p><p>　　cout<<"每個(gè)進(jìn)程最多所需的各資源數(shù)"<<endl;</p><p>　　for(i=0;i<m;i++)</p><p>　　{for(j=0;j<

73、;n;j++)</p><p>　　cout<<""<<MAX[i][j]<<" ";</p><p><b>　　if(j=n-1)</b></p><p>　　cout<<" "<<endl;</p>&

74、lt;p><b>　　}</b></p><p>　　cout<<"每個(gè)進(jìn)程已分配的各資源數(shù)"<<endl;</p><p>　　for(i=0;i<m;i++)</p><p>　　{for(j=0;j<n;j++)</p><p>　　cout<&l

75、t;""<<ALLOCATION[i][j]<<" ";</p><p><b>　　if(j=n-1)</b></p><p>　　cout<<" "<<endl;</p><p><b>　　}</b><

76、;/p><p>　　cout<<"各個(gè)資源現(xiàn)有的數(shù)目:"<<endl;</p><p>　　for(i=0;i<n;i++)</p><p>　　cout<<""<<AVAILABLE[i]<<" ";</p><p>

77、;　　cout<<" "<<endl;</p><p>　　cout<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"<<endl;</p><p><b>　　}</b

78、></p><p>　　void Bank() /*銀行家算法*/</p><p><b>　　{</b></p><p>　　int i,j,cusneed;</p><p>　　char again;</p><p>　　int sum=0;

79、 /*監(jiān)測(cè)某一進(jìn)程資源是否分配完畢*/</p><p>　　int add=0;</p><p><b>　　while(1)</b></p><p><b>　　{</b></p><p>　　cout<<"請(qǐng)輸入要申請(qǐng)資源的進(jìn)程號(hào)(注:第1個(gè)進(jìn)程號(hào)為0,依次類推)&q

80、uot;<<endl;</p><p>　　cin>>cusneed;</p><p>　　cout<<"請(qǐng)輸入進(jìn)程所請(qǐng)求的各資源的數(shù)量"<<endl;</p><p>　　for(i=0;i<n;i++)</p><p><b>　　{</b>&

81、lt;/p><p>　　cin>>REQUEST[cusneed][i];</p><p>　　if(REQUEST[cusneed][i]>NEED[cusneed][i])</p><p><b>　　{</b></p><p>　　cout<<"您輸入的本個(gè)請(qǐng)求數(shù)超過進(jìn)程的需求量

82、!請(qǐng)重新輸入!"<<endl;</p><p><b>　　i--;</b></p><p><b>　　continue;</b></p><p><b>　　}</b></p><p>　　if(REQUEST[cusneed][i]>AVAIL

83、ABLE[i])</p><p><b>　　{</b></p><p>　　cout<<"您輸入的本個(gè)請(qǐng)求數(shù)超過系統(tǒng)有的資源數(shù)!請(qǐng)重新輸入!"<<endl;</p><p><b>　　i--;</b></p><p><b>　　contin

84、ue;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　for(i=0;i<n;i++) //資源分配</p><p><b>　　{</b></p>

85、<p>　　AVAILABLE[i]-=REQUEST[cusneed][i];</p><p>　　ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];</p><p>　　NEED[cusneed][i]-=REQUEST[cusneed][i];</p><p><b>　　}</b><

86、/p><p>　　if(Safe())</p><p><b>　　{</b></p><p>　　cout<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"<<endl;</p&g

87、t;<p>　　cout<<"同意分配請(qǐng)求!"<<endl;</p><p>　　cout<<"此次分配后狀態(tài)顯示:"<<endl;</p><p>　　cout<<"當(dāng)前每個(gè)進(jìn)程最多尚需的各資源數(shù)"<<endl;</p><

88、p>　　for(i=0;i<m;i++)</p><p>　　{for(j=0;j<n;j++)</p><p>　　cout<<""<<NEED[i][j]<<" ";</p><p><b>　　if(j=n-1)</b></p>

89、<p>　　cout<<" "<<endl;</p><p><b>　　}</b></p><p>　　cout<<"當(dāng)前每個(gè)進(jìn)程已分配過的各資源數(shù)"<<endl;</p><p>　　for(i=0;i<m;i++)</p>

90、<p>　　{for(j=0;j<n;j++)</p><p>　　cout<<""<<ALLOCATION[i][j]<<" ";</p><p><b>　　if(j=n-1)</b></p><p>　　cout<<"

91、 "<<endl;</p><p><b>　　}</b></p><p>　　for(i=0;i<m;i++)</p><p>　　for(j=0;j<n;j++)</p><p>　　add=NEED[i][j]+add; //是否已分配完畢</p><p&

92、gt;　　if(add!=0)</p><p><b>　　{</b></p><p>　　for(i=0;i<n;i++) </p><p>　　sum=NEED[cusneed][i]+sum;</p><p>　　cout<<"sum值:"<<sum<<

93、;""<<endl;</p><p>　　cout<<" "<<endl;</p><p>　　if (sum==0)</p><p>　　{ for(i=0;i<n;i++)</p><p>　　AVAILABLE[i]= ALLOCATION[cusneed

94、][i]+AVAILABLE[i];</p><p><b>　　}</b></p><p><b>　　sum=0;</b></p><p>　　cout<<"各個(gè)資源現(xiàn)有的數(shù)目:"<<endl;</p><p>　　for(i=0;i<n;i++

95、)</p><p>　　cout<<""<<AVAILABLE[i]<<" ";</p><p>　　cout<<" "<<endl;</p><p><b>　　add=0; </b></p><p&

96、gt;<b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　cout<<"各個(gè)資源現(xiàn)有的數(shù)目:"<<endl;</p><p>　　for(i=0;i<

97、;n;i++)</p><p>　　cout<<""<<SUMMIT[i]<<" ";</p><p>　　cout<<" "<<endl;</p><p><b>　　}</b></p><p>

98、　　cout<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"<<endl;</p><p><b>　　}</b></p><p><b>　　else</b></p>

99、<p><b>　　{</b></p><p>　　cout<<"您的請(qǐng)求被拒絕!"<<endl; //撤消資源分配</p><p>　　for(i=0;i<n;i++)</p><p><b>　　{</b></p><p>　　AVA

100、ILABLE[i]+=REQUEST[cusneed][i];</p><p>　　ALLOCATION[cusneed][i]-=REQUEST[cusneed][i];</p><p>　　NEED[cusneed][i]+=REQUEST[cusneed][i];</p><p><b>　　}</b></p><p&

101、gt;<b>　　}</b></p><p>　　for(i=0;i<m;i++)</p><p><b>　　{</b></p><p>　　FINISH[i]=false;</p><p><b>　　}</b></p><p>　　cout&

102、lt;<"您還想再次請(qǐng)求分配嗎?是請(qǐng)按y/Y,否請(qǐng)按其它鍵"<<endl;</p><p>　　cin>>again;</p><p>　　if(again=='y'||again=='Y')</p><p><b>　　{</b></p><

103、p><b>　　continue;</b></p><p><b>　　}</b></p><p>　　break; //跳出while</p><p>　　} </p><p><b>　　}<

104、/b></p><p>　　bool Safe() /*安全性算法*/</p><p><b>　　{</b></p><p>　　int i,j,k,l=0;</p><p>　　int Work[MAXRESOURCE];

105、 /*工作數(shù)組*/</p><p>　　for(i=0;i<n;i++)</p><p>　　Work[i]=AVAILABLE[i];</p><p>　　for(i=0;i<m;i++)</p><p><b>　　{</b></p><p>　　FINISH[i

106、]=false;</p><p><b>　　}</b></p><p>　　for(i=0;i<m;i++)</p><p><b>　　{ </b></p><p>　　if(FINISH[i]==true)</p><p><b>　　{</

107、b></p><p><b>　　continue;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　for(j=0;j

108、<n;j++)</p><p><b>　　{</b></p><p>　　if(NEED[i][j]>Work[j])</p><p><b>　　{</b></p><p><b>　　break;</b></p><p><b&g

109、t;　　}</b></p><p><b>　　}</b></p><p><b>　　if(j==n)</b></p><p><b>　　{ </b></p><p>　　FINISH[i]=true; //FINISH在此被賦值,表進(jìn)程i可順利進(jìn)行&l

110、t;/p><p>　　for(k=0;k<n;k++) //并假設(shè)已執(zhí)行完成</p><p><b>　　{</b></p><p>　　Work[k]+=ALLOCATION[i][k];</p><p><b>　　}</b></p><p><b>　

111、　p[l++]=i;</b></p><p>　　i=-1; //再從i=0開始判斷</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><

112、;p>　　continue; </p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　if(l==m) //所有進(jìn)程都可完成</p><p><b>　　{</b></p>&l

113、t;p>　　cout<<"系統(tǒng)是安全的"<<endl;</p><p>　　cout<<"安全序列:"<<endl;</p><p>　　for(i=0;i<l;i++)</p><p><b>　　{</b></p><p&

114、gt;　　cout<<p[i];</p><p>　　if(i!=l-1) //最后一項(xiàng)不輸--></p><p><b>　　{</b></p><p>　　cout<<"-->";</p><p><b>　　}</b></p&

115、gt;<p><b>　　}</b></p><p>　　cout<<""<<endl;</p><p>　　return true;</p><p><b>　　}</b></p><p><b>　　}</b><