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

1、<p>　　《操作系統(tǒng)課程設(shè)計報告》</p><p><b>　　銀行家算法</b></p><p>　　姓 名： </p><p>　　學(xué) 號： </p><p>　　課 程： 計算機(jī)操作系統(tǒng) </p><p>　　指導(dǎo)老師：

2、 </p><p><b>　　目錄</b></p><p><b>　　一、設(shè)計目的1</b></p><p><b>　　二、設(shè)計要求1</b></p><p>　　三、設(shè)計內(nèi)容和步驟1</p><p><b>　　四、算法

3、描述4</b></p><p><b>　　五、實驗結(jié)果11</b></p><p><b>　　六、實驗心得12</b></p><p>　　七、參考文獻(xiàn)………………………………………………………………………15</p><p><b>　　一、設(shè)計目的</b&g

4、t;</p><p>　　銀行家算法是避免死鎖的一種重要方法，本實驗要求用高級語言編寫和調(diào)試一個簡單的銀行家算法程序。加深了解有關(guān)資源申請、避免死鎖等概念，并體會和了解死鎖和避免死鎖的具體實施方法。</p><p><b>　　二、設(shè)計要求</b></p><p>　　在了解和掌握銀行家算法的基礎(chǔ)上，能熟練的處理課本例題中所給狀態(tài)的安全性問題，

5、能編制銀行家算法通用程序，將調(diào)試結(jié)果顯示在計算機(jī)屏幕上。</p><p>　　具體程序的功能要求：</p><p>　　1．設(shè)定進(jìn)程對各類資源最大申請表示及初值確定。2．設(shè)定系統(tǒng)提供資源初始狀況（已分配資源、可用資源）。3．設(shè)定每次某個進(jìn)程對各類資源的申請表示。4．編制程序，依據(jù)銀行家算法，決定其申請是否得到滿足。</p><p><b>　　、&l

6、t;/b></p><p><b>　　三、設(shè)計內(nèi)容和步驟</b></p><p><b>　　設(shè)計內(nèi)容</b></p><p>　　銀行家算法的思路：先對用戶提出的請求進(jìn)行合法性檢查，即檢查請求的是不大于需要的，是否不大于可利用的。若請求合法，則進(jìn)行試分配。最后對試分配后的狀態(tài)調(diào)用安全性檢查算法進(jìn)行安全性檢查。若安

7、全，則分配，否則，不分配，恢復(fù)原來狀態(tài)，拒絕申請。</p><p><b>　　設(shè)計步驟</b></p><p>　　1、為實現(xiàn)銀行家算法，系統(tǒng)中需要設(shè)置若干數(shù)據(jù)結(jié)構(gòu)，用來表示系統(tǒng)中各進(jìn)程的資源分配及需求情況。</p><p>　　假定系統(tǒng)中有M個進(jìn)程，N類資源。進(jìn)程數(shù)和資源數(shù)由程序中直接定義</p><p>　　#de

8、fine M 5 //總進(jìn)程數(shù)</p><p>　　#define N 3 //總資源數(shù)</p><p>　　銀行家算法中使用的數(shù)據(jù)結(jié)構(gòu)如下：</p><p>　?。?）可利用資源Available。這是一個含有m個元素的數(shù)組，其中的每一個元素代表一類資源的空閑資源數(shù)目，其初值是系統(tǒng)中所配置的該類資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動態(tài)

9、的改變。如果Available[j]=k，表示系統(tǒng)中Rj類資源有k個。</p><p>　?。?）最大需求矩陣Max。這是一個n*m的矩陣，它定義了系統(tǒng)中每一個進(jìn)程對各類資源的最大需求數(shù)目。如果Max[i，j]=k，表示進(jìn)程Pi對Rj類資源的最大需求數(shù)為k個。</p><p>　?。?）分配矩陣Allocation。這是一個n*m的矩陣，它定義了系統(tǒng)中當(dāng)前已分配給每一個進(jìn)程的各類資源。如果

10、Allocation[i,j]＝k, 表示進(jìn)程Pi當(dāng)前已分到 Rj類資源有k個。</p><p>　?。?）需求矩陣Need。這是一個n*m的矩陣，它定義了系統(tǒng)中每一個進(jìn)程還需要的各類資源的數(shù)目。如果Need [i，j]=k，表示進(jìn)程Pi需要Rj類資源有k個，才能完成任務(wù)。</p><p>　　int Max[5][3]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{

11、4,3,3}};//每個進(jìn)程對每類資源的最大需求</p><p>　　int Allocation[5][3]={{0,1,0},{2,0,0},{3,0,2},{2,1,1},{0,0,2}};//系統(tǒng)已分配資源</p><p>　　int Avaliable[3]={3,3,2}; //系統(tǒng)可利用資源</p><p>　　int Need[5][3]={{7,4

12、,3},{1,2,2},{6,0,0},{0,1,1},{4,3,1}};//還需要資源</p><p>　　int Request[3];</p><p><b>　　2、實現(xiàn)過程</b></p><p><b>　　主函數(shù)</b></p><p>　　int main()//主函數(shù)</p&

13、gt;<p>　　{ int choice,i;</p><p><b>　　Begin:</b></p><p>　　printf("請輸入A、B、C的可利用資源數(shù)量：");</p><p>　　for(i=0;i<N;i++)</p><p>　　scanf("%

14、d",&Available[i]); </p><p>　　showdata();</p><p>　　safeAlgorithm();</p><p>　　if(run==False)goto Begin;</p><p><b>　　do</b></p><p>　　{

15、 printf("\n輸入接下來你要進(jìn)行的操作 1：分配資源 2:顯示資源 否則按任意鍵退出: ");</p><p>　　scanf("%d",&choice);</p><p>　　switch(choice)</p><p><b>　　{ </b></p><p

16、>　　case 1: bankerAlgorithm(); break;</p><p>　　case 2: showdata(); break;</p><p>　　default: break;</p><p><b>　　} </b></p><p>　　}while((choice==1)||(choi

17、ce==2));</p><p>　　其中用到的函數(shù)操作有三個</p><p>　　showdata();//顯示資源矩陣</p><p>　　safeAlgorithm();//安全性檢測算法</p><p>　　bankerAlgorithm();//利用銀行家算法對申請資源對進(jìn)行判定</p><p><b&

18、gt;　　3、安全性檢查</b></p><p>　　程序中安全性算法的描述如下：</p><p>　　（1） 設(shè)置如下兩個工作向量：</p><p>　　Work：表示系統(tǒng)可提供給進(jìn)程繼續(xù)運行的各類資源的空閑資源數(shù)目，它含有m個元素，執(zhí)行安全性算法開始時，Work＝Available。</p><p>　　Finish：表示系統(tǒng)

19、是否有足夠的資源分配給進(jìn)程，使之運行完成。開始時，F(xiàn)inish[i]＝false；當(dāng)有足夠的資源分配給進(jìn)程Pi時，令Finish[i]＝true。</p><p>　?。?） 從進(jìn)程集合中找到一個能滿足下列條件的進(jìn)程：</p><p>　　Finish[i]＝＝false；</p><p>　　Need i<= Work；，</p><p&

20、gt;　　如果找到了就執(zhí)行步驟（3），否則執(zhí)行步驟（4）。</p><p>　?。?） 當(dāng)進(jìn)程Pi獲得資源后，可執(zhí)行直到完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行</p><p>　　Work = Work + Allocation;</p><p>　　Finish[i]＝false；</p><p>　　然后轉(zhuǎn)向第（2）步驟。</p&g

21、t;<p>　?。?） 若所有進(jìn)程中的Finish[i]都是true，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。</p><p>　　此過程由一個安全性檢測函數(shù)實現(xiàn)：safeAlgorithm();//安全性檢測算法</p><p>　　4、對進(jìn)程申請資源的處理</p><p>　　當(dāng)某一進(jìn)程提出資源申請時，系統(tǒng)須做出判斷，能否將所申請資源分配

22、給該進(jìn)程。設(shè)request為進(jìn)程i的請求向量，如果request[j]=K，表示進(jìn)程i需要K個j資源。當(dāng)系統(tǒng)發(fā)出請求后，系統(tǒng)按下述步驟開始檢查： （1） 如果request[j]<=need[i][j],轉(zhuǎn)向步驟2；否則報告出錯，申請的資源大于它需要的最大值。 （2） 如果request[j]<=available[j],轉(zhuǎn)向步驟3；否則報告出錯，尚無足夠的資源。 （3）系統(tǒng)試探著把資源分配給p[i]，并修

23、改下列數(shù)據(jù)結(jié)構(gòu)中的值： available[j]=available[j]-request[j] allocation[i][j]=allocation[i][j]+request[j] need[i][j]=need[i][j]-request[j] （4）系統(tǒng)進(jìn)行安全性算法，檢查此次分配后，系統(tǒng)是否還處于安全狀態(tài)，若安全，把資源分配給進(jìn)程i；否則，恢復(fù)原來的資源

24、分配狀態(tài)，讓進(jìn)程i等待。整個過程由銀行家算法實現(xiàn)：bankerAlg</p><p><b>　　四、算法描述</b></p><p>　　#include<string.h></p><p>　　#include<stdio.h></p><p>　　#define M 5 //定

25、義進(jìn)程數(shù) </p><p>　　#define N 3 //定義資源數(shù) s</p><p>　　#define False 0</p><p>　　#define True 1</p><p>　　int Max[5][3]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}}; //每個進(jìn)

26、程對每類資源的最大需求</p><p>　　int Allocation[5][3]={{0,1,0},{2,0,0},{3,0,2},{2,1,1},{0,0,2}};//系統(tǒng)已分配資源</p><p>　　int Available[3]; //系統(tǒng)可利用資源</p><p>　　int Need[5][3]={{7,4,3},{1,2,2},{6,0,0},

27、{0,1,1},{4,3,1}};//還需要資源</p><p>　　int Request[3];</p><p>　　int run=True;</p><p>　　void showdata()//顯示資源矩陣</p><p><b>　　{</b></p><p><b>　　i

28、nt i,j;</b></p><p>　　printf("\n系統(tǒng)目前資源A、B、C的情況如下表:\n\n");</p><p>　　printf("進(jìn)程 Max Allocation Need Available\n"); </p><p>　　for(i=0

29、;i<M;i++){</p><p>　　printf(" pr%d ",i);</p><p>　　for(j=0;j<N;j++)</p><p>　　printf("%d ",Max[i][j]);</p><p>　　printf(" ");&l

30、t;/p><p>　　for(j=0;j<N;j++)</p><p>　　printf("%d ",Allocation[i][j]);</p><p>　　printf(" ");</p><p>　　for(j=0;j<N;j++)</p><p>　　p

31、rintf("%d ",Need[i][j]);</p><p><b>　　if(i==0)</b></p><p><b>　　{</b></p><p>　　printf(" "); </p><p>　　for(j=0;j<

32、N;j++)</p><p>　　printf("%d ",Available[j]);</p><p><b>　　}</b></p><p>　　printf("\n");</p><p><b>　　}</b></p><p>

33、　　printf("\n");</p><p><b>　　}</b></p><p>　　void release(int i)//判斷是否安全，若不安全則釋放第j類資源</p><p><b>　　{ </b></p><p><b>　　int j;&l

34、t;/b></p><p>　　for (j=0;j<N;j++)</p><p><b>　　{</b></p><p>　　Available[j]=Available[j]+Request[j];</p><p>　　Allocation[i][j]=Allocation[i][j]-Request[j

35、];</p><p>　　Need[i][j]=Need[i][j]+Request[j];</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void distribute(int i)//若符合條件則對第j類資源進(jìn)行分配</p>&

36、lt;p><b>　　{ </b></p><p><b>　　int j;</b></p><p>　　for (j=0;j<M;j++)</p><p><b>　　{</b></p><p>　　Available[j]=Available[j]-Reques

37、t[j];</p><p>　　Allocation[i][j]=Allocation[i][j]+Request[j];</p><p>　　Need[i][j]=Need[i][j]-Request[j];</p><p><b>　　}</b></p><p><b>　　}</b></

38、p><p>　　void safeAlgorithm()//安全性算法</p><p><b>　　{</b></p><p>　　int Work[3],Finish[M]={0},result[M];</p><p><b>　　run=True;</b></p><p>　

39、　/* work：表示系統(tǒng)可提供給進(jìn)程繼續(xù)運行的所需的各類資源數(shù)目</p><p>　　finish： 表示系統(tǒng)是否有足夠的資源分配給進(jìn)程</p><p>　　result用來存放依次執(zhí)行成功的線程 */</p><p>　　int i,j,k=0,m,demand;</p><p>　　for(i=0;i<3;i++)</p&

40、gt;<p><b>　　{</b></p><p>　　Work[i]=Available[i]; //開始的時候work=available</p><p><b>　　}</b></p><p>　　for(i=0;i<M;i++) </p><p><b>　　

41、{ </b></p><p><b>　　demand=0;</b></p><p>　　for(j=0;j<N;j++)</p><p><b>　　{</b></p><p>　　if (Finish[i]==False&&Need[i][j]<=Work

42、[j])</p><p>　　{ demand++;</p><p>　　if(demand==3)//只有ABC三類資源都滿足才把相應(yīng)的線程記入數(shù)組result中</p><p><b>　　{</b></p><p>　　for(m=0;m<N;m++)</p><p>　　Wor

43、k[m]=Work[m]+Allocation[i][m];//重新分配第i類線程的當(dāng)前可利用資源</p><p>　　Finish[i]=True;</p><p>　　result[k]=i;</p><p><b>　　i=-1; </b></p><p><b>　　k++;</b><

44、/p><p>　　} </p><p><b>　　}</b></p><p><b>　　else </b></p><p>　　if(Finish[i]==False)</p><p><b>　　{</b></p><

45、;p>　　if(i==M-1)</p><p><b>　　{ </b></p><p>　　printf("系統(tǒng)不安全\n\n");//如果不成功，輸出系統(tǒng)不安全</p><p>　　run=False;</p><p><b>　　}</b></p>

46、;<p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　if(run==False)break;</p><p><b>　　}</b></p>

47、;<p>　　if(run==True)</p><p><b>　　{</b></p><p>　　printf("系統(tǒng)資源分配成功!");//如果安全，輸出成功</p><p>　　printf("分配的序列:\n");</p><p>　　for(i=0;i&l

48、t;M;i++)//輸出運行進(jìn)程數(shù)組</p><p><b>　　{</b></p><p>　　printf("pr%d ",result[i]);</p><p><b>　　}</b></p><p><b>　　}</b></p>&

49、lt;p><b>　　}</b></p><p>　　void bankerAlgorithm()//利用銀行家算法對申請資源對進(jìn)行判定</p><p><b>　　{</b></p><p>　　int i,j,OK=1;</p><p>　　printf("\n請輸入第一個要求分

50、配的資源進(jìn)程號從(0 to 4):"); </p><p>　　scanf("%d",&i);//輸入須申請的資源號</p><p>　　printf("請輸入進(jìn)程 %d 申請的資源:\n",i);</p><p>　　for(j=0;j<3;j++)</p><p><

51、b>　　{</b></p><p>　　printf("第 %d 個資源:",j+1);</p><p>　　scanf("%d",&Request[j]);//輸入需要申請的資源</p><p><b>　　}</b></p><p>　　for (j=

52、0;j<N;j++)</p><p><b>　　{</b></p><p>　　if(Request[j]>Need[i][j])//判斷申請是否大于需求，若大于則出錯</p><p><b>　　{ </b></p><p>　　printf("進(jìn)程 %d 申請的資源大于它

53、需要的資源",i);</p><p>　　printf(" error!\n");</p><p><b>　　OK=0;</b></p><p><b>　　break;</b></p><p><b>　　}</b></p>&l

54、t;p><b>　　else </b></p><p><b>　　{</b></p><p>　　if(Request[j]>Available[j])//判斷申請是否大于當(dāng)前資源，若大于則出錯</p><p>　　{ </p><p&g

55、t;　　printf("進(jìn)程 %d 申請的資源大于當(dāng)前可利用資源,進(jìn)程進(jìn)入等待",i);</p><p>　　printf(" error!\n");</p><p><b>　　OK=0;</b></p><p><b>　　break;</b></p><p&

56、gt;<b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　if(OK==1)//若都符合條件，則進(jìn)行分配</p><p><b>　　{</b></p><p&g

57、t;　　distribute(i);//根據(jù)進(jìn)程請求分配資源</p><p>　　showdata();//顯示變換后的資源</p><p>　　safeAlgorithm();//通過安全算法判斷該序列是否安全</p><p>　　if(run==False)//若不安全，則進(jìn)行釋放第I類資源</p><p>　　releas

58、e(i);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　int main()//主函數(shù)</p><p>　　{ int choice,i;</p><p><b>　　Begin:</b><

59、;/p><p>　　printf("請輸入A、B、C的可利用資源數(shù)量：");</p><p>　　for(i=0;i<N;i++)</p><p>　　scanf("%d",&Available[i]); </p><p>　　showdata();</p><p>

60、　　safeAlgorithm();</p><p>　　if(run==False)goto Begin;</p><p><b>　　do</b></p><p>　　{ printf("\n輸入接下來你要進(jìn)行的操作 1：分配資源 2:顯示資源 否則按任意鍵退出: ");</p><p>　

61、　scanf("%d",&choice);</p><p>　　switch(choice)</p><p><b>　　{ </b></p><p>　　case 1: bankerAlgorithm(); break;</p><p>　　case 2: showdata(); br

62、eak;</p><p>　　default: break;</p><p><b>　　} </b></p><p>　　}while((choice==1)||(choice==2));</p><p><b>　　}</b></p><p><b>　　五

63、、實驗結(jié)果</b></p><p><b>　　六、實驗心得</b></p><p>　　在避免死鎖的方法中，允許進(jìn)程動態(tài)地申請資源，系統(tǒng)在進(jìn)行資源分配之前，先計算資源分配的安全性。若此次分配不會導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)，便將資源分配給進(jìn)程，否則進(jìn)程等待。銀行家算法是死鎖避免算法中的一種，通過上面這個例子，我們看到銀行家算法確實能保證系統(tǒng)時時刻刻都處于安全狀

64、態(tài)，在銀行家算法這個系統(tǒng)之中，所采用的數(shù)據(jù)結(jié)構(gòu)應(yīng)是最基本的部分。銀行家算法的數(shù)據(jù)結(jié)構(gòu)我們采用了一維數(shù)組與二維數(shù)組來存儲，比如最大需求量Max[][]、已分配資源數(shù)Allocation[][]、仍需求資源數(shù)Need[][]、以及系統(tǒng)可利用的資源數(shù)、申請各類資源等數(shù)組。</p><p>　　數(shù)據(jù)結(jié)構(gòu)雖然重要但卻只是基礎(chǔ)，而最主要的用以實現(xiàn)系統(tǒng)功能的應(yīng)該有兩個部分，一是用銀行家算法來判斷，二是用安全性算法來檢測系統(tǒng)的安

65、全性。</p><p>　　在本程序代碼中，銀行家算法用judge( )函數(shù)來實現(xiàn)。</p><p>　　首先，輸入欲申請資源的進(jìn)程以及其所申請的資源數(shù)，存放在Request數(shù)組中。</p><p>　　然后，判斷進(jìn)程請求的資源數(shù)是否大于其所需的資源數(shù)，若大于則報錯并返回，若不大于則繼續(xù)判斷它是否大于系統(tǒng)在此時刻可利用的資源數(shù)，同樣，如果大于則報錯并反回，如果不大于

66、則調(diào)用changedata( )函數(shù)來進(jìn)行預(yù)分配，之后再調(diào)用安全型算法safty檢查。</p><p>　　最后，無論此次分配是否成功，我們都可以選擇繼續(xù)分配或者退出系統(tǒng)。</p><p><b>　　安全性檢測。</b></p><p>　　首先，F(xiàn)inish[]為布爾型，默認(rèn)是False，即該進(jìn)程未完成。而Work——即該系統(tǒng)中可以用來工作

67、的資源數(shù)——最開始為系統(tǒng)最初可以用的資源數(shù)。</p><p>　　然后，我們從第一個進(jìn)程開始判斷該進(jìn)程未完成且其所需求的資源量不大于該系統(tǒng)中可以用來工作的資源量這個條件是否成立，即Finish[]=False且Need[][]<=Work[]是否成立。成立的話則將當(dāng)前在工作的資源量與該進(jìn)程已分配的資源量相加，存放于當(dāng)前可用來工作的資源量當(dāng)中，即Work[]=Work[]+Allocation，并將Finis

68、h[]的值改為True。</p><p>　　否則便將此進(jìn)程的優(yōu)先級減一，排在隊位，然后開始往后循環(huán)。</p><p>　　待所有的進(jìn)程循環(huán)完畢，我們再次判斷是否還存在進(jìn)程的Finish[]=False，如果仍存在，則說明系統(tǒng)沒有安全序列，處于不安全狀態(tài)，不可以進(jìn)行分配；否則，系統(tǒng)處于安全狀態(tài)，將預(yù)分配變?yōu)閷嶋H分配，求出安全序列并且將實際分配后的資源分配情況打印輸出。</p>

69、<p>　　總之，銀行家算法是避免死鎖的主要方法，其思路在很多方面都非常值得我們來學(xué)習(xí)借鑒。</p><p><b>　　參考文獻(xiàn)</b></p><p>　　湯小丹，梁紅兵，哲鳳屏，湯子瀛.計算機(jī)操作系統(tǒng). 西安：西安電子科技大學(xué)出版社，2007.</p><p>　　嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu). 北京：清華大學(xué)出版社，2006.