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

沈陽理工大學(xué)課程設(shè)計(jì)專用紙No1PAGE目錄一、課程設(shè)計(jì)目的及要求 1二、相關(guān)知識(shí) 1三、題目分析 1四、概要設(shè)計(jì) 4五、代碼及流程 5六、運(yùn)行結(jié)果 10七、設(shè)計(jì)心得 12七、參考文獻(xiàn) 13一、課程設(shè)計(jì)目的及要求銀行家算法管理員可以把一定數(shù)量的作業(yè)供多個(gè)用戶周轉(zhuǎn)使用，為保證作業(yè)的安全管理員規(guī)定：（1）當(dāng)一個(gè)用戶對(duì)作業(yè)的最大需求量不超過管理員現(xiàn)有的資金就要接納該用戶；（2）用戶可以分期貸款,但貸款的總數(shù)不能超過最大需求量；（3）當(dāng)管理員現(xiàn)有的作業(yè)不能滿足用戶的沿需數(shù)時(shí),對(duì)用戶的請(qǐng)求可推遲支付,但總能使用戶在有限的時(shí)間里得到請(qǐng)求；（4）當(dāng)用戶得到所需的全部作業(yè)后,一定能在有限的時(shí)間里歸還所有的作業(yè)。二、相關(guān)知識(shí)1.銀行家算法:

設(shè)進(jìn)程i提出請(qǐng)求Request[n]，則銀行家算法按如下規(guī)則進(jìn)行判斷。

(1)如果Request[n]>Need[i，n]，則報(bào)錯(cuò)返回。

(2)如果Request[n]>Available，則進(jìn)程i進(jìn)入等待資源狀態(tài)，返回。

(3)假設(shè)進(jìn)程i的申請(qǐng)已獲批準(zhǔn)，于是修改系統(tǒng)狀態(tài)：

Available=Available-Request

Allocation=Allocation+Request

Need=Need-Request

(4)系統(tǒng)執(zhí)行安全性檢查，如安全，則分配成立；否則試探險(xiǎn)性分配作廢，系統(tǒng)恢復(fù)原狀，進(jìn)程等待。

2.安全性檢查

(1)設(shè)置兩個(gè)工作向量Work=Available；Finish[M]=False

(2)從進(jìn)程集合中找到一個(gè)滿足下述條件的進(jìn)程，

Finish[i]=False

Need<=Work

如找到，執(zhí)行(3)；否則，執(zhí)行(4)

(3)設(shè)進(jìn)程獲得資源，可順利執(zhí)行，直至完成，從而釋放資源。

Work=Work+Allocation

Finish=True

GOTO2

(4)如所有的進(jìn)程Finish[M]=true，則表示安全；否則系統(tǒng)不安全三、題目分析銀行家算法是一種最有代表性的避免死鎖的算法。

要解釋銀行家算法，必須先解釋操作系統(tǒng)安全狀態(tài)和不安全狀態(tài)。

安全狀態(tài)：如果存在一個(gè)由系統(tǒng)中所有進(jìn)程構(gòu)成的安全序列P1，…，Pn，則系統(tǒng)處于安全狀態(tài)。安全狀態(tài)一定是沒有死鎖發(fā)生。

不安全狀態(tài):不存在一個(gè)安全序列。不安全狀態(tài)不一定導(dǎo)致死鎖。

那么什么是安全序列呢？

安全序列：一個(gè)進(jìn)程序列{P1，…，Pn}是安全的，如果對(duì)于每一個(gè)進(jìn)程Pi(1≤i≤n），它以后尚需要的資源量不超過系統(tǒng)當(dāng)前剩余資源量與所有進(jìn)程Pj(j<i)當(dāng)前占有資源量之和。銀行家算法：

我們可以把操作系統(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ù)之和是否超過了該進(jìn)程對(duì)資源的最大需求量。若超過則拒絕分配資源，若沒有超過則再測(cè)試系統(tǒng)現(xiàn)存的資源能否滿足該進(jìn)程尚需的最大資源量，若能滿足則按當(dāng)前的申請(qǐng)量分配資源，否則也要推遲分配。四、概要設(shè)計(jì)1.初始化算法init()可利用資源向量intAvailable[j]j為資源的種類。最大需求矩陣intMax[i][j]i為進(jìn)程的數(shù)量。分配矩陣intAllocation[i][j]需求矩陣intneed[i][j]=Max[i][j]-Allocation[i][j]申請(qǐng)各類資源數(shù)量intRequesti[j]i進(jìn)程申請(qǐng)j資源的數(shù)量工作向量intWork[x]intFinish[y]2銀行家算法bank()進(jìn)程i發(fā)出請(qǐng)求申請(qǐng)k個(gè)j資源，Requesti[j]=k(1)檢查申請(qǐng)量是否不大于需求量：Requesti[j]<=need[i,j],若條件不符重新輸入，不允許申請(qǐng)大于需求量。(2)檢查申請(qǐng)量是否小于系統(tǒng)中的可利用資源數(shù)量：Requesti[j]<=available[i,j]，若條件不符就申請(qǐng)失敗，阻塞該進(jìn)程，用goto語句跳轉(zhuǎn)到重新申請(qǐng)資源。(3)若以上兩個(gè)條件都滿足，則系統(tǒng)試探著將資源分配給申請(qǐng)的進(jìn)程，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：Available[i,j]=Available[i,j]-Requesti[j]；Allocation[i][j]=Allocation[i][j]+Requesti[j]；need[i][j]=need[i][j]-Requesti[j]；(4)試分配后，執(zhí)行安全性檢查，調(diào)用safe()函數(shù)檢查此次資源分配后系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程；否則本次試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓該進(jìn)程等待。(5)用do{…}while循環(huán)語句實(shí)現(xiàn)輸入字符y/n判斷是否繼續(xù)進(jìn)行資源申請(qǐng)。3安全性檢查算法（safe()函數(shù)）(1)設(shè)置兩個(gè)向量：工作向量Work，它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目，在執(zhí)行安全性算法開始時(shí)，Work=Available。Finish，它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開始時(shí)先做Finish[i]=0；當(dāng)有足夠的資源分配給進(jìn)程時(shí)，再令Finish[i]=1。(2)在進(jìn)程中查找符合以下條件的進(jìn)程：條件1：Finish[i]=0；條件2：need[i][j]<=Work[j]若找到，則執(zhí)行步驟(3)否則，執(zhí)行步驟(4)(3)當(dāng)進(jìn)程獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行：Work[j]=Work[j]+Allocation[i][j]；Finish[i]=1；gotostep2；(4)如果所有的Finish[i]=1都滿足，則表示系統(tǒng)處于安全狀態(tài)，否則，處于不安全狀態(tài)。五、代碼及流程#include<iostream.h>#include<vector>#include<iomanip>usingnamespacestd;#defineTRUE1//定義TRUE=1#defineFALSE0//定義FLASE=0voidbank(vector<int>,vector<vector<int>>,vector<vector<int>>,int,int);//聲明bank（銀行家算法）intsafe(vector<int>Available,vector<vector<int>>Need,vector<vector<int>>Allocation,intn,intm);//聲明safe（）安全性算法voidinit();voidmain(){init();}voidinit(){intm;//m資源類數(shù) intn;//進(jìn)程數(shù) cout<<"輸入資源類數(shù)"<<endl; cin>>m; vector<int>Available(m);//動(dòng)態(tài)申請(qǐng)數(shù)組Available可用資源向量總的資源 cout<<"輸入各類資源總數(shù):"<<endl; FILE*fp; fp=fopen("Available.txt","r+"); cout<<"從Available.txt文件中讀入數(shù)據(jù)，并輸出"<<endl; for(inti=0;i<m;i++) { fscanf(fp,"%d",&Available[i]); cout<<Available[i]<<'\t'; } fclose(fp); cout<<"\n輸入進(jìn)程數(shù)"<<endl; cin>>n; vector<vector<int>>Max(n,vector<int>(m));//進(jìn)程所需的最大資源數(shù) fp=fopen("Max.txt","r+"); cout<<"從Max.txt文件中讀入數(shù)據(jù)，并輸出"<<endl; for(i=0;i<n;i++) { for(intj=0;j<m;j++) { fscanf(fp,"%d",&Max[i][j]); cout<<Max[i][j]<<""; } cout<<endl; } fclose(fp); cout<<"輸入已分配的Allocation"<<endl;//已經(jīng)分配給進(jìn)程的資源數(shù) vector<vector<int>>Allocation(n,vector<int>(m)); vector<vector<int>>Need(n,vector<int>(m)); fp=fopen("Allocation.txt","r+"); cout<<"Allocation.txt從文件中讀入數(shù)據(jù)，并輸出"<<endl; for(i=0;i<n;i++) { for(intj=0;j<m;j++) { fscanf(fp,"%d",&Allocation[i][j]); Need[i][j]=Max[i][j]-Allocation[i][j];//在初始化Max時(shí)，同時(shí)初始化Need數(shù)組 Available[j]=Available[j]-Allocation[i][j];//在初始化Max時(shí)，同時(shí)修改Available數(shù)組 cout<<Allocation[i][j]<<""; } cout<<endl; } fclose(fp); safe(Available,Need,Allocation,n,m); cout<<"此狀態(tài)安全!"<<endl; bank(Available,Need,Allocation,n,m);//調(diào)用銀行家算法bank()函數(shù)}voidbank(vector<int>Available,vector<vector<int>>Need,vector<vector<int>>Allocation,intn,intm){ vector<int>Request(m); intall=0; //定義變量all，如果all==0，表示進(jìn)程已經(jīng)運(yùn)行完，如果all>=1，表示還有進(jìn)程沒有運(yùn)行完 for(inti=0;i<n;i++) for(intj=0;j<m;j++) all+=Need[i][j]; if(0==all) { cout<<"所有進(jìn)程已經(jīng)運(yùn)行完，結(jié)束"<<endl; exit(0); } intjc;//任選一個(gè)進(jìn)程 charagain; all=0;//重新初始化all， while(1) { while(all==0) { all=0; //如果all==0，表示進(jìn)程已經(jīng)運(yùn)行完，如果all>=1，表示還有進(jìn)程沒有運(yùn)行完 //循環(huán)直至all>0,即找到一個(gè)未運(yùn)行完的進(jìn)程 cout<<"任選一個(gè)進(jìn)程作為當(dāng)前進(jìn)程0--"<<n-1<<endl; cin>>jc; for(intj=0;j<m;j++) { all+=Need[jc][j]; } if(0==all) { cout<<"此進(jìn)程已經(jīng)運(yùn)行，重新輸入"<<endl; } } cout<<"輸入該進(jìn)程的請(qǐng)求向量"<<endl; for(i=0;i<m;i++) { cin>>Request[i]; while(Request[i]>Need[jc][i]||Request[i]>Available[i]) { cout<<"請(qǐng)求向量無法滿足"<<endl; break;} } ////////////////////////////////////////////////////////////////////////// //系統(tǒng)試探著把資源分配給該進(jìn)程/////////////////////////////////////////// for(i=0;i<m;i++) { Available[i]=Available[i]-Request[i]; Allocation[jc][i]=Allocation[jc][i]+Request[i]; Need[jc][i]=Need[jc][i]-Request[i]; } intbb=0; bb=safe(Available,Need,Allocation,n,m);//調(diào)用安全性算法，判斷此次資源分配后，系統(tǒng)是否處安全狀態(tài) if(1==bb) { cout<<"系統(tǒng)成功分配資源"<<endl; } else { cout<<"系統(tǒng)未能成分配資源,收回預(yù)分配資源"<<endl; for(i=0;i<m;i++) { Available[i]=Available[i]+Request[i]; Allocation[jc][i]=Allocation[jc][i]-Request[i]; Need[jc][i]=Need[jc][i]+Request[i]; } } cout<<"您還想再次請(qǐng)求分配嗎?是請(qǐng)按y/Y,否請(qǐng)按其它鍵"<<endl; cin>>again;if(again=='y'||again=='Y'){all=0; continue;}break; }}/**************************************安全性算法safe()函數(shù)*********************************************************/intsafe(vector<int>Available,vector<vector<int>>Need,vector<vector<int>>Allocation,intn,intm){ vector<int>Work(m),Finish(n);//申請(qǐng)工作向量work，finish Work=Available; vector<int>count(n);//記錄安全序列 intflag=0; intlen=-1;//記錄安全序列的進(jìn)程個(gè)數(shù)，如果len==n，即表示所有的finish【i】=true，處于安全狀態(tài) for(inti=0;i<n;i++)Finish[i]=FALSE;for(i=0;i<n;i=(++i)%n){ flag++; intneeded=1; for(intj=0;j<m;j++) { if(Need[i][j]<=Work[j]) { needed=needed*TRUE; } elseneeded=needed*FALSE; } if((Finish[i]==FALSE)&&needed==1) { for(j=0;j<m;j++) { Work[j]=Work[j]+Allocation[i][j]; } Finish[i]=TRUE; len=len+1; count[len]=i; flag=0; } if(flag>=n)break; } if(len==n-1) {cout<<"系統(tǒng)是安全的"<<endl; cout<<"安全序列"<<endl; for(i=0;i<=len;i++) { cout<<count[i]; if(i!=len) { cout<<"-->"; } } cout<<endl; returnTRUE; } else { cout<<"系統(tǒng)是不安全的"<<endl; returnFALSE;}}六、運(yùn)行結(jié)果初始化結(jié)果圖4.1運(yùn)行結(jié)果檢測(cè)系統(tǒng)資源分配是否安全結(jié)果：圖4.2安全性檢測(cè)圖4.3安全性檢