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

1、<p><b>　　課程設(shè)計(jì)報告</b></p><p><b>　　操作系統(tǒng)原理</b></p><p><b>　　———銀行家算法</b></p><p><b>　　銀行家算法</b></p><p><b>　　一、銀行家算法

2、原理</b></p><p>　　銀行家算法是一種最有代表性的避免死鎖的算法。要解釋銀行家算法，必須先解釋操作系統(tǒng)安全狀態(tài)和不安全狀態(tài)。</p><p>　　安全狀態(tài)：如果存在一個由系統(tǒng)中所有進(jìn)程構(gòu)成的安全序列P1，…，Pn，則系統(tǒng)處于安全狀態(tài)。安全狀態(tài)一定是沒有死鎖發(fā)生。</p><p>　　不安全狀態(tài):不存在一個安全序列。不安全狀態(tài)不一定導(dǎo)致死鎖。那

3、么什么是安全序列呢？</p><p>　　安全序列：一個進(jìn)程序列{P1，…，Pn}是安全的，如果對于每一個進(jìn)程Pi(1≤i≤n），它以后尚需要的資源量不超過系統(tǒng)當(dāng)前剩余資源量與所有進(jìn)程Pj (j < i ) 我們可以把操作系統(tǒng)看作是銀行家，操作系統(tǒng)管理的資源相當(dāng)于銀行家管理的資金，進(jìn)程向操作系統(tǒng)請求分配資源相當(dāng)于用戶向銀行家貸款。操作系統(tǒng)按照銀行家制定的規(guī)則為進(jìn)程分配資源，當(dāng)進(jìn)程首次申請資源時，要測

4、試該進(jìn)程對資源的最大需求量，如果系統(tǒng)現(xiàn)存的資源可以滿足它的最大需求量則按當(dāng)前的申請量分配資源，否則就推遲分配。當(dāng)進(jìn)程在執(zhí)行中繼續(xù)申請資源時，先測試該進(jìn)程已占用的資源數(shù)與本次申請的資源數(shù)之和是否超過了該進(jìn)程對資源的最大需求量。若超過則拒絕分配資源，若沒有超過則再測試系統(tǒng)現(xiàn)存的資源能否滿足該進(jìn)程尚需的最大資源量，若能滿足則按當(dāng)前的申請量分配資源，否則也要推遲分配。</p><p>　　在避免死鎖的方法中，所施加的限制

5、條件較弱，有可能獲得令人滿意的系統(tǒng)性能。在該方法中把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，只要能使系統(tǒng)始終都處于安全狀態(tài)，便可以避免發(fā)生死鎖。</p><p>　　銀行家算法的基本思想是分配資源之前,判斷系統(tǒng)是否是安全的;若是,才分配。它是最具有代表性的避免死鎖的算法。</p><p><b>　　二、算法的數(shù)據(jù)結(jié)構(gòu)</b></p><p>　　

6、（1）可利用資源向量Available</p><p>　　是個含有m個元素的數(shù)組，其中的每一個元素代表一類可利用的資源數(shù)目。如果Available[j]=K，則表示系統(tǒng)中現(xiàn)有Rj類資源K個。</p><p>　?。?）最大需求矩陣Max</p><p>　　這是一個n×m的矩陣，它定義了系統(tǒng)中n個進(jìn)程中的每一個進(jìn)程對m類資源的最大需求。如果Max[i,j

7、]=K，則表示進(jìn)程i需要Rj類資源的最大數(shù)目為K。</p><p>　　（3）分配矩陣Allocation</p><p>　　這也是一個n×m的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果Allocation[i,j]=K，則表示進(jìn)程i當(dāng)前已分得Rj類資源的 數(shù)目為K。</p><p>　?。?）需求矩陣Need</p>

8、<p>　　這也是一個n×m的矩陣，用以表示每一個進(jìn)程尚需的各類資源數(shù)。如果Need[i,j]=K，則表示進(jìn)程i還需要Rj類資源K個，方能完成其任務(wù)。</p><p>　　其中Need[i,j]=Max[i,j]-Allocation[i,j]</p><p><b>　　三、程序流程圖</b></p><p><b

9、>　　四、程序代碼</b></p><p>　　#include<iostream></p><p>　　using namespace std;</p><p>　　#include<string.h></p><p>　　#include<stdio.h></p><

10、;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><p>　　char name[100]={0};//

11、資源的名稱</p><p>　　int Allocation[100][100]={0};//系統(tǒng)已分配資源</p><p>　　int Need[100][100]={0};//還需要資源 </p><p>　　int Request[100]={0};//請求資源向量 </p><p>　　int temp[100]={0};//存放安全

12、序列 </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()//顯示資源矩陣 </p><p>&l

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

14、t;" "; </p><p>　　cout<<endl; </p><p>　　for (j=0;j<N;j++)</p><p>　　cout<<Avaliable[j]<<" ";//輸出分配資源</p><p>　　cout<<endl; &

15、lt;/p><p>　　cout<<" Max Allocation Need"<<endl; </p><p>　　cout<<"進(jìn)程名 "; </p><p>　　for(j=0;j<3;j++)</p><p><b>　　{</b>&l

16、t;/p><p>　　for(i=0;i<N;i++)</p><p>　　cout<<name[i]<<" ";</p><p>　　cout<<" ";</p><p><b>　　}</b></p><p>　　c

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

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

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

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

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

22、/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 saf

23、e()//安全性算法</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>　　Wo

24、rk[0]=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>　　{</b></p><p><

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

26、</b></p><p><b>　　apply++;</b></p><p>　　if(apply==N)</p><p><b>　　{ </b></p><p>　　for(m=0;m<N;m++)</p><p>　　Work[m]=Work[m]+

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

28、</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　for(i=0;i<M;i++)</p><p><b>　　{</b></p><p>　　if(Finish[i]==False)</p

29、><p><b>　　{</b></p><p>　　cout<<"系統(tǒng)不安全"<<endl;//不成功系統(tǒng)不安全</p><p>　　return -1;</p><p><b>　　}</b></p><p><b>　　

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

31、t;/b></p><p>　　//輸出運(yùn)行進(jìn)程數(shù)組</p><p>　　cout<<temp[i];</p><p><b>　　if(i<M-1)</b></p><p>　　cout<<"->";</p><p><b>

32、;　　}</b></p><p>　　cout<<endl;</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　void share()//利用銀行家算法對申請資源對進(jìn)行判定</p><p&

33、gt;<b>　　{</b></p><p><b>　　char ch;</b></p><p>　　int i=0,j=0;</p><p><b>　　ch='y';</b></p><p>　　cout<<"請輸入要求分配的資源進(jìn)程

34、號(0-"<<M-1<<"):";</p><p>　　cin>>i;//輸入須申請的資源號</p><p>　　cout<<"請輸入進(jìn)程 "<<i<<" 申請的資源:"<<endl;</p><p>　　for(

35、j=0;j<N;j++)</p><p><b>　　{</b></p><p>　　cout<<name[j]<<":";</p><p>　　cin>>Request[j];//輸入需要申請的資源</p><p><b>　　} </b&g

36、t;</p><p>　　for (j=0;j<N;j++)</p><p><b>　　{</b></p><p>　　if(Request[j]>Need[i][j])//判斷申請是否大于需求，若大于則出錯</p><p><b>　　{</b></p><p&g

37、t;　　cout<<"進(jìn)程 "<<i<<"申請的資源大于它需要的資源";</p><p>　　cout<<" 分配不合理，不予分配！"<<endl; </p><p><b>　　ch='n'; </b></p><

38、;p><b>　　break;</b></p><p><b>　　} </b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　if(Request[j]>Avaliable[j])/

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

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

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

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

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

44、t;b>　　flag=N; </b></p><p><b>　　N=N+n;</b></p><p>　　for(int i=0;i<n;i++)</p><p><b>　　{</b></p><p>　　cout<<"名稱:";</

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

46、();</p><p><b>　　safe();</b></p><p><b>　　} </b></p><p>　　void delresources()</p><p><b>　　{//刪除資源 </b></p><p>　　char ming

47、;</p><p>　　int i,flag=1; </p><p>　　cout<<"請輸入需要刪除的資源名稱：";</p><p><b>　　do{</b></p><p>　　cin>>ming;</p><p>　　for(i=0;i<N

48、;i++)</p><p>　　if(ming==name[i])</p><p><b>　　{</b></p><p><b>　　flag=0;</b></p><p><b>　　break; </b></p><p><b>　　}

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

50、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></p&g

51、t;<p><b>　　N=N-1; </b></p><p>　　showdata(); </p><p><b>　　safe(); </b></p><p><b>　　}</b></p><p>　　void addprocess()</p>

52、<p><b>　　{//添加作業(yè)</b></p><p>　　int flag=M;</p><p><b>　　M=M+1; </b></p><p>　　cout<<"請輸入該作業(yè)的最打需求量[Max]"<<endl; </p><p>

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

54、flag][i]-Allocation[flag][i]; </p><p><b>　　} </b></p><p>　　showdata(); </p><p><b>　　safe(); </b></p><p><b>　　} </b></p><p

55、>　　int main()//主函數(shù)</p><p><b>　　{</b></p><p>　　int i,j,number,choice,m,n,flag;</p><p>　　char ming;</p><p>　　cout<<"*****************資源管理系統(tǒng)的設(shè)計(jì)與實(shí)

56、現(xiàn)*****************"<<endl;</p><p>　　cout<<"請首先輸入系統(tǒng)可供資源種類的數(shù)量:"; </p><p><b>　　cin>>n; </b></p><p><b>　　N=n; </b></p>&l

57、t;p>　　for(i=0;i<n;i++)</p><p><b>　　{</b></p><p>　　cout<<"資源"<<i+1<<"的名稱:";</p><p>　　cin>>ming;</p><p>　　na

58、me[i]=ming;</p><p>　　cout<<"資源的數(shù)量:"; </p><p>　　cin>>number; </p><p>　　Avaliable[i]=number;</p><p><b>　　} </b></p><p>　　co

59、ut<<endl; </p><p>　　cout<<"請輸入作業(yè)的數(shù)量:";</p><p><b>　　cin>>m; </b></p><p><b>　　M=m;</b></p><p>　　cout<<"請輸入各

60、進(jìn)程的最大需求量("<<m<<"*"<<n<<"矩陣)[Max]:"<<endl;</p><p>　　for(i=0;i<m;i++)</p><p>　　for(j=0;j<n;j++)</p><p>　　cin>>Max[i]

61、[j];</p><p><b>　　do{</b></p><p><b>　　flag=0;</b></p><p>　　cout<<"請輸入各進(jìn)程已經(jīng)申請的資源量("<<m<<"*"<<n<<"矩陣)[All

62、ocation]:"<<endl;</p><p>　　for(i=0;i<m;i++)</p><p>　　for(j=0;j<n;j++)</p><p><b>　　{</b></p><p>　　cin>>Allocation[i][j];</p>&l

63、t;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></p><p>&

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

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

66、/p><p>　　cout<<" 1:增加資源 "<<endl;</p><p>　　cout<<" 2:刪除資源 "<<endl;</p><p>　　cout<<" 3:分配資源 "<<endl;</p><p>

67、;　　cout<<" 4:增加作業(yè) "<<endl;</p><p>　　cout<<"*******************************************"<<endl;</p><p>　　cout<<"請選擇功能號：";</p>&l

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

69、;<p>　　case 3: share();break;</p><p>　　case 4: addprocess();break;</p><p>　　default: cout<<"請正確選擇功能號(0-5)!"<<endl;break;</p><p><b>　　}</b>&l

70、t;/p><p><b>　　} </b></p><p><b>　　return 1;</b></p><p><b>　　}</b></p><p><b>　　五、運(yùn)行結(jié)果</b></p><p><b>　　六、設(shè)計(jì)

71、體會</b></p><p>　　經(jīng)過幾天的自己動手練習(xí)，對操作系統(tǒng)的掌握又進(jìn)了一步，收獲了很多課堂上和書上未出現(xiàn)過的或老師未講到的一些知識。在完成實(shí)驗(yàn)的過程中，進(jìn)行了反復(fù)的修改和調(diào)試，這次實(shí)驗(yàn)，讓我基本上明白了銀行家算法的基本原理，加深了對課堂上知識的理解，也懂得了如何讓銀行家算法實(shí)現(xiàn)，但編程功底的原因使程序很是繁瑣。</p><p>　　這次的設(shè)計(jì)數(shù)據(jù)是通過一道實(shí)際的題目來

72、體現(xiàn)銀行家算法避免死鎖的問題，先用銀行家算法給其中一個進(jìn)程分配資源，看它所請求的資源是否大于它的需求量，才和系統(tǒng)所能給的資源相比較.讓進(jìn)程形成一個安全隊(duì)列,看系統(tǒng)是否安全.再利用安全性算法檢查此時系統(tǒng)是否安全。</p><p>　　要做一個課程設(shè)計(jì)，如果知識面只是停留在書本上，是不可能把課程設(shè)計(jì)完全地做好。用VC++6.0編程，感覺自己有點(diǎn)力不從心，很多C語言的知識都忘了，只好翻出以前的C語言課本和數(shù)據(jù)結(jié)構(gòu)來復(fù)習(xí)

73、。每次的課程設(shè)計(jì)中都能將以前的知識順便再復(fù)習(xí)一遍，課程設(shè)計(jì)是給了我們一個機(jī)會去動手和主動復(fù)習(xí)，同時也是提醒我們應(yīng)該注重平時的積累。從課程設(shè)計(jì)以后還是要多多的動手，在實(shí)踐中體會理論知識，這樣才不會在要做實(shí)驗(yàn)和設(shè)計(jì)時，覺得無從下手。</p><p>　　銀行家算法是操作系統(tǒng)中避免死鎖的典型算法。我設(shè)計(jì)的這個程序中包含了三大塊，利用數(shù)據(jù)結(jié)構(gòu)初始化，銀行家算法，安全性算法。在初始化這一塊，程序需要用到可利用資源向量Ava

74、ilable[j]、最大需求矩陣Max[i.j]、分配矩陣Allocation[i,j]、需求矩陣Need[i,j]。它們之間有著一定的聯(lián)系，Need[i,j]=Max[I,j]-Allocation[i,j]，請求資源時需要用到銀行家算法，檢查資源的分配需要用到安全性算法。在將三大塊結(jié)合起來就能很好的避免死鎖的發(fā)生了。</p><p>　　通過這次的實(shí)驗(yàn)，我更進(jìn)一步的了解了銀行家算法，并對數(shù)據(jù)結(jié)構(gòu)的用法理解的更

75、透徹了，在實(shí)驗(yàn)的過程中我深刻的體會到了合作的意義，我遇到了一些困難，通過對書上所學(xué)的知識反復(fù)的思考與理解和與同學(xué)之間的相互討論，最終將銀行家算法真正的理解，并且將它用C++實(shí)現(xiàn)。在以后的學(xué)習(xí)當(dāng)中我會更加努力的將這一門課程學(xué)好。這次課程設(shè)計(jì)時間上雖說倉促點(diǎn)，但是我依然學(xué)到了很多的實(shí)用性知識。除了更深的了解這個算法，而且對C語言進(jìn)行了復(fù)習(xí)，而且其過程中有很多的知識點(diǎn)都不記得了。</p><p><b>　　

76、七、參考文獻(xiàn)</b></p><p>　　[1] 龐麗萍.《操作系統(tǒng)原理》[M]. 武漢：華中科技大學(xué)出版社，2008</p><p>　　[2] 楊樹青,王歡.《Linux環(huán)境下C編程指南》[M]. 北京：清華大學(xué)出版社，2007</p><p>　　[3] 陳維興,林小茶. 《C++面對對象程序設(shè)計(jì)教程》[M]. 北京：清華大學(xué)出版社，2004<