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

1、<p><b>　　課程設(shè)計任務(wù)書</b></p><p>　　2011 — 2012 學(xué)年第 2 學(xué)期</p><p>　　計算機(jī)與通信 學(xué)院（系、部） 計算機(jī)科學(xué)與技術(shù) 專業(yè) 09-3 班級</p><p>　　課程名稱： 操作系統(tǒng) </

2、p><p>　　設(shè)計題目： 模擬銀行家算法 </p><p>　　完成期限：自 2011 年 12 月 19 日至 2011 年 12 月 24 日共 1 周</p><p>　　指導(dǎo)教師（簽字）： 年 月 日</p

3、><p>　　系（教研室）主任（簽字）： 年 月 日</p><p><b>　　一、課程設(shè)計目的</b></p><p>　　通過設(shè)計和調(diào)試銀行家算法通用程序，加深對死鎖概念和死鎖避免方法的了解。</p><p><b>　　二、課程設(shè)計內(nèi)容</b&

4、gt;</p><p>　　編制銀行家算法程序，并檢測所給狀態(tài)的系統(tǒng)安全性。</p><p><b>　　三、算法的原理</b></p><p>　　銀行家算法是一種最有代表性的避免死鎖的算法。要解釋銀行家算法，必須先解釋操作系統(tǒng)安全狀態(tài)和不安全狀態(tài)。</p><p>　　安全狀態(tài)：如果存在一個由系統(tǒng)中所有進(jìn)程構(gòu)成的安全

5、序列P1，…，Pn，則系統(tǒng)處于安全狀態(tài)。安全狀態(tài)一定是沒有死鎖發(fā)生。</p><p>　　不安全狀態(tài):不存在一個安全序列。不安全狀態(tài)不一定導(dǎo)致死鎖。</p><p>　　那么什么是安全序列呢？</p><p>　　安全序列：一個進(jìn)程序列{P1，…，Pn}是安全的，如果對于每一個進(jìn)程Pi(1≤i≤n），它以后尚需要的資源量不超過系統(tǒng)當(dāng)前剩余資源量與所有進(jìn)程Pj (j

6、< i ) 我們可以把操作系統(tǒng)看作是銀行家，操作系統(tǒng)管理的資源相當(dāng)于銀行家管理的資金，進(jìn)程向操作系統(tǒng)請求分配資源相當(dāng)于用戶向銀行家貸款。操作系統(tǒng)按照銀行家制定的規(guī)則為進(jìn)程分配資源，當(dāng)進(jìn)程首次申請資源時，要測試該進(jìn)程對資源的最大需求量，如果系統(tǒng)現(xiàn)存的資源可以滿足它的最大需求量則按當(dāng)前的申請量分配資源，否則就推遲分配。當(dāng)進(jìn)程在執(zhí)行中繼續(xù)申請資源時，先測試該進(jìn)程已占用的資源數(shù)與本次申請的資源數(shù)之和是否超過了該進(jìn)程對資源的最大需求

7、量。若超過則拒絕分配資源，若沒有超過則再測試系統(tǒng)現(xiàn)存的資源能否滿足該進(jìn)程尚需的最大資源量，若能滿足則按當(dāng)前的申請量分配資源，否則也要推遲分配。</p><p>　　1）對用銀行家算法來避免死鎖的方法有較深入的了解，給出系統(tǒng)的初始狀態(tài)，模擬避免死鎖的動態(tài)過程。</p><p>　　2）銀行家算法中的數(shù)據(jù)結(jié)構(gòu)</p><p>　　（1）可利用資源向量Available。

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

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

10、能完成其任務(wù)。</p><p>　　上述三個矩陣存在如下關(guān)系：</p><p>　　Need[i,j]= Max[i，j]- Allocation[i，j]</p><p><b>　　3）銀行家算法</b></p><p>　　設(shè)Request[i] 是進(jìn)程Pi的請求向量，如果Request[i，j]=K,表示進(jìn)程需要

11、K個Rj類型的資源。當(dāng)Pi發(fā)出資源請求后，系統(tǒng)按下述步驟進(jìn)行檢查：</p><p>　　（1）如果Request[i，j]<= Need[i，j]，便轉(zhuǎn)向步驟（2）；否則認(rèn)為出錯，因為它所需要的資源數(shù)已超過它所宣布的最大值。</p><p>　?。?）如果Request[i，j]<= Available[j]，便轉(zhuǎn)向步驟（3）；否則，表示尚無足夠資源，Pi須等待。</p&

12、gt;<p>　?。?）系統(tǒng)試探著把資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：</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]= Nee

13、d[i，j]- Request[i，j]；</p><p>　?。?）系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓進(jìn)程Pi等待。</p><p><b>　　4）安全性算法</b></p><p>　　系統(tǒng)所執(zhí)行的安全性算

14、法可描述如下：</p><p>　?。?）設(shè)置兩個向量：①工作向量Work：它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行</p><p>　　所需要的各類資源數(shù)目，它含有m個元素，在執(zhí)行安全算發(fā)開始時，Work=Available；②Finish：它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開始時先做Finish[i]=false；當(dāng)有足夠資源分配給進(jìn)程時，再令Finish[i]=true。&l

15、t;/p><p>　?。?）從進(jìn)程集合中找到一個能滿足下述條件的進(jìn)程：</p><p>　?、貴inish[i]=false；②Need[i，j] <= Work[j]；若找到，執(zhí)行步驟（3），否則，執(zhí)行</p><p><b>　　步驟（4）。</b></p><p>　　（3）當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行，直至

16、完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行：</p><p>　　Work[j]= Work[i]+ Allocation[i，j]；</p><p>　　Finish[i]=true；</p><p>　　go to step 2；</p><p>　?。?）如果所有進(jìn)程的Finish[i]=true都滿足，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處

17、于不安全狀態(tài)。</p><p>　　5）銀行家算法程序流程圖如圖3.1所示，銀行家算法所用數(shù)據(jù)可參考ppt上的例子。</p><p><b>　　四、數(shù)據(jù)流程圖</b></p><p>　　圖一、銀行家算法程序流程圖</p><p><b>　　五、源程序代碼</b></p><

18、p><b>　　源代碼：</b></p><p>　　#include<iostream></p><p>　　using namespace std;</p><p>　　#define F 0</p><p>　　#define T 1</p><p>　　int main(

19、)</p><p><b>　　{</b></p><p>　　int n,m,i,j;</p><p>　　n=4;m=3; //// 定義進(jìn)程總數(shù)和資源類總數(shù)。</p><p>　　int Available[3]; ///可利用的各類的資源數(shù)。</p><p>　　int

20、Max[4][3]; ////每個進(jìn)程對每類資源的最大需求數(shù)。</p><p>　　int Allocation[4][3]; /////每個進(jìn)程已分配的各類資源個數(shù)。。</p><p>　　int Need[4][3]; ///// 每個進(jìn)程還需要每類資源的個數(shù)。</p><p>　　////////////////</p

21、><p>　　int Request[4][3]; ///// 每個進(jìn)程對每類資源的申請的個數(shù)。</p><p>　　int Work[3]; //////// 在安全性算法中表示可利用的資源個數(shù)。</p><p>　　int Finish[4]; ////在安全性算法中每個進(jìn)程的完成情況。</p><p>　　//////

22、/////</p><p>　　int securityArithmetic(int *Work,int *Available,int *Finish,int Need[][3],int Allocation[][3],int n,int m); ////安全性算法的子程序的聲明。</p><p>　　///////////下面是輸入資源分配表的情況。</p><

23、p>　　cout<<"input the Available: "<<endl;</p><p>　　for(j=0;j<m;j++)</p><p><b>　　{</b></p><p>　　cout<<"Available["<<j<

24、<"]:";</p><p>　　cin>>Available[j]; cout<<endl; ///輸入每類資源可利用的個數(shù)。</p><p><b>　　}</b></p><p>　　/////下面是輸入各類資源的已分配的、最大需求的、現(xiàn)在還需要的資源個數(shù)。</p><

25、;p>　　cout<<"input the Allocation ,Max ,Need :"<<endl;</p><p>　　for(i=0;i<n;i++)</p><p><b>　　{</b></p><p>　　for(j=0;j<m;j++)</p><

26、;p><b>　　{</b></p><p>　　cout<<"Allocation["<<i<<"]["<<j<<"]:"; </p><p>　　cin>>Allocation[i][j];cout<<endl; /

27、//輸入i號進(jìn)程已分配的j類資源的個數(shù)</p><p>　　cout<<"Max["<<i<<"]["<<j<<"]:"; </p><p>　　cin>>Max[i][j];cout<<endl;///輸入i號進(jìn)程對j類資源的最大需求個數(shù)。<

28、;/p><p>　　cout<<"Need["<<i<<"]["<<j<<"]:"; </p><p>　　cin>>Need[i][j];cout<<endl; ///輸入i號進(jìn)程還需要j類資源的個數(shù)。</p><p><

29、;b>　　}</b></p><p><b>　　}</b></p><p>　　/////////////////</p><p>　　////////下面是輸入某個進(jìn)程對每類資源的申請個數(shù)。。</p><p>　　int Request_Num=0;</p><p>　　in

30、t thedoing;</p><p>　　cout<<"讀入請求分配資源的進(jìn)程個數(shù) Request_Num :";</p><p>　　cin>>Request_Num; ///輸入申請資源的進(jìn)程個數(shù)。</p><p>　　cout<<endl;</p><p>　　while(Req

31、uest_Num!=0)</p><p><b>　　{</b></p><p>　　int security=T; ///設(shè)置一個標(biāo)志變量，用于判斷對i號進(jìn)程的</p><p>　　/////申請預(yù)分配后系統(tǒng)是否是安全的。。</p><p>　　int b=1; ///b也是判斷標(biāo)志變量，用于判斷是否所有進(jìn)程的F

32、inish[i]=T.</p><p>　　cout<<"讀入 i 進(jìn)程的資源請求：";</p><p><b>　　cin>>i;</b></p><p>　　thedoing=i; ////輸入請求資源的進(jìn)程號。。</p><p>　　cout<<endl&l

33、t;<"輸入請求的各類資源數(shù)目：";</p><p>　　for(j=0;j<m;j++)</p><p><b>　　{</b></p><p>　　cout<<"輸入第"<<j<<"類的個數(shù)：";</p><p&g

34、t;　　cin>>Request[i][j]; ///輸入i進(jìn)程對各類資源的申請個數(shù)。</p><p><b>　　}</b></p><p>　　//////////////</p><p>　　///進(jìn)程 i 的資源預(yù)分配</p><p>　　int aa=1; ///控制變量aa是用于判斷是否能

35、對i進(jìn)程的申請進(jìn)行預(yù)分配。</p><p>　　for(j=0;j<m;j++)</p><p><b>　　{</b></p><p>　　if (!(Request[i][j]<=Need[i][j] && Request[i][j]<=Available[j]))</p><p&g

36、t;<b>　　{</b></p><p><b>　　aa=0;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　if(aa=1) ///如果aa=1,即所申請的<所需要的，并且所申請的&

37、lt;可利用的。</p><p>　　{ ////就可進(jìn)行預(yù)分配。</p><p>　　for(j=0;j<m;j++)</p><p>　　{ ////下面是進(jìn)行預(yù)分配時所要改變的相關(guān)變量參數(shù)。</p><p>　　Available[j]= Available[j]- Request[i][j];</p>

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

39、;<p>　　else ////如果不能進(jìn)行預(yù)分配，則退出循環(huán)，結(jié)束程序。</p><p>　　{ cout<<”警告：申請資源個數(shù)大于所需的或可利用的個數(shù)..”;</p><p>　　return 0; </p><p><b>　　}</b></p><p>　　///////////

40、///////</p><p>　　/// 調(diào)用安全性算法，返回一個控制變量，表明是否存在安全序列，是否有安全狀態(tài).</p><p>　　b=securityArithmetic(Work,Available,Finish,Need,Allocation, n,m);</p><p>　　//////////////////////////////////</

41、p><p>　　///////如果有安全序列，b==1，則該進(jìn)程的此次請求分配可行。</p><p><b>　　if(b==1)</b></p><p><b>　　{</b></p><p>　　for(i=0;i<n;i++) Finish[i]=F; ///如果b==1，則表明此次申請安

42、全，并把///Finish[i]都置為 F .為下一個進(jìn)程的申請做準(zhǔn)備。</p><p><b>　　}</b></p><p>　　else security=F;</p><p>　　if(security==T) ///判斷當(dāng)前進(jìn)程申請各類資源后系統(tǒng)是否安全。</p><p><b>　　{</b

43、></p><p>　　cout<<"進(jìn)程"<<thedoing<<"請求資源后：存在安全序列，是可行的。"<<endl;</p><p>　　cout<<endl;</p><p><b>　　}</b></p><p

44、><b>　　else </b></p><p><b>　　{</b></p><p>　　cout<<"進(jìn)程"<<thedoing<<"請求資源后：不存在安全序列，是不可行的。"<<endl; ////下面是如果當(dāng)前進(jìn)程申請資源后有死

45、鎖危險，則撤銷之前的預(yù)分配。</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&

46、gt;<p><b>　　}</b></p><p>　　Request_Num--; //申請的進(jìn)程數(shù)量減一，進(jìn)行下一個進(jìn)程的資源預(yù)分配和系統(tǒng)安全性判斷。</p><p><b>　　}</b></p><p>　　return 0; ///對每個申請資源的進(jìn)程進(jìn)行了銀行家算法后，程序結(jié)束。。</p&

47、gt;<p><b>　　}</b></p><p>　　///////////定義安全性算法子程序</p><p>　　int securityArithmetic(int *Work,int *Available,int *Finish,int Need[][3],int Allocation[][3],int n,int m)</

48、p><p><b>　　{</b></p><p><b>　　int i,j;</b></p><p>　　for(i=0;i<n;i++)</p><p><b>　　{</b></p><p>　　Finish[i]=F;</p>

49、<p><b>　　}</b></p><p>　　for(j=0;j<m;j++)</p><p><b>　　{</b></p><p>　　Work[j]=Available[j];</p><p><b>　　}</b></p><p

50、>　　////////下面的 a、b、c 都是控制標(biāo)志變量。</p><p><b>　　int b=1;</b></p><p>　　int a=1; ///標(biāo)志某一進(jìn)程目前還需要的各類資源<可利用的個數(shù)。</p><p>　　int c=0; ///標(biāo)志Finish[c]=T 的進(jìn)程號。</p><p&

51、gt;<b>　　int d;</b></p><p>　　for(d=0;d<n;d++) //////</p><p><b>　　{</b></p><p>　　for(i=0;i<n;i++)////找一個可執(zhí)行完但還沒執(zhí)行完的進(jìn)程 c 。</p><p><b>　

52、　{a=1;</b></p><p>　　for(j=0;j<m;j++)</p><p><b>　　{</b></p><p>　　//////判斷i 進(jìn)程的所需的所有的資源是否＜可利用的。。</p><p>　　if(Need[i][j]<=Work[j]) c=i;</p>

53、;<p><b>　　else a=0;</b></p><p><b>　　}</b></p><p>　　if(Finish[c]==F && a==1) ////如果所需＜可用的，且Finish==F，則進(jìn)程</p><p>　　{ /// i

54、 就釋放其占有的資源。。</p><p>　　for(j=0;j<m;j++)</p><p>　　Work[j]=Work[j]+Allocation[c][j];</p><p>　　Finish[c]=T;</p><p><b>　　}</b></p><p><b>　　

55、}</b></p><p><b>　　b=1;</b></p><p>　　for(i=0;i<n;i++) ////如果所有的進(jìn)程都已經(jīng)執(zhí)行完,則b==1,表示執(zhí)行此次///////////分配是安全的。。。</p><p><b>　　{</b></p><p>　　if(

56、Finish[i]==T) ;///是否所有進(jìn)程都能運(yùn)行完成。</p><p><b>　　else b=0;</b></p><p><b>　　} </b></p><p><b>　　}</b></p><p>　　return b; ///返回標(biāo)志目前系統(tǒng)是否安

57、全的標(biāo)志變量 b .</p><p><b>　　}</b></p><p>　　六、程序運(yùn)行結(jié)果顯示</p><p>　　（1）、資源分配表情況</p><p><b>　?。?）、運(yùn)行結(jié)果</b></p><p>　　1、輸入可利用的資源數(shù)：Available。然后輸入每

58、個進(jìn)程的 ：Allocation的資源個數(shù)。Max的資源個數(shù)。Need的資源個數(shù)。</p><p>　　2、 當(dāng)把資源分配表的情況輸入完后，再輸入要請求分配資源的進(jìn)程的個數(shù)，這里我輸入了2，表示有兩個進(jìn)程請求資源。再輸入請求資源的進(jìn)程號，然后再輸入請求的各類資源的個數(shù)，但不能超過Available 中的個數(shù)。我的輸入是：</p><p>　　1號進(jìn)程，請求各類資源數(shù)為：1、0、2 。照理論

59、是安全的。和運(yùn)行結(jié)果一樣的。然后再輸入：0號進(jìn)程，請求各類資源數(shù)為：0、1、1 。因為這時Available已經(jīng)變成：0、1、0. 所以0號進(jìn)程請求后就處于不安全狀態(tài)了。。</p><p><b>　　七、總結(jié)</b></p><p>　　經(jīng)過幾天的自己動手練習(xí)，對操作系統(tǒng)的掌握又進(jìn)了一步，收獲了很多課堂上和書上未出現(xiàn)過的或老師未講到的一些知識。在完成實驗的過程中，進(jìn)

60、行了反復(fù)的修改和調(diào)試，這次實驗，讓我基本上明白了銀行家算法的基本原理，加深了對課堂上知識的理解，也懂得了如何讓銀行家算法實現(xiàn)，但編程功底的原因使程序很是繁瑣。</p><p>　　銀行家算法是這樣的：</p><p>　　1）當(dāng)一個用戶對資金的最大的需求量不超過銀行家現(xiàn)有的資金時就可以接納該用戶。</p><p>　　2）用戶可以分期貸款，但貸款的總數(shù)不能超過最大需

61、求量。</p><p>　　3）當(dāng)銀行家現(xiàn)有的資金不能滿足用戶的尚需貸款時，對用戶的貸款可推遲支付，但總能使用戶在有限的時間里得到貸款。</p><p>　　4）當(dāng)用戶得到所需的全部資金后，一定能在有限的時間里歸還所有資金。</p><p>　　我們把操作系統(tǒng)看作是銀行家，操作系統(tǒng)管理的資源相當(dāng)于是銀行家管理的資金，則銀行家算法就是：</p><

62、p>　　1）當(dāng)一個進(jìn)程首次申請資源時，測試該進(jìn)程對資源的最大的需求量，如果不超過系統(tǒng)現(xiàn)存資源時就可以按他的當(dāng)前申請量為其分配資源。 否則推遲分配。</p><p>　　2）進(jìn)程執(zhí)行中繼續(xù)申請資源時，測試該進(jìn)程占用資源和本次申請資源總數(shù)有沒有超過最大需求量。超過就不分配，沒超過則再測試現(xiàn)存資源是否滿足進(jìn)程還需要的最大資源量，滿足則按當(dāng)前申請量分配，否則也推遲分配。</p><p>　　

63、總之，銀行家算法要保證分配資源時系統(tǒng)現(xiàn)存資源一定能滿足至少一個進(jìn)程所需的全部資源。這樣就可以保證所有進(jìn)程都能在有限時間內(nèi)得到需要的全部資源。這就是安全狀態(tài)。</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1] 龐麗萍.《操作系統(tǒng)原理》[M]. 武漢：華中科技大學(xué)出版社，2008</p><p>　　[2] 楊樹青,王歡.《