银行家死锁避免算法模拟课程设计(C#)

华南理工大学1序号课程名称:操作系统指导老师:XXX学号:10563387120188008学生姓名:XXX学习中心:学院直属班提交日期:2017-05-30评审日期__________成绩_________评审教师(签名)__________华南理工大学继续教育学院华南理工大学2一、实验目的：通过本次实验掌握银行家死锁避免算法的基本思想。当进程提出资源申请时，能够用该算法和安全性检查判断是否拒绝进程请求。二、实验内容：认真阅读教材“利用银行家算法避免死锁”内容，理解该算法是如何能够实现死锁避免的。编写一个银行家算法模拟程序用于处理进程的资源申请。1。假设系统共有5类资源，分别以A、B、C、D、E来标识，每类资源的初始数量全部为50。2。进程可以通过程序界面随时提交新的资源申请，提交的信息包括进程名称、对5类资源的最大需求数量。3。每次当有资源申请时，先输出系统当前状态（5类资源当前可用数量，每个进程已分配的每类资源数量），再利用银行家算法判断是否该满足进程请求。如果可以分配，输出给该进程分配资源后的系统状态，再输出至少一个“安全序列”。三、实验原理：1.产生死锁的四个条件：互斥条件---进程要求对所分配的资源进行排它性控制，即在一段时间内某资源仅为一进程所占用。占有并等待条件---当进程因请求资源而阻塞时,对已获得的资源保持不放。非抢占条件---进程已获得的资源在未使用完之前,不能剥夺,只能在使用完时由自己释放。循环等待条件---在发生死锁时,必然存在一个进程--资源的环形链。2.避免死锁实际上是从破坏以上四个必要条件来实现，下面利用银行家算法来进行演示。3.银行家算法步骤：（1）如果进程Pi发出请求Requesti[j]≤Need[i,j],则转向步骤(2)；否则，认为出错，因为它所需要的资源数已超过它所宣布的最大值。（2）如果Requesti[j]≤Available[j],则转向步骤（3）；否则，表示系统中尚无足够的资源，进程必须等待。（3）系统试探把要求的资源分配给进程Pi,并修改下面数据结构中的数值：Available[j]=Available[j]-Requesti[j];Allocation[i,j]=Allocation[i,j]+Requesti[j];Need[i,j]=Need[i,j]-Requesti[j];(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。4.安全性算法步骤：（1）设置两个向量①工作向量Work。它表示系统可提供进程继续运行所需要的各类资源数目，执行安全算法开始时，Work=Allocation;华南理工大学3②布尔向量Finish。它表示系统是否有足够的资源分配给进程i，使之运行完成，开始时先做Finish[i]=false，当有足够资源分配给进程时，令Finish[i]=true。（2）从进程集合中找到一个能满足下述条件的进程：①Finish[i]=false;②Need[i,j]≤Work[j];如找到，执行步骤（3）；否则，执行步骤（4）。（3）当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Work[j]=Work[j]+Allocation[i,j];Finish[i]=true;转向步骤（2）。（4）如果所有进程的Finish[i]=true,则表示系统处于安全状态；否则，系统处于不安全状态，并恢复试分配的资源。四、实验环境：1.开发工具：MicrosoftVisualStudioCommunity20172.开发语言：C#五、实验方法1.算法数据结构：1）可利用资源向量Available，它是一个最多含有50个元素的数组，其中的每一个元素代表一类可利用的资源的数目，其初始值是系统中所配置的该类全部可用资源数目。其数值随该类资源的分配和回收而动态地改变。如果Available（j）=k，表示系统中现有j类资源k个。2）最大需求矩阵Max，这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max（i，j）=k，表示进程i需要j类资源的最大数目为k。3）分配矩阵Allocation，这也是一个n×m的矩阵，它定义了系统中的每类资源当前一分配到每一个进程的资源数。如果Allocation（i，j）=k，表示进程i当前已经分到j类资源的数目为k。Allocationi表示进程i的分配向量，有矩阵Allocation的第i行构成。4）需求矩阵Need，这还是一个n×m的矩阵，用以表示每个进程还需要的各类资源的数目。如果Need（i，j）=k，表示进程i还需要j类资源k个，才能完成其任务。Needi表示进程i的需求向量，由矩阵Need的第i行构成。5）上述三个矩阵间存在关系：Need（i，j）=Max（i，j）-Allocation（i，j）；华南理工大学44.算法流程图开始定义五种资源类型和各类资源总数50，初始化Available向量定义进程数5，i=0输入进程i的最大需求向量maxmax。i≤4max≤资源总数提示错误重新输入i加1任选一个进程作为当前进程输入该进程的资源请求量Request调用银行家算法Need向量为0该进程已运行结束Need矩阵为0所有进程运行都结束结束NYYNNY初始化need矩阵NY安全性检查N给出安全提示，并输出安全序列Y提示不安全并恢复资源华南理工大学5四、实验代码以及运行示例1.设计资源矩阵如下:资源进程MaxAllocationNeedAvailableABCDEABCDEABCDEABCDEP0121510118101081162520244373P1131110101591010101241003P21081061210682902243P3101412151210811101206150P4141512121071210108732222.程序源代码如下：usingSystem;namespaceConsoleApp1{classMainClass{publicclassBankCalculator{staticint[]available=newint[5];//五个资源类型staticint[,]max=newint[5,5];//最大资源需求staticint[,]allocation=newint[5,5];//已经分配的资源staticint[,]need=newint[5,5];//还需要的资源staticint[]request=newint[5];//资源请求staticbool[]finish=newbool[5];//是否有足够资源提供给进程继续运行staticint[]work=newint[5];//当前系统可提供给进程继续运行的资源intthread;//线程号//利用正则判断输入是否为整数staticboolIsNumeric(stringstr){System.Text.RegularExpressions.Regexreg1=newSystem.Text.RegularExpressions.Regex(@^[0-9]\d*$);returnreg1.IsMatch(str);}//判断输入是否为整数并返回输入值staticintGetStr(){intSnum=0;stringnum=Console.ReadLine();boola=IsNumeric(num);华南理工大学6if(a)returnSnum=int.Parse(num.Trim());elseConsole.WriteLine(输入有误，请重新输入);returnGetStr();}//判断输入分配资源是否为整数且小于最大需求并返回输入值staticintGetAlo(intmax){intSnum=0;stringnum=Console.ReadLine();boola=IsNumeric(num);if(!a){Console.WriteLine(输入有误，请重新输入);returnGetAlo(max);}elseif(int.Parse(num.Trim())max){Console.WriteLine(输入不能大于+max);returnGetAlo(max);}else{returnSnum=int.Parse(num.Trim());}}//初始化各类的值publicvoidgetData(){//定义A,B,C,D,E五类资源数量for(inti=0;i5;i++){available[i]=50;}//输入进程对五类资源的最大需求max=newint[5,5]{{12,15,10,11,8},{13,11,10,10,15},{10,8,10,6,12},{10,14,12,15,12},{14,15,12,12,10}};//输入进程已分配的五类资源数allocation=newint[5,5]{{10,10,8,11,6},{9,10,10,10,12},{10,6,8,2,9},{10,8,11,10,12},{7,12,10,10,8}};华南理工大学7//计算进程还需要的五类资源数for(inti=0;i5;i++){for(intj=0;j5;j++){need[i,j]=max[i,j]-allocation[i,j];}}//重新计算availablefor(inti=0;i5;i++){for(intj=0;j5;j++){available[i]-=allocation[j,i];}}}//用户输入要申请资源的线程和申请的资源，并进行判断publicvoidgetThread(){Console.WriteLine(请输入申请资源的线程，范围0~4);//读取输入的线程intthread=GetStr();if(thread0||thread4){Console.WriteLine(该线程不存在,请重新输入);getThread();}else{Console.WriteLine(请输入P+thread+进程申请request的各资源类型资源数);this.thread=thread;for(inti=0;i5;i++){request[i]=GetStr();}Console.WriteLine(当前P+thread+进程request的各资源类型资源数);Console.WriteLine(=====A类=====B类=====C类=====D类=====E类=====：);Console.Write();华南理工大学8for(inti=0;i5;i++){Console.Write(request[i]+);}Console.WriteLine();Console.WriteLine(============================================);Console.WriteLine();if(request[0]need[thread,0]||request[1]need[thread,1]||request[2]need[thread,2]||request[3]need[thread,3]||request[4]need[thread,4]){Console.WriteLine(thread+线程申请的资源超出其需要的资源，请重新输入);getThread();}else{if(request[0]available[0]||request[1]available[1]||request[2]available[2]||request[3]available[3]||request[4]available[4]){Console.WriteLine(thread+线程申请的资源大于系统可用资源，请重新输入);getThread();}}changeData(thread);if(check(thread)){Console.