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

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

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

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

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

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

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

7、全，則分配，否則，不分配，恢復(fù)原來(lái)狀態(tài)，拒絕申請(qǐng)。</p><p><b>　　設(shè)計(jì)步驟</b></p><p>　　1、為實(shí)現(xiàn)銀行家算法，系統(tǒng)中需要設(shè)置若干數(shù)據(jù)結(jié)構(gòu)，用來(lái)表示系統(tǒng)中各進(jìn)程的資源分配及需求情況。</p><p>　　假定系統(tǒng)中有M個(gè)進(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。這是一個(gè)含有m個(gè)元素的數(shù)組，其中的每一個(gè)元素代表一類資源的空閑資源數(shù)目，其初值是系統(tǒng)中所配置的該類資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動(dòng)態(tài)

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

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

11、4,3,3}};//每個(gè)進(jìn)程對(duì)每類資源的最大需求</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、實(shí)現(xiàn)過(guò)程</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("請(qǐng)輸入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輸入接下來(lái)你要進(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ù)操作有三個(gè)</p><p>　　showdata();//顯示資源矩陣</p><p>　　safeAlgorithm();//安全性檢測(cè)算法</p><p>　　bankerAlgorithm();//利用銀行家算法對(duì)申請(qǐng)資源對(duì)進(jìn)行判定</p><p><b&

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

19、是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開始時(shí)，F(xiàn)inish[i]＝false；當(dāng)有足夠的資源分配給進(jìn)程Pi時(shí)，令Finish[i]＝true。</p><p>　?。?） 從進(jìn)程集合中找到一個(gè)能滿足下列條件的進(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>　　此過(guò)程由一個(gè)安全性檢測(cè)函數(shù)實(shí)現(xiàn)：safeAlgorithm();//安全性檢測(cè)算法</p><p>　　4、對(duì)進(jìn)程申請(qǐng)資源的處理</p><p>　　當(dāng)某一進(jìn)程提出資源申請(qǐng)時(shí)，系統(tǒng)須做出判斷，能否將所申請(qǐng)資源分配

22、給該進(jìn)程。設(shè)request為進(jìn)程i的請(qǐng)求向量，如果request[j]=K，表示進(jìn)程i需要K個(gè)j資源。當(dāng)系統(tǒng)發(fā)出請(qǐng)求后，系統(tǒng)按下述步驟開始檢查： （1） 如果request[j]<=need[i][j],轉(zhuǎn)向步驟2；否則報(bào)告出錯(cuò)，申請(qǐng)的資源大于它需要的最大值。 （2） 如果request[j]<=available[j],轉(zhuǎn)向步驟3；否則報(bào)告出錯(cuò)，尚無(wú)足夠的資源。 （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ù)原來(lái)的資源

24、分配狀態(tài)，讓進(jìn)程i等待。整個(gè)過(guò)程由銀行家算法實(shí)現(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}}; //每個(gè)進(jìn)

26、程對(duì)每類資源的最大需求</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)//若符合條件則對(duì)第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ù)運(yùn)行的所需的各類資源數(shù)目</p><p>　　finish： 表示系統(tǒng)是否有足夠的資源分配給進(jìn)程</p><p>　　result用來(lái)存放依次執(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]; //開始的時(shí)候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++)//輸出運(yùn)行進(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()//利用銀行家算法對(duì)申請(qǐng)資源對(duì)進(jìn)行判定</p><p><b>　　{</b></p><p>　　int i,j,OK=1;</p><p>　　printf("\n請(qǐng)輸入第一個(gè)要求分

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

51、b>　　{</b></p><p>　　printf("第 %d 個(gè)資源:",j+1);</p><p>　　scanf("%d",&Request[j]);//輸入需要申請(qǐng)的資源</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])//判斷申請(qǐng)是否大于需求，若大于則出錯(cuò)</p><p><b>　　{ </b></p><p>　　printf("進(jìn)程 %d 申請(qǐng)的資源大于它

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])//判斷申請(qǐng)是否大于當(dāng)前資源，若大于則出錯(cuò)</p><p>　　{ </p><p&g

55、t;　　printf("進(jìn)程 %d 申請(qǐng)的資源大于當(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)程請(qǐng)求分配資源</p><p>　　showdata();//顯示變換后的資源</p><p>　　safeAlgorithm();//通過(guò)安全算法判斷該序列是否安全</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("請(qǐng)輸入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輸入接下來(lái)你要進(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、、實(shí)驗(yàn)結(jié)果</b></p><p><b>　　六、實(shí)驗(yàn)心得</b></p><p>　　在避免死鎖的方法中，允許進(jìn)程動(dòng)態(tài)地申請(qǐng)資源，系統(tǒng)在進(jìn)行資源分配之前，先計(jì)算資源分配的安全性。若此次分配不會(huì)導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)，便將資源分配給進(jìn)程，否則進(jìn)程等待。銀行家算法是死鎖避免算法中的一種，通過(guò)上面這個(gè)例子，我們看到銀行家算法確實(shí)能保證系統(tǒng)時(shí)時(shí)刻刻都處于安全狀

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

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

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

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

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

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