操作系統(tǒng)課程設(shè)計----模擬銀行家算法避免死鎖

1、<p>　　模擬通過銀行家算法避免死鎖</p><p>　　銀行家算法產(chǎn)生的背景及目的</p><p>　　1：在多道程序系統(tǒng)中，雖然借助于多個進程的并發(fā)執(zhí)行來改善系統(tǒng)的利用率，提高系統(tǒng)的吞吐量，但可能發(fā)生一種危險—死鎖。死鎖就是多個進程在運行過程中因爭奪資源而造成的一種僵局，當進程處于這種僵局狀態(tài)時，如無外力作用，他們將無法再向前進行，如再把信號量作為同步工具時，多個Wait和

2、Signal操作順序不當，會產(chǎn)生進程死鎖。</p><p>　　然而產(chǎn)生死鎖的必要條件有互斥條件，請求和保持條件，不剝奪條件和環(huán)路等待條件。在預防死鎖的幾種方法中，都施加了較強的限制條件，在避免死鎖的方法中，所施加的條件較弱，有可能獲得令人滿意的系統(tǒng)性能。在該方法中把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，只要能使系統(tǒng)都處于安全狀態(tài)，便可避免死鎖。</p><p>　　2：實驗目的：讓學生獨立

3、的使用編程語言編寫和調(diào)試一個系統(tǒng)分配資源的簡單模擬程序，了解死鎖產(chǎn)生的原因及條件。采用銀行家算法及時避免死鎖的產(chǎn)生，進一步理解課堂上老師講的相關(guān)知識點。銀行家算法是從當前狀態(tài)出發(fā)，逐個按安全序列檢查各客戶中誰能完成其工作，然后假定其完成工作且歸還全部貸款，再進而檢查下一個能完成工作的客戶。如果所有客戶都能完成工作，則找到一個安全序列，銀行家才是安全的。</p><p>　　二：銀行家算法中的數(shù)據(jù)結(jié)構(gòu) </p

4、><p>　　1：可利用資源向量Available。這是一個含有m個元素的數(shù)組，其中的每個元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動態(tài)的改變。如果Available[j]=k，z</p><p>　　則表示系統(tǒng)中現(xiàn)有Rj類資源K 個。</p><p>　　2：最大需求矩陣Max。這是一個n*m的矩陣，它

5、定義了系統(tǒng)中n個進程中的每一個進程對m類資源的最大需求。如果Max[i,j]=k，表示第i個進程需要第Rj類資源的最大數(shù)目k個.</p><p>　　3: 分配矩陣Allocation,也是n*m的矩陣，若Allocation[i,j]=k,表示第i</p><p>　　個進程已分配Rj類資源的數(shù)目為k個。</p><p>　　4：需求矩陣Need。也是一個n*m的

6、矩陣，Need[i,j]=k,表示第i個進程還需Rj類資源k個。</p><p>　　三、銀行家算法及安全性算法 </p><p><b>　　1：銀行家算法</b></p><p>　　設(shè)Request[i]是進程Pi的請求向量，若Request[i][j]=k;表示進程需要j類資源k個。當Pi發(fā)出資源請求時，系統(tǒng)按下屬步驟進行檢查；<

7、;/p><p>　　如果Request[i][j]<=Need[i][j];便轉(zhuǎn)向步驟（2），否則認為出錯，因為它所需要的資源數(shù)已超過他所宣布的最大值。</p><p>　　如果Request[i][j]<=Available[i][j],便轉(zhuǎn)向步驟（3），否則認為尚無足夠資源，進程需等待。</p><p>　　系統(tǒng)試探著把資源分配給進程，并修改下面數(shù)據(jù)結(jié)構(gòu)

8、的數(shù)據(jù)</p><p>　　Available[i][j]=Available[i][j]-Request[i][j];</p><p>　　Allocation[i][j]=Allocation[i][j]+Request[i][j];</p><p>　　Need[i][j]=Need[i][j]-Request[i][j];</p><p&

9、gt;　　系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進程Pi，已完成此次分配。否則，將本次的試探分配作廢，回復原來的資源分配狀態(tài)，將進程Pi等待。</p><p><b>　　2：安全性算法</b></p><p><b>　　設(shè)置兩個向量；</b></p><p>　　1：工作

10、向量Work，表示系統(tǒng)可提供給進程運行所需的各類資源數(shù)目，它含有m個元素，初始時Work=Available</p><p>　　2：Finish ,表示系統(tǒng)是否有足夠的資源分配給進程，使之運行完成。開始時先做Finish[i]=true</p><p>　　從進程中找到一個能滿需下屬條件的進程</p><p>　　1；Finish[i]=false；</p&

11、gt;<p>　　2：Need[i][j]<=Work[j];若找到執(zhí)行步驟（3），否則執(zhí)行步驟（4）</p><p>　　當進程Pi順利獲得資源后，直至完成，并釋放分配給它的資源，執(zhí)行：</p><p>　　Work[j]=Work[j]+Allocation[i][j];</p><p>　　Finish[i]=true;</p>

12、<p>　　Go to step (2);</p><p>　　如果所有的進程Finish[i]都滿足，則表示系統(tǒng)處于安全狀態(tài)，否則，處于不安全狀態(tài)。</p><p>　　四、模塊設(shè)計與分析及整體功能概述</p><p><b>　　模塊設(shè)計與分析：</b></p><p>　　整個銀行家算法分為初始化函數(shù)

13、Init（），安全性算法函數(shù) safe（），銀行家算法函數(shù)bank（）三部分。初始化函數(shù)生成開始時刻系統(tǒng)中的進程和資源情況，安全性算法判斷當某進程申請資源時，系統(tǒng)能否處于安全狀態(tài)。在本實驗中，若系統(tǒng)處于安全狀態(tài)，便生成一個安全進程序列（安全序列可能有多個）。銀行家算法函數(shù)bank（）負責整體的檢查與異常判斷。</p><p><b>　　整體功能概述：</b></p><

14、p>　　死鎖會引起系統(tǒng)陷入僵局，操作系統(tǒng)必須防止此現(xiàn)象的發(fā)生。本實驗通過一個動態(tài)分配資源的模擬程序，更清楚的理解死鎖產(chǎn)生的原因和條件。Dijkstra的銀行家算法是最有代表性的避免死鎖的方法。運行程序時用戶設(shè)定系統(tǒng)中進程和可利用資源的種類數(shù)目。輸入各進程的可利用資源Available，最大需求MAX，已分配資源Allocation ，需求資源Need，之后各系統(tǒng)發(fā)出資源請求Request，利用實驗中的安全性算法判斷能否產(chǎn)生一個安全

15、性隊列，若能，則給該進程分配成功，否則，不予分配。</p><p><b>　　五、流程圖設(shè)計</b></p><p>　　六、源代碼及調(diào)試分析 </p><p>　　#include<iostream.h></p><p>　　#define MAXm 50 // 定義最大進程

16、數(shù)</p><p>　　#define MAXn 100 //定義最大資源數(shù)</p><p>　　int MAX[MAXm][MAXn]; //最大需求矩陣</p><p>　　int Allocation[MAXm][MAXn]; //已分配矩陣</p><p>　　int Availa

17、ble[MAXn]; //可用資源數(shù)組</p><p>　　int Need[MAXm][MAXn]; //需求矩陣</p><p>　　int Request[MAXm][MAXn]; //請求矩陣</p><p>　　int Finish[MAXm]; //存儲完成資源分配的進程</

18、p><p>　　int Sequence[MAXm]; //模擬的資源分配序列</p><p>　　int Work[MAXn]; //系統(tǒng)是否有足夠的資源分配給進程</p><p>　　int m,n; //m個進程,n個資源</p><p>　　#define F

19、alse 0</p><p>　　#define True 1</p><p>　　void input(); //數(shù)據(jù)輸入函數(shù)</p><p>　　int safealg(); //安全性算法函數(shù)</p><p>　　void banker(); //銀行家算法函數(shù)</p><p>　　void main()&

20、lt;/p><p>　　{input();safealg();banker();}</p><p>　　//*************初始化算法***************</p><p>　　void input() </p><p><b>　　{</b></p><p><b>　　

21、int i,j;</b></p><p>　　//************自定義進程數(shù)目與資源種類*******************</p><p>　　cout<<"***********************************\n";</p><p>　　cout<<"*利用銀行家算法

22、避免死鎖*\n";</p><p>　　cout<<"* *\n";</p><p>　　cout<<"************************************\n";</p><p>　　cout<<"請輸入進

23、程的數(shù)目:";</p><p><b>　　cin>>m;</b></p><p>　　cout<<"請輸入資源的種類:";</p><p><b>　　cin>>n;</b></p><p>　　//*****輸入每個進程對每種資源

24、的最大需求、已經(jīng)獲得的數(shù)量、每種類型資源的數(shù)目</p><p>　　cout<<"各進程資源最大需求(Max),按照"<<m<<"x"<<n<<"矩陣輸入:\n";</p><p>　　for(i=0;i<m;i++)</p><p><

25、;b>　　{</b></p><p>　　cout<<"P"<<i<<":";</p><p>　　for(j=0;j<n;j++)</p><p><b>　　{</b></p><p>　　cin>>MAX

26、[i][j]; </p><p><b>　　if(j==n)</b></p><p>　　cout<<"資源種類數(shù)匹配出現(xiàn)錯誤！";//當資源配置的種類數(shù)大于預先輸入的數(shù)值時，出錯</p><p><b>　　}</b></p><p><b>　　}&l

27、t;/b></p><p>　　cout<<"各進程當前獲得資源(Allocation),按照"<<m<<"x"<<n<<"矩陣輸入"<<endl;</p><p>　　for(i=0;i<m;i++)</p><p>&l

28、t;b>　　{ </b></p><p>　　cout<<"P"<<i<<":";</p><p>　　for(j=0;j<n;j++)</p><p><b>　　{</b></p><p>　　cin>>

29、Allocation[i][j];</p><p><b>　　if(j==n)</b></p><p>　　cout<<"資源種類數(shù)匹配出現(xiàn)錯誤！";//當資源配置的種類數(shù)大于預先輸入的數(shù)值時，出錯</p><p>　　Need[i][j]=MAX[i][j]-Allocation[i][j];//需求數(shù)等于最

30、大需求減去已經(jīng)分配數(shù)</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　cout<<"系統(tǒng)可用資源(Available):"<<endl;</p><p>　　for(j=0;j<n;j++)<

31、/p><p><b>　　{ </b></p><p>　　cin>>Available[j];//輸入各種資源的可利用數(shù)</p><p><b>　　}</b></p><p>　　cout<<"當前時刻的進程分配情況如圖：\n";</p>

32、<p>　　cout<<"進程號-"<<"MAX----"<<"Allocation---"<<"Need--"<<"Available---\n";//顯示各進程的資源情況</p><p>　　for(i=0;i<m;i++)</p

33、><p><b>　　{</b></p><p>　　cout<<"P"<<i<<": ";</p><p>　　for(j=0;j<n;j++)</p><p>　　cout<<" "<<MAX[

34、i][j];</p><p>　　for(j=0;j<n;j++)</p><p>　　cout<<" "<<Allocation[i][j];</p><p>　　cout<<" ";</p><p>　　for(j=0;j<n;j++)</p

35、><p>　　cout<<" "<<Need[i][j];</p><p>　　for(j=0;j<n;j++)</p><p>　　cout<<" "<<Available[j];</p><p>　　cout<<endl;//回車換行

36、</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　//*****************銀行家算法，為進程分配資源***********//</p><p>　　void banker() </p><p><b>

37、;　　{</b></p><p><b>　　int i,j; </b></p><p>　　int choice; </p><p><b>　　while(1)</b></p><p><b>　　{</b></p><p>　　c

38、out<<endl;</p><p>　　cout<<"輸入要進行的操作(1:分配資源 2:離開) :"; //用戶選擇</p><p>　　cin>>choice;</p><p>　　if(choice==1) //分配資源</p><p><b>　　{<

39、;/b></p><p>　　cout<<"從P0到P"<<m-1<<"之間選擇要分配資源的進程號:\n";</p><p><b>　　cin>>i;</b></p><p><b>　　if(i>=m)</b></

40、p><p><b>　　{</b></p><p>　　cout<<"無此進程號!請重新輸入:\n";</p><p>　　cin>>i;//重新輸入進程號</p><p><b>　　} </b></p><p>　　cout<

41、;<"請輸入進程申請的資源(Request):"<<endl;</p><p>　　for(j=0;j<n;j++)</p><p>　　cin>>Request[i][j]; </p><p>　　//**********銀行家算法進行檢查*************// </p>

42、<p>　　for(j=0;j<n;j++)</p><p><b>　　{</b></p><p>　　if(Request[i][j]>Need[i][j])</p><p><b>　　{</b></p><p>　　cout<<"申請的資源大于它

43、需要的資源數(shù),請重新輸入!\n";//資源申請不合理</p><p><b>　　continue;</b></p><p><b>　　}</b></p><p>　　if(Request[i][j]>Available[j])</p><p><b>　　{</b

44、></p><p>　　//資源申請數(shù)目大于可利用數(shù)，無法分配，得等待</p><p>　　cout<<"當前系統(tǒng)可用資源不夠，請等待!"<<endl;</p><p>　　continue; </p><p><b>　　}</b></p><p&

45、gt;<b>　　}</b></p><p>　　for(j=0;j<n;j++)//資源申請得到允許時，變換各個資源數(shù)</p><p><b>　　{</b></p><p>　　Available[j]=Available[j]-Request[i][j]; //可用資源減少</p><p

46、>　　Allocation[i][j]=Allocation[i][j]+Request[i][j];//所得資源增加</p><p>　　Need[i][j]=Need[i][j]-Request[i][j]; //仍需資源減少</p><p><b>　　}</b></p><p>　　if(safealg()<0)

47、//安全性算法的返回值</p><p><b>　　{</b></p><p>　　cout<<"分配不成功，請等待！";</p><p>　　for (j=0;j<n;j++) //把資源恢復成分配之前的狀態(tài)</p><p><b>　　{ </b&g

48、t;</p><p>　　Available[j]=Available[j]+Request[i][j]; </p><p>　　Allocation[i][j]=Allocation[i][j]-Request[i][j]; </p><p>　　Need[i][j]=Need[i][j]+Request[i][j]; </p><p>&

49、lt;b>　　}</b></p><p>　　for(i=0;i<m;i++)</p><p><b>　　{</b></p><p>　　Finish[i]=False;//沒有足夠的資源分配給該進程</p><p><b>　　}</b></p><

50、p>　　}//if(safealg()<0) </p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　cout<<"同意分配請求!"<<endl;</p><p>　　for(j=0;j&l

51、t;n;j++)</p><p>　　Work[j]=Available[j];</p><p>　　cout<<"進程號-"<<"--Work----"<<"Need---"<<"Allocation---"<<"Work+Allocati

52、on--"</p><p>　　<<"Finish--"<<endl;</p><p>　　for(i=0;i<m;i++)//按模擬分配序列進行分配</p><p><b>　　{</b></p><p>　　cout<<"進程P&quo

53、t;<<Sequence[i]<<": "; </p><p>　　for(j=0;j<n;j++)</p><p>　　cout<<Work[j]<<" "; </p><p>　　cout<<" ";</p><p

54、>　　for(j=0;j<n;j++)</p><p>　　cout<<Need[Sequence[i]][j]<<" ";</p><p>　　cout<<" ";</p><p>　　for(j=0;j<n;j++)</p><p>　　cou

55、t<<Allocation[Sequence[i]][j]<<" ";</p><p>　　cout<<" ";</p><p>　　for(j=0;j<n;j++)</p><p>　　cout<<Allocation[Sequence[i]][j]+Work

56、[j]<<" ";</p><p>　　cout<<" ";</p><p>　　cout<<Finish[Sequence[i]]<<" ";//完成該進程</p><p>　　for(j=0;j<n;j++)</p>

57、<p>　　Work[j]=Allocation[Sequence[i]][j]+Work[j];//回收該進程所分配的資源</p><p>　　cout<<endl;</p><p><b>　　}</b></p><p>　　}//if(safealg()>=0)</p><p>　　

58、}//if(choice=1)</p><p>　　else if(choice==2) //離開————</p><p><b>　　break; </b></p><p>　　else cout<<"請輸入1或2!";//只認可1或2</p><p>　　}//while(1)&

59、lt;/p><p><b>　　}</b></p><p>　　//*********安全性算法 ************//</p><p>　　int safealg() </p><p><b>　　{</b></p><p>　　int i,j,k,l=0;</p&

60、gt;<p>　　//int Work[MAXn]; //工作組</p><p><b>　　//記錄序列</b></p><p>　　for(i=0;i<n;i++)</p><p>　　Work[i]=Available[i]; //工作分配初始化為系統(tǒng)可用資源 </p&g

61、t;<p>　　for(i=0;i<m;i++) //掃描所有進程，預設(shè)所有進程不能運行</p><p><b>　　{</b></p><p>　　Finish[i]=False;</p><p><b>　　}</b></p><p>　　

62、for(i=0;i<m;i++)</p><p><b>　　{ //</b></p><p>　　if(Finish[i]==True)</p><p><b>　　{</b></p><p><b>　　continue;</b></p><p&g

63、t;<b>　　}</b></p><p>　　else //對于未運行的進程，進行如下處理</p><p><b>　　{///</b></p><p>　　for(j=0;j<n;j++)//找到一個滿足Finish[i]=false且Need[i][j]<=Work[j]的進程</p>&l

64、t;p><b>　　{</b></p><p>　　if(Need[i][j]>Work[j])//由于部分資源得不到滿足，進程i無法運行</p><p><b>　　{</b></p><p><b>　　break;</b></p><p><b>　

65、　}</b></p><p><b>　　}</b></p><p>　　if(j==n)//進程各類資源全部得到滿足</p><p><b>　　{ </b></p><p>　　Finish[i]=True;</p><p>　　for(k=0;k<n;

66、k++)//進程i正常運行后，釋放其占有的資源</p><p><b>　　{</b></p><p>　　Work[k]+=Allocation[i][k]; //工作分配加上可用資源</p><p><b>　　}</b></p><p>　　Sequence[l++]=i; //模擬資源

67、分配序列生成</p><p>　　i=-1; //重新掃描所有進程從i=0開始</p><p><b>　　}</b></p><p><b>　　else</b></p><p>　　{ //某一資源得不到滿足</p><p>　　continue; //試探下

68、一個進程</p><p><b>　　}</b></p><p><b>　　}//</b></p><p>　　if(l==m)//都試探完畢</p><p><b>　　{</b></p><p>　　cout<<"系統(tǒng)安全!&

69、quot;<<endl; </p><p>　　cout<<"安全序列：";</p><p>　　for(i=0;i<l;i++) //輸出安全序列</p><p>　　cout<<"進程P"<<Sequence[i]<<"--> &qu

70、ot;;</p><p>　　cout<<endl;</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p><b>　　}//</b></p><p>　　cout<<&q

71、uot;系統(tǒng)進入不安全狀態(tài)！"<<endl;</p><p>　　return -1;</p><p><b>　　}</b></p><p>　　分析：輸入各進程的可利用資源Available，最大需求MAX，已分配資源Allocation ，需求資源Need，之后各系統(tǒng)發(fā)出資源請求Request，利用實驗中的安全性算法

72、判斷能否產(chǎn)生一個安全性隊列，若能，則給該進程分配成功，否則，不予分配。在確定安全序列的過程中，要檢測所有進程的Finish[i]的值，每次循環(huán)檢測完后要重復從第一個進程開始。</p><p><b>　　七、運行結(jié)果 </b></p><p>　　假設(shè)輸入進程個數(shù)為5，資源種類數(shù)為3，并以此輸入各進程初始時刻的各種資源數(shù)量 ，如下</p><p&

73、gt;　　若再繼續(xù)申請資源，假設(shè)為P4 ，申請資源（1 2 2）</p><p>　　假設(shè)P1 申請資源（2 2 4）有</p><p><b>　　八、心得體會 </b></p><p>　　經(jīng)過這次操作系統(tǒng)課程設(shè)計，讓我受益匪淺，收獲頗多。主要體會如下：</p><p>　　1.利用Vc++編譯程序編寫銀行家算法，

74、進一步理解到通過銀行家算法避免死鎖的思想,同時也理解了系統(tǒng)死鎖產(chǎn)生的原因及條件。</p><p>　　2.在實驗過程中所有的設(shè)計步驟遵循老師教授的程序功能化的思想，分別定義了三個函數(shù)，init()初始化函數(shù),safealg()安全性算法函數(shù)，bank（）銀行家算法函數(shù)，體現(xiàn)了函數(shù)的模塊化思想。這樣的話，不僅提高了程序的可讀性和可操作性，而且還提高了CPU的利用率和內(nèi)存的利用率，因為程序的運行是局部性的，這種思想對