操作系统银行家算法

[操作系统]银行家算法操作系统实验报告实验目标1.理解银行家算法。2.掌握进程安全性检查的方法及资源分配的方法。3.加深了解有关资源申请、避免死锁等概念。4.体会和了解死锁和避免死锁的具体实施方法。实验要求编写和调试一个系统动态分配资源的简单模拟程序，观察死锁产生的条件，并采用银行家算法，有效的防止和避免死锁的发生。设计思路1.银行家算法在避免死锁的方法中，如果施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。基本思想为：在分配资源之前，判断系统是否是安全的；若安全，才分配。它是最具代表性的死锁算法，具体算法如下表示：假设进程P提出请求Request[i]，则银行家算法按如下步骤进行判断：1)如果Request[i]=Need[i]，则转向2）；否则出错。2)如果Request[i]=Available[i]，则转向3）；否则出错。3)系统试探分配相关资源，修改相关数据：Available[i]=Available[i]-Request[i];Allocation[i]=Allocation[i]+Request[i];Need[i]=Need[i]-Request[i];4)系统执行安全性检查，如安全，则分配成立；否则试探性分配资源作废，系统恢复原状，进程进入等待状态。根据以上银行家算法步骤，可得出如下图所示流程图:2.安全性检查算法安全性检查算法主要是根据银行家算法进行资源分配后，检查资源分配后的系统状态是否处于安全状态之中。具体算法如下所示:1)设置两个工作向量Work=Available，Finish=false；2)从进程集合中找到一个满足下述条件的进程；Finish=false;Need=work;如果能够找到该进程，则执行3），否则，执行4）；3)假设上述找到的进程获得资源，可顺利执行，直至完成，从而释放资源。Work=Work+Allocation;Finish=true;Goto2);4)如果所有进程的Finish=true，则表示该系统安全，否则系统不安全，请求被拒。5)根据以上安全检查算法步骤，可得出如下图所示流程图:主要数据结构#includeiostream.h////////////////////////////////////////////////////////////////////////////全局变量定义intAvailable[100];//可利用资源数组intMax[50][100];//最大需求矩阵intAllocation[50][100];//分配矩阵intNeed[50][100];//需求矩阵intRequest[50][100];//M个进程还需要N类资源的资源量intFinish[50];intp[50];intm,n;//M个进程,N类资源主要代码结构///////////////////////////////////////////////////////////////////////////安全性算法intSafe(){inti,j,l=0;intWork[100];//可利用资源数组for(i=0;in;i++)Work[i]=Available[i];for(i=0;im;i++)Finish[i]=0;for(i=0;im;i++){if(Finish[i]==1)continue;else{for(j=0;jn;j++){if(Need[i][j]Work[j])break;}if(j==n){Finish[i]=1;for(intk=0;kn;k++)Work[k]+=Allocation[i][k];p[l++]=i;i=-1;}elsecontinue;}if(l==m){cout系统是安全的'\n';cout系统安全序列是:\n;for(i=0;il;i++){coutp[i];if(i!=l-1)cout--;}cout'\n';return1;}}}///////////////////////////////////////////////////////////////////////////////////银行家算法intmain(){inti,j,mi;cout输入进程的数目:\n;cinm;cout输入资源的种类:\n;cinn;cout输入每个进程最多所需的各类资源数,按照mxn矩阵输入\n;for(i=0;im;i++)for(j=0;jn;j++)cinMax[i][j];cout输入每个进程已经分配的各类资源数,按照mxn矩阵输入\n;for(i=0;im;i++){for(j=0;jn;j++){cinAllocation[i][j];Need[i][j]=Max[i][j]-Allocation[i][j];if(Need[i][j]0){cout你输入的第i+1个进程所拥有的第j+1个资源错误，请重新输入:\n;j--;continue;}}}cout请输入各个资源现有的数目:\n;for(i=0;in;i++)cinAvailable[i];Safe();while(1){cout输入要申请的资源的进程号：（第一个进程号为0，第二个进程号为1，依此类推）\n;cinmi;cout输入进程所请求的各个资源的数量\n;for(i=0;in;i++){if(Request[mi][i]Need[mi][i]){cout所请求资源数超过进程的需求量！\n;return0;}if(Request[mi][i]Available[i]){cout所请求资源数超过系统所有的资源数！\n;return0;}}for(i=0;in;i++){Available[i]-=Request[mi][i];Allocation[mi][i]+=Request[mi][i];Need[mi][i]-=Request[mi][i];}if(Safe())cout同意分配请求~~~\n;else{coutSORRY╮(╯▽╰)╭……你的请求被拒绝…\n;for(i=0;in;i++){Available[i]+=Request[mi][i];Allocation[mi][i]-=Request[mi][i];Need[mi][i]+=Request[mi][i];}}for(i=0;im;i++)Finish[i]=0;charFlag;//标志位cout是否再次请求分配？是请按Y/y，否请按N/n;while(1){cinFlag;if(Flag=='Y'||Flag=='y'||Flag=='N'||Flag=='n')break;else{cout请按要求重新输入:\n;continue;}}if(Flag=='Y'||Flag=='y')continue;elsebreak;}}主要代码段分析1.在开始编写程序时，由于相关参数由用户自己进行输入时，由于运用scanf和printf语句，造成程序长度很长，而且输入子程序复杂度为O()，程序反应速度也比较慢。后来改用cin和cout函数程序长度大大缩短。2.由于程序的可重复使用的方便性，采取设立标志位Flag，由用户输入命令（Y/N或y/n）用以作为程序继续运行和结束的标志。实验心得本次试验老师要求对固定的资源进行分配，虽然实现起来比较简单，但是其只能算固定的一种情况，所以在此基础上，我进行了改进，即相关参数由用户自己进行输入增加其实用性。下图为程序运行情况：