操作系统课程设计之模拟通过银行家算法避免死锁

1、模拟通过银行家算法避免死锁一、银行家算法产生的背景及目的1 :在多道程序系统中，虽然节奏、虽然借助于多个进程的并发执行来改善系统的 利用率，提高系统的吞吐量，但可能发生一种危险一死锁。，死锁就是多个进程在运 行过程中因争夺资源而造成的一种僵局，当进程处于这种 僵局状态时，如无外力作用, 他们将无法再向前进行，如再把信号量作为同步工具时，多个Wait和Signal操作 顺序不当，会产生进程死锁。然而产生死锁的必要条件有互斥条件，请求和保持条件， 不剥夺条件和环路等待条件。在预防死锁的几种方法中，都施加了较强的限制条件，在 避免死锁的方法中，所施加的条件较弱，有可能获得令人满意的系统性能。在该方法

2、 中把系统的状态分为安全状态和不安全状态，只要能使系统都处于安全状态，便可避 免死锁。2：实验目的：让学生独立的使用编程语言编写和调试一个系统分配资源的简 单 模拟程序，了解死锁产生的原因及条件。采用银行家算法及时避免死锁的产生，进 一步理解课堂上老师讲的相关知识点。银行家算法是从当前状态出发，逐个按安全序 列检查各客户中谁能完成其工作，然后假定其完成工作且归还全部贷款，再进而检查下 一个能完成工作的客户。如果所有客户都能完成工作，则找到一个安全序列，银行家 才是安全的。二：银行家算法中的数据结构1 ：可利用资源向量Availableo这是一个含有ni个元素的数组，其中的每个元 素代表 一类可

3、利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数 值随该类资源的分配和回收而动态的改变。如果Availablej=k , z则表示系统中现 有RJ类资源K个。2 :最大需求矩阵Max这是一个n*ni的矩阵，它定义了系统中n个进程中的每一个进程 对m类资源的最大需求。如果Maxi,j=k ,表示第i个进程需要第Rj类资源的最大 数目k个.3:分配矩阵Allocation, 也是n*m的矩阵,若Allocationi, j=k, 表示第i 个进程已分配RJ类资源的数目为k个。4 :需求矩阵Neeco也是一个n*ni的矩阵，Needi, j二k,表示第i个进程还需Rj类 资源k个

4、。三、银行家算法及安全性算法1 :银行家算法设Request i是进程Pi的请求向量，若Request i j二k;表示进程需要j类资源 k个。当Pi发出资源请求时，系统按下属步骤进行检查；如果Requestij=Needij;便转向步骤（2）,否则认为出错，因为它 所需 要的资源数已超过他所宣布的最大值。（2）如果Requesti j=Availablei j,便转向步骤（3）,否则认为尚无足够资源，进程需等待。（3）系统试探着把资源分配给进程，并修改下面数据结构的数据Availablei j=Availa.blei j-Request i j;Alloca.tioni j=Allocati

5、oni j+Requesti j;Needi j二Needi j-Requesti j;（4）系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全, 才正式将资源分配给进程Pi ,已完成此次分配。否则，将本次的试探分配作废, 回复原来的资源分配状态，将进程Pi等待。2：安全性算法（1）设置两个向量；1 :工作向量Work,表示系统可提供给进程运行所需的各类资源数目，它含有m个元素，初始时Work=Ava订able2 : Finish ,表示系统是否有足够的资源分配给进程，使之运行完成。开始时先 做 Finishi=true（2）从进程中找到一个能满需下属条件的进程1 ； Fini

6、shi二false ；2: Needi jAvailableo r系统不安全退出六、源代码及调试分析 MAXn 100 int MAXMAXmMAXn; AvailableMAXn; int NeedMAXmMAXn: int RequestMAXmMAXn; int FinishMAXm; int SequenceMAXm: int WorkMAXn; int m, n;#include #define MAXm 50 #define int AllocationMAXmMAXn: int/定义最大进程数定义最大资源数#define False 0#define True 1 void in

7、put () ;/数据输入函数 int safealg() : /安全性算法最大需求矩阵已分配矩阵可用资源数组需求矩阵请求矩阵存储完成资源分配的进程模拟的 资源分配序列系统是否有足够的资 源分配给进程 口个进程,n个资源函数void banker () ;/银行家算法函数void ma.in() input () : safealg() :banker () ; void input ()/* int i,j;自定义进程数目与资源种类 / ZZvizvizvizvizviz 1十 个个平个个于平个平于平个个于平个个个平个个于平个平于 * n cout鄴利常彼行家算法避免死锁*g；*nH;*/*

8、初始化算法coutII *nn;cout* coutz，请输入进程的数目 cinm;cout/z请输入资源的种类cinn;/*输入每个进程对每种资源的最大需求、已经获得的数量、 每种类型资源的数目cout，z各进程资源最大需求(Max),按照mxn矩阵 输入：；for(i=0;im;i+)coutPi：；for (j二0;jn;j+)cinMAXij;if(j=n) cout，z资源种类数匹配出现错误！ ;/当资源配置 的种 类数大于预先输入的数值时，出错cout/z各 进程 当前获 得资源(Allocation),按 照 矩阵输入 endl;for(i=0;im;i+)cout/，P/，i，

9、/:; for (j=0; jAllocationi j;if(j=n) cout/，资源种类数匹配出现错误！ ;/当 资源配置的种 类数大于预先输入的数值时，出错Needi j=MAXi j-Allocationi j ;/ 需求数等于 最大需求减去已经分配数cout/z系统可用资源(Ava订able) : endl;for(j=0;jAva订ablej ;/输入各种资源的可利用数COUt，Z当前时刻的进程分配情况如图：； cout/z进程号-locationNeed-z，z/Available n;/ 显示各进程的资源情况for(i=0;im;i+)coutPi：；for(j=0;jn;j

10、+) coutz，MAXLi j;for(j=0;jn;j+)cout，/，zAllocationi j;cout，/;for(j=0;jn;j+)coutz/，Needi j;for(j=0;jn;j+)cout/zz/Availablej ; coutchoice;if (choice=l/分配资丿源cout/z从P0到P，zvvm-li;if(i=m)(cout，/无此进程号！请重新输入：； cini;/重新输入进程号coutRequesti j;/* 银行家算法进行检查 */ for (j=0;jn;j+)if(RequestijNeedij)coutz，申请的资源大于它需要的资源数

11、，请重 新输入！;/资源申请不合理continue;if(RequestijAvailablej)/资源申请数目大于可利用数，无法分配，得等待 cout当前系统可用资源不够，请等待!e ndl;continue; for(j=0; jn; j+)/ 资源申请得到允许 时，变换各个资源数Availablej=Availablej-Requesti j; / 可用资 源减少Allocationi j=Allocationi j+Requesti j;/所得资源增加减少的状态Work -Needi j二Needi j-Requesti j ;/仍需资源if (safealgO 0)/安全性算法的返回

12、值cout/z分配不成功，请等待！ ； for (j=0; jn; j+)/把资源恢复成分配之前AvailablejAvailablej +Requesti j; Allocationi j二Allocation!. j-Requesti j；Needi j二Needi j+Requesti j;for(i=0;im;i+)Finishi=False;/没有足够的资源分配给该进程/if (saf ealgO 0)elsecout，/同意分配请求!，zendl;for(j=0;jn;j+)Workj=Availablej:cout，z进程号NeedAllocationWork+Allocatio

13、n-Finish-z，endl;for (i=0; im; i+)/按模拟分配序列进行分配cout/z进程 PSequencei：; for(j=0;jn;j+)coutWork jcout，z/，;for(j=0;jn;j+)coutNeedSequenceij”；cout；for (j=0;jn;j+) coutAllocationSequenceij；COUtZZ，/ ;for(j=0;jn;j+) coutAllocationSequenceij+Workj“； cout，z，/;coutFinishSequencei；/ 完成该进程for(j=0;j=0)/ if(choice=1)

14、else if(choice=2) 离开break;else coutn请输入1或2!”;/只认可1或2coutendl;/*安全性算法*/wh订eInt safealg()int i,j,k,l=O;/int WorkMAXn;for(i=0;ivn;i+)Worki=Availablei; for(i=0;im;i+) 所有进程不能运行工作组记录序列工作分配初始化为系统可用资源扫描所有进程，预设Fin ishi=False;for(i=0;ivm;i+)/if(Finishi=True)conti nue;else /对于未运行的进程，进行如下处理/for(j=0; jn; j+)/ 找

15、到一个 满 足 FinishEi=false 且 NeedijWorkj)/由于部分资源得不到满足,进程i无法运行break;if(j=n)/进程各类资源全部得到满足Finishi=True;for (k=0; kn; k+) /进程i正常运行后，释放其占的资源*Workk+=Allocationi k; / 工作分配加上可 用资源Sequence l+=i ; /模拟资源分配丿了:列生成i=T ; /重新扫描所有进程从i=0开始? else /某一资源得不到满足continue; /试探下一个进程/ if(l=m)/都试探完毕coutz/系统安全！endl; cout/z安全序列：“； fo

16、r(i=0;il;i+)/输出安全序列coutz/进程 PSequencei； cout iTt-J J* *W!X iljt-jtlk利用银行家算法避免死锁-H入入程 隹113P0： 4 5 7P1： 5 4 t进程的数目汚漏的种參2療最头需求5磁儿按照5也矩阵输入:PZ： 4 3 MP3： 3 S 4P4： 4 j 2各进 程当前茯侍资源3 L1。*按照心矩阵输入PH： 2 2P1： 2 J 2P2： 0 iL 1P3： 1 JP4: 2系址可用资源V f t va i 1 ahLe :2 3 3量翦吁刻的进程分配情况如图:进柱万1Allocat ionNeedAvailable27542

17、 3 4 2 23 2 1102；2 0 126 3 4 24 3 55 4 3统全poDT 97YQ22 Z224 4 2 3 23 3 2 3 2逬行间程二逬求Dr程 Z ;请債进全P4列配一入2芬4- 号输Im 4请丄玉女燼进进进进进H己 八一要 S的n若再继续申请资源，假设为P4 ,申请资源(1 2 2)假设P1申请资源(2 2 4 )有IDU V用用曙的 he可可可不功行y 统统费成进，4系 系專不要S备翌嗣 统配入獲2当当当主冃主冃主冃、1等事:分至冏原2禺开ontinuie八、心得体会经过这次操作系统课程设计，让我受益匪浅，收获颇多。主要体会如下：1 利用Vc+编译程序编写银行家算法，进一步理解到通过银行家算法避免死锁的思 想，同时也理解了