實(shí)驗(yàn)二(3)銀行家算法

1、實(shí)驗(yàn)二（3）銀行家算法一、實(shí)驗(yàn)?zāi)康?）掌握死鎖的產(chǎn)生的原因、產(chǎn)生死鎖的必要條件和處理死鎖的基本方法。2）了解多道程序系統(tǒng)中，多個(gè)進(jìn)程并發(fā)執(zhí)行的資源分配。3）掌握預(yù)防死鎖的方法，系統(tǒng)安全狀態(tài)的基本概念4）掌握銀行家算法，了解資源在進(jìn)程并發(fā)執(zhí)行中的資源分配策略。二、實(shí)驗(yàn)內(nèi)容設(shè)計(jì)一個(gè)n個(gè)并發(fā)進(jìn)程共享m個(gè)系統(tǒng)資源的系統(tǒng)。進(jìn)程課動(dòng)態(tài)申請(qǐng)資源和釋放資源，系統(tǒng)按照進(jìn)程的申請(qǐng)動(dòng)態(tài)的分配資源。用銀行家算法設(shè)計(jì)實(shí)現(xiàn)。三、實(shí)驗(yàn)原理我們可以把操作系統(tǒng)看作是銀行家，操作系統(tǒng)管理的資源相當(dāng)于銀行家管理的資金，進(jìn)程向操作系統(tǒng)請(qǐng)求分配資源相當(dāng)于用戶向銀行家貸款。 為保證資金的安全,銀行家規(guī)定: (1) 當(dāng)一個(gè)顧客對(duì)資金的最大

2、需求量不超過(guò)銀行家現(xiàn)有的資金時(shí)就可接納該顧客; (2) 顧客可以分歧貸款,但貸款的總數(shù)不能超過(guò)最大需求量; (3) 當(dāng)銀行家現(xiàn)有的資金不能滿足顧客尚需的貸款數(shù)額時(shí),對(duì)顧客的貸款可推遲支付,但總能使顧客在有限的時(shí)間里得到貸款; (4) 當(dāng)顧客得到所需的全部資金后,一定能在有限的時(shí)間里歸還所有的資金. 操作系統(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ò)

3、則拒絕分配資源，若沒(méi)有超過(guò)則再測(cè)試系統(tǒng)現(xiàn)存的資源能否滿足該進(jìn)程尚需的最大資源量，若能滿足則按當(dāng)前的申請(qǐng)量分配資源，否則也要推遲分配。四、算法實(shí)現(xiàn)（1） 初始化這組進(jìn)程的最大資源請(qǐng)求和依次申請(qǐng)的資源序列。把各進(jìn)程已占用和需求資源情況記錄在進(jìn)程控制塊中。假定進(jìn)程控制塊的內(nèi)容包括：進(jìn)程名，狀態(tài)，當(dāng)前申請(qǐng)量，資源需求總量，已占資源量，能執(zhí)行完標(biāo)志。其中，進(jìn)程的狀態(tài)有：就緒、等待和完成。當(dāng)系統(tǒng)不能滿足進(jìn)程的資源請(qǐng)求時(shí)，進(jìn)程處于等待態(tài)。資源需求總量表示進(jìn)程運(yùn)行過(guò)程中對(duì)資源的總的需求量。 已占資源量表示進(jìn)程目前已經(jīng)得到但還未歸還的資源量。因此，進(jìn)程在以后還需要的剩余資源量等于資源需要總量減去已占資源量。顯然

4、每個(gè)進(jìn)程的資源需求總量不應(yīng)超過(guò)系統(tǒng)擁有的資源總量。 （2） 銀行家算法分配資源的原則是：當(dāng)某個(gè)進(jìn)程提出資源請(qǐng)求時(shí)，假定先分配資源給它，然后查找各進(jìn)程的剩余請(qǐng)求，檢查系統(tǒng)的剩余資源量是否由于進(jìn)程的分配而導(dǎo)致系統(tǒng)死鎖。若能，則讓進(jìn)程等待，否則，讓進(jìn)程的假分配變?yōu)檎娣峙洹?a) 查找各進(jìn)程的剩余請(qǐng)求，檢查系統(tǒng)的剩余資源量是否能滿足其中一進(jìn)程。如果能，則轉(zhuǎn)b)。 b) 將資源分配給所選的進(jìn)程，這樣，該進(jìn)程已獲得資源最大請(qǐng)求，最終能運(yùn)行完成。標(biāo)記這個(gè)進(jìn)程為終止進(jìn)程，并將其占有的全部資源歸還給系統(tǒng)。 重復(fù)第a)步和第b)步，直到所有進(jìn)程都標(biāo)記為終止進(jìn)程，或直到一個(gè)死鎖發(fā)生。若所有進(jìn)程都標(biāo)記為終止進(jìn)程，則系

5、統(tǒng)的初始狀態(tài)是安全的，否則為不安全的。若安全，則正式將資源分配給它，否則，假定的分配作廢，讓其等待。數(shù)據(jù)結(jié)構(gòu)：#define MAXPROCESS 50 /*最大進(jìn)程數(shù)*/#define MAXRESOURCE 100 /*最大資源數(shù)*/int AVAILABLEMAXRESOURCE; /*可用資源數(shù)組*/int MAXMAXPROCESSMAXRESOURCE; /*最大需求矩陣*/int ALLOCATIONMAXPROCESSMAXRESOURCE; /*分配矩陣*/int NEEDMAXPROCESSMAXRESOURCE; /*需求矩陣*/int REQUESTMAXPROCESS

6、MAXRESOURCE; /*進(jìn)程需要資源數(shù)*/bool FINISHMAXPROCESS; /*系統(tǒng)是否有足夠的資源分配*/int pMAXPROCESS; /*記錄序列*/int WorkMAXRESOURCE; /*工作數(shù)組*/int m,n; /*m個(gè)進(jìn)程,n個(gè)資源*/string showdata14="max ","allo","need","aval"/*繪制資源以及進(jìn)程狀態(tài)時(shí)使用*/string showdata25="work","need","a

7、llo","w+al","finish"/*繪制銀行家算法過(guò)程時(shí)使用*/五、流程圖1：主函數(shù)流程圖：結(jié)束開(kāi)始調(diào)用初始化函數(shù)(Init)圖1主函數(shù)流程圖安全性檢測(cè)(Safe)銀行家算法(Bank)安全YN2：初始化流程圖結(jié)束返回Init()開(kāi)始輸入進(jìn)程的數(shù)目m圖2初始化流程圖輸入資源的種類(lèi)n輸入AVAILABLEi輸入正確YN輸入MAXij輸入ALLOCATIONij 顯示當(dāng)前系統(tǒng)狀態(tài)(iShow)提示錯(cuò)誤，重新輸入相應(yīng)數(shù)據(jù)3：安全性檢測(cè)流程圖結(jié)束返回Safe()開(kāi)始繪制結(jié)果表格頭部(fShow)圖3安全性檢測(cè)流程圖Worki=AVAILABLE

8、i;FINISHi=false;輸出找到的安全序列，返回trueNEEDi<=Work&&FINISHi=falseYNWorki+=ALLOCATIONiFINISHi=true輸出進(jìn)程及資源變化結(jié)果系統(tǒng)不安全，返回false所有進(jìn)程FINISHi=ture;YN4:銀行家算法流程圖結(jié)束返回Bank()開(kāi)始輸入請(qǐng)求資源的進(jìn)程cusneed圖4銀行家算法流程圖輸入進(jìn)程請(qǐng)求資源REQUESTcusneedi提示安全,允許請(qǐng)求REQUESTcusneedi<=NEEDcusneediYNAVAILABLEi-=REQUESTcusneedi;ALLOCATIONcusn

9、eedi+=REQUESTcusneedi;NEEDcusneedi-=REQUESTcusneedi;分配資源分配資源操作回滾，恢復(fù)到未分配REQUESTcusneedi<= AVAILABLEiYNNSafe();繼續(xù)分配？YN六、源程序#include <iostream>#include <iomanip>#include <string>using namespace std;#define MAXPROCESS 50 /*最大進(jìn)程數(shù)*/#define MAXRESOURCE 100 /*最大資源數(shù)*/int AVAILABLEMAXRESO

10、URCE; /*可用資源數(shù)組*/int MAXMAXPROCESSMAXRESOURCE; /*最大需求矩陣*/int ALLOCATIONMAXPROCESSMAXRESOURCE; /*分配矩陣*/int NEEDMAXPROCESSMAXRESOURCE; /*需求矩陣*/int REQUESTMAXPROCESSMAXRESOURCE; /*進(jìn)程需要資源數(shù)*/bool FINISHMAXPROCESS; /*系統(tǒng)是否有足夠的資源分配*/int pMAXPROCESS; /*記錄序列*/int WorkMAXRESOURCE; /*工作數(shù)組*/int m,n; /*m個(gè)進(jìn)程,n個(gè)資源*/

11、string showdata14="max ","allo","need","aval"/*輸出表格用標(biāo)題*/string showdata25="work","need","allo","w+al","finish"/*輸出表格用標(biāo)題*/void iShow()int size,size2;cout<<"系統(tǒng)"for(int k=0;k<4;k+)size=showdata1

12、k.length();size2=(n*3+5-size)/2; /*計(jì)算出字符前端的空格*/cout<<setw(size2+size)<<showdata1k<<setw(size2)<<" "/*使得文字在資源標(biāo)志ABC總寬度下劇中*/cout<<endl;cout<<"資源"for(k=0;k<4;k+)char sourcename='A' /*資源命名，從A開(kāi)始*/cout<<" "for(int kk=0;kk<

13、;n;kk+)cout<<" "<<sourcename;sourcename+;cout<<" "cout<<endl;for(int ii=0;ii<m;ii+)cout<<"P"<<ii<<" "/*輸出進(jìn)程名及狀態(tài)*/for(int jj=0;jj<n;jj+)cout<<setw(3)<<MAXiijj;cout<<" "for(jj=0;jj<n;

14、jj+)cout<<setw(3)<<ALLOCATIONiijj;cout<<" "for(jj=0;jj<n;jj+)cout<<setw(3)<<NEEDiijj;cout<<" "if(ii=0)for(int iii=0;iii<n;iii+)cout<<setw(3)<<AVAILABLEiii;cout<<" "<<endl;void fShow()/*顯示表格*/cout<<&

15、quot;系統(tǒng)"for(int k=0;k<5;k+)int size=showdata2k.length();int size2=(n*3+5-size)/2;cout<<setw(size2+size)<<showdata2k<<setw(size2)<<" "cout<<endl;cout<<"資源"for(k=0;k<4;k+)char sourcename='A'cout<<" "for(int kk=0

16、;kk<n;kk+)cout<<setw(3)<<sourcename;sourcename+;cout<<" "cout<<endl;void Init() /*初始化算法*/ int i,j; cout<<"請(qǐng)輸入進(jìn)程的數(shù)目:" cin>>m; cout<<"請(qǐng)輸入資源的種類(lèi):" cin>>n; cout<<"請(qǐng)輸入每個(gè)進(jìn)程最多所需的各資源數(shù),按照"<<m<<"x&

17、quot;<<n<<"矩陣輸入"<<endl; for(i=0;i<m;i+) for(j=0;j<n;j+) cin>>MAXij; cout<<"請(qǐng)輸入每個(gè)進(jìn)程已分配的各資源數(shù),也按照"<<m<<"x"<<n<<"矩陣輸入"<<endl; for(i=0;i<m;i+) for(j=0;j<n;j+) cin>>ALLOCATIONij; NEEDij=MA

18、Xij-ALLOCATIONij; if(NEEDij<0) cout<<"您輸入的第"<<i+1<<"個(gè)進(jìn)程所擁有的第"<<j+1<<"個(gè)資源數(shù)錯(cuò)誤,請(qǐng)重新輸入:"<<endl; j-; continue; cout<<"請(qǐng)輸入各個(gè)資源現(xiàn)有的數(shù)目:"<<endl; for(i=0;i<n;i+) cin>>AVAILABLEi; iShow();bool Safe() /*安全性算法*/fSho

19、w(); int i,j,k,l=0; for(i=0;i<n;i+) Worki=AVAILABLEi; for(i=0;i<m;i+) FINISHi=false; for(i=0;i<m;i+) if(FINISHi=true) continue; else for(j=0;j<n;j+) if(NEEDij>Workj) break; if(j=n) FINISHi=true;cout<<"P"<<i<<" "for(k=0;k<n;k+)cout<<setw(3

20、)<<Workk;cout<<" "for(k=0;k<n;k+)cout<<setw(3)<<NEEDik;cout<<" "for(k=0;k<n;k+)cout<<setw(3)<<ALLOCATIONik;cout<<" "for(k=0;k<n;k+)cout<<setw(3)<<Workk+ALLOCATIONik;cout<<" "cout<<

21、;setw(3)<<"true"<<endl; for(k=0;k<n;k+) Workk+=ALLOCATIONik; pl+=i; i=-1; /*再次由進(jìn)程從小到大遍歷*/ else continue; if(l=m) /*進(jìn)程記錄p的數(shù)量等于資源總量，全部進(jìn)程均已經(jīng)滿足*/ cout<<"系統(tǒng)是安全的"<<endl; cout<<"安全序列:"<<endl; for(i=0;i<l;i+) cout<<pi; if(i!=l-1)

22、cout<<"->" cout<<""<<endl; return true; cout<<"n無(wú)法繼續(xù)找到可滿足的進(jìn)程!"<<endl; cout<<"系統(tǒng)是不安全的"<<endl; return false; void Bank() /*銀行家算法*/ int i,cusneed; /*cusneed為進(jìn)程*/ char again; while(1) cout<<"請(qǐng)輸入要申請(qǐng)資源的進(jìn)程號(hào)(注:第個(gè)

23、進(jìn)程號(hào)為,依次類(lèi)推):P" cin>>cusneed; cout<<"n請(qǐng)輸入進(jìn)程所請(qǐng)求的各資源的數(shù)量"<<endl; for(i=0;i<n;i+) cin>>REQUESTcusneedi; for(i=0;i<n;i+) if(REQUESTcusneedi>NEEDcusneedi) cout<<"您輸入的請(qǐng)求數(shù)超過(guò)進(jìn)程的需求量!請(qǐng)重新輸入!"<<endl; continue; if(REQUESTcusneedi>AVAILABLEi) cout&