操作系统课设-银行家算法

沈阳理工大学课程设计专用纸No1PAGE目录一、课程设计目的及要求 1二、相关知识 1三、题目分析 1四、概要设计 4五、代码及流程 5六、运行结果 10七、设计心得 12七、参考文献 13一、课程设计目的及要求银行家算法管理员可以把一定数量的作业供多个用户周转使用，为保证作业的安全管理员规定：（1）当一个用户对作业的最大需求量不超过管理员现有的资金就要接纳该用户；（2）用户可以分期贷款,但贷款的总数不能超过最大需求量；（3）当管理员现有的作业不能满足用户的沿需数时,对用户的请求可推迟支付,但总能使用户在有限的时间里得到请求；（4）当用户得到所需的全部作业后,一定能在有限的时间里归还所有的作业。二、相关知识1.银行家算法:

设进程i提出请求Request[n]，则银行家算法按如下规则进行判断。

(1)如果Request[n]>Need[i，n]，则报错返回。

(2)如果Request[n]>Available，则进程i进入等待资源状态，返回。

(3)假设进程i的申请已获批准，于是修改系统状态：

Available=Available-Request

Allocation=Allocation+Request

Need=Need-Request

(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。

2.安全性检查

(1)设置两个工作向量Work=Available；Finish[M]=False

(2)从进程集合中找到一个满足下述条件的进程，

Finish[i]=False

Need<=Work

如找到，执行(3)；否则，执行(4)

(3)设进程获得资源，可顺利执行，直至完成，从而释放资源。

Work=Work+Allocation

Finish=True

GOTO2

(4)如所有的进程Finish[M]=true，则表示安全；否则系统不安全三、题目分析银行家算法是一种最有代表性的避免死锁的算法。

要解释银行家算法，必须先解释操作系统安全状态和不安全状态。

安全状态：如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。

不安全状态:不存在一个安全序列。不安全状态不一定导致死锁。

那么什么是安全序列呢？

安全序列：一个进程序列{P1，…，Pn}是安全的，如果对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj(j<i)当前占有资源量之和。银行家算法：

我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。四、概要设计1.初始化算法init()可利用资源向量intAvailable[j]j为资源的种类。最大需求矩阵intMax[i][j]i为进程的数量。分配矩阵intAllocation[i][j]需求矩阵intneed[i][j]=Max[i][j]-Allocation[i][j]申请各类资源数量intRequesti[j]i进程申请j资源的数量工作向量intWork[x]intFinish[y]2银行家算法bank()进程i发出请求申请k个j资源，Requesti[j]=k(1)检查申请量是否不大于需求量：Requesti[j]<=need[i,j],若条件不符重新输入，不允许申请大于需求量。(2)检查申请量是否小于系统中的可利用资源数量：Requesti[j]<=available[i,j]，若条件不符就申请失败，阻塞该进程，用goto语句跳转到重新申请资源。(3)若以上两个条件都满足，则系统试探着将资源分配给申请的进程，并修改下面数据结构中的数值：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)试分配后，执行安全性检查，调用safe()函数检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程；否则本次试探分配作废，恢复原来的资源分配状态，让该进程等待。(5)用do{…}while循环语句实现输入字符y/n判断是否继续进行资源申请。3安全性检查算法（safe()函数）(1)设置两个向量：工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目，在执行安全性算法开始时，Work=Available。Finish，它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish[i]=0；当有足够的资源分配给进程时，再令Finish[i]=1。(2)在进程中查找符合以下条件的进程：条件1：Finish[i]=0；条件2：need[i][j]<=Work[j]若找到，则执行步骤(3)否则，执行步骤(4)(3)当进程获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Work[j]=Work[j]+Allocation[i][j]；Finish[i]=1；gotostep2；(4)如果所有的Finish[i]=1都满足，则表示系统处于安全状态，否则，处于不安全状态。五、代码及流程#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资源类数 intn;//进程数 cout<<"输入资源类数"<<endl; cin>>m; vector<int>Available(m);//动态申请数组Available可用资源向量总的资源 cout<<"输入各类资源总数:"<<endl; FILE*fp; fp=fopen("Available.txt","r+"); cout<<"从Available.txt文件中读入数据，并输出"<<endl; for(inti=0;i<m;i++) { fscanf(fp,"%d",&Available[i]); cout<<Available[i]<<'\t'; } fclose(fp); cout<<"\n输入进程数"<<endl; cin>>n; vector<vector<int>>Max(n,vector<int>(m));//进程所需的最大资源数 fp=fopen("Max.txt","r+"); cout<<"从Max.txt文件中读入数据，并输出"<<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;//已经分配给进程的资源数 vector<vector<int>>Allocation(n,vector<int>(m)); vector<vector<int>>Need(n,vector<int>(m)); fp=fopen("Allocation.txt","r+"); cout<<"Allocation.txt从文件中读入数据，并输出"<<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时，同时初始化Need数组 Available[j]=Available[j]-Allocation[i][j];//在初始化Max时，同时修改Available数组 cout<<Allocation[i][j]<<""; } cout<<endl; } fclose(fp); safe(Available,Need,Allocation,n,m); cout<<"此状态安全!"<<endl; bank(Available,Need,Allocation,n,m);//调用银行家算法bank()函数}voidbank(vector<int>Available,vector<vector<int>>Need,vector<vector<int>>Allocation,intn,intm){ vector<int>Request(m); intall=0; //定义变量all，如果all==0，表示进程已经运行完，如果all>=1，表示还有进程没有运行完 for(inti=0;i<n;i++) for(intj=0;j<m;j++) all+=Need[i][j]; if(0==all) { cout<<"所有进程已经运行完，结束"<<endl; exit(0); } intjc;//任选一个进程 charagain; all=0;//重新初始化all， while(1) { while(all==0) { all=0; //如果all==0，表示进程已经运行完，如果all>=1，表示还有进程没有运行完 //循环直至all>0,即找到一个未运行完的进程 cout<<"任选一个进程作为当前进程0--"<<n-1<<endl; cin>>jc; for(intj=0;j<m;j++) { all+=Need[jc][j]; } if(0==all) { cout<<"此进程已经运行，重新输入"<<endl; } } cout<<"输入该进程的请求向量"<<endl; for(i=0;i<m;i++) { cin>>Request[i]; while(Request[i]>Need[jc][i]||Request[i]>Available[i]) { cout<<"请求向量无法满足"<<endl; break;} } ////////////////////////////////////////////////////////////////////////// //系统试探着把资源分配给该进程/////////////////////////////////////////// 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);//调用安全性算法，判断此次资源分配后，系统是否处安全状态 if(1==bb) { cout<<"系统成功分配资源"<<endl; } else { cout<<"系统未能成分配资源,收回预分配资源"<<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<<"您还想再次请求分配吗?是请按y/Y,否请按其它键"<<endl; cin>>again;if(again=='y'||again=='Y'){all=0; continue;}break; }}/**************************************安全性算法safe()函数*********************************************************/intsafe(vector<int>Available,vector<vector<int>>Need,vector<vector<int>>Allocation,intn,intm){ vector<int>Work(m),Finish(n);//申请工作向量work，finish Work=Available; vector<int>count(n);//记录安全序列 intflag=0; intlen=-1;//记录安全序列的进程个数，如果len==n，即表示所有的finish【i】=true，处于安全状态 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<<"系统是安全的"<<endl; cout<<"安全序列"<<endl; for(i=0;i<=len;i++) { cout<<count[i]; if(i!=len) { cout<<"-->"; } } cout<<endl; returnTRUE; } else { cout<<"系统是不安全的"<<endl; returnFALSE;}}六、运行结果初始化结果图4.1运行结果检测系统资源分配是否安全结果：图4.2安全性检测图4.3安全性检