实验三 银行家算法

实验三银行家算法实验目的死锁会引起计算机工作僵死，因此操作系统中必须防止。本实验的目的在于使用高级语言编写和调试一个系统动态分配资源的简单模拟程序，了解死锁产生的条件和原因，并采用银行家算法有效地防止死锁的发生，以加深对课堂上所讲授的知识的理解。实验要求设计有n个进程共享m个系统资源的系统，进程可动态的申请和释放资源，系统按各进程的申请动态的分配资源。系统能显示各个进程申请和释放资源，以及系统动态分配资源的过程，便于用户观察和分析；数据结构可利用资源向量Available，它是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源的数目，其初始值是系统中所配置的该类全部可用资源数目。其数值随该类资源的分配和回收而动态地改变。如果Available（j）=k，标是系统中现有Rj类资源k个。最大需求矩阵Max，这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max（i，j）=k，表示进程i需要Rj类资源的最大数目为k。分配矩阵Allocation，这是一个n×m的矩阵，它定义了系统中的每类资源当前一分配到每一个进程的资源数。如果Allocation（i，j）=k，表示进程i当前已经分到Rj类资源的数目为k。Allocationi表示进程i的分配向量，有矩阵Allocation的第i行构成。需求矩阵Need，这是一个n×m的矩阵，用以表示每个进程还需要的各类资源的数目。如果Need（i，j）=k，表示进程i还需要Rj类资源k个，才能完成其任务。Needi表示进程i的需求向量，由矩阵Need的第i行构成。上述三个矩阵间存在关系：Need（i，j）=Max（i，j）-Allocation（i，j）；银行家算法Requesti是进程Pi的请求向量。Requesti（j）=k表示进程Pi请求分配Rj类资源k个。当Pi发出资源请求后，系统按下述步骤进行检查：如果Requesti≤Need，则转向步骤2；否则，认为出错，因为它所请求的资源数已超过它当前的最大需求量。如果Requesti≤Available，则转向步骤3；否则，表示系统中尚无足够的资源满足Pi的申请，Pi必须等待。系统试探性地把资源分配给进程Pi，并修改下面数据结构中的数值：Available=Available-RequestiAllocationi=Allocationi+RequestiNeedi=Needi-Requesti系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。如果安全才正式将资源分配给进程Pi，以完成本次分配；否则，将试探分配作废，恢复原来的资源分配状态，让进程Pi等待。安全性算法设置两个向量。Work：它表示系统可提供给进程继续运行的各类资源数目，它包含m个元素，开始执行安全性算法时，Work=Available。Finish：它表示系统是否有足够的资源分配给进程，使之运行完成，开始Finish（I）=false；当有足够资源分配给进程Pi时，令Finish（i）=true；从进程集合中找到一个能满足下述条件的进程。Finish（i）==false；Needi≤work；如找到则执行步骤3；否则，执行步骤4；当进程Pi获得资源后，可顺利执行直到完成，并释放出分配给它的资源，故应执行Work=work+AllocationiFinish（i）=true；转向步骤2；若所有进程的Finish（i）都为true，则表示系统处于安全状态；否则，系统处于不安全状态。开始输入资源数m,及各类资源总数，初始化Available向量输入进程数n，i=1开始输入资源数m,及各类资源总数，初始化Available向量输入进程数n，i=1输入进程i的最大需求向量max。i≤nmax≤资源总数提示错误重新输入i加1任选一个进程作为当前进程输入该进程的资源请求量Request调用银行家算法，及安全性算法，完成分配，或并给出提示该进程的Need向量为0该进程已运行结束Need矩阵为0所有进程运行都结束结束NYYNNY初始化need矩阵NY七．银行家算法程序代码#include<string.h>#include<stdio.h>#include<iostream.h>#defineFALSE0#defineTRUE1#defineW10#defineR10intM;//总进程数intN;//资源种类intALL_RESOURCE[W];//各种资源的数目总和intMAX[W][R];//M个进程对N类资源最大资源需求量intAVAILABLE[R];//系统可用资源数intALLOCATION[W][R];//M个进程已经得到N类资源的资源量intNEED[W][R];//M个进程还需要N类资源的资源量intRequest[R];//请求资源个数intP[W];//进程安全序列voidoutput(){inti,j;cout<<endl<<"━━━━━━━━━━━━━━━━━━"<<endl;cout<<"各种资源的总数量:"<<endl;for(j=0;j<N;j++)cout<<"资源"<<j<<":"<<ALL_RESOURCE[j];cout<<endl;cout<<"━━━━━━━━━━━━━━━━━━"<<endl;cout<<"目前各种资源可利用的数量为:"<<endl;for(j=0;j<N;j++)cout<<"资源"<<j<<":"<<AVAILABLE[j];cout<<endl;cout<<"━━━━━━━━━━━━━━━━━━"<<endl;cout<<"各进程还需要的资源数量:"<<endl<<endl;for(i=0;i<N;i++)cout<<"资源"<<i;cout<<endl;for(i=0;i<M;i++){cout<<"进程"<<i<<":";for(j=0;j<N;j++)cout<<NEED[i][j]<<""; cout<<endl;}cout<<endl;cout<<"━━━━━━━━━━━━━━━━━━"<<endl;cout<<"各进程已经得到的资源量:"<<endl<<endl;for(i=0;i<N;i++)cout<<"资源"<<i;cout<<endl;for(i=0;i<M;i++){cout<<"进程"<<i<<":";for(j=0;j<N;j++)cout<<ALLOCATION[i][j]<<""; cout<<endl;}cout<<endl;}voiddistribute(intk)//执行资源分配{intj;for(j=0;j<N;j++){AVAILABLE[j]=AVAILABLE[j]-Request[j];ALLOCATION[k][j]=ALLOCATION[k][j]+Request[j];NEED[k][j]=NEED[k][j]-Request[j];}}voidrestore(intk)//撤销资源分配{intj;for(j=0;j<N;j++){AVAILABLE[j]=AVAILABLE[j]+Request[j];ALLOCATION[k][j]=ALLOCATION[k][j]-Request[j];NEED[k][j]=NEED[k][j]+Request[j];}}intcheck()//安全性检查{intWORK[R],FINISH[W];inti,j,l=0;for(j=0;j<N;j++)WORK[j]=AVAILABLE[j];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(intk=0;k<N;k++) WORK[k]=WORK[k]+ALLOCATION[i][k]; P[l++]=i; i=-1; } elsecontinue; }if(l==M) { cout<<endl;cout<<"经安全性检查，系统安全，本次分配成功。"<<endl;cout<<endl; cout<<"安全序列是："<<endl; for(i=0;i<l;i++) { cout<<P[i]; if(i!=l-1)cout<<"-->"; } cout<<endl;return0; } }cout<<endl;cout<<"系统不安全!!!本次资源申请不成功!!!"<<endl;cout<<endl;return1;}voidbank()//银行家算法{inti=0,j=0;charflag='Y';while(flag=='Y'||flag=='y'){i=-1;while(i<0||i>=M){cout<<"━━━━━━━━━━━━━━━━━━"<<endl;cout<<endl<<"请输入需申请资源的进程号:";cin>>i;if(i<0||i>=M)cout<<"输入的进程号不存在，重新输入!"<<endl;}cout<<"请输入进程"<<i<<"申请各类资源的数量:"<<endl;for(j=0;j<N;j++){cout<<"资源"<<j<<":";cin>>Request[j];if(Request[j]>NEED[i][j])//若请求的资源数大于进程还需要i类资源的资源量j{cout<<endl<<"进程"<<i<<"申请的资源数大于进程"<<i<<"还需要"<<j<<"类资源的数量!";cout<<"若继续执行系统将处于不安全状态!"<<endl;flag='N';break;}else{if(Request[j]>AVAILABLE[j])//若请求的资源数大于可用资源数{cout<<endl<<"进程"<<i<<"申请的资源数大于系统可用"<<j<<"类资源的数量!";cout<<"若继续执行系统将处于不安全状态!"<<endl;flag='N';break;}}}if(flag=='Y'||flag=='y'){distribute(i);//调用distribute(i)函数，改变资源数if(check())//若系统不安全{restore(i);//调用restore(i)函数，恢复资源数output();//输出资源分配情况}else//若系统安全output();//输出资源分配情况}else//若flag=N||flag=ncout<<endl;cout<<"是否继续银行家算法演示,按'Y'或'y'键继续,按'N'或'n'键退出演示:";cin>>flag;}}voidversion(){cout<<endl;cout<<"\t银行家算法"<<endl;}voidmain()//主函数{inti=0,j=0,p;version();getchar();cout<<endl<<"请输入总进程数:";cin>>M;cout<<endl<<"━━━━━━━━━━━━━━━━━━"<<endl;cout<<"请输入总资源种类:";cin>>N;cout<<endl<<"━━━━━━━━━━━━━━━━━━"<<endl;cout<<"请输入各类资源总数:(需要输入数为"<<N<<"个)";for(i=0;i<N;i++)cin>>ALL_RESOURCE[i];cout<<endl<<"━━━━━━━━━━━━━━━━━━"<<endl;cout<<"输入各进程所需要的各类资源的最大数量:(需要输入数为"<<M*N<<"个)";for(i=0;i<M;i++){for(j=0;j<N;j++){do{cin>>MAX[i][j];if(MAX[i][j]>ALL_RESOURCE[j])cout<<endl<<"占有资源超过了声明的该资源总数,请重新输入"<<endl;}while(MAX[i][j]>ALL_RESOURCE[j]);}}cout<<endl<<"━━━━━━━━━━━━━━━━━━"<<endl;cout<<"输入各进程已经占据的各类资源的数量:(需要输入数为"<<M *N<<"个)";for(i=0;i<M;i++){for(j=0;j<N;j++){do{cin>>ALLOCATION[i][j];if(ALLOCATION[i][j]>MAX[i