實驗3：銀行家算法

實驗3：銀行家算法要求：編制模擬銀行家算法的程序，并以下面給出的例子驗證所編寫的程序的正確性。某系統(tǒng)有A、B、C、D4類資源共5個進(jìn)程〔P0、P1、P2、P3、P4〕共享，各進(jìn)程對資源的需求和分配情況如下表所示：進(jìn)程已占資源最大需求數(shù)ABCDABCDP000000012P110001750P213542356P306320652P400140656現(xiàn)在系統(tǒng)中A、B、C、D4類資源分別還剩1、5、2、0個，請按銀行家算法答復(fù)以下問題：1〕現(xiàn)在系統(tǒng)是否處于平安狀態(tài)？2〕如果現(xiàn)在進(jìn)程P1提出需要〔0、4、2、0〕個資源的請求，系統(tǒng)能否滿足它的請求？提示：假設(shè)進(jìn)程P提出請求Request[i]，那么銀行家算法按如下步驟進(jìn)行判斷。Step1：如果Request[i]<=Need[i]，那么轉(zhuǎn)向Step2；否那么，出錯。Step2：如果Request[i]<=Available[i]，那么轉(zhuǎn)向Step3；否那么，出錯。Step3：系統(tǒng)試探分配相關(guān)資源，修改相關(guān)數(shù)據(jù)：Available[i]=Available[i]-Request[i],Allocation[i]=Allocation[i]+Request[i],Need[i]=Need[i]-Request[i]Step4：系統(tǒng)執(zhí)行平安性檢查，如平安，那么分配成立；否那么試探性分配資源作廢，系統(tǒng)恢復(fù)原狀，進(jìn)程進(jìn)入等待狀態(tài)。利用平安性檢查算法檢查根據(jù)銀行家算法進(jìn)行資源分配后系統(tǒng)狀態(tài)是否處于平安狀態(tài)。具體算法如下：Step1：設(shè)置兩個工作向量work=Available，finish=false；Step2：從進(jìn)程集合中找到一個滿足下述條件的進(jìn)程；finish=false,Need<=work假設(shè)能找到該進(jìn)程，那么執(zhí)行Step3，否那么，執(zhí)行Step4。Step3：假設(shè)上述找到的進(jìn)程獲得資源，可順利執(zhí)行，直至完成，從而釋放資源，做如下修改。work=work+Allocation,finish=true,gotoStep2;Step4：如果所有進(jìn)程的finish=true，那么表示該系統(tǒng)平安；否那么系統(tǒng)不平安。源程序代碼：#include<stdio.h>//#include<tchar.h>#include<iostream>usingnamespacestd;#defineMaxprocess50/*最大進(jìn)程數(shù)*/#defineMaxresource100/*最大資源數(shù)*/intAvailable[Maxresource];/*可用資源數(shù)組*/intMAX[Maxprocess][Maxresource];/*最大需求矩陣*/intAllocation[Maxprocess][Maxresource];/*分配矩陣*/intneed[Maxprocess][Maxresource];/*需求矩陣*/intRequest[Maxprocess][Maxresource];/*進(jìn)程需要資源數(shù)*/boolfinish[Maxprocess];/*系統(tǒng)是否有足夠的資源分配*/intp[Maxprocess];/*記錄序列*/intm,n;/*m個進(jìn)程,n個資源*/voidInit();/*初始化算法*/boolSafe();/*平安性算法*/voidBank();/*銀行家算法*/intmain(){ Init(); Safe(); Bank(); return1;}voidInit()/*初始化算法*/{ inti,j; cout<<"請輸入進(jìn)程的數(shù)目：";/*m個進(jìn)程,n個資源*/ cin>>m; cout<<endl; cout<<"請輸入資源的種類數(shù)目："; cin>>n; cout<<endl; cout<<"請輸入每個進(jìn)程最大需求的各資源數(shù)目,按照"<<m<<"x"<<n<<"矩陣輸入："<<endl; for(i=0;i<m;i++) for(j=0;j<n;j++) cin>>MAX[i][j]; cout<<endl; cout<<"請輸入每個進(jìn)程已占各資源數(shù)目,也按照"<<m<<"x"<<n<<"矩陣輸入："<<endl; for(i=0;i<m;i++) { for(j=0;j<n;j++) { cin>>Allocation[i][j]; need[i][j]=MAX[i][j]-Allocation[i][j]; if(need[i][j]<0) { cout<<"您輸入的第"<<i+1<<"個進(jìn)程所擁有的第"<<j+1<<"個資源數(shù)錯誤,請重新輸入:"<<endl; j--; continue; } } } cout<<endl; cout<<"請輸入各個資源現(xiàn)有的數(shù)目："; for(i=0;i<n;i++) { cin>>Available[i]; } cout<<endl;}voidBank()/*銀行家算法*/{ inti,cusneed; charagain; while(1) { cout<<endl; cout<<"請輸入要申請資源的進(jìn)程號(注:第1個進(jìn)程號為0,依次類推)："; cin>>cusneed; cout<<endl; cout<<"請輸入進(jìn)程所請求的各資源的數(shù)目："; for(i=0;i<n;i++) { cin>>Request[cusneed][i]; } for(i=0;i<n;i++) { if(Request[cusneed][i]>need[cusneed][i]) { cout<<"您輸入的請求數(shù)超過進(jìn)程的需求量!請重新輸入!"<<endl; continue; } if(Request[cusneed][i]>Available[i]) { cout<<"您輸入的請求數(shù)超過系統(tǒng)有的資源數(shù)!請重新輸入!"<<endl; continue; } } for(i=0;i<n;i++) { Available[i]-=Request[cusneed][i]; Allocation[cusneed][i]+=Request[cusneed][i]; need[cusneed][i]-=Request[cusneed][i]; } if(Safe()) { cout<<endl; cout<<"同意分配請求!"<<endl; } else { cout<<endl; cout<<"您的請求被拒絕!"<<endl; for(i=0;i<n;i++) { Available[i]+=Request[cusneed][i]; Allocation[cusneed][i]-=Request[cusneed][i]; need[cusneed][i]+=Request[cusneed][i]; } } for(i=0;i<m;i++) { finish[i]=false; } cout<<endl; cout<<"您還想再次請求分配嗎?是請按y/Y,否請按其它鍵!"<<endl; cin>>again; if(again=='y'||again=='Y') { continue; } break; }}boolSafe()/*平安性算法*/{ inti,j,k,l=0; intWork[Maxresource]; for(i=0;i<n;i++) Work[i]=Available[i]; for(i=0;i<m;i++) { finish[i]=false; } for(i=0;i<m;i++) { if(finish[i]==true) { continue; } else { for(j=0;j<n;j++) { if(need[i][j]>Work[j]) { break; } } if(j==n) { finish[i]=true; for(k=0;k<n;k++) { Work[k]+=Allocation[i][k]; cout<<Work[k]; } p[l++]=i; i=-1; } else { continue; } } if(l==m) { cout<<"系統(tǒng)是平安的!"<<endl; cout<<endl; cout