銀行家算法-課程設(shè)計.doc

課程設(shè)計報告 操作系統(tǒng)原理 銀行家算法 專業(yè)軟件工程學(xué)生姓名陳鵬班級3班學(xué)號0810321306指導(dǎo)教師萬方完成日期2011.06.24銀行家算法一、銀行家算法原理銀行家算法是一種最有代表性的避免死鎖的算法。要解釋銀行家算法，必須先解釋操作系統(tǒng)安全狀態(tài)和不安全狀態(tài)。安全狀態(tài)：如果存在一個由系統(tǒng)中所有進(jìn)程構(gòu)成的安全序列P1，Pn，則系統(tǒng)處于安全狀態(tài)。安全狀態(tài)一定是沒有死鎖發(fā)生。不安全狀態(tài):不存在一個安全序列。不安全狀態(tài)不一定導(dǎo)致死鎖。那么什么是安全序列呢？安全序列：一個進(jìn)程序列P1，Pn是安全的，如果對于每一個進(jìn)程Pi(1in），它以后尚需要的資源量不超過系統(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)程首次申請資源時，要測試該進(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)前的申請量分配資源，否則也要推遲分配。在避免死鎖的方法中，所施加的限制條件較弱，有可能獲得令人滿意的系統(tǒng)性能。在該方法中把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，只要能使系統(tǒng)始終都處于安全狀態(tài)，便可以避免發(fā)生死鎖。銀行家算法的基本思想是分配資源之前,判斷系統(tǒng)是否是安全的;若是,才分配。它是最具有代表性的避免死鎖的算法。二、算法的數(shù)據(jù)結(jié)構(gòu)（1）可利用資源向量Available是個含有m個元素的數(shù)組，其中的每一個元素代表一類可利用的資源數(shù)目。如果Availablej=K，則表示系統(tǒng)中現(xiàn)有Rj類資源K個。（2）最大需求矩陣Max這是一個nm的矩陣，它定義了系統(tǒng)中n個進(jìn)程中的每一個進(jìn)程對m類資源的最大需求。如果Maxi,j=K，則表示進(jìn)程i需要Rj類資源的最大數(shù)目為K。（3）分配矩陣Allocation這也是一個nm的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果Allocationi,j=K，則表示進(jìn)程i當(dāng)前已分得Rj類資源的 數(shù)目為K。（4）需求矩陣Need這也是一個nm的矩陣，用以表示每一個進(jìn)程尚需的各類資源數(shù)。如果Needi,j=K，則表示進(jìn)程i還需要Rj類資源K個，方能完成其任務(wù)。其中Needi,j=Maxi,j-Allocationi,j三、程序流程圖開始輸入資源數(shù)m及各類資源總數(shù)，初始化輸入進(jìn)程數(shù)ni=n輸入進(jìn)程i的最大需求向量Max=資源總數(shù)提示錯誤i加1初始化needNeed矩陣為0所有進(jìn)程運行結(jié)束任選一個進(jìn)程作為當(dāng)前進(jìn)程Need向量為0該進(jìn)程已運行輸入該進(jìn)程的資源請求量調(diào)用銀行家算法，及安全性算法，完成分配并給出提示YNNYYYNN 四、程序代碼#includeusing namespace std;#include#include#define False 0#define True 1 int Max100100=0;/各進(jìn)程所需各類資源的最大需求int Avaliable100=0;/系統(tǒng)可用資源char name100=0;/資源的名稱int Allocation100100=0;/系統(tǒng)已分配資源int Need100100=0;/還需要資源 int Request100=0;/請求資源向量 int temp100=0;/存放安全序列 int Work100=0;/存放系統(tǒng)可提供資源 int M=100;/作業(yè)的最大數(shù)為100 int N=100;/資源的最大數(shù)為100 void showdata()/顯示資源矩陣 int i,j; cout系統(tǒng)目前可用的資源Avaliable:endl; for(i=0;iN;i+)coutnamei ; coutendl; for (j=0;jN;j+)coutAvaliablej ;/輸出分配資源coutendl; cout Max Allocation Needendl; cout進(jìn)程名 ; for(j=0;j3;j+)for(i=0;iN;i+)coutnamei ;cout ;coutendl;for(i=0;iM;i+)cout i ;for(j=0;jN;j+)coutMaxij ;cout ;for(j=0;jN;j+)coutAllocationij ;cout ;for(j=0;jN;j+)coutNeedij ;coutendl; int changdata(int i)/進(jìn)行資源分配int j;for (j=0;jM;j+) Avaliablej=Avaliablej-Requestj; Allocationij=Allocationij+Requestj; Needij=Needij-Requestj; return 1;int safe()/安全性算法int i,k=0,m,apply,Finish100=0; int j; int flag=0; Work0=Avaliable0; Work1=Avaliable1; Work2=Avaliable2; for(i=0;iM;i+)apply=0; for(j=0;jN;j+)if (Finishi=False&Needij=Workj)apply+;if(apply=N) for(m=0;mN;m+)Workm=Workm+Allocationim;/變分配數(shù)Finishi=True;tempk=i;i=-1; k+;flag+;for(i=0;iM;i+)if(Finishi=False)cout系統(tǒng)不安全endl;/不成功系統(tǒng)不安全return -1;cout系統(tǒng)是安全的!endl;/如果安全，輸出成功cout分配的序列:;for(i=0;iM;i+)/輸出運行進(jìn)程數(shù)組couttempi;if(iM-1)cout;coutendl;return 0;void share()/利用銀行家算法對申請資源對進(jìn)行判定char ch;int i=0,j=0;ch=y;cout請輸入要求分配的資源進(jìn)程號(0-M-1i;/輸入須申請的資源號cout請輸入進(jìn)程 i 申請的資源:endl;for(j=0;jN;j+)coutnamejRequestj;/輸入需要申請的資源 for (j=0;jNeedij)/判斷申請是否大于需求，若大于則出錯cout進(jìn)程 i申請的資源大于它需要的資源;cout 分配不合理，不予分配！Avaliablej)/判斷申請是否大于當(dāng)前資源，若大于則/出錯cout進(jìn)程i申請的資源大于系統(tǒng)現(xiàn)在可利用的資源;cout 分配出錯，不予分配!endl;ch=n;break; if(ch=y)changdata(i);/根據(jù)進(jìn)程需求量變換資源showdata();/根據(jù)進(jìn)程需求量顯示變換后的資源 safe();/根據(jù)進(jìn)程需求量進(jìn)行銀行家算法判斷 void addresources()/添加資源int n,flag;coutn; flag=N; N=N+n;for(int i=0;in;i+)coutnameflag; coutAvaliableflag+; showdata();safe(); void delresources()/刪除資源 char ming;int i,flag=1; coutming;for(i=0;iN;i+)if(ming=namei)flag=0;break; if(i=N)cout該資源名稱不存在，請重新輸入：; while(flag); for(int j=i;jN-1;j+) namej=namej+1;Avaliablej=Avaliablej+1; N=N-1; showdata(); safe(); void addprocess()/添加作業(yè)int flag=M;M=M+1; cout請輸入該作業(yè)的最打需求量Maxendl; for(int i=0;iN;i+)coutnameiMaxflagi;Needflagi=Maxflagi-Allocationflagi; showdata(); safe(); int main()/主函數(shù)int i,j,number,choice,m,n,flag;char ming;cout*資源管理系統(tǒng)的設(shè)計與實現(xiàn)*endl;coutn; N=n; for(i=0;in;i+)cout資源i+1ming;namei=ming;coutnumber; Avaliablei=number; coutendl; coutm; M=m;cout請輸入各進(jìn)程的最大需求量(m*n矩陣)Max:endl;for(i=0;im;i+)for(j=0;jMaxij;doflag=0;cout請輸入各進(jìn)程已經(jīng)申請的資源量(m*n矩陣)Allocation:endl;for(i=0;im;i+)for(j=0;jAllocationij;if(AllocationijMaxij)flag=1; Needij=Maxij-Allocationij; if(flag)cout申請的資源大于最大需求量，請重新輸入!n;while(flag);showdata();/顯示各種資源safe();/用銀行家算法判定系統(tǒng)是否安全while(true)cout*銀行家算法演示*endl;cout 1:增加資源 endl;cout 2:刪除資源 endl;cout 3:分配資源 endl;cout 4:增加作業(yè) endl;cout*endl;coutchoice;switch(choice)case 1: addresources();break;case 2: delresources();break;case 3: share();break;case 4: addprocess();break;default: cout請正確選擇功能號(0-5)!endl;break; return 1;五、運行結(jié)果六、設(shè)計體會經(jīng)過幾天的自己動手練習(xí)，對操作系統(tǒng)的掌握又進(jìn)了一步，收獲了很多課堂上和書上未出現(xiàn)過的或老師未講到的一些知識。在完成實驗的過程中，進(jìn)行了反復(fù)的修改和調(diào)試，這次實驗，讓我基本上明白了銀行家算法的基本原理，加深了對課堂上知識的理解，也懂得了如何讓銀行家算法實現(xiàn)，但編程功底的原因使程序很是繁瑣。這次的設(shè)計數(shù)據(jù)是通過一道實際的題目來體現(xiàn)銀行家算法避免死鎖的問題，先用銀行家算法給其中一個進(jìn)程分配資源，看它所請求的資源是否大于它的需求量，才和系統(tǒng)所能給的資源相比較.讓進(jìn)程形成一個安全隊列,看系統(tǒng)是否安全.再利用安全性算法檢查此時系統(tǒng)是否安全。要做一個課程設(shè)計，如果知識面只是停留在書本上，是不可能把課程設(shè)計完全地做好。用VC+6.0編程，感覺自己有點力不從心，很多C語言的知識都忘了，只好翻出以前的C語言課本和數(shù)據(jù)結(jié)構(gòu)來復(fù)習(xí)。每次的課程設(shè)計中都能將以前的知識順便再復(fù)習(xí)一遍，課程設(shè)計是給了我們一個機會去動手和主動復(fù)習(xí)，同時也是提醒我們應(yīng)該注重平時的積累。從課程設(shè)計以后還是要多多的動手，在實踐中體會理論知識，這樣才不會在要做實驗和設(shè)計時，覺得無從下手。銀行家算法是操作系統(tǒng)中避免死鎖的典型算法。我設(shè)計的這個程序中包含了三大塊，利用數(shù)據(jù)結(jié)構(gòu)初始化，銀行家算法，安全性算法。在初始化這一塊，程序需要用到可利用資源向量Availablej、最大需求矩陣Maxi.j、分配矩陣Allocationi,j、需求矩陣Needi,j。它們之間有著一定的聯(lián)系，Needi,j=MaxI,j-Allocationi,j，請求資源時需要用到銀行家算法，檢查資源的分配需要用到安全性算法。在將三大塊結(jié)合起來就能很好的避免死鎖的發(fā)生了。通過這次的實驗，我更進(jìn)一步的了解了銀行家算法，并對數(shù)據(jù)結(jié)構(gòu)的用法理解的更透徹了，在實驗的過程中我深刻的體會到了合作的意義，我遇到了一些困難，通過對書上所學(xué)的知識反復(fù)的思考與理解和與同學(xué)之間的相互討論，最終將銀行家算法真正的理