操作系统银行家算法

1、创作編 鱼 BG7531400019813488897SX- 创作者：别如克操作系统银行家算法操作系统实验报 告实验目标1. 理解银行家算法。2. 掌握进程安全性检査的方法及资源分配的方法。3. 加深了解有关资源申请、避免死锁等概念。4. 体会和了解死锁和避免死锁的具体实施方法。实验要求编写和调试一个系统动态分配资源的简单模拟程序，观察死锁产生的条件，并采用银 行家算法，有效的防止和避免死锁的发生。设计思路1 银行家算法在避免死锁的方法中，如果施加的限制条件较弱，有可能获得令人满意的系统性能。 在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全 状态，便可以避免发生死锁

2、。基本思想为：在分配资源之前，判断系统是否是安全的：若安全，才分配。它是最具 代表性的死锁算法，具体算法如下表示：假设进程P提出请求Request®,则银行家算法按如下步骤进行判断：1）如果Request® <=Needi,则转向2）；否则出错。2）如果 Request® <=Availablei,则转向 3）；否则岀错。3）系统试探分配相关资源，修改相关数据：Availablei=Availablei-Requesti;Allocationi=Allocationi+Requesti;Needi=Needi-Requesti;4）系统执行安全性检查，

3、如安全，则分配成立：否则试探性分配资源作废，系统恢 复原状，进程进入等待状态。根拯以上银行家算法步骤，可得出如下图所示流程图：2 安全性检査算法安全性检查算法主要是根据银行家算法进行资源分配后，检査资源分配后的系统状态 是否处于安全状态之中。具体算法如下所示：1）设置两个匸作向量 Work二Available, Finish=false：2）从进程集合中找到一个满足下述条件的进程：Finish=false;Need<=work;如果能够找到该进程，则执行3）,否则，执行4）：3）假设上述找到的进程获得资源，可顺利执行，直至完成，从而释放资源。Work=Work+Allocation;Fi

4、n ish=true;Goto 2）;4）如果所有进程的Finish=true,则表示该系统安全，否则系统不安全，请求被拒。5）根拯以上安全检查算法步骤，可得岀如下图所示流程图：#include <iostream.h>/ 全局变量定义int Available100; /可利用资源数组int Max50100; 最大需求矩阵int Allocation50100; 分配矩阵int Need50100;需求矩阵int Request50100;/M个进程还需要N类资源的资源量int Finish50;int p50;int m,n; /M个进程,N类资源主要代码结构/安全性算法in

5、t Safe)int ij,l=O;int Work100; /可利用资源数组for (i=0;i<n;i+)Worki=Availablei;创作編-J： BG7531400019813488897SX创作者：别如克for (i=O;i<m;i+)Finishi=O;for (i=0;i<m;i+)if (Finishi=l)continue;elsefor (j=O；j<n;j+)if (Needij>Workj)break;if (j=n)Finishi=l;for(int k=0;k<n;k+)Workk+=Allocationik; pl+=i；

6、i=-l；else continue;if (l=m)coutV系统是安全的tv、rV;cout«"系统安全序列是:n"for (i=0;i<l;i+)cout«pi;if (i!=l-l)cout«H->n;cout«'n；return 1;lllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll银行家算法int main()int i jmi;cout<<”输入进程的数目:n"cin&

7、gt;>m;cout<<"输入资源的种类:n“;cin»n;cout<<"输入每个进程最多所需的各类资源数，按照"<<、“<<*<"矩阵输入n"for (i=0;i<m;i+)for(j=0;j<n;j+)cin»Maxij；cout«"输入每个进程已经分配的各类资源数，按照"<<m<<"x“<<n<<"矩阵输入n"for (i=O;i<m;

8、i+)for(j=0;j<n;j+)cin»Allocationij;Needij=Maxij-Allocationij;if (Needij<0)cout«N你输入的第个进程所拥有的第,«j+l«u个资源错误，请重新输入:n"->contin ue;创作编；：BG7531400019813488897SX 创作者COUtS请输入各个资源现有的数目:卍；for (i=0;i<n;i+)cin»Availablei;Safef);while (1)coutvv”输入要申请的资源的进程号：(第一个进程号为0,第二个

9、进程号为1, 依此类推)n”；cin»mi;cout<< "输入进程所请求的各个资源的数量n”；for (i=0;i<n;l+)if (Requestmii>Needmii)cout«H所请求资源数超过进程的需求量！ nM;return 0;if (Requestmii>Availablei)cout«N所请求资源数超过系统所有的资源数！ 卍；return 0;for (i=0;i<n;l+)Availablei-=Requestmii);Allocationmii+=Requestmii;Needmii-=Reque

10、stmii;if (Safe()cout«"同意分配请求n"elsecouWSORRYr (丿计厂你的请求被拒绝严；for (i=O;i<n;i+)Availablei+=Requestmii;Allocationmii-=Requestmii;Needmii+=Requestmii;for (i=O;i<m;i+)Finishi=0;char Flag;标志位cout«"是否再次请求分配？是请按Y/y,否请按N/n"while (1)cin>> Flag;if (Flag=lY'| |Flag=,y&

11、#39;| |Flag=,N'| |Flag=,n,)break;elsecout«-请按要求重新输入:rf;conti nue;if (Flag=lY,| |Flag=y)conti niie;else break;主要代码段分析1. 在开始编写程序时，由于相关参数由用户自己进行输入时，由于运用scanf和printf 语句，造成程序长度很长，而且输入子程序复杂度为o(n)，程序反应速度也比较 慢。后来改用cin和cout函数程序长度大大缩短。2. 由于程序的可重复使用的方便性，采取设立标志位Flag,由用户输入命令(Y/N或 y/n)用以作为程序继续运行和结朿的标志。实验心得本次试验老师要求对固左的资源进行分配，虽然实现起来比较简单，但是其只能算固 泄的一种情况，所以在此基础上，我进行了改进，即相关参数由用户自己进行输入增 加其实用性。下图为程序运行情况：nkerDebugbanker.exe*a需入每0 0 111 7 5H2 3 50 6 50 6 5 .输入每个进程已经分配的各类资源数按照5沢4矩阵输入0 12 0 0 03 5 46 3 20 14阳11°