操作系统课程设计--银行家算法.doc

课程设计说明书 NO.19银行家算法1. 课程设计的目的了解多道程序系统中，多个进程并发执行的资源分配，及死锁的产生原因、必要条件和处理死锁的基本方法，掌握预防死锁的方法，系统安全状态的基本概念，了解银行家算法，及资源在进程并发执行中的资源分配策略，并且理解死锁避免在当前计算机系统不常使用的原因。根据设计题目的要求，充分地分析和理解题目，叙述系统的要求，明确程序要求实现的功能以及限制条件。明白自己需要用代码实现的功能，清楚编写每部分代码的目的，做到有的放矢，有条理不遗漏的用代码实现银行家算法。2.设计方案论证2.1题目描述银行家算法是一种最有代表性的避免死锁的算法。在多道程序系统中，多个进程的并发执行来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险死锁。所谓死锁(Deadlock)，是指多个进程在运行过程中因争夺资源而造成的一种僵局（DeadlyEmbrace），当进程处于这种状态时，若无外力作用，他们都无法在向前推进。要预防死锁，有摒弃“请求和保持”条件，摒弃“不剥夺”条件，摒弃“环路等待”条件等方法。但是，在预防死锁的几种方法之中，都施加了较强的限制条件；而在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统状态分为安全状态和不安全状态，便可避免死锁的发生。要解释银行家算法，必须先解释操作系统安全状态和不安全状态。安全状态是指系统能按照某种进程顺序P1,P2,，Pn（称P1,P2,，Pn 序列为安全序列），来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可以顺利完成。安全状态一定没有死锁发生。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。安全序列：一个进程序列P1，Pn是安全的，如果对于每一个进程Pi(1in），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j NEEDcusneedi REQUESTcusneediAVAILABLEiYN试分配changdata()NSafe()Put()输出内容 Y图1银行家算法流程图（2）安全性算法，如图2所示。初始化work数组，使Workj=Availablej; Finishi=false Finishi=true Y NNeedijWorkj Y Napply+;appy=N Y YFinishi=trueWorkm+=Allocationimtempk=i;k+l=mY不安全Availablei=Availablei+Requesti;Allocationnumi=Allocationnumi-RequestjNeednumi=Neednumi+Requesti; N输出安全序列Return trueMaxnumi=Allocationnumi; Allocationnumi=0; Availablei = Availablei + Allocationnumi;图2安全性算法流程图2.3.3调试结果（1）资源分配情况，如图3所示。图3资源分配情况（2）安全判断，如图4所示。图4安全判断 （3）为1分配资源，如图5所示。图5为1分配资源 （4）为4分配资源，如图6所示。图6为4分配资源（5）为0分配资源，如图7所示。图7为0分配资源3.设计体会通过本次课程设计，我收获很多，首先我对十大算法之一的银行家算法有了清楚的认识，认真分析了进程产生死锁的原因，了解为什么要进行死锁的避免，掌握银行家算法的数据结构，了解了算法的执行过程，加深了对银行家算法的理解。其次，我对编程有了个清楚的认识，编程就是将先现实中的规律模拟成电脑能运行的程序，方便我们的工作和学习生活。最后，我也清楚认识到理论联系实际重要性，动手操作能力和编程逻辑思维能力的提高的重要性，对自己所编写的程序要学会调试，不断改进，向更加全面的方向考虑，同时也要考虑程序的可行性和健壮性。总而言之，我在编写程序方面有了更加深入的认识。不同的算法可以实现相同的功能，这是我从本次实验中深深体会到的，因而在今后的学习中遇到问题我会尝试着用的不同的方法来解决，有时候换个角度可以很方便的解决问题课程设计是我们对专业课程知识综合应用的实践训练，只有认真的进行课程设计，学会脚踏实地认真思考学习，课程设计是培养我们综合运用所学知识，发现、提出、分析和解决实际问题、锻炼实践能力的重要环节,是对我们实际能力的考察过程。4.参考文献1 汤小丹，梁红兵，哲凤屏，汤子瀛.计算机操作系统.M 西安：西安电子科技大学出版社，2007. 150-2202 严蔚敏，吴伟民.数据结构. M 北京：清华大学出版社，2006. 14-993 赵莉，杨国梁，孙喁喁，徐飞.Java程序设计教程. M 西安：西安科技大学出版社，2009.25-994 刘璟等.高级语言C+程序设计.M西安电子科技大学出版社,2009.66-102附录#include#include#define False 0#define True 1char name50=0;/资源名称int Max5050=0;/进程所需各类资源的最大需求int Allocation5050=0;/系统已分配资源int Need5050=0;/进程需求资源int Available50=0;/系统可用资源向量int Request50=0;/进程请求资源向量int Work50=0;/存放系统可提供进程继续运行所需各类资源数目int temp50=0;/存放安全序列int b50=0;/系统各类资源总数int M=50;/进程的最大数目为50int N=50;/资源的最大数目为50void display() int i,j,number,m,n;char ming;int a50=0;coutn;N=n;for(i=0;in;i+) cout资源i+1mingnumber;namei=ming;bi=number;coutm;M=m;cout请输入各进程的最大需求(m*n矩阵)Max:endl;for(i=0;im;i+)for(j=0;jMaxij;cout请输入各进程的已分配(m*n矩阵)Allocation:endl;for(i=0;im;i+)for(j=0;jAllocationij;Needij=Maxij-Allocationij;if(Needij0)cout您输入的第i+1个进程所拥有的第j+1个资源数错误,请重新输入:endl;j-;continue;cout目前可用的资源:endl;for(i=0;iN;i+)coutnamei ;coutendl;for (j=0;jN;j+)for(i=0;iM;i+)aj+=Allocationij;Availablej=bj-aj;for(i=0;iN;i+)coutAvailablei ;/输出分配资源coutendl;void print()/显示资源分配情况int i,j;cout Max Allocation Needendl;cout进程名 ;for(j=0;j3;j+)for(i=0;iN;i+)coutnamei ;cout ;coutendl;for(i=0;iM;i+)cout i ;for(j=0;jN;j+)coutMaxij ;cout ;for(j=0;jN;j+)coutAllocationij ;cout ;for(j=0;jN;j+)coutNeedij ;coutendl;int changdata(int i)/进行资源分配 int j;for (j=0;jM;j+) Availablej=Availablej-Requestj; Allocationij=Allocationij+Requestj; Needij=Needij-Requestj;return 1;int safe(int num,int M,int N)/安全性算法对系统进行分析int i,j,k=0,m,apply,Finish5=0;int flag;int flag1;for(j=0;jM;j+) Workj=Availablej; for(flag=0;flagM;flag+)for(i=0;iM;i+)apply=0;for(j=0;jN;j+)if (Finishi=False&Needij=Workj) apply+;if(apply=N)for(m=0;mN;m+)Workm=Workm+Allocationim;/变分配数Finishi=True;tempk=i;k+;for(i=0;iM;i+)if(Finishi=False)cout系统不安全endl;/不成功系统不安全for(i = 0;iN;i+) Availablei=Availablei+Requesti;Allocationnumi=Allocationnumi-Requesti; Neednumi=Neednumi+Requesti; return -1; cout系统是安全的!endl;/如果安全，输出成功 cout分配的序列:;for(i=0;iM;i+)/输出运行进程数组couttempi;if(iM-1) cout;coutendl;for(i = 0;iN;i+)if(Maxnumi = Allocationnumi) flag1 = 1; elseflag1 = 0;break;if(flag1 = 1)for(i=0;iN;i+)Availablei = Availablei + Allocationnumi;Allocationnumi = 0;return 0;void bank(int M,int N)/银行家算法对申请资源对进行判定char ch; int i=0,j=0; ch=y;cout请输入要求分配的资源进程号(0-M-1i;/输入须申请的资源号cout请输入进程 i 申请的资源:endl; for(j=0;jN;j+)coutnamejRequestj;/输入需要申请的资源for (j=0;jNeedij)/判断申请是否大于需求，若大于则出错 cout进程 i申请的资源大于它需要的资源;cout 分配不合理，不予分配！Availablej)/判断申请是否大于当前资源，若大于则出错cout进程i申请的资源