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

1、<p><b>　　操作系統(tǒng)課程設(shè)計(jì)</b></p><p><b>　　進(jìn)程管理</b></p><p><b>　　死鎖避免算法設(shè)計(jì)</b></p><p>　　姓 名： </p><p>　　學(xué) 號(hào)：

2、 </p><p>　　系 別： 計(jì)算機(jī)科學(xué)與工程 </p><p>　　專 業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù) </p><p>　　年 級(jí)： </p><p>　　指導(dǎo)教師： </p

3、><p>　　2011年 5 月16 日</p><p>　　一、課程設(shè)計(jì)項(xiàng)目介紹（含項(xiàng)目介紹及設(shè)計(jì)目的）</p><p><b>　　項(xiàng)目介紹：</b></p><p>　　1、前言介紹：在多道程序系統(tǒng)中，雖可借助于多個(gè)進(jìn)程的并發(fā)執(zhí)行，來(lái)改善系統(tǒng)的資源利用提高吞吐量，但可能發(fā)生一種危險(xiǎn)——死鎖。當(dāng)進(jìn)程處于這種僵持狀態(tài)時(shí)，若

4、無(wú)外力作用，他們都無(wú)法再向前推進(jìn)。</p><p>　　在操作系統(tǒng)的資源分配也有類似的問(wèn)題，如果資源分配不得當(dāng)就會(huì)發(fā)生進(jìn)程循環(huán)等待資源，就會(huì)出現(xiàn)死鎖的現(xiàn)象。而最有代表性的避免死鎖的算法就是銀行家算法。銀行家算法是避免死鎖的一種重要方法，本次課程設(shè)計(jì)用C語(yǔ)言編寫(xiě)和調(diào)試一個(gè)簡(jiǎn)單的銀行家算法程序，用銀行家算法檢查是否允許分配資源給進(jìn)程，避免死鎖。</p><p><b>　　2、設(shè)計(jì)內(nèi)

5、容：</b></p><p>　　內(nèi)容：實(shí)現(xiàn)教材3.6.3節(jié)中所描述的銀行家避免死鎖算法。 要求：可自定義進(jìn)程數(shù)目、資源類型和每種類型資源的數(shù)目；   可輸入每個(gè)進(jìn)程對(duì)每種資源的最大需求、已經(jīng)獲得的數(shù)量；   當(dāng)某進(jìn)程發(fā)起某種資源請(qǐng)求時(shí)，計(jì)算系統(tǒng)狀態(tài)是否安全。</p><p><b>

6、　　設(shè)計(jì)目的：</b></p><p>　　1、加深我們對(duì)了解有關(guān)資源申請(qǐng)、避免死鎖等概念，提高了我們分析、解決問(wèn)題的能力。</p><p>　　2、通過(guò)課程設(shè)計(jì)深入理解避免死鎖的原理，并加深我們對(duì)銀行家算法理解。</p><p>　　二、總體設(shè)計(jì)（含系統(tǒng)的總體結(jié)構(gòu)、原理框圖或各模塊介紹等）</p><p><b>　　

7、總體結(jié)構(gòu)：</b></p><p>　　1、初始化進(jìn)程數(shù)以及資源數(shù)；</p><p><b>　　2、銀行家算法；</b></p><p><b>　　3、安全性算法。</b></p><p><b>　　模塊介紹： </b></p><p&

8、gt;　　1、主函數(shù)main()</p><p>　?。?）、確定初始進(jìn)程數(shù)</p><p>　　（2）、確定初始資源種類數(shù)以及可用資源的數(shù)目</p><p>　　（3）、確定初始各進(jìn)程所需最大的資源數(shù)以及目前已分配的資源數(shù)目</p><p>　　(4)、調(diào)用其他模塊</p><p>　　2、銀行家算法Bank()&l

9、t;/p><p>　　(1)、如果Request<=NEED,則轉(zhuǎn)向（2）;否則,出錯(cuò)</p><p>　　(2)、如果Request<= ALLOCATION,則轉(zhuǎn)向（3）,否則等待</p><p>　　(3)、系統(tǒng)嘗試分配資源給進(jìn)程</p><p>　　(4)、系統(tǒng)執(zhí)行安全性算法</p><p>　　3、安

10、全性算法chkerr ()</p><p>　　(1)、設(shè)置兩個(gè)向量</p><p>　　工作向量: WORK= AVAILABLE (表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需要的各類資源數(shù)目)</p><p>　　FINISH:表示系統(tǒng)是否有足夠資源分配給進(jìn)程(TRUE表示有; FALSE表示沒(méi)有),初始化為FALSE。.</p><p>　?。?

11、）、若FINISH [i]=FALSE&&NEED<=WORK,則執(zhí)行3;否則執(zhí)行4</p><p>　?。?）、進(jìn)程P獲得第i類資源,則順利執(zhí)行直至完成!并釋放資源:</p><p>　　WORK=WORK+ALLOCATION[i][j];</p><p>　　FINISH[i]=TRUE;</p><p><

12、b>　　轉(zhuǎn)2</b></p><p>　?。?）、若所有進(jìn)程的FINISH[i]=TRUE,則表示系統(tǒng)安全;否則,不安全!</p><p>　　三、詳細(xì)設(shè)計(jì)（含主要的數(shù)據(jù)結(jié)構(gòu)、程序流程圖、關(guān)鍵代碼段及注釋等）</p><p><b>　　數(shù)據(jù)結(jié)構(gòu):</b></p><p>　　1.可利用資源向量AVAI

13、LABLE 2.分配矩陣ALLOCATION</p><p>　　3.需求矩陣NEED</p><p><b>　　程序流程圖：</b></p><p><b>　　關(guān)鍵代碼段：</b></p><p>　　#include <stdio.h> </p><p&g

14、t;　　#define M 50 //總進(jìn)程數(shù)</p><p>　　#define N 30 //總資源數(shù) </p><p>　　#define FALSE 0 </p><p>　　#define TRUE 1 </p><p>　　int E,F; //系統(tǒng)可用資源數(shù)</p><p>　　int AVAILABL

15、E[N]; //可用資源的數(shù)組</p><p>　　int ALLOCATION[M][N]; //已分配到的資源</p><p>　　int NEED[M][N]; //需求矩陣</p><p>　　int Request[N]; //進(jìn)程請(qǐng)求的資源數(shù)</p><p>　　main() //主函數(shù)</p><p>&

16、lt;b>　　{ </b></p><p>　　int i=0,j=0; </p><p>　　int flag=1; //合法的資源申請(qǐng)</p><p>　　void showdata(); //顯示資源分配情況函數(shù)</p><p>　　void changdata(int); //更改資源分配函數(shù)</p>

17、<p>　　void rstordata(int); //還原預(yù)分配資源函數(shù)</p><p>　　void bank(); //銀行家算法函數(shù)</p><p>　　int chkerr(int); //安全性算法函數(shù)</p><p>　　printf("\n———銀 行 家 算 法———\n\n");</p><p

18、>　　printf("***輸入進(jìn)程總數(shù) E: ");</p><p>　　scanf(" %d", &E); //輸入進(jìn)程總數(shù) </p><p>　　printf("***輸入資源種類總數(shù) F: ");</p><p>　　scanf(" %d&q

19、uot;, &F); //輸入資源種類數(shù)</p><p>　　printf("***輸入已分配資源數(shù): \n");</p><p>　　for(i=0;i<E; i++)</p><p>　　for(j=0;j<F; j++)</p><p><b>　　{</b>&l

20、t;/p><p>　　scanf(" %d",&ALLOCATION[i][j]); //輸入以分配資源數(shù)</p><p><b>　　}</b></p><p>　　printf("***輸入還需要的資源數(shù)\n");</p><p>　　for (i=0;i<E; i+

21、+)</p><p>　　for(j=0;j<F; j++)</p><p><b>　　{</b></p><p>　　scanf(" %d",&NEED [i][j]); //輸入還需資源數(shù)</p><p><b>　　}</b></p><

22、;p>　　printf("***輸入可利用的資源數(shù)\n");</p><p>　　for (i=0;i<F; i++)</p><p>　　scanf(" %d", &AVAILABLE[i]); //輸入可利用的資源數(shù)</p><p>　　printf("\n");</p&g

23、t;<p>　　showdata(); //顯示資源分配情況</p><p>　　bank(); //執(zhí)行銀行家算法</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　void bank() //銀行家算法</p&

24、gt;<p><b>　　{</b></p><p>　　int i=0,j=0; </p><p>　　int flag=1; //合法的資源申請(qǐng)</p><p>　　void showdata(); </p><p>　　void changdata(int); </p><p>

25、;　　void rstordata(int);</p><p>　　int chkerr(int);</p><p>　　while(flag) </p><p><b>　　{</b></p><p><b>　　i=-1; </b></p><p>　　while(i&l

26、t;0||i>=E) //輸入不合法進(jìn)程號(hào)的處理</p><p><b>　　{ </b></p><p>　　printf("***請(qǐng)輸入需申請(qǐng)資源的進(jìn)程號(hào)（從0到E-1!）:"); </p><p>　　scanf("%d",&i); </p><p>　　if(

27、i<0||i>=E)</p><p>　　printf("————輸入的進(jìn)程號(hào)不存在，重新輸入!————\n"); </p><p><b>　　}</b></p><p>　　printf("***請(qǐng)輸入進(jìn)程%d申請(qǐng)的資源數(shù)\n",i); </p><p>　　for

28、 (j=0;j<F;j++)</p><p><b>　　{ </b></p><p>　　printf("資源%d: ",j); </p><p>　　scanf(" %d",&Request[j]); </p><p>　　if(Request[j]>NEE

29、D[i][j]) //輸入不合法的資源量的處理</p><p><b>　　{ </b></p><p>　　printf("***進(jìn)程%d申請(qǐng)的資源量大于還需要%d類資源的資源量!\n",i,j); </p><p>　　printf("————申請(qǐng)不合理，出錯(cuò)!請(qǐng)重新選擇————\n!"); <

30、/p><p>　　flag=0; //申請(qǐng)不合理</p><p><b>　　break; </b></p><p><b>　　} </b></p><p><b>　　else </b></p><p><b>　　{ </b>&l

31、t;/p><p>　　if(Request[j]>AVAILABLE[j]) //輸入不合法的資源量的處理</p><p><b>　　{ </b></p><p>　　printf("***進(jìn)程%d申請(qǐng)的資源數(shù)大于系統(tǒng)可用%d類資源的資源量!",i,j); </p><p>　　printf(&q

32、uot;————申請(qǐng)不合理，出錯(cuò)!請(qǐng)重新選擇!————\n"); </p><p>　　flag=0; //申請(qǐng)不合理</p><p><b>　　break; </b></p><p><b>　　} </b></p><p><b>　　} </b></p&

33、gt;<p><b>　　} </b></p><p><b>　　if(flag) </b></p><p><b>　　{ </b></p><p>　　changdata(i); //更改資源分配數(shù)情況</p><p>　　if(chkerr(i)) <

34、;/p><p><b>　　{ </b></p><p>　　rstordata(i); //系統(tǒng)不安全時(shí)還原預(yù)分配的資源</p><p><b>　　} </b></p><p><b>　　} </b></p><p><b>　　else &

35、lt;/b></p><p>　　showdata(); //顯示資源分配情況</p><p>　　printf("\n"); </p><p>　　printf("是否繼續(xù)銀行家算法演示,按1鍵繼續(xù),按0鍵退出演示: \n選擇：");</p><p>　　scanf(" %d"

36、;,&flag);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void showdata() //顯示資源分配情況</p><p><b>　　{ </b></p><p>　　int i

37、,j; </p><p>　　printf("***系統(tǒng)可用的資源數(shù)為: \n"); </p><p>　　for (j=0;j<F;j++)</p><p>　　printf("資源%d: %d ",j,AVAILABLE[j]);</p><p>　　printf("\n&quo

38、t;); </p><p>　　printf("***各進(jìn)程已經(jīng)得到的資源量:\n "); </p><p>　　for (i=0;i<E;i++) </p><p><b>　　{ </b></p><p>　　printf("進(jìn)程%d: ",i); </p>

39、<p>　　for (j=0;j<F;j++)</p><p>　　printf("資源%d: %d ",j,ALLOCATION[i][j]); </p><p>　　printf("\n");</p><p><b>　　} </b></p><p>　　p

40、rintf("\n"); </p><p>　　printf("***各進(jìn)程還需要的資源量: \n"); </p><p>　　for (i=0;i<E;i++) //輸入各進(jìn)程還需要的資源量</p><p><b>　　{ </b></p><p>　　printf(&qu

41、ot;進(jìn)程%d: ",i);</p><p>　　for (j=0;j<F;j++)</p><p>　　printf("資源%d: %d ",j,NEED[i][j]);</p><p>　　printf("\n");}</p><p>　　printf("\n")

42、; </p><p><b>　　} </b></p><p>　　void changdata(int k) //修改資源分配情況</p><p><b>　　{</b></p><p><b>　　int j; </b></p><p>　　for

43、(j=0;j<F;j++)</p><p><b>　　{</b></p><p>　　AVAILABLE[j]=AVAILABLE[j]-Request[j]; //把可用資源數(shù)減去請(qǐng)求資源數(shù)的值賦值給可用資源</p><p>　　ALLOCATION[k][j]=ALLOCATION[k][j]+Request[j]; //把已分配資

44、源數(shù)加上請(qǐng)求資源數(shù)賦值給已分配資源</p><p>　　NEED[k][j]=NEED[k][j]-Request[j]; //把資源需求數(shù)減去請(qǐng)求資源數(shù)的值賦值給資源需求數(shù)</p><p><b>　　} </b></p><p><b>　　}; </b></p><p>　　void rsto

45、rdata(int k) //還原資源分配</p><p><b>　　{ </b></p><p><b>　　int j; </b></p><p>　　for (j=0;j<F;j++) </p><p><b>　　{ </b></p><p&

46、gt;　　AVAILABLE[j]=AVAILABLE[j]+Request[j]; //把可用資源數(shù)加上請(qǐng)求資源數(shù)的值賦值給可用資源</p><p>　　ALLOCATION[k][j]=ALLOCATION[k][j]-Request[j]; //把已分配資源數(shù)減去請(qǐng)求資源數(shù)賦值給已分配資源</p><p>　　NEED[k][j]=NEED[k][j]+Request[j]; //把

47、資源需求數(shù)加上請(qǐng)求資源數(shù)的值賦值給資源需求數(shù)</p><p><b>　　} </b></p><p><b>　　}; </b></p><p>　　int chkerr(int s) //安全性算法</p><p><b>　　{ </b></p><p

48、>　　int WORK; //系統(tǒng)可提供分配的資源數(shù)</p><p>　　int FINISH[M]; //系統(tǒng)是否有足夠資源分配給進(jìn)程</p><p>　　int temp[M]; //進(jìn)程號(hào) </p><p>　　int i,j,k=0; </p><p>　　for(i=0;i<E;i++)</p><p

49、>　　FINISH[i]=FALSE;//將每一個(gè)進(jìn)程的FINISH值初始化為FALSE </p><p>　　for(j=0;j<F;j++)</p><p><b>　　{ </b></p><p>　　WORK=AVAILABLE[j]; </p><p><b>　　i=s; </b&

50、gt;</p><p>　　while(i<E)</p><p><b>　　{</b></p><p>　　if (FINISH[i]==FALSE&&NEED[i][j]<=WORK) </p><p><b>　　{ </b></p><p>

51、;　　WORK=WORK+ALLOCATION[i][j]; //進(jìn)程獲得資源</p><p>　　FINISH[i]=TRUE; //系統(tǒng)有足夠資源分配給進(jìn)程</p><p>　　temp[k]=i; //保存進(jìn)程號(hào)</p><p><b>　　k++; </b></p><p><b>　　i=0; <

52、;/b></p><p><b>　　} </b></p><p><b>　　else</b></p><p><b>　　i++;</b></p><p><b>　　}</b></p><p>　　for(i=0;i&l

53、t;E;i++) </p><p>　　if(FINISH[i]==FALSE) //系統(tǒng)沒(méi)有足夠資源分配給進(jìn)程</p><p><b>　　{ </b></p><p>　　printf("\n"); </p><p>　　printf("\t————系統(tǒng)不安全!!! 本次資源申請(qǐng)不成功!

54、!!————"); </p><p>　　printf("\n"); </p><p>　　return 1; </p><p><b>　　}</b></p><p><b>　　} </b></p><p>　　printf("\n

55、"); </p><p>　　printf("————經(jīng)安全性檢查,系統(tǒng)安全,本次分配成功!————"); </p><p>　　printf("\n"); </p><p>　　printf("本次安全序列："); </p><p>　　for(i=0;i<E;i+

56、+) //輸出安全序列</p><p>　　printf("進(jìn)程%d",temp[i]); </p><p>　　printf("\n"); </p><p><b>　　return 0;</b></p><p><b>　　};</b></p>

57、<p>　　四、運(yùn)行結(jié)果（含運(yùn)行及測(cè)試結(jié)果和用戶使用說(shuō)明書(shū)）（四號(hào)宋體）</p><p><b>　　初始化資源分配：</b></p><p><b>　　進(jìn)程號(hào)不合法：</b></p><p><b>　　申請(qǐng)資源數(shù)不合法：</b></p><p><b&

58、gt;　　運(yùn)行結(jié)果：</b></p><p><b>　　用戶使用說(shuō)明書(shū)：</b></p><p>　　1、運(yùn)行環(huán)境: Microsoft Visual C++ 6.0</p><p><b>　　2、運(yùn)行步驟：</b></p><p>　?。?）直接打開(kāi)文件夾"0808111

59、40"下的"Debug"下的0.exe ，運(yùn)行080811140.exe.（2）進(jìn)入程序后按提示初始化資源，初始化結(jié)束后會(huì)顯示資源的分配情況，依次 輸入進(jìn)程號(hào)及申請(qǐng)的資源數(shù)，系統(tǒng)將會(huì)計(jì)算本次分配是否安全，并顯示結(jié)果。</p><p>　　五、課程設(shè)計(jì)小結(jié)與心得體會(huì)（不小于300字）（四號(hào)宋體）</p><p>　　這次課程設(shè)計(jì)的運(yùn)行環(huán)境是：Micro

60、soft Visual C++ 6.0，相對(duì)于其他設(shè)計(jì)語(yǔ)言我對(duì)C語(yǔ)言比較熟悉，所以我選用了C語(yǔ)言來(lái)完成這次的設(shè)計(jì)。銀行家算法是避免死鎖的一種重要方法，在課程設(shè)計(jì)的過(guò)程中，我了解到銀行家算法確實(shí)能保證系統(tǒng)時(shí)刻都處在安全狀態(tài)，但是銀行家算法也有個(gè)缺點(diǎn)：它需要不斷檢測(cè)各個(gè)進(jìn)程對(duì)各類資源的占用情況和申請(qǐng)情況，所以在保證系統(tǒng)安全的情況下要花費(fèi)較多的時(shí)間。</p><p>　　為了完成更有效地完成課程設(shè)計(jì)，我花了幾天的時(shí)間溫