課程設(shè)計(jì)---銀行家算法實(shí)驗(yàn)報(bào)告

1、<p>　　計(jì)算機(jī)學(xué)院《操作系統(tǒng)》課程設(shè)計(jì)報(bào)告</p><p>　　設(shè)計(jì)題目：銀行家算法的實(shí)現(xiàn)</p><p>　　銀行家算法分析、設(shè)計(jì)與實(shí)現(xiàn)</p><p><b>　　設(shè)計(jì)理論描述</b></p><p>　　本設(shè)計(jì)的目的是通過(guò)編寫(xiě)和調(diào)試一個(gè)系統(tǒng)動(dòng)態(tài)分配資源的簡(jiǎn)單模擬程序，觀察死鎖產(chǎn)生的條件，并采用適當(dāng)?shù)乃?/p>

2、法，有效地防止和避免死鎖地發(fā)生。要求如下：</p><p>　?。?） 模擬一個(gè)銀行家算法；</p><p>　?。?） 初始化時(shí)讓系統(tǒng)擁有一定的資源；</p><p>　?。?） 用鍵盤輸入的方式申請(qǐng)資源；</p><p>　?。?） 如果預(yù)分配后，系統(tǒng)處于安全狀態(tài)，則修改系統(tǒng)的資源分配情況；<

3、/p><p>　?。?） 如果預(yù)分配后，系統(tǒng)處于不安全狀態(tài)，則提示不能滿足請(qǐng)求，</p><p>　　設(shè)計(jì)的主要內(nèi)容是模擬實(shí)現(xiàn)動(dòng)態(tài)資源分配。同時(shí)編寫(xiě)和調(diào)試一個(gè)系統(tǒng)動(dòng)態(tài)資源的簡(jiǎn)單模擬程序，觀察死鎖產(chǎn)生的條件，并使用適當(dāng)?shù)乃惴?，有效的防止和避免死鎖的發(fā)生。</p><p>　　銀行家算法. 顧名思義是來(lái)源于銀行的借貸業(yè)務(wù)，一定數(shù)量的本金要應(yīng)多個(gè)客戶的借貸周轉(zhuǎn)，為了

4、防止銀行加資金無(wú)法周轉(zhuǎn)而倒閉，對(duì)每一筆貸款，必須考察其是否能限期歸還。在操作系統(tǒng)中研究資源分配策略時(shí)也有類似問(wèn)題，系統(tǒng)中有限的資源要供多個(gè)進(jìn)程使用，必須保證得到的資源的進(jìn)程能在有限的時(shí)間內(nèi)歸還資源，以供其他進(jìn)程使用資源。如果資源分配不得到就會(huì)發(fā)生進(jìn)程循環(huán)等待資源，則進(jìn)程都無(wú)法繼續(xù)執(zhí)行下去的死鎖現(xiàn)象。</p><p>　　把一個(gè)進(jìn)程需要和已占有資源的情況記錄在進(jìn)程控制中，假定進(jìn)程控制塊PCB其中“狀態(tài)”有就緒態(tài)、等

5、待態(tài)和完成態(tài)。當(dāng)進(jìn)程在處于等待態(tài)時(shí)，表示系統(tǒng)不能滿足該進(jìn)程當(dāng)前的資源申請(qǐng)。“資源需求總量”表示進(jìn)程在整個(gè)執(zhí)行過(guò)程中總共要申請(qǐng)的資源量。顯然，，每個(gè)進(jìn)程的資源需求總量不能超過(guò)系統(tǒng)擁有的資源總數(shù), 銀行算法進(jìn)行資源分配可以避免死鎖.</p><p>　　二、算法描述及數(shù)據(jù)結(jié)構(gòu)模型</p><p>　　1.銀行家算法: 設(shè)進(jìn)程i提出請(qǐng)求Request[n]，則銀行家算法按如下規(guī)則進(jìn)行判斷。

6、(1)如果Request[n]>Need[i，n]，則報(bào)錯(cuò)返回。 (2)如果Request[n]>Available，則進(jìn)程i進(jìn)入等待資源狀態(tài)，返回。 (3)假設(shè)進(jìn)程i的申請(qǐng)已獲批準(zhǔn)，于是修改系統(tǒng)狀態(tài)： Available=Available-Request Allocation=Allocation+Request Need=Need-Request(4)系統(tǒng)執(zhí)行安全性檢查，如安全，則分配

7、成立；否則試探險(xiǎn)性分配作廢，系統(tǒng)恢復(fù)原狀，進(jìn)程等待。 2.安全性檢查 (1)設(shè)置兩個(gè)工作向量Work=Available；Finish[M]=False(2)從進(jìn)程集合中找到一個(gè)滿足下述條件的進(jìn)程， Finish [i]=False Need<=Work 如找到，執(zhí)行(3)；否則，執(zhí)行(4) (3)設(shè)進(jìn)程獲得資源，可順利執(zhí)行，直至完成，從而釋放資源。 Work=Work+Allocation

8、 Finish=True </p><p><b>　　3.數(shù)據(jù)結(jié)構(gòu)</b></p><p>　　#define False 0</p><p>　　#define True 1</p><p>　　int Max[100][100]={0};//各進(jìn)程所需各類資源的最大需求</p>&l

9、t;p>　　int Avaliable[100]={0};//系統(tǒng)可用資源</p><p>　　char name[100]={0};//資源的名稱</p><p>　　int Allocation[100][100]={0};//系統(tǒng)已分配資源</p><p>　　int Need[100][100]={0};//還需要資源</p><p

10、>　　int Request[100]={0};//請(qǐng)求資源向量</p><p>　　int temp[100]={0};//存放安全序列</p><p>　　int Work[100]={0};//存放系統(tǒng)可提供資源</p><p>　　int M=100;//作業(yè)的最大數(shù)為100</p><p>　　int N=100;//資源的最

11、大數(shù)為100</p><p>　　void showdata()//顯示資源矩陣</p><p><b>　　三、源代碼</b></p><p>　　#include<iostream.h></p><p>　　#include<string.h></p><p>　　#i

12、nclude<stdio.h></p><p>　　#define False 0</p><p>　　#define True 1</p><p>　　int Max[100][100]={0};//各進(jìn)程所需各類資源的最大需求</p><p>　　int Avaliable[100]={0};//系統(tǒng)可用資源</p>

13、;<p>　　char name[100]={0};//資源的名稱</p><p>　　int Allocation[100][100]={0};//系統(tǒng)已分配資源</p><p>　　int Need[100][100]={0};//還需要資源</p><p>　　int Request[100]={0};//請(qǐng)求資源向量</p>&l

14、t;p>　　int temp[100]={0};//存放安全序列</p><p>　　int Work[100]={0};//存放系統(tǒng)可提供資源</p><p>　　int M=100;//作業(yè)的最大數(shù)為100</p><p>　　int N=100;//資源的最大數(shù)為100</p><p>　　void showdata()//顯示資

15、源矩陣</p><p><b>　　{</b></p><p><b>　　int i,j;</b></p><p>　　cout<<"系統(tǒng)目前可用的資源[Avaliable]:"<<endl;</p><p>　　for(i=0;i<N;i++)&

16、lt;/p><p>　　cout<<name[i]<<" ";</p><p>　　cout<<endl;</p><p>　　for (j=0;j<N;j++)</p><p>　　cout<<Avaliable[j]<<" ";//輸出分

17、配資源</p><p>　　cout<<endl;</p><p>　　cout<<" Max Allocation Need"<<endl;</p><p>　　cout<<"進(jìn)程名 ";</p><p&g

18、t;　　for(j=0;j<3;j++){</p><p>　　for(i=0;i<N;i++)</p><p>　　cout<<name[i]<<" ";</p><p>　　cout<<" ";</p><p><b>　　}<

19、;/b></p><p>　　cout<<endl;</p><p>　　for(i=0;i<M;i++){</p><p>　　cout<<" "<<i<<" ";</p><p>　　for(j=0;j<N;j++)&

20、lt;/p><p>　　cout<<Max[i][j]<<" ";</p><p>　　cout<<" ";</p><p>　　for(j=0;j<N;j++)</p><p>　　cout<<Allocation[i][j]<<

21、" ";</p><p>　　cout<<" ";</p><p>　　for(j=0;j<N;j++)</p><p>　　cout<<Need[i][j]<<" ";</p><p>　　cout<<endl;<

22、;/p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　int changdata(int i)//進(jìn)行資源分配</p><p><b>　　{ </b></p><p><b>　　int j;<

23、/b></p><p>　　for (j=0;j<M;j++) {</p><p>　　Avaliable[j]=Avaliable[j]-Request[j];</p><p>　　Allocation[i][j]=Allocation[i][j]+Request[j];</p><p>　　Need[i][j]=Need[i]

24、[j]-Request[j];</p><p><b>　　}</b></p><p><b>　　return 1;</b></p><p><b>　　}</b></p><p>　　int safe()//安全性算法</p><p><b&g

25、t;　　{</b></p><p>　　int i,k=0,m,apply,Finish[100]={0};</p><p><b>　　int j;</b></p><p>　　int flag=0;</p><p>　　Work[0]=Avaliable[0];</p><p>　

26、　Work[1]=Avaliable[1];</p><p>　　Work[2]=Avaliable[2];</p><p>　　for(i=0;i<M;i++){ </p><p><b>　　apply=0;</b></p><p>　　for(j=0;j<N;j++){</p><p

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

28、]=Work[m]+Allocation[i][m];//變分配數(shù)</p><p>　　Finish[i]=True;</p><p>　　temp[k]=i;</p><p><b>　　i=-1; </b></p><p><b>　　k++;</b></p><p>&

29、lt;b>　　flag++;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>

30、　　for(i=0;i<M;i++){</p><p>　　if(Finish[i]==False){</p><p>　　cout<<"系統(tǒng)不安全"<<endl;//不成功系統(tǒng)不安全</p><p>　　return -1;</p><p><b>　　}</b><

31、;/p><p><b>　　}</b></p><p>　　cout<<"系統(tǒng)是安全的!"<<endl;//如果安全，輸出成功</p><p>　　cout<<"分配的序列:";</p><p>　　for(i=0;i<M;i++){//輸出運(yùn)

32、行進(jìn)程數(shù)組</p><p>　　cout<<temp[i];</p><p>　　if(i<M-1) cout<<"->";</p><p><b>　　}</b></p><p>　　cout<<endl;</p><p>&l

33、t;b>　　return 0;</b></p><p><b>　　}</b></p><p>　　void share()//利用銀行家算法對(duì)申請(qǐng)資源對(duì)進(jìn)行判定</p><p><b>　　{</b></p><p><b>　　char ch;</b>&l

34、t;/p><p>　　int i=0,j=0;</p><p><b>　　ch='y';</b></p><p>　　cout<<"請(qǐng)輸入要求分配的資源進(jìn)程號(hào)(0-"<<M-1<<"):"; </p><p>　　cin>&g

35、t;i;//輸入須申請(qǐng)的資源號(hào)</p><p>　　cout<<"請(qǐng)輸入進(jìn)程 "<<i<<" 申請(qǐng)的資源:"<<endl;</p><p>　　for(j=0;j<N;j++)</p><p><b>　　{</b></p><p&

36、gt;　　cout<<name[j]<<":";</p><p>　　cin>>Request[j];//輸入需要申請(qǐng)的資源</p><p><b>　　}</b></p><p>　　for (j=0;j<N;j++){</p><p>　　if(Reque

37、st[j]>Need[i][j])//判斷申請(qǐng)是否大于需求，若大于則出錯(cuò)</p><p><b>　　{ </b></p><p>　　cout<<"進(jìn)程 "<<i<<"申請(qǐng)的資源大于它需要的資源";</p><p>　　cout<<" 分配

38、不合理，不予分配！"<<endl;</p><p><b>　　ch='n';</b></p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　else {</b

39、></p><p>　　if(Request[j]>Avaliable[j])//判斷申請(qǐng)是否大于當(dāng)前資源，若大于則</p><p>　　{ //出錯(cuò)</p><p>　　cout<<"進(jìn)程"<<i<<"申請(qǐng)的資源大于系統(tǒng)現(xiàn)在可利用的資源&q

40、uot;;</p><p>　　cout<<" 分配出錯(cuò)，不予分配!"<<endl;</p><p><b>　　ch='n';</b></p><p><b>　　break;</b></p><p><b>　　}</b

41、></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　if(ch=='y') {</p><p>　　changdata(i);//根據(jù)進(jìn)程需求量變換資源</p><p>　　showdata();//根

42、據(jù)進(jìn)程需求量顯示變換后的資源</p><p>　　safe();//根據(jù)進(jìn)程需求量進(jìn)行銀行家算法判斷</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void addresources(){//添加資源</p><p>　　

43、int n,flag;</p><p>　　cout<<"請(qǐng)輸入需要添加資源種類的數(shù)量:";</p><p><b>　　cin>>n;</b></p><p><b>　　flag=N;</b></p><p><b>　　N=N+n;<

44、/b></p><p>　　for(int i=0;i<n;i++){</p><p>　　cout<<"名稱:";</p><p>　　cin>>name[flag];</p><p>　　cout<<"數(shù)量:";</p><p>

45、;　　cin>>Avaliable[flag++];</p><p><b>　　}</b></p><p>　　showdata();</p><p><b>　　safe();</b></p><p><b>　　}</b></p><p&g

46、t;　　void delresources(){//刪除資源</p><p>　　char ming;</p><p>　　int i,flag=1;</p><p>　　cout<<"請(qǐng)輸入需要?jiǎng)h除的資源名稱：";</p><p><b>　　do{</b></p><

47、;p>　　cin>>ming;</p><p>　　for(i=0;i<N;i++)</p><p>　　if(ming==name[i]){</p><p><b>　　flag=0;</b></p><p><b>　　break;</b></p><

48、p><b>　　}</b></p><p><b>　　if(i==N)</b></p><p>　　cout<<"該資源名稱不存在，請(qǐng)重新輸入：";</p><p><b>　　}</b></p><p>　　while(flag);&l

49、t;/p><p>　　for(int j=i;j<N-1;j++)</p><p><b>　　{</b></p><p>　　name[j]=name[j+1];</p><p>　　Avaliable[j]=Avaliable[j+1];</p><p><b>　　}</b

50、></p><p><b>　　N=N-1;</b></p><p>　　showdata();</p><p><b>　　safe();</b></p><p><b>　　}</b></p><p>　　void changeresource

51、s(){//修改資源函數(shù)</p><p>　　cout<<"系統(tǒng)目前可用的資源[Avaliable]:"<<endl;</p><p>　　for(int i=0;i<N;i++)</p><p>　　cout<<name[i]<<":"<<Avaliable[

52、i]<<endl;</p><p>　　cout<<"輸入系統(tǒng)可用資源[Avaliable]:"<<endl;</p><p>　　cin>>Avaliable[0]>>Avaliable[1]>>Avaliable[2];</p><p>　　cout<<&qu

53、ot;經(jīng)修改后的系統(tǒng)可用資源為"<<endl;</p><p>　　for (int k=0;k<N;k++)</p><p>　　cout<<name[k]<<":"<<Avaliable[k]<<endl;</p><p>　　showdata();</p>

54、;<p><b>　　safe();</b></p><p><b>　　}</b></p><p>　　void addprocess(){//添加作業(yè)</p><p>　　int flag=M;</p><p><b>　　M=M+1;</b></p&g

55、t;<p>　　cout<<"請(qǐng)輸入該作業(yè)的最打需求量[Max]"<<endl;</p><p>　　for(int i=0;i<N;i++){</p><p>　　cout<<name[i]<<":";</p><p>　　cin>>Max[fl

56、ag][i];</p><p>　　Need[flag][i]=Max[flag][i]-Allocation[flag][i];</p><p><b>　　}</b></p><p>　　showdata();</p><p><b>　　safe();</b></p><p

57、><b>　　}</b></p><p>　　int main()//主函數(shù)</p><p><b>　　{</b></p><p>　　int i,j,number,choice,m,n,flag;</p><p>　　char ming;</p><p>　　cou

58、t<<"*****************單處理機(jī)系統(tǒng)進(jìn)程調(diào)度實(shí)現(xiàn)*****************"<<endl;</p><p>　　cout<<"請(qǐng)首先輸入系統(tǒng)可供資源種類的數(shù)量:";</p><p><b>　　cin>>n;</b></p><p>

59、;<b>　　N=n;</b></p><p>　　for(i=0;i<n;i++)</p><p><b>　　{</b></p><p>　　cout<<"資源"<<i+1<<"的名稱:";</p><p>　　c

60、in>>ming;</p><p>　　name[i]=ming;</p><p>　　cout<<"資源的數(shù)量:";</p><p>　　cin>>number;</p><p>　　Avaliable[i]=number;</p><p><b>　

61、　}</b></p><p>　　cout<<endl;</p><p>　　cout<<"請(qǐng)輸入作業(yè)的數(shù)量:";</p><p><b>　　cin>>m;</b></p><p><b>　　M=m;</b></p>

62、<p>　　cout<<"請(qǐng)輸入各進(jìn)程的最大需求量("<<m<<"*"<<n<<"矩陣)[Max]:"<<endl;</p><p>　　for(i=0;i<m;i++)</p><p>　　for(j=0;j<n;j++)</

63、p><p>　　cin>>Max[i][j];</p><p><b>　　do{</b></p><p><b>　　flag=0;</b></p><p>　　cout<<"請(qǐng)輸入各進(jìn)程已經(jīng)申請(qǐng)的資源量("<<m<<"*&

64、quot;<<n<<"矩陣)[Allocation]:"<<endl;</p><p>　　for(i=0;i<m;i++)</p><p>　　for(j=0;j<n;j++){</p><p>　　cin>>Allocation[i][j];</p><p>

65、　　if(Allocation[i][j]>Max[i][j])</p><p><b>　　flag=1;</b></p><p>　　Need[i][j]=Max[i][j]-Allocation[i][j];</p><p><b>　　}</b></p><p><b>　　

66、if(flag)</b></p><p>　　cout<<"申請(qǐng)的資源大于最大需求量，請(qǐng)重新輸入!\n";</p><p><b>　　}</b></p><p>　　while(flag);</p><p>　　showdata();//顯示各種資源</p>&

67、lt;p>　　safe();//用銀行家算法判定系統(tǒng)是否安全</p><p>　　while(choice)</p><p><b>　　{</b></p><p>　　cout<<"**************銀行家算法演示***************"<<endl;</p>

68、<p>　　cout<<" 1:增加資源 "<<endl;</p><p>　　cout<<" 2:刪除資源 "<<endl;</p><p>　　cout<<" 3:修改資源

69、 "<<endl;</p><p>　　cout<<" 4:分配資源 "<<endl;</p><p>　　cout<<" 5:增加作業(yè) "<<endl;</p><p>　　cout

70、<<" 0:離開(kāi) "<<endl;</p><p>　　cout<<"*******************************************"<<endl;</p><p>　　cout<<"請(qǐng)選擇功能號(hào)：";&l

71、t;/p><p>　　cin>>choice;</p><p>　　switch(choice)</p><p><b>　　{</b></p><p>　　case 1: addresources();break;</p><p>　　case 2: delresources();bre

72、ak;</p><p>　　case 3: changeresources();break;</p><p>　　case 4: share();break;</p><p>　　case 5: addprocess();break;</p><p>　　case 0: choice=0;break;</p><p>

73、　　default: cout<<"請(qǐng)正確選擇功能號(hào)(0-5)!"<<endl;break;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　return 1;</b></p><

74、;p><b>　　}</b></p><p>　　四、程序運(yùn)行結(jié)果及分析</p><p>　　T0 時(shí)刻的資源分配表(各種資源的數(shù)量分別為：10、5、7)</p><p><b>　　運(yùn)行結(jié)果</b></p><p>　　五、課程設(shè)計(jì)心得與體會(huì)</p><p>　　銀行

75、家算法是避免死鎖的一種重要方法，通過(guò)編寫(xiě)一個(gè)簡(jiǎn)單的銀行家算法程序，加深了解有關(guān)資源申請(qǐng)、避免死鎖等概念，并體會(huì)和了解死鎖和避免死鎖的具體實(shí)施方法。死鎖的產(chǎn)生，必須同時(shí)滿足四個(gè)條件，即一個(gè)資源每次只能由一個(gè)進(jìn)程；第二個(gè)為等待條件，即一個(gè)進(jìn)程請(qǐng)求資源不能滿足時(shí)，它必須等待，但它仍繼續(xù)保持已得到的所有其他資源；第三個(gè)為非剝奪條件，即在出現(xiàn)死鎖的系統(tǒng)中一定有不可剝奪使用的資源；第四個(gè)為循環(huán)等待條件，系統(tǒng)中存在若干個(gè)循環(huán)等待的進(jìn)程，即其中每一個(gè)進(jìn)