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

1、課程設(shè)計(jì)報(bào)告 操作系統(tǒng)原理 銀行家算法 專業(yè)軟件工程學(xué)生姓名陳鵬班級(jí)3班學(xué)號(hào)0810321306指導(dǎo)教師萬(wàn)方完成日期2011.06.24銀行家算法一、銀行家算法原理銀行家算法是一種最有代表性的避免死鎖的算法。要解釋銀行家算法，必須先解釋操作系統(tǒng)安全狀態(tài)和不安全狀態(tài)。安全狀態(tài)：如果存在一個(gè)由系統(tǒng)中所有進(jìn)程構(gòu)成的安全序列p1，pn，則系統(tǒng)處于安全狀態(tài)。安全狀態(tài)一定是沒(méi)有死鎖發(fā)生。不安全狀態(tài):不存在一個(gè)安全序列。不安全狀態(tài)不一定導(dǎo)致死鎖。那么什么是安全序列呢？安全序列：一個(gè)進(jìn)程序列p1，pn是安全的，如果對(duì)于每一個(gè)進(jìn)程pi(1in），它以后尚需要的資源量不超過(guò)系統(tǒng)當(dāng)前剩余資源量與所有進(jìn)程pj (j

2、i ) 我們可以把操作系統(tǒng)看作是銀行家，操作系統(tǒng)管理的資源相當(dāng)于銀行家管理的資金，進(jìn)程向操作系統(tǒng)請(qǐng)求分配資源相當(dāng)于用戶向銀行家貸款。操作系統(tǒng)按照銀行家制定的規(guī)則為進(jìn)程分配資源，當(dāng)進(jìn)程首次申請(qǐng)資源時(shí)，要測(cè)試該進(jìn)程對(duì)資源的最大需求量，如果系統(tǒng)現(xiàn)存的資源可以滿足它的最大需求量則按當(dāng)前的申請(qǐng)量分配資源，否則就推遲分配。當(dāng)進(jìn)程在執(zhí)行中繼續(xù)申請(qǐng)資源時(shí)，先測(cè)試該進(jìn)程已占用的資源數(shù)與本次申請(qǐng)的資源數(shù)之和是否超過(guò)了該進(jìn)程對(duì)資源的最大需求量。若超過(guò)則拒絕分配資源，若沒(méi)有超過(guò)則再測(cè)試系統(tǒng)現(xiàn)存的資源能否滿足該進(jìn)程尚需的最大資源量，若能滿足則按當(dāng)前的申請(qǐng)量分配資源，否則也要推遲分配。在避免死鎖的方法中，所施加的限制條件

3、較弱，有可能獲得令人滿意的系統(tǒng)性能。在該方法中把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，只要能使系統(tǒng)始終都處于安全狀態(tài)，便可以避免發(fā)生死鎖。銀行家算法的基本思想是分配資源之前,判斷系統(tǒng)是否是安全的;若是,才分配。它是最具有代表性的避免死鎖的算法。二、算法的數(shù)據(jù)結(jié)構(gòu)（1）可利用資源向量available是個(gè)含有m個(gè)元素的數(shù)組，其中的每一個(gè)元素代表一類可利用的資源數(shù)目。如果availablej=k，則表示系統(tǒng)中現(xiàn)有rj類資源k個(gè)。（2）最大需求矩陣max這是一個(gè)nm的矩陣，它定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì)m類資源的最大需求。如果maxi,j=k，則表示進(jìn)程i需要rj類資源的最大數(shù)目為k。（3）分

4、配矩陣allocation這也是一個(gè)nm的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果allocationi,j=k，則表示進(jìn)程i當(dāng)前已分得rj類資源的 數(shù)目為k。（4）需求矩陣need這也是一個(gè)nm的矩陣，用以表示每一個(gè)進(jìn)程尚需的各類資源數(shù)。如果needi,j=k，則表示進(jìn)程i還需要rj類資源k個(gè)，方能完成其任務(wù)。其中needi,j=maxi,j-allocationi,j三、程序流程圖開(kāi)始輸入資源數(shù)m及各類資源總數(shù)，初始化輸入進(jìn)程數(shù)ni=n輸入進(jìn)程i的最大需求向量max=資源總數(shù)提示錯(cuò)誤i加1初始化needneed矩陣為0所有進(jìn)程運(yùn)行結(jié)束任選一個(gè)進(jìn)程作為當(dāng)前進(jìn)程need

5、向量為0該進(jìn)程已運(yùn)行輸入該進(jìn)程的資源請(qǐng)求量調(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;/請(qǐng)求資源向量 int temp

6、100=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+)cout

7、namei ;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;i

8、nt 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+)

9、if(finishi=false)cout系統(tǒng)不安全endl;/不成功系統(tǒng)不安全return -1;cout系統(tǒng)是安全的!endl;/如果安全，輸出成功cout分配的序列:;for(i=0;im;i+)/輸出運(yùn)行進(jìn)程數(shù)組couttempi;if(im-1)cout;coutendl;return 0;void share()/利用銀行家算法對(duì)申請(qǐng)資源對(duì)進(jìn)行判定char ch;int i=0,j=0;ch=y;cout請(qǐng)輸入要求分配的資源進(jìn)程號(hào)(0-m-1i;/輸入須申請(qǐng)的資源號(hào)cout請(qǐng)輸入進(jìn)程 i 申請(qǐng)的資源:endl;for(j=0;jn;j+)coutnamejrequestj;/輸入需

10、要申請(qǐng)的資源 for (j=0;jneedij)/判斷申請(qǐng)是否大于需求，若大于則出錯(cuò)cout進(jìn)程 i申請(qǐng)的資源大于它需要的資源;cout 分配不合理，不予分配！avaliablej)/判斷申請(qǐng)是否大于當(dāng)前資源，若大于則/出錯(cuò)cout進(jìn)程i申請(qǐng)的資源大于系統(tǒng)現(xiàn)在可利用的資源;cout 分配出錯(cuò)，不予分配!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; fla

11、g=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該資源名稱不存在，請(qǐng)重新輸入：; while(flag); for(int j=i;jn-1;j+) namej=namej+1;avaliablej=avaliablej+1; n=n-1; showdata()

12、; safe(); void addprocess()/添加作業(yè)int flag=m;m=m+1; cout請(qǐng)輸入該作業(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è)計(jì)與實(shí)現(xiàn)*endl;coutn; n=n; for(i=0;in;i+)cout資源i+1ming;namei=ming;cout

13、number; avaliablei=number; coutendl; coutm; m=m;cout請(qǐng)輸入各進(jìn)程的最大需求量(m*n矩陣)max:endl;for(i=0;im;i+)for(j=0;jmaxij;doflag=0;cout請(qǐng)輸入各進(jìn)程已經(jīng)申請(qǐng)的資源量(m*n矩陣)allocation:endl;for(i=0;im;i+)for(j=0;jallocationij;if(allocationijmaxij)flag=1; needij=maxij-allocationij; if(flag)cout申請(qǐng)的資源大于最大需求量，請(qǐng)重新輸入!n;while(flag);show

14、data();/顯示各種資源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請(qǐng)正確選擇功能號(hào)(0-5

15、)!endl;break; return 1;五、運(yùn)行結(jié)果六、設(shè)計(jì)體會(huì)經(jīng)過(guò)幾天的自己動(dòng)手練習(xí)，對(duì)操作系統(tǒng)的掌握又進(jìn)了一步，收獲了很多課堂上和書(shū)上未出現(xiàn)過(guò)的或老師未講到的一些知識(shí)。在完成實(shí)驗(yàn)的過(guò)程中，進(jìn)行了反復(fù)的修改和調(diào)試，這次實(shí)驗(yàn)，讓我基本上明白了銀行家算法的基本原理，加深了對(duì)課堂上知識(shí)的理解，也懂得了如何讓銀行家算法實(shí)現(xiàn)，但編程功底的原因使程序很是繁瑣。這次的設(shè)計(jì)數(shù)據(jù)是通過(guò)一道實(shí)際的題目來(lái)體現(xiàn)銀行家算法避免死鎖的問(wèn)題，先用銀行家算法給其中一個(gè)進(jìn)程分配資源，看它所請(qǐng)求的資源是否大于它的需求量，才和系統(tǒng)所能給的資源相比較.讓進(jìn)程形成一個(gè)安全隊(duì)列,看系統(tǒng)是否安全.再利用安全性算法檢查此時(shí)系統(tǒng)是否安

16、全。要做一個(gè)課程設(shè)計(jì)，如果知識(shí)面只是停留在書(shū)本上，是不可能把課程設(shè)計(jì)完全地做好。用vc+6.0編程，感覺(jué)自己有點(diǎn)力不從心，很多c語(yǔ)言的知識(shí)都忘了，只好翻出以前的c語(yǔ)言課本和數(shù)據(jù)結(jié)構(gòu)來(lái)復(fù)習(xí)。每次的課程設(shè)計(jì)中都能將以前的知識(shí)順便再?gòu)?fù)習(xí)一遍，課程設(shè)計(jì)是給了我們一個(gè)機(jī)會(huì)去動(dòng)手和主動(dòng)復(fù)習(xí)，同時(shí)也是提醒我們應(yīng)該注重平時(shí)的積累。從課程設(shè)計(jì)以后還是要多多的動(dòng)手，在實(shí)踐中體會(huì)理論知識(shí)，這樣才不會(huì)在要做實(shí)驗(yàn)和設(shè)計(jì)時(shí)，覺(jué)得無(wú)從下手。銀行家算法是操作系統(tǒng)中避免死鎖的典型算法。我設(shè)計(jì)的這個(gè)程序中包含了三大塊，利用數(shù)據(jù)結(jié)構(gòu)初始化，銀行家算法，安全性算法。在初始化這一塊，程序需要用到可利用資源向量availablej、最大需求矩陣maxi.j、分配矩陣allocationi,j、需求矩陣needi,j。它們之間有著一定的聯(lián)系，needi,j=maxi,j-allocationi,j，請(qǐng)求資源時(shí)需要用到銀行家算法，檢查資源的分配需要用到安全性算法。在將三大塊結(jié)合起來(lái)就能很好的避免死鎖的發(fā)生了。通過(guò)這次的實(shí)驗(yàn)，我更進(jìn)一步的了解了銀行家算法，并對(duì)數(shù)據(jù)結(jié)構(gòu)的用法理解的更透徹了，在實(shí)驗(yàn)的過(guò)程中我深刻的體會(huì)到了合作的意義，我遇到了一些困難，通過(guò)對(duì)書(shū)上所學(xué)的知識(shí)反復(fù)的思考與理解和與同學(xué)之間的相互討論，最終將銀行家算法真正的理