实验3：银行家算法

实验3：银行家算法要求：编制模拟银行家算法的程序，并以下面给出的例子验证所编写的程序的正确性。某系统有A、B、C、D4类资源共5个进程〔P0、P1、P2、P3、P4〕共享，各进程对资源的需求和分配情况如下表所示：进程已占资源最大需求数ABCDABCDP000000012P110001750P213542356P306320652P400140656现在系统中A、B、C、D4类资源分别还剩1、5、2、0个，请按银行家算法答复以下问题：1〕现在系统是否处于平安状态？2〕如果现在进程P1提出需要〔0、4、2、0〕个资源的请求，系统能否满足它的请求？提示：假设进程P提出请求Request[i]，那么银行家算法按如下步骤进行判断。Step1：如果Request[i]<=Need[i]，那么转向Step2；否那么，出错。Step2：如果Request[i]<=Available[i]，那么转向Step3；否那么，出错。Step3：系统试探分配相关资源，修改相关数据：Available[i]=Available[i]-Request[i],Allocation[i]=Allocation[i]+Request[i],Need[i]=Need[i]-Request[i]Step4：系统执行平安性检查，如平安，那么分配成立；否那么试探性分配资源作废，系统恢复原状，进程进入等待状态。利用平安性检查算法检查根据银行家算法进行资源分配后系统状态是否处于平安状态。具体算法如下：Step1：设置两个工作向量work=Available，finish=false；Step2：从进程集合中找到一个满足下述条件的进程；finish=false,Need<=work假设能找到该进程，那么执行Step3，否那么，执行Step4。Step3：假设上述找到的进程获得资源，可顺利执行，直至完成，从而释放资源，做如下修改。work=work+Allocation,finish=true,gotoStep2;Step4：如果所有进程的finish=true，那么表示该系统平安；否那么系统不平安。源程序代码：#include<stdio.h>//#include<tchar.h>#include<iostream>usingnamespacestd;#defineMaxprocess50/*最大进程数*/#defineMaxresource100/*最大资源数*/intAvailable[Maxresource];/*可用资源数组*/intMAX[Maxprocess][Maxresource];/*最大需求矩阵*/intAllocation[Maxprocess][Maxresource];/*分配矩阵*/intneed[Maxprocess][Maxresource];/*需求矩阵*/intRequest[Maxprocess][Maxresource];/*进程需要资源数*/boolfinish[Maxprocess];/*系统是否有足够的资源分配*/intp[Maxprocess];/*记录序列*/intm,n;/*m个进程,n个资源*/voidInit();/*初始化算法*/boolSafe();/*平安性算法*/voidBank();/*银行家算法*/intmain(){ Init(); Safe(); Bank(); return1;}voidInit()/*初始化算法*/{ inti,j; cout<<"请输入进程的数目：";/*m个进程,n个资源*/ cin>>m; cout<<endl; cout<<"请输入资源的种类数目："; cin>>n; cout<<endl; cout<<"请输入每个进程最大需求的各资源数目,按照"<<m<<"x"<<n<<"矩阵输入："<<endl; for(i=0;i<m;i++) for(j=0;j<n;j++) cin>>MAX[i][j]; cout<<endl; cout<<"请输入每个进程已占各资源数目,也按照"<<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+1<<"个资源数错误,请重新输入:"<<endl; j--; continue; } } } cout<<endl; cout<<"请输入各个资源现有的数目："; for(i=0;i<n;i++) { cin>>Available[i]; } cout<<endl;}voidBank()/*银行家算法*/{ inti,cusneed; charagain; while(1) { cout<<endl; cout<<"请输入要申请资源的进程号(注:第1个进程号为0,依次类推)："; cin>>cusneed; cout<<endl; cout<<"请输入进程所请求的各资源的数目："; for(i=0;i<n;i++) { cin>>Request[cusneed][i]; } for(i=0;i<n;i++) { if(Request[cusneed][i]>need[cusneed][i]) { cout<<"您输入的请求数超过进程的需求量!请重新输入!"<<endl; continue; } if(Request[cusneed][i]>Available[i]) { cout<<"您输入的请求数超过系统有的资源数!请重新输入!"<<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<<"系统是平安的!"<<endl; cout<<endl; cout