操作系统实验报告 银行家算法.doc

实验四 银行家算法l 实习内容通过编程理解银行家算法，掌握进程安全性检查的方法及资源分配的方法，加深了解有关资源申请、避免死锁等概念，体会和了解死锁和避免死锁的具体实施方法。l 实习目的银行家算法是避免死锁的代表性算法。本实习旨在加深了解有关资源申请、避免死锁、状态安全性等概念，并体会和运用避免死锁的具体实施方法。然后依照本实习，自行设计模拟程序。l 实习原理算法思想：银行家算法操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。安全状态：如果存在一个由系统中所有进程构成的安全序列P1，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。不安全状态:不存在一个安全序列。不安全状态一定导致死锁。l 实习编程思路和流程在避免死锁的方法中，如果施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。基本思想为：在分配资源之前，判断系统是否是安全的；若安全，才分配。它是最具代表性的死锁算法，具体算法如下表示：假设进程P提出请求Requesti，则银行家算法按如下步骤进行判断：1) 如果Requesti =Needi，则转向2）；否则出错。2) 如果Requesti =Availablei，则转向3）；否则出错。3) 系统试探分配相关资源，修改相关数据：Availablei=Availablei-Requesti;Allocationi=Allocationi+Requesti;Needi=Needi-Requesti;4) 系统执行安全性检查，如安全，则分配成立；否则试探性分配资源作废，系统恢复原状，进程进入等待状态。5) 根据以上银行家算法步骤，可得出如下图所示流程图:安全性检查算法主要是根据银行家算法进行资源分配后，检查资源分配后的系统状态是否处于安全状态之中。具体算法如下所示:1) 设置两个工作向量Work=Available，Finish=false；2) 从进程集合中找到一个满足下述条件的进程；Finish=false;Need=work;如果能够找到该进程，则执行3），否则，执行4）；3) 假设上述找到的进程获得资源，可顺利执行，直至完成，从而释放资源。Work=Work+Allocation;Finish=true;Goto 2);4) 如果所有进程的Finish=true，则表示该系统安全，否则系统不安全，请求被拒。5) 根据以上安全检查算法步骤，可得出如下图所示流程图:l 源程序结构分析 主要数据结构#include /全局变量定义int Available100; /可利用资源数组int Max50100; /最大需求矩阵int Allocation50100; /分配矩阵int Need50100; /需求矩阵int Request50100; /M个进程还需要N类资源的资源量int Finish50;int p50;int m,n; /M个进程,N类资源 主要代码结构/安全性算法 int Safe() int i,j,l=0;int Work100; /可利用资源数组for (i=0;in;i+)Worki=Availablei;for (i=0;im;i+)Finishi=0;for (i=0;im;i+)if (Finishi=1)continue;elsefor (j=0;jWorkj)break;if (j=n)Finishi=1;for(int k=0;kn;k+)Workk+=Allocationik;pl+=i;i=-1;else continue;if (l=m)cout系统是安全的n;cout系统安全序列是:n;for (i=0;il;i+)coutpi;if (i!=l-1)cout;coutn;return 1;/银行家算法 int main()int i,j,mi;coutm;coutn;cout输入每个进程最多所需的各类资源数,按照mxn矩阵输入n;for (i=0;im;i+)for(j=0;jMaxij;cout输入每个进程已经分配的各类资源数,按照mxn矩阵输入n;for (i=0;im;i+)for(j=0;jAllocationij;Needij=Maxij-Allocationij;if (Needij0)cout你输入的第i+1个进程所拥有的第j+1个资源错误，请重新输入:n;j-;continue;cout请输入各个资源现有的数目:n;for (i=0;iAvailablei;Safe();while (1)coutmi;cout输入进程所请求的各个资源的数量n;for (i=0;iNeedmii)coutAvailablei)cout所请求资源数超过系统所有的资源数！n;return 0;for (i=0;in;i+)Availablei-=Requestmii;Allocationmii+=Requestmii;Needmii-=Requestmii;if (Safe()cout同意分配请求n;elsecoutSORRY()你的请求被拒绝n;for (i=0;in;i+)Availablei+=Requestmii;Allocationmii-=Requestmii;Needmii+=Requestmii;for (i=0;im;i+) Finishi=0;char Flag; /标志位coutFlag;if (Flag=Y|Flag=y|Flag=N|Flag=n)break;elsecout请按要求重新输入:n;continue;if (Flag=Y|Flag=y)continue;else break;l 模拟程序运行结果截图初始化状态：随机分派的进程和资源配置结构上一个失败的请求；因为分配后的状态不安全，所以未能得到资源。发起一个请求，系统试分配，分配后安全，所以请求成功，同时生成一个安全的进程执行序列。l 总结与心得在开始编写程序时，由于相关参数由用户自己进行输入时，由于运用scanf和printf语句，造成程序长度很长，而且输入子程序复杂度较高，程序反应速度也比较慢。后来改用