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

1、<p><b>　　目 錄</b></p><p>　　第一章 功能需求描述2</p><p>　　1.1功能列表與說明2</p><p>　　1.2操作界面和操作方法2</p><p>　　第二章 設(shè)計描述3</p><p>　　2.1任務(wù)分解說明3</p>

2、;<p>　　2.2主要數(shù)據(jù)結(jié)構(gòu)設(shè)計說明3</p><p>　　2.3主要函數(shù)接口設(shè)計說明3</p><p>　　第三章 算法描述5</p><p>　　第四章 開發(fā)過程描述14</p><p>　　4.1程序代碼14</p><p>　　4.2設(shè)計中的問題和解決方法23</p

3、><p>　　4.3測試用例和測試方法24</p><p>　　第五章 設(shè)計心得體會32</p><p>　　計算機科學(xué)與技術(shù)學(xué)院</p><p><b>　　課程設(shè)計任務(wù)書</b></p><p>　　第一章 功能需求描述</p><p>　　1.1功能列表與說明<

4、;/p><p>　　添加進程：規(guī)定現(xiàn)在操作系統(tǒng)中運行的進程數(shù)。</p><p>　　添加資源：規(guī)定當(dāng)前需要資源的種類數(shù)和各種類資源的數(shù)目。</p><p>　　分配資源：給各進程分配資源。</p><p>　　安全性檢查：檢查資源分配后是否會發(fā)生死鎖，若發(fā)生則不這樣進行分配。</p><p>　　資源釋放：當(dāng)一個進程結(jié)束后

5、釋放其所占有的各類資源。</p><p>　　得到安全序列：當(dāng)資源分配能夠保證各進程順利結(jié)束，則得到進程的安全序列。</p><p>　　刪除資源：即取消某資源</p><p>　　1.2操作界面和操作方法</p><p>　　*************銀行家算法演示****************</p><p>　

6、　請首先輸入系統(tǒng)可供資源種類的數(shù)量:</p><p><b>　　資源*的名稱：</b></p><p><b>　　資源的數(shù)量：</b></p><p><b>　　請輸入作業(yè)的數(shù)量：</b></p><p>　　請輸入各進程的最大需求量：</p><p&

7、gt;　　請輸入各進程已經(jīng)申請的資源量：</p><p><b>　　系統(tǒng)目前可用資源：</b></p><p><b>　　系統(tǒng)是否安全？</b></p><p><b>　　分配的序列：</b></p><p>　　********銀行家算法演示***********<

8、;/p><p><b>　　1：增加資源</b></p><p><b>　　2：刪除資源</b></p><p><b>　　3：修改資源</b></p><p><b>　　4：分配資源</b></p><p><b>　

9、　5：增加作業(yè)</b></p><p><b>　　0：離開</b></p><p>　　在如上的操作界面中分別按照提示進行輸入，按回車鍵表示當(dāng)前輸入完畢，然后進行下個步驟的輸入或者得到最終結(jié)果。</p><p><b>　　第二章 設(shè)計描述</b></p><p><b>

10、　　2.1任務(wù)分解說明</b></p><p>　　銀行家算法的實現(xiàn)過程主要分為以下幾個部分：為實現(xiàn)銀行家算法，系統(tǒng)中必須設(shè)置若干數(shù)據(jù)結(jié)構(gòu)。其中有allocation，記錄已經(jīng)分配的系統(tǒng)資源；max，記錄每個進程的資源最大需求；available，記錄剩余資源；need用來記錄現(xiàn)在每個進程需要多少資源，need=max-allocation；request 請求資源；temp，記錄路徑，即輸出的順序；

11、finish，用來實現(xiàn)循環(huán)，以判斷是否安全，這也就是安全性檢查。</p><p>　　2.2主要數(shù)據(jù)結(jié)構(gòu)設(shè)計說明</p><p>　　#define False 0</p><p>　　#define True 1</p><p>　　int Max[100][100]={0};//各進程所需各類資源的最大需求</p><

12、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&g

13、t;　　int Request[100]={0};//請求資源向量</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;//資源的最大數(shù)

14、為100</p><p>　　void showdata()//顯示資源矩陣</p><p>　　采用了二維數(shù)組來創(chuàng)建的數(shù)據(jù)結(jié)構(gòu)。</p><p>　　2.3主要函數(shù)接口設(shè)計說明</p><p>　?。?）void showdata() 顯示資源矩陣</p><p>　?。?）int changdata(int i

15、) 進行資源分配</p><p>　?。?）int safe() 安全性算法</p><p>　　（4）void share() 利用銀行家算法對申請資源對進行判定</p><p>　?。?）void addresources() 添加資源</p><p>　?。?）void delresources() 刪除資源</p>

16、;<p>　　（7）void changeresources() 修改資源函數(shù)</p><p>　?。?）void addprocess() 添加作業(yè)</p><p>　　第三章 算法描述</p><p><b>　　主函數(shù)流程圖</b></p><p>　　圖3-1 主函數(shù)流程圖</p

17、><p>　　顯示資源矩陣showdata函數(shù)流程圖</p><p>　　圖3-2 showdata函數(shù)流程圖</p><p>　　資源分配changedata函數(shù)流程圖</p><p>　　圖3-3 changedata函數(shù)流程圖</p><p>　　安全性檢查safe函數(shù)流程圖</p>

18、<p>　　圖3-4 safe函數(shù)流程圖</p><p>　　利用銀行家算法對進程申請資源進行判定share函數(shù)流程圖</p><p>　　圖3-5 share函數(shù)流程圖</p><p>　　添加資源的addresources函數(shù)流程圖</p><p>　　圖3-6 addresources函數(shù)流程圖</p&

19、gt;<p>　　刪除資源delresources函數(shù)流程圖</p><p>　　圖3-7 delresources函數(shù)流程圖</p><p>　　修改資源changeresources函數(shù)流程圖</p><p>　　圖3-8 changeresources函數(shù)流程圖</p><p>　　添加進程作業(yè)addproce

20、ss函數(shù)流程圖</p><p>　　圖3-9 addprocess函數(shù)流程圖</p><p>　　第四章 開發(fā)過程描述</p><p><b>　　4.1程序代碼</b></p><p>　　#include<iostream.h></p><p>　　#include<s

21、tring.h></p><p>　　#include<stdio.h></p><p>　　#define False 0</p><p>　　#define True 1</p><p>　　int Max[100][100]={0};//各進程所需各類資源的最大需求</p><p>　　int

22、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>　　int Req

23、uest[100]={0};//請求資源向量</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;//資源的最大數(shù)為100</p&

24、gt;<p>　　void showdata()//顯示資源矩陣</p><p><b>　　{</b></p><p><b>　　int i,j;</b></p><p>　　cout<<"系統(tǒng)目前可用的資源[Avaliable]:"<<endl;</p&

25、gt;<p>　　for(i=0;i<N;i++)</p><p>　　cout<<name[i]<<" ";</p><p>　　cout<<endl;</p><p>　　for (j=0;j<N;j++)</p><p>　　cout<<Ava

26、liable[j]<<" ";//輸出分配資源</p><p>　　cout<<endl;</p><p>　　cout<<" Max Allocation Need"<<endl;</p><p>　　cout<<"

27、;進程名 ";</p><p>　　for(j=0;j<3;j++){</p><p>　　for(i=0;i<N;i++)</p><p>　　cout<<name[i]<<" ";</p><p>　　cout<<" ";

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

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

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

31、gt;<p>　　cout<<endl;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　int changdata(int i)//進行資源分配</p><p><b>　　{ </b></p

32、><p><b>　　int j;</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];</

33、p><p>　　Need[i][j]=Need[i][j]-Request[j];</p><p><b>　　}</b></p><p><b>　　return 1;</b></p><p><b>　　}</b></p><p>　　int safe(

34、)//安全性算法</p><p><b>　　{</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]

35、=Avaliable[0];</p><p>　　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>　　f

36、or(j=0;j<N;j++){</p><p>　　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<

37、;N;m++)</p><p>　　Work[m]=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>　　

38、k++;</b></p><p><b>　　flag++;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b&g

39、t;　　}</b></p><p>　　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>

40、<p><b>　　}</b></p><p><b>　　}</b></p><p>　　cout<<"系統(tǒng)是安全的!"<<endl;//如果安全，輸出成功</p><p>　　cout<<"分配的序列:";</p>

41、<p>　　for(i=0;i<M;i++){//輸出運行進程數(shù)組</p><p>　　cout<<temp[i];</p><p>　　if(i<M-1) cout<<"->";</p><p><b>　　}</b></p><p>　　cout

42、<<endl;</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　void share()//利用銀行家算法對申請資源對進行判定</p><p><b>　　{</b></p><

43、p><b>　　char ch;</b></p><p>　　int i=0,j=0;</p><p><b>　　ch='y';</b></p><p>　　cout<<"請輸入要求分配的資源進程號(0-"<<M-1<<"):&quo

44、t;; </p><p>　　cin>>i;//輸入須申請的資源號</p><p>　　cout<<"請輸入進程 "<<i<<" 申請的資源:"<<endl;</p><p>　　for(j=0;j<N;j++)</p><p><

45、b>　　{</b></p><p>　　cout<<name[j]<<":";</p><p>　　cin>>Request[j];//輸入需要申請的資源</p><p><b>　　}</b></p><p>　　for (j=0;j<N;

46、j++){</p><p>　　if(Request[j]>Need[i][j])//判斷申請是否大于需求，若大于則出錯</p><p><b>　　{ </b></p><p>　　cout<<"進程 "<<i<<"申請的資源大于它需要的資源";</p&g

47、t;<p>　　cout<<" 分配不合理，不予分配！"<<endl;</p><p><b>　　ch='n';</b></p><p><b>　　break;</b></p><p><b>　　}</b></p&g

48、t;<p><b>　　else {</b></p><p>　　if(Request[j]>Avaliable[j])//判斷申請是否大于當(dāng)前資源，若大于則</p><p>　　{ //出錯</p><p>　　cout<<"進程"<&l

49、t;i<<"申請的資源大于系統(tǒng)現(xiàn)在可利用的資源";</p><p>　　cout<<" 分配出錯，不予分配!"<<endl;</p><p><b>　　ch='n';</b></p><p><b>　　break;</b><

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

51、lt;/p><p>　　showdata();//根據(jù)進程需求量顯示變換后的資源</p><p>　　safe();//根據(jù)進程需求量進行銀行家算法判斷</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void addresou

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

53、><p><b>　　N=N+n;</b></p><p>　　for(int i=0;i<n;i++){</p><p>　　cout<<"名稱:";</p><p>　　cin>>name[flag];</p><p>　　cout<<

54、"數(shù)量:";</p><p>　　cin>>Avaliable[flag++];</p><p><b>　　}</b></p><p>　　showdata();</p><p><b>　　safe();</b></p><p><b

55、>　　}</b></p><p>　　void delresources(){//刪除資源</p><p>　　char ming;</p><p>　　int i,flag=1;</p><p>　　cout<<"請輸入需要刪除的資源名稱：";</p><p><

56、;b>　　do{</b></p><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&g

57、t;　　break;</b></p><p><b>　　}</b></p><p><b>　　if(i==N)</b></p><p>　　cout<<"該資源名稱不存在，請重新輸入：";</p><p><b>　　}</b>&

58、lt;/p><p>　　while(flag);</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];<

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

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

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

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

63、gt;<p>　　showdata();</p><p><b>　　safe();</b></p><p><b>　　}</b></p><p>　　void addprocess(){//添加作業(yè)</p><p>　　int flag=M;</p><p>

64、;<b>　　M=M+1;</b></p><p>　　cout<<"請輸入該作業(yè)的最打需求量[Max]"<<endl;</p><p>　　for(int i=0;i<N;i++){</p><p>　　cout<<name[i]<<":";<

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

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

67、char ming;</p><p>　　cout<<"*****************銀行家算法的實現(xiàn)*****************"<<endl;</p><p>　　cout<<"請首先輸入系統(tǒng)可供資源種類的數(shù)量:";</p><p><b>　　cin>>

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

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

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

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

72、;p>　　for(j=0;j<n;j++)</p><p>　　cin>>Max[i][j];</p><p><b>　　do{</b></p><p><b>　　flag=0;</b></p><p>　　cout<<"請輸入各進程已經(jīng)申請的資源量

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

74、tion[i][j];</p><p>　　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>

75、</p><p><b>　　if(flag)</b></p><p>　　cout<<"申請的資源大于最大需求量，請重新輸入!\n";</p><p><b>　　}</b></p><p>　　while(flag);</p><p>　　

76、showdata();//顯示各種資源</p><p>　　safe();//用銀行家算法判定系統(tǒng)是否安全</p><p>　　while(choice)</p><p><b>　　{</b></p><p>　　cout<<"**************銀行家算法演示**************

77、*"<<endl;</p><p>　　cout<<" 1:增加資源 "<<endl;</p><p>　　cout<<" 2:刪除資源 "<<endl;</p><p>　　cout<

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

79、endl;</p><p>　　cout<<" 0:離開 "<<endl;</p><p>　　cout<<"*******************************************"<<endl;</p><p>　　co

80、ut<<"請選擇功能號：";</p><p>　　cin>>choice;</p><p>　　switch(choice)</p><p><b>　　{</b></p><p>　　case 1: addresources();break;</p><p

81、>　　case 2: delresources();break;</p><p>　　case 3: changeresources();break;</p><p>　　case 4: share();break;</p><p>　　case 5: addprocess();break;</p><p>　　case 0: choi

82、ce=0;break;</p><p>　　default: cout<<"請正確選擇功能號(0-5)!"<<endl;break;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　re

83、turn 1;</b></p><p><b>　　}</b></p><p>　　4.2設(shè)計中的問題和解決方法</p><p>　　在測試時，出現(xiàn)了很多漏掉標(biāo)點符號的錯誤，比較典型的一個就是在中文輸入法下輸入了標(biāo)點符號，導(dǎo)致出錯。同時在main函數(shù)中應(yīng)該有一個int類型的返回值，忽略了這個細節(jié)導(dǎo)致了產(chǎn)生了警告。</p>

84、<p>　　圖4-1 編譯出錯圖</p><p>　　修改了這些錯誤之后，進行編譯，顯示編譯正確，如圖</p><p>　　圖4-2 修改后調(diào)試成功圖</p><p>　　4.3測試用例和測試方法</p><p>　　測試方法即為輸入多個實例，進行測試，測試數(shù)據(jù)在此只列出一個，如圖所示。</p><p

85、>　　T0 時刻的資源分配表(各種資源的數(shù)量分別為：10、5、7)</p><p>　　表4-1 輸入實例表</p><p>　　圖4-3 測試程序圖 1</p><p>　　圖 4-4 測試程序圖 2</p><p>　　圖 4 -5 測試程序圖 3</p><p>　　圖 4 - 6 測試程

86、序圖 4</p><p>　　圖4 - 7 測試程序圖 5</p><p>　　圖 4 - 8 測試程序圖 6</p><p>　　圖 4 - 9 測試程序圖 7</p><p><b>　　設(shè)計心得體會</b></p><p>　　“課程設(shè)計是培養(yǎng)學(xué)生綜合運用所學(xué)知識、發(fā)現(xiàn)、提出、分析和解決實際

87、問題,鍛煉實踐能力的重要環(huán)節(jié),是對學(xué)生實際工作能力的具體訓(xùn)練和考察過程?！?在這次課程設(shè)計的過程中，我深深地體會到了理論與實踐結(jié)合的過程，當(dāng)實踐成功時的成就感，從整個過程中我受益匪淺。</p><p>　　從確定了題目，一直到完成整個大作業(yè)，我學(xué)到很多的東西。不僅可以鞏固了以前所學(xué)過的知識，并且發(fā)掘了很多在已有的書本上所沒有的知識，給我?guī)砹藰O大的收獲。</p><p>　　對銀行家算法有

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

89、進程，即其中每一個進程分別等待它前一個進程所持有的資源。防止死鎖的機構(gòu)只能確保上述四個條件之一不出現(xiàn)，則系統(tǒng)就不會發(fā)生死鎖。</p><p>　　至今我感慨頗多的應(yīng)當(dāng)是一些難以查出的錯誤，編譯時查不出的錯誤，其被發(fā)現(xiàn)時很可能只是位置的錯誤，僅隔數(shù)行，這些微小的信息卻極大地影響了整體的效果。這不僅存在于一個程序之中，因而我對于生活中的細節(jié)也有了改觀，對于整體和局部的觀念也有了更多的見解。</p>&l