操作系統(tǒng)課程設(shè)計(jì)--銀行家算法

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

2、個(gè)模塊的算法思想通過(guò)流程圖表示，分塊編寫(xiě)代碼，并進(jìn)行測(cè)試，最后進(jìn)行程序的測(cè)試，在設(shè)計(jì)思路上嚴(yán)格按照軟件工程的思想執(zhí)行，確保了設(shè)計(jì)和實(shí)現(xiàn)的可行，可信。代碼實(shí)現(xiàn)采用C語(yǔ)言。 </p><p>　　關(guān)鍵詞：銀行家算法；死鎖；避免死鎖；安全性序列</p><p><b>　　abstract</b></p><p>　　The banker Dij

3、kstra algorithm is the most representative of avoid deadlock algorithm, this algorithm can be used in the banking system due to cash the release of the loan and its name. Bankers algorithm is to ensure the safety in the

4、current system under the premise of the advance. To process request to safety inspection to determine resource allocation or not, so as to ensure the security of the system, effective avoid deadlocks occur.</p>&l

5、t;p>　　The paper in the understanding and analysis of the banker algorithm is the core idea of the state and the essence of the meaning on the premise of the realization of the algorithm in the overall design, includin

6、g in the algorithm points module design, and each module algorithm thought through the flow chart, said block coding, and testing, the program testing, in the design idea in strict accordance with the concept of software

7、 engineering implementation, to ensure that the design and implementa</p><p>　　Keywords: bankers algorithm; Deadlock; Avoid deadlock; Safety sequence</p><p>　　前言:20世紀(jì)末，隨著計(jì)算機(jī)科學(xué)的發(fā)展，C語(yǔ)言的應(yīng)用越來(lái)越廣泛，很多程

8、序都需要使用C語(yǔ)言 來(lái)編寫(xiě)。C語(yǔ)言使用方便快捷，它已經(jīng)成為計(jì)算機(jī)編程中不可缺少的一部分，而且它也被用于各個(gè)方面。例如：政府部門(mén)，銀行，學(xué)校等等。</p><p>　　銀行家算法是判斷系統(tǒng)是否安全，并且允許其它進(jìn)程來(lái)申請(qǐng)這里的資源，任何一個(gè)進(jìn)程來(lái)申請(qǐng)資源時(shí)，必須先登記該進(jìn)程對(duì)資源的申請(qǐng)要求然后由系統(tǒng)檢查當(dāng)前資源的狀況，并用銀行家算法和安全性算法來(lái)檢查是否允許分配資源給進(jìn)程。通過(guò)課程設(shè)計(jì)，加深我們對(duì)利用銀行家算法避免

9、死鎖的理解。在設(shè)計(jì)中主要的難點(diǎn)是用語(yǔ)言編寫(xiě)銀行家算法和安全性算法，使系統(tǒng)資源分配能安全進(jìn)行，避免系統(tǒng)死鎖。</p><p><b>　　緒論</b></p><p>　　1 進(jìn)程并發(fā)控制的必要性</p><p>　　控制工作流程，管理資源，為用戶(hù)服務(wù)，是操作系統(tǒng)的主要功能。在資源管理中，操作系統(tǒng)的任務(wù)是使各種系統(tǒng)資源得到充分合理的應(yīng)用，解決用戶(hù)

10、作業(yè)因?yàn)橘Y源而產(chǎn)生的矛盾，并合理地讓用戶(hù)在合適的時(shí)間內(nèi)得到其應(yīng)有的服務(wù)。</p><p>　　現(xiàn)代操作系統(tǒng)引入了多道程序設(shè)計(jì)技術(shù)，允許多個(gè)進(jìn)程同時(shí)駐留內(nèi)存并發(fā)執(zhí)行。若干個(gè)進(jìn)程將不可避免地會(huì)競(jìng)爭(zhēng)系統(tǒng)資源，如果操作系統(tǒng)不能協(xié)調(diào)多個(gè)進(jìn)程對(duì)系統(tǒng)資源的競(jìng)爭(zhēng)和共享，將會(huì)導(dǎo)致執(zhí)行結(jié)果異常，系統(tǒng)不穩(wěn)定、失效等多種問(wèn)題，因此操作系統(tǒng)提供了多種機(jī)制實(shí)現(xiàn)對(duì)進(jìn)程的并發(fā)控制。</p><p><b>　　

11、2進(jìn)程死鎖的定義</b></p><p>　　操作系統(tǒng)利用了包括軟件方法、硬件方法、信號(hào)量方法、管程方法以及消息傳遞方法等機(jī)制實(shí)現(xiàn)了對(duì)若干進(jìn)程的同步與互斥的控制，但是要確保進(jìn)程之間能夠正常通信、合理分配系統(tǒng)資源、提高系統(tǒng)的運(yùn)行效率還需要解決進(jìn)程的死鎖問(wèn)題。</p><p>　　死鎖可以描述為，當(dāng)多個(gè)進(jìn)程在執(zhí)行過(guò)程中，因?yàn)楦?jìng)爭(zhēng)資源或執(zhí)行時(shí)推進(jìn)的順序不當(dāng)而造成的一種相互阻塞的現(xiàn)象，

12、若無(wú)外力作用，它們都將無(wú)法推進(jìn)下去。</p><p><b>　　3產(chǎn)生死鎖的原因</b></p><p>　　一、競(jìng)爭(zhēng)資源引起進(jìn)程死鎖</p><p>　　當(dāng)系統(tǒng)中供多個(gè)進(jìn)程共享的資源如打印機(jī)、公用隊(duì)列的等，其數(shù)目不足以滿足諸進(jìn)程的需要時(shí)，會(huì)引起諸進(jìn)程對(duì)資源的競(jìng)爭(zhēng)而產(chǎn)生死鎖。</p><p>　　二、進(jìn)程推進(jìn)順序不當(dāng)引

13、起死鎖</p><p>　　由于進(jìn)程在運(yùn)行中具有異步性特征，這可能使P1和P2兩個(gè)進(jìn)程按下述兩種順序向前推進(jìn)。 </p><p>　　4死鎖產(chǎn)生的必要條件</p><p>　　雖然進(jìn)程在運(yùn)行過(guò)程中，可能發(fā)生死鎖，但死鎖的發(fā)生也必須具備一定的條件，死鎖的發(fā)生必須具備以下四個(gè)必要條件。 </p><p>　?。?）互斥條件　?。?）占有且等待　　

14、（3）非剝奪</p><p>　?。?）循環(huán)等待如圖2-1.</p><p>　　互斥，占有且等待，非剝奪這三個(gè)條件是死鎖產(chǎn)生的必要條件，但不是充分條件?；コ鈼l件是臨界資源固有的屬性，保證進(jìn)程胡此訪問(wèn)臨界資源是必要的，不能因?yàn)榛コ鈺?huì)導(dǎo)致死鎖而禁止互斥。循環(huán)等待是前3個(gè)條件可能產(chǎn)生的結(jié)果，只有存在互斥，占有且等待與非剝奪三個(gè)條件時(shí)，才可能出現(xiàn)循環(huán)等待。只要系統(tǒng)出現(xiàn)了循環(huán)等待，則一定出現(xiàn)死鎖。

15、</p><p><b>　　5 解決死鎖的方法</b></p><p>　　解決死鎖的方法可以按解決死鎖的時(shí)機(jī)分為四類(lèi)：</p><p><b>　?。?) 預(yù)防死鎖。</b></p><p><b>　?。?) 避免死鎖。</b></p><p>&

16、lt;b>　?。?)檢測(cè)死鎖。 </b></p><p><b>　?。?)解除死鎖。 </b></p><p><b>　　需求分析</b></p><p><b>　　1 問(wèn)題描述</b></p><p>　　運(yùn)用銀行家算法，避免死鎖的發(fā)生。在確保當(dāng)前系統(tǒng)

17、安全的前提下推進(jìn)的。對(duì)進(jìn)程請(qǐng)求先進(jìn)行安全性檢查，來(lái)決定資源分配與否，從而確保系統(tǒng)的安全，有效的避免了死鎖的發(fā)生。</p><p>　　問(wèn)題的關(guān)鍵在于安全性算法，即找安全性序列。</p><p><b>　　2功能需求</b></p><p>　　1.添加進(jìn)程的可用資源，最大資源，已分配資源；</p><p>　　2.判斷

18、系統(tǒng)是否安全；</p><p><b>　　3.申請(qǐng)資源；</b></p><p>　　4.申請(qǐng)資源后如何分配；</p><p><b>　　5.進(jìn)行安全檢查。</b></p><p><b>　　3數(shù)據(jù)需求</b></p><p>　　主要數(shù)據(jù)包括：可

19、用資源，最大資源，已分配資源，申請(qǐng)資源數(shù)</p><p><b>　　4基本要求</b></p><p>　?。?）從鍵盤(pán)輸入當(dāng)前系統(tǒng)的資源信息，包括當(dāng)前可用資源，每個(gè)進(jìn)程對(duì)各類(lèi)資源的最大需求量，每個(gè)進(jìn)程當(dāng)前已分配的各個(gè)資源量和每個(gè)進(jìn)程尚需要的各個(gè)資源量，輸出結(jié)果顯示在DOS界面上；</p><p>　?。?）輸入進(jìn)程請(qǐng)求，按照設(shè)計(jì)好的安全性算

20、法進(jìn)行檢查，得到結(jié)果并輸出整個(gè)執(zhí)行過(guò)程的相關(guān)信息和最終結(jié)果（主要包括資源分配表和安全序列）</p><p>　?。?）要求要有各種異常的處理，程序的可控制性和可連續(xù)性執(zhí)行。包括對(duì)進(jìn)程的存在有無(wú)檢查，請(qǐng)求向量的不合法檢查，試分配失敗后的數(shù)據(jù)恢復(fù)和重新接受進(jìn)程請(qǐng)求等。</p><p><b>　　5數(shù)據(jù)流模型</b></p><p><b&g

21、t;　　概要設(shè)計(jì)</b></p><p><b>　　1算法思路：</b></p><p>　　先對(duì)用戶(hù)提出的請(qǐng)求進(jìn)行合法性檢查，即檢查請(qǐng)求是否大于需要的，是否大于可利用的。若請(qǐng)求合法，則進(jìn)行預(yù)分配，對(duì)分配后的狀態(tài)調(diào)用安全性算法進(jìn)行檢查。若安全，則分配；若不安全，則拒絕申請(qǐng)，恢復(fù)到原來(lái)的狀態(tài)，拒絕申請(qǐng)。</p><p><b&

22、gt;　　2總體設(shè)計(jì)</b></p><p><b>　　總體功能模塊圖如下</b></p><p><b>　　3模塊的劃分</b></p><p>　　由于該算法規(guī)模較小，所以選用結(jié)構(gòu)化的設(shè)計(jì)方法，將該系統(tǒng)劃為五塊，分別是：</p><p>　　(1)主模塊，處在整個(gè)系統(tǒng)的最高層，負(fù)

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

24、;b>　　4模塊調(diào)用關(guān)系</b></p><p>　　各模塊之間的調(diào)用如下圖示：</p><p><b>　　5 流程圖</b></p><p><b>　　1：主函數(shù)流程圖：</b></p><p><b>　　2：初始化流程</b></p>

25、<p>　　3：安全性檢測(cè)流程圖</p><p>　　4:銀行家算法流程圖</p><p><b>　　詳細(xì)設(shè)計(jì)</b></p><p><b>　　1.算法的數(shù)據(jù)結(jié)構(gòu)</b></p><p>　　可利用資源向量Available</p><p>　　是個(gè)含有m個(gè)元

26、素的數(shù)組，其中的每一個(gè)元素代表一類(lèi)可利用的資源數(shù)目。如果Available[j]=K，則表示系統(tǒng)中現(xiàn)有Rj類(lèi)資源K個(gè)。　　</p><p>　　最大需求矩陣Max　　</p><p>　　這是一個(gè)n×m的矩陣，它定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì)m類(lèi)資源的最大需求。如果Max[i,j]=K，則表示進(jìn)程i需要Rj類(lèi)資源的最大數(shù)目為K?！　?lt;/p><p>

27、　　分配矩陣Allocation　　</p><p>　　這也是一個(gè)n×m的矩陣，它定義了系統(tǒng)中每一類(lèi)資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果Allocation[i,j]=K，則表示進(jìn)程i當(dāng)前已分得Rj類(lèi)資源的 數(shù)目為K?！　?lt;/p><p>　　需求矩陣Need?！　?lt;/p><p>　　這也是一個(gè)n×m的矩陣，用以表示每一個(gè)進(jìn)程尚需的各類(lèi)資源

28、數(shù)。如果Need[i,j]=K，則表示進(jìn)程i還需要Rj類(lèi)資源K個(gè)，方能完成其任務(wù)。</p><p><b>　　2.算法的實(shí)現(xiàn)</b></p><p><b>　　1）初始化</b></p><p>　　即是初始化Max，Allocation，Available，Need這四個(gè)數(shù)組。其中Max，Allocation，Ava

29、ilable這三個(gè)數(shù)組在程序開(kāi)始前是已知的，Need數(shù)組是根據(jù)Max和Allocation計(jì)算出來(lái)的。</p><p><b>　　2）銀行家算法</b></p><p>　　在避免死鎖的方法中，所施加的限制條件較弱，有可能獲得令人滿意的系統(tǒng)性能。在該方法中把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，只要能使系統(tǒng)始終都處于安全狀態(tài)，便可以避免發(fā)生死鎖 。</p>

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

31、 Avalable[i]-Request[i];　</p><p>　　Allocation[REQUEST][i]= Allocation[REQUEST][i]+Request[i];</p><p>　　Need[REQUEST][i]= Need[REQUEST][i]-Request[i];</p><p>　?。?)系統(tǒng)利用安全性算法，檢查此次資源分配以

32、后，系統(tǒng)是否處于安全狀態(tài)。若安全，才將資源分配給是進(jìn)程Pi,完成此次分配；否則，試探分配是小，回復(fù)原來(lái)的資源分配狀態(tài)，讓進(jìn)程Pi等待。</p><p><b>　　3）安全性檢查算法</b></p><p>　　(1)設(shè)置兩個(gè)工作向量：</p><p>　　Finish[FACT_PROGRESS]：若Finish[n]=true,則表示該進(jìn)程

33、已經(jīng)申請(qǐng)到了資源得到執(zhí)行。當(dāng)該進(jìn)程執(zhí)行完畢后，釋放資源。FACT_PROGRESS代表實(shí)際進(jìn)程集合的數(shù)量?！inish數(shù)組初始化時(shí)，全部元素置為false。</p><p>　　Work[FACT_SOURCE]：初始化為Available，表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行的資源集合。FACT_SOURCE是一個(gè)全局變量，表示實(shí)際的資源種類(lèi)。</p><p>　　從進(jìn)程集合中找到一個(gè)滿足下述

34、條件的進(jìn)程：</p><p>　　Finish[i]==false并且Need[i][]<=Work[];如找到，則執(zhí)行(3)；否則，執(zhí)行(4)。</p><p>　　這是系統(tǒng)找到了一個(gè)滿足條件的進(jìn)程，并讓該進(jìn)程得資源，可順利執(zhí)行，直至完成，從而釋放所有的資源，執(zhí)行以下操作：</p><p>　　Work[]= Work[]+Allocation[i][];&

35、lt;/p><p>　　Need[i][]=0;</p><p>　　Available[i][]=Available[i][]+Allocation[i][];</p><p>　　Allocation[i][]=0;</p><p>　　Finish=true;　　</p><p>　　然后返回（2）找到符合條件的進(jìn)程

36、并執(zhí)行相關(guān)操作，直到?jīng)]有找到符合條件的進(jìn)程為止?！?lt;/p><p>　　如所有的進(jìn)程Finish[]= true，則申請(qǐng)的資源分配可以使所有的進(jìn)程都順利執(zhí)行，表示系統(tǒng)處于安全狀態(tài)；若Finish[]數(shù)組不全為true，則表示申請(qǐng)資源的進(jìn)程所申請(qǐng)的資源分配不能是系統(tǒng)中所有的進(jìn)程都順利得到資源并執(zhí)行，系統(tǒng)不安全狀態(tài)</p><p><b>　　源代碼</b></p&

37、gt;<p><b>　　//銀行家算法</b></p><p>　　#include<stdio.h></p><p>　　#include<stdlib.h></p><p>　　#include<string.h></p><p>　　#define M 3 //

38、系統(tǒng)資源的種類(lèi)</p><p>　　#define N 10 // 進(jìn)程上限</p><p>　　#define D12 %5d%5d%5d%5d%5d%5d%5d%5d%5d%5d%5d%5d //輸入輸出格式定義</p><p>　　typedef struct my_process</p><p><b>　　{</b

39、></p><p>　　int num; //進(jìn)程標(biāo)號(hào)</p><p>　　int Max[M];// 表示某個(gè)進(jìn)程對(duì)某類(lèi)資源的最大需求</p><p>　　int Allocation[M];// 表示某個(gè)進(jìn)程已分配到某類(lèi)資源的個(gè)數(shù)</p><p>　　int Need[M];// 表示某個(gè)進(jìn)程尚需要

40、某類(lèi)資源的個(gè)數(shù)</p><p>　　struct my_process* next;</p><p><b>　　}process;</b></p><p>　　void Insret_Tail(process **head,process node) //尾插法建立進(jìn)程鏈表</p><p><b>　　

41、{</b></p><p>　　process* p=(process*)malloc(sizeof(process));</p><p>　　process* last=NULL;</p><p>　　memcpy(p,&node,sizeof(process)); //動(dòng)態(tài)創(chuàng)建進(jìn)程結(jié)點(diǎn)</p><p>　　p-

42、>next=NULL;</p><p>　　if(NULL==*head)</p><p><b>　　{</b></p><p><b>　　*head=p;</b></p><p><b>　　}</b></p><p>　　else

43、 //找表尾</p><p><b>　　{</b></p><p>　　last=*head;</p><p>　　while(last->next!=NULL)</p><p><b>　　{</b></p><p>　　last=last->next;<

44、;/p><p><b>　　}</b></p><p>　　last->next=p;//插入鏈尾</p><p>　　}</p><p><b>　　}</b></p><p>　　void Init_process(process *

45、*head,int m,int* count)//初始化系統(tǒng)資源</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)從0開(kāi)始，輸入-1 結(jié)束輸入:\n");

46、</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>　　print

47、f("最大需求矩陣: ");</p><p>　　scanf("%d",&node.Max[0]);</p><p>　　if(node.Max[0]!=-1) //輸入-1 結(jié)束輸入</p><p><b>　　{</b></p><p>　　fo

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

49、p><p>　　for(i=0;i<m;i++)</p><p><b>　　{</b></p><p>　　scanf("%d",&node.Allocation[i]);</p><p><b>　　}</b></p><p>　　print

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

51、gt;<p>　　Insret_Tail(head,node);//插入鏈尾</p><p>　　(*count)++;//進(jìn)程數(shù)加1</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{&

52、lt;/b></p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　while(1);</b></p><p><b

53、>　　}</b></p><p>　　void Print(process *head,int *avail,int m)//打印初識(shí)系統(tǒng)資源</p><p><b>　　{</b></p><p>　　process* p=NULL;</p><p><b>　　int i,j;<

54、/b></p><p><b>　　char ch;</b></p><p><b>　　p=head;</b></p><p>　　if(NULL==p)</p><p><b>　　{</b></p><p>　　printf(&

55、quot;當(dāng)前無(wú)進(jìn)程 !\n"); </p><p><b>　　exit(0);</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p&g

56、t;<p>　　printf("| Process | Max | |Allocation| | Need | |Available|\n\n");</p><p>　　printf("\t");</p><p>　　for(i=0;i<4;i++)</p><p>&

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

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

59、NULL)</p><p><b>　　{</b></p><p>　　printf("%8.2d",p->num);</p><p>　　for(j=0;j<m;j++)</p><p><b>　　{</b></p><p>　　print

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

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

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

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

64、><b>　　}</b></p><p><b>　　puts("");</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　process* Location(proces

65、s* head,int pro_num)//進(jìn)程定位函數(shù)，找到當(dāng)前請(qǐng)求進(jìn)程在進(jìn)程鏈表中的位置，以便后面對(duì)其操作</p><p><b>　　{</b></p><p>　　process *p=NULL;</p><p><b>　　p=head;</b></p><p>　　if(NULL==p

66、)</p><p><b>　　{</b></p><p>　　printf("error !\n");//異常，當(dāng)前鏈表為空</p><p><b>　　return p;</b></p><p><b>　　}</b></p>&l

67、t;p><b>　　else</b></p><p><b>　　{</b></p><p>　　while(p!=NULL)</p><p><b>　　{</b></p><p>　　if(p->num==pro_num)</p><p>

68、;<b>　　{</b></p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p

69、>　　p=p->next;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　if(NULL==p)//無(wú)此進(jìn)程，輸入錯(cuò)誤</p><p><b>　　{</b></p><p>

70、　　printf("無(wú)此進(jìn)程 !\n");</p><p><b>　　return p;</b></p><p><b>　　}</b></p><p><b>　　else </b></p><p><b>　　{</b></

71、p><p><b>　　return p;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　process* Attempt_Alloc

72、ation(process* head,int *request,int *avail,int m)</p><p><b>　　{//試分配</b></p><p>　　int num,i;</p><p>　　process* p=NULL;</p><p>　　printf("請(qǐng)輸入進(jìn)程編號(hào): \n&q

73、uot;);</p><p>　　scanf("%d",&num);</p><p>　　p=Location(head,num);</p><p>　　if(p==NULL)</p><p><b>　　{</b></p><p>　　printf("無(wú)此進(jìn)

74、程!\n");</p><p><b>　　return p;</b></p><p><b>　　}</b></p><p>　　printf("請(qǐng)輸入該進(jìn)程的請(qǐng)求向量: \n");</p><p>　　for(i=0;i<m;i++)</p>&

75、lt;p><b>　　{</b></p><p>　　scanf("%d",&request[i]);</p><p><b>　　}</b></p><p>　　for(i=0;i<m;i++)//請(qǐng)求的合法性檢驗(yàn)</p><p><b>　　

76、{</b></p><p>　　if(request[i]<=p->Need[i])</p><p><b>　　{</b></p><p><b>　　;</b></p><p><b>　　}</b></p><p><

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

78、<b>　　}</b></p><p>　　for(i=0;i<m;i++)</p><p><b>　　{</b></p><p>　　if(request[i]<=avail[i])</p><p><b>　　{</b></p><p>

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

80、gt;<p>　　return NULL;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　for(i=0;i<m;i++) //試分配，修改相關(guān)數(shù)據(jù)結(jié)構(gòu)</p><p><b>

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

82、<p><b>　　}</b></p><p><b>　　return p;</b></p><p><b>　　}</b></p><p>　　process* Reasonable(process* head,int*finish,int*work,int m,int n)//找當(dāng)

83、前可執(zhí)行的進(jìn)程</p><p><b>　　{</b></p><p>　　int i=0,j=0,count=0;</p><p>　　process* p=NULL;</p><p><b>　　while(1)</b></p><p><b>　　{<

84、/b></p><p>　　if(finish[i]!=-1) //表示該進(jìn)程未執(zhí)行安全性檢查</p><p><b>　　{</b></p><p>　　p=Location(head,finish[i]);//定位該進(jìn)程</p><p>　　if(p!=NULL)</p><p>

85、<b>　　{</b></p><p>　　for(j=0;j<m;j++)</p><p><b>　　{</b></p><p>　　if(p->Need[j]>work[j])</p><p><b>　　{</b></p><p&g

86、t;<b>　　break;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p><b>　　continue;</b></p&g

87、t;<p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　if(j==m)</b></p><p><b>　　{</b></p><p><b>　　return p;</b&g

88、t;</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　i++; //當(dāng)前進(jìn)程檢查沒(méi)有通過(guò)，則進(jìn)行下一個(gè)進(jìn)程的檢查</p><p><b>　

89、　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　i++; //當(dāng)

90、前進(jìn)程已經(jīng)檢查過(guò)，則進(jìn)行下一個(gè)進(jìn)程的檢查</p><p><b>　　}</b></p><p><b>　　if(i==n)</b></p><p><b>　　{</b></p><p>　　return NULL; //遍歷所有進(jìn)程都未找到，則跳出返回NULL</

91、p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void Alter_Data(process* p,int* work,int* finish,int record[][M],int m)

92、//修改相關(guān)數(shù)據(jù)結(jié)構(gòu)</p><p><b>　　{</b></p><p><b>　　int i;</b></p><p>　　for(i=0;i<m;i++)</p><p><b>　　{</b></p><p>　　record[p-&g

93、t;num][i]=work[i];</p><p>　　work[i]=work[i]+p->Allocation[i];</p><p><b>　　}</b></p><p>　　finish[p->num]=-1; //表示該進(jìn)程已通過(guò)安全性檢查</p><p><b>　　}</

94、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&

95、gt;　　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));//當(dāng)前系統(tǒng)可供給進(jìn)程的各個(gè)資源數(shù)目</

96、p><p>　　finish=(int*)malloc(n*sizeof(int));//標(biāo)志數(shù)組</p><p>　　//safety=(int*)malloc(n*sizeof(int));</p><p><b>　　p=head;</b></p><p>　　for(i=0;i<m;i++)</p&g

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

98、gt;<b>　　{</b></p><p>　　finish[i]=p->num;</p><p>　　p=p->next;</p><p><b>　　i++;</b></p><p><b>　　}</b></p><p><b&

99、gt;　　i=0;</b></p><p>　　while(count<n)</p><p><b>　　{</b></p><p>　　pro=Reasonable(head,finish,work,m,n);</p><p>　　if(pro!=NULL)//Need[i,j]<

100、=work[j],即當(dāng)前系統(tǒng)可以滿足該進(jìn)程</p><p><b>　　{</b></p><p>　　Alter_Data(pro,work,finish,Record,m);</p><p><b>　　count++;</b></p><p>　　safety[i]=pro->num;

101、 //</p><p><b>　　i++;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　printf("當(dāng)前

102、系統(tǒng)處于不安全狀態(tài) !\n");</p><p>　　//remark=1;</p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　if(coun

103、t==n)</p><p><b>　　{</b></p><p>　　printf("當(dāng)前系統(tǒng)處于安全狀態(tài),存在一個(gè)安全序列 :\n");</p><p>　　for(i=0;i<n;i++)</p><p><b>　　{</b></p><p>

104、;　　printf("%d,",safety[i]); //打印安全序列</p><p><b>　　}</b></p><p><b>　　puts("");</b></p><p><b>　　}</b></p><p>　　

105、free(finish);</p><p>　　free(work);</p><p>　　finish=NULL;</p><p>　　work=NULL;</p><p>　　if(count==n)</p><p><b>　　{</b></p><p>　　retu

106、rn 1; //找到安全序列則返回1</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　return 0;//未找到安全序列則返回0</p><p>&

107、lt;b>　　}</b></p><p><b>　　}</b></p><p>　　void Return_Source(process* p,int *request,int *avail,int m) //若試分配失敗，則恢復(fù)試分配前的資源狀態(tài)</p><p><b>　　{</b></p&

108、gt;<p><b>　　int i;</b></p><p><b>　　{</b></p><p>　　for(i=0;i<m;i++)</p><p><b>　　{</b></p><p>　　p->Allocation[i]-=request

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

110、/b></p><p>　　void Print_After_Safety(process *head,int *safety,int work[][M],int m,int n) //打印試分配后的系統(tǒng)資源狀態(tài)</p><p><b>　　{</b></p><p>　　process* p=NULL;</p><

111、p><b>　　int i,j;</b></p><p><b>　　char ch;</b></p><p><b>　　p=head;</b></p><p>　　if(NULL==p)</p><p><b>　　{</b></p>

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

113、 Work | | Need | |Allocation| |Work+Allocation| | Finish |\n\n");</p><p>　　printf("\t");</p><p>　　for(i=0;i<4;i++)</p><p><b>　　{</b

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

115、lt;b>　　}</b></p><p>　　printf("\t");</p><p><b>　　}</b></p><p><b>　　puts("");</b></p><p>　　for(i=0;i<n;i++)</p&

116、gt;<p><b>　　{</b></p><p><b>　　p=head;</b></p><p>　　while(p!=NULL)</p><p><b>　　{</b></p><p>　　if(p->num==safety[i])</p&

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

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

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

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

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

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

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

124、gt;　　void main()</p><p><b>　　{</b></p><p>　　int i,flag=0,count=0;</p><p><b>　　char ch;</b></p><p>　　int *p=NULL;//進(jìn)程鏈頭指針數(shù)組</p><p>

125、;　　int Available[M]={0};// 其中每一個(gè)數(shù)組元素表示當(dāng)前某類(lèi)資源的可用數(shù)目，初始化為系統(tǒng)所提供的資源的最大數(shù)目</p><p>　　int Request[M]={0};</p><p>　　int Record_work[N][M]={0};</p><p>　　int Safety[N]={0}; //存儲(chǔ)安全序列，以便后面排序

126、</p><p>　　process *head=NULL;</p><p>　　process *pro=NULL;</p><p><b>　　p=&count;</b></p><p>　　printf("請(qǐng)初始化當(dāng)前可用資源 !\n");</p><p>　

127、　for(i=0;i<M;i++)</p><p><b>　　{</b></p><p>　　scanf("%d",&Available[i]);</p><p><b>　　}</b></p><p>　　Init_process(&head,M,p);

128、//初識(shí)化系統(tǒng)資源</p><p>　　Print(head,Available,M); //打印初始化資源狀況</p><p><b>　　do</b></p><p><b>　　{</b></p><p>　　flag=Safety_Algorithm(head,Available,

129、Safety,Record_work,M,count); //安全性檢驗(yàn)</p><p>　　if(1==flag)</p><p><b>　　{</b></p><p>　　printf("當(dāng)前系統(tǒng)是安全的，可進(jìn)行試探分配 !\n");</p><p><b>　　do</b>

130、;</p><p><b>　　{</b></p><p>　　pro=Attempt_Allocation(head,Request,Available,M); //通過(guò)則試分配</p><p>　　if(NULL!=pro)</p><p><b>　　{</b></p>

131、<p>　　printf("試分配成功，當(dāng)前系統(tǒng)資源分配如下表 !\n");</p><p>　　Print(head,Available,M);</p><p><b>　　break;</b></p><p><b>　　}</b></p><p>　　else

132、// 否則，退到上一級(jí)</p><p><b>　　{</b></p><p>　　printf("當(dāng)前請(qǐng)求系統(tǒng)不能滿足 ! 您可以選擇重新輸入請(qǐng)求向量(Y/y)，或者退出(N/n)\n\n");</p><p>　　printf("您是否要繼續(xù)操作 (Y/N):\n");</p>

133、<p>　　getchar();</p><p>　　scanf("%c",&ch);</p><p>　　if(ch=='N'|| ch=='n')</p><p><b>　　{</b></p><p><b>　　exit(0);&

134、lt;/b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　}while(ch=='Y'||ch=='y');</p><p><b>　　}</b></p><p&

135、gt;　　else //未通過(guò)安全性算法</p><p><b>　　{</b></p><p>　　printf("當(dāng)前系統(tǒng)不安全，不能響應(yīng)任何進(jìn)程的請(qǐng)求 !\n");</p><p><b>　　exit(0);</b></p><p><b>　　}

136、</b></p><p>　　flag=Safety_Algorithm(head,Available,Safety,Record_work,M,count);</p><p>　　if(1==flag)</p><p><b>　　{</b></p><p>　　printf("分配成功！當(dāng)前資源

137、分配狀態(tài)如下表 :\n");</p><p>　　Print_After_Safety(head,Safety,Record_work,M,count);</p><p>　　printf("您是否還要繼續(xù)操作 (Y(y)/N(y)\n)");</p><p>　　getchar();</p><p>　　sca

138、nf("%c",&ch);</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　printf("當(dāng)前系統(tǒng)處于不安全狀態(tài),本次嘗試分配作廢，恢復(fù)原來(lái)

139、的資源分配狀態(tài) ! :\n");</p><p>　　Return_Source(pro,Request,Available,M);</p><p>　　Print(head,Available,M);</p><p>　　printf("您是否還要繼續(xù)操作 (Y(y)/N(y)\n)");</p><p>　　

140、getchar();</p><p>　　scanf("%c",&ch);</p><p><b>　　}</b></p><p>　　}while(ch=='Y'|| ch=='y');</p><p>　　printf("您已經(jīng)正常退出!\n\n&

141、quot;);</p><p><b>　　}</b></p><p><b>　　程序分析測(cè)試</b></p><p>　　函數(shù)的書(shū)寫(xiě)分模塊進(jìn)行，每完成一個(gè)模塊進(jìn)行調(diào)試、測(cè)試直到該函數(shù)運(yùn)行無(wú)誤。</p><p>　　1初始化系統(tǒng)資源模塊Init_process(process **head,i

142、nt m,int* count)的測(cè)試</p><p>　　按提示輸入，以-1結(jié)束整個(gè)初始化過(guò)程，并打印結(jié)果。</p><p>　　2 試分配模塊Attempt_Allocation的測(cè)試</p><p>　　試分配模塊，主要是在系統(tǒng)進(jìn)過(guò)第一次安全檢查后，對(duì)系統(tǒng)資源的一次嘗試性分配，試分配完成后，相關(guān)的數(shù)據(jù)結(jié)構(gòu)被修改。</p><p>　　3

143、安全模塊Safety_Algorithm的調(diào)試</p><p>　　試分配前的安全算法，結(jié)果如果輸出一個(gè)安全性序列，并且經(jīng)過(guò)人工檢查該安全性序列，確實(shí)有效，則該模塊正確；如果系統(tǒng)不安全，打印出相關(guān)信息，返回上一層。效果如下圖示：</p><p>　?。?）試分配后的安全算法，結(jié)果如果輸出一個(gè)安全性序列，并且經(jīng)過(guò)人工檢查該安全性序列，確實(shí)有效，則該模塊正確；否則，之前的試分配作廢，恢復(fù)試分配

144、前的資源狀態(tài)。</p><p><b>　　設(shè)計(jì)體會(huì)</b></p><p>　　經(jīng)過(guò)幾天的自己動(dòng)手練習(xí)，對(duì)操作系統(tǒng)的掌握又進(jìn)了一步，收獲了很多課堂上和書(shū)上未出現(xiàn)過(guò)的或老師未講到的一些知識(shí)。在完成實(shí)驗(yàn)的過(guò)程中，進(jìn)行了反復(fù)的修改和調(diào)試，這次實(shí)驗(yàn)，讓我基本上明白了銀行家算法的基本原理，加深了對(duì)課堂上知識(shí)的理解，也懂得了如何讓銀行家算法實(shí)現(xiàn)，但編程功底的原因使程序很是繁瑣。

145、</p><p>　　這次的設(shè)計(jì)數(shù)據(jù)是通過(guò)一道實(shí)際的題目來(lái)體現(xiàn)銀行家算法避免死鎖的問(wèn)題，先用銀行家算法給其中一個(gè)進(jìn)程分配資源，看它所請(qǐng)求的資源是否大于它的需求量，才和系統(tǒng)所能給的資源相比較.讓進(jìn)程形成一個(gè)安全隊(duì)列,看系統(tǒng)是否安全.再利用安全性算法檢查此時(shí)系統(tǒng)是否安全。</p><p>　　要做一個(gè)課程設(shè)計(jì)，如果知識(shí)面只是停留在書(shū)本上，是不可能把課程設(shè)計(jì)完全地做好。用VC++6.0編程，感覺(jué)