银行家算法课程设计1.doc

摘 要银行家算法是最有代表性的避免死锁的算法，该算法由于能用于银行系统现金贷款的发放而得名。银行家算法是在确保当前系统安全的前提下推进的。对进程请求先进行安全性检查，来决定资源分配与否，从而确保系统的安全，有效的避免了死锁的发生。该设计在理解和分析了银行家算法的核心思想以及状态的本质涵义的前提下，对算法的实现在总体上进行了设计，包括在对算法分模块设计，并对各个模块的算法思想通过流程图表示，分块编写代码，并进行测试，最后进行程序的测试，在设计思路上严格按照软件工程的思想执行，确保了设计和实现的可行，可信。 关键词：银行家算法；死锁；避免死锁；安全性序列目 录1绪论11.1课题背景11.2 课题意义11.3 银行家算法原理11.4 死锁21.5安全性序列22需求分析32.1 问题描述32.2 基本要求32.3死锁的预防33 设计思路43.1设计原理43.2设计目的43.3各模块之间的调用图44详细设计54.1初始化程序设计54.2银行家算法设计54.3安全性检查算法64.4流程图75运行调试及结果说明86总结11参考文献12致 谢13附录（源程序）：141绪论1.1课题背景在多道程序系统中，虽可以借助多个进程的并发执行来改善系统的资源利用率，提高系统吞吐量，但可能发生一种危险死锁，即多个进程在运行过程中因争夺资源而造成的一种僵局，若无外力作用，将无法再向前推进。如此，寻求一种避免死锁的方法便显得有为重要。死锁的产生一般的原因有两点：竞争资源和进程间推进顺序非法。因此，我们只需在当前的有限资源下，找到一组合法的执行顺序，便能很好的避免死锁，我们称它为安全序列。而银行家算法起源于银行系统的发放贷款，和计算机操作系统的资源分配完全符合，因此可以借鉴该算法的思想，设计出一种有效的算法程序，解决该问题。1.2 课题意义（1）运用操作系统学过的知识和方法设计和实现，又是一次实战演练，从而提高自己的分析问题，解决问题和动手能力；（2）通过整个算法的设计与实现进一步加深了对算法的理解和多道程序下的计算机系统资源分配现状，为以后进一步的学习打下了良好的基础。1.3 银行家算法原理为保证资金的安全,银行家规定:(1) 当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客;(2) 顾客可以分歧贷款,但贷款的总数不能超过最大需求量;(3) 当银行家现有的资金不能满足顾客尚需的贷款数额时,对顾客的贷款可推迟支付,但总能使顾客在有限的时间里得到贷款;(4) 当顾客得到所需的全部资金后,一定能在有限的时间里归还所有的资金,操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。1.4 死锁死锁是进程死锁的简称，是由Dijkstra于1965年研究银行家算法时首先提出来的。是指多个进程循环等待它方占有的资源而无限期地僵持下去的局面。很显然，如果没有外力的作用，那麽死锁涉及到的各个进程都将永远处于封锁状态。它是计算机操作系统乃至并发程序设计中最难处理的问题之一。实际上，死锁问题不仅在计算机系统中存在，在我们日常生活中它也广泛存在。在计算机系统中，涉及软件，硬件资源都可能发生死锁。例如：系统中只有一台CD-ROM驱动器和一台打印机，某一个进程占有了CD-ROM驱动器，又申请打印机；另一进程占有了打印机，还申请CD-ROM。结果，两个进程都被阻塞，永远也不能自行解除。1.5安全性序列安全序列的的实际意义在于：系统每次进行资源分配后，如果对于系统中新的资源状况，存在一个安全序列，则至少存在一条确保系统不会进入死锁的路径。按照该序列，银行家可以实施一个有效的分配过程使得所有客户得到满足。银行家算法的核心在于安全序列的产生。安全序列正是一种安全的进程推进顺序。2需求分析2.1 问题描述运用银行家算法，避免死锁的发生。在确保当前系统安全的前提下推进的。对进程请求先进行安全性检查，来决定资源分配与否，从而确保系统的安全，有效的避免了死锁的发生。问题的关键在于安全性算法，即找安全性序列。2.2 基本要求（1）从键盘输入当前系统的资源信息，包括当前可用资源，每个进程对各类资源的最大需求量，每个进程当前已分配的各个资源量和每个进程尚需要的各个资源量，输出结果显示在DOS界面上；（2）输入进程请求，按照设计好的安全性算法进行检查，得到结果并输出整个执行过程的相关信息和最终结果（主要包括资源分配表和安全序列）（3）要求要有各种异常的处理，程序的可控制性和可连续性执行。包括对进程的存在有无检查，请求向量的不合法检查，试分配失败后的数据恢复和重新接受进程请求等。2.3死锁的预防出现死锁有4个必要条件，只要确保至少一个必要条件不成立，就能预防死锁发生。（1）互斥。通常不能通过否定互斥条件来预防死锁。有些资源本身是非共享的。（2）占有并等待。当一个进程申请一个资源时，它不能占有其他资源。执行前申请并获得所有资源申请其他资源之前，必须释放其现在已分配的所有资源，缺点是资源利用率可能比较低，可能发生饥饿。（3）非抢占。如果一个进程占有资源并申请另一个不能立即分配的资源，那么其现已分配的资源都被抢占。通常应用于其状态可以保存和恢复的资源，如CPU寄存器和内存空间，不能适用于其他资源如打印机和磁带驱动器。3 设计思路3.1设计原理我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。3.2设计目的学生通过该题目的设计过程，掌握银行家算法实现的原理、软件开发方法。模拟实现银行家算法，用银行家算法实现资源分配并提高解决实际问题的能力。3.3各模块之间的调用图初始化模块安全性模块主程序模块ain()银行家模块图3.1各模块之间的调用图4详细设计4.1初始化程序设计由用户输入数据，分别对可利用资源向量矩阵AVAILABLE、最大需求矩阵MAX、分配矩阵ALLOCATION、需求矩阵NEED赋值。程序使用的全局变量：#define MAXPROCESS 50 /*最大进程数*/ #define MAXRESOURCE 100 /*最大资源数*/int AVAILABLEMAXRESOURCE; /*可用资源数组*/int MAXMAXPROCESSMAXRESOURCE; /*最大需求矩阵*/int ALLOCATIONMAXPROCESSMAXRESOURCE; /*分配矩阵*/int NEEDMAXPROCESSMAXRESOURCE; /*需求矩阵*/int REQUESTMAXPROCESSMAXRESOURCE;/进程需要资源数int SUMMITMAXRESOURCE=0 ; /*各种资源总量*/int NEEDcMAXRESOURCE=0; /*辅助向量*/bool FINISHMAXPROCESS; /*系统是否有足够的资源分配*/int pMAXPROCESS; /*记录序列*/int m,n; /*m个进程,n个资源*/4.2银行家算法设计在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。设进程cusneed提出请求REQUEST i，则银行家算法按如下规则进行判断。(1)如果REQUEST cusneed i<= NEEDcusneedi，则转(2)；否则，出错。(2)如果REQUEST cusneed i<= AVAILABLEcusneedi，则转(3)；否则，出错。(3)系统试探分配资源，修改相关数据： AVAILABLEi-=REQUESTcusneedi; ALLOCATIONcusneedi+=REQUESTcusneedi; NEEDcusneedi-=REQUESTcusneedi;(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。(5)对于某一进程i，若对所有的j，有NEEDij=0，则表此进程资源分配完毕，应将占用资源释放。4.3安全性检查算法(1)设置两个工作向量Work=AVAILABLE;FINISH(2)从进程集合中找到一个满足下述条件的进程，FINISH=false;NEED<=Work;如找到，执行(3)；否则，执行(4)(3)设进程获得资源，可顺利执行，直至完成，从而释放资源。Work+=ALLOCATION;Finish=true;GOTO 2(4)如所有的进程Finish= true，则表示安全；否则系统不安全。安全性检查结束释放资源继续分配进程执行完保持原分配报错，重新输入开始初始化录入请求资源数AVAILABLEi-=REQUESTi;ALLOCATIONi+=REQUESTi;NEEDi-= REQUESTi;REQUESTi>NEEDi或者 REQUESTi>AVAILABLEi安全AVAILABLEi+=REQUESTi;ALLOCATIONi-=REQUESTi;NEEDi+= REQUESTi;YESNONONONOYESYESYES4.4流程图 图4.1程序设计流程图5运行调试及结果说明初始化时若已分配资源多于最多所需资源则会报错，需重新输入（如图5.1所示）：图5.1为输入报错初始化后状态显示图5.2图5.2为正确输入资源分配时请求量超过需求量或现有资源数同样会报错（如图5.3）图5.3为超出需求量报错显示特殊情况：若申请资源数既不大于资源需求量，又不大于现有资源数，但仍有可能导致死锁，如上图所示。此时会显示系统不安全，请求被拒绝。图5.4为拒绝分配资源Sum=0，表某一进程资源分配完毕，资源释放（请结合图5.4）图5.5资源分配完毕资源释放6总结本次设计中首先要解决的问题是对所做题目的理解。简单的文字描述总是生涩难懂，像银行家算法这一问题，如果单看题目要求往往不知如何下手，更不要谈下一步的设计过程。但倘若联系实际生活中银行贷款这一现象，再来看问题时，一切开始显得清晰，再加上老师的指点，便可以把自己究竟该作何工作搞清楚。这也给我一启示，我们要解决的诸多问题都源自生活，若要解决它，联系实际是个很不错的选择。明白了需求，下一个难点是如何通过软件实现。我所做的银行家算法这一题目，为了防止死锁，需要进行大量的判断，这也导致了一个问题，即在进行调试时，一旦出现问题，往往难以找到问题所在，针对这一问题，我编写了一些监测行（请参看源程序），这样能比较容易的找到问题的原因所在，这也是此次课程设计中在编程方面的一个收获。通过本次课程设计，我对软件的开发的过程有了较为深入的了解，虽然只是对一个问题的简单模拟，但麻雀虽小五脏俱全，我对相关问题的解决已经有了一定的认识，对软件技术这门课程也有了更为透彻的感悟。本次课程设计，锻炼了我分析问题和解决问题的能力，为今后相关问题的解决积累了宝贵经验，也增强了自己的耐心与自信，受益匪浅。参考文献1 严蔚敏,吴伟民.数据结构(C语言版).清华大学出版社.1999年 2 汤小丹,梁红兵,哲凤屏,汤子嬴.计算机操作系统（第三版）.西安电子科技大学出版社；3 汤子瀛,哲凤屏.计算机操作系统M.西安：西安电子科技大学学出版社.1996年4 王万森.计算机操作系统原理M.北京：高等教育出版社.2001年5 周长林，左万历.计算机操作系统教程M.北京：高等教育出版社.1994年6 黄廷辉，王宇英.计算机操作系统实践教程M.北京：清华大学出版社. 2007年5月7 殷兆麟.计算机操作系统M.北京：清华大学出版社.2007年3月8 张尧学,史美林，张高.计算机操作系统教程M.北京：清华大学出版社.1993年致 谢在这次操作系统银行家算法实现程序设计中，我得到了马生菊老师的认真指导和帮助，同时也感谢我的队友刘城辉同学，因为他才提高了我设计进度和效率。我和刘城辉同学共同完成这次课程设计，在程序设计过程中难免会遇到各种问题，谢谢马老师的耐心指导，谢谢同伴的包容，在这次课程设计中我感觉我有了很大的提高，我相信自己以后会做得更好。通过本次设计，我的知识领域得到了进一步扩展，专业技能进一步提高，同时增强了分析和解决实际问题的综合能力。首先，我们要感谢学校给我们提供了此次课程设计的机会，能让我们在一起学习与研究，让我们有机会对所学的理论知识进行实践。最后，在我设计完成后对程序的测试，并在同学与队友的帮助下才得以完成没有他们，也许就难以发现一些潜在的错误，在此一并表示感谢。附录（源程序）：#include <iostream>#include <windows.h> #include <time.h> using namespace std;#define MAXPROCESS 50 /*最大进程数*/ #define MAXRESOURCE 100 /*最大资源数*/int AVAILABLEMAXRESOURCE; /*可用资源数组*/int MAXMAXPROCESSMAXRESOURCE; /*最大需求矩阵*/int ALLOCATIONMAXPROCESSMAXRESOURCE; /*分配矩阵*/int NEEDMAXPROCESSMAXRESOURCE; /*需求矩阵*/int REQUESTMAXPROCESSMAXRESOURCE; /*进程需要资源数*/int SUMMITMAXRESOURCE=0 ; /*各种资源总量*/int NEEDcMAXRESOURCE=0; /*辅助向量*/bool FINISHMAXPROCESS; /*系统是否有足够的资源分配*/int pMAXPROCESS; /*记录序列*/int m,n; /*m个进程,n个资源*/void Init();bool Safe();void Bank();void main() system("color 01f"); /设置当前窗口的背景色和前景色 0 = 黑色 8 = 灰色 Init(); Safe(); Bank();void Init() /*初始化算法*/int i,j; cout<<" "<<endl; cout<<" 银行家算法模拟"<<endl; cout<<" "<<endl;cout<<" "<<endl; cout<<" "<<endl;cout<<" "<<endl;cout<<" 算法简介："<<endl;cout<<" 在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意"<<endl; cout<<" 的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要"<<endl; cout<<" 能使系统始终都处于安全状态，便可以避免发生死锁"<<endl;cout<<" 银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是"<<endl;cout<<" ,才分配。它是最具有代表性的避免死锁的算法。"<<endl;cout<<" "<<endl;cout<<" "<<endl;cout<<" "<<endl;cout<<" "<<endl;cout<<" 请稍候.6秒后跳入主界面" <<endl; Sleep(6000); system("cls"); cout<<" "<<endl; cout <<" 运行界面"<<endl; cout<<">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>"<<endl;cout<<"请输入进程的数目:"<<endl; cin>>m; cout<<"请输入资源的种类:"<<endl; cin>>n; cout<<"请输入每个进程最多所需的各资源数,按照"<<m<<"x"<<n<<"矩阵输入"<<endl; for(i=0;i<m;i+) for(j=0;j<n;j+) cin>>MAXij; cout<<"请输入每个进程已分配的各资源数,也按照"<<m<<"x"<<n<<"矩阵输入"<<endl; for(i=0;i<m;i+) for(j=0;j<n;j+) cin>>ALLOCATIONij; NEEDij=MAXij-ALLOCATIONij; if(NEEDij<0) cout<<"您输入的第"<<i+1<<"个进程所拥有的第"<<j+1<<"个资源数错误,请重新输入:"<<endl; j-; continue; for(j=0;j<n;j+) /已分配各资源总数for(i=0;i<m;i+) NEEDcj=ALLOCATIONij+NEEDcj; cout<<"请输入各个资源现有的数目:"<<endl; for(i=0;i<n;i+) cin>>AVAILABLEi; for(i=0;i<n;i+) /总资源数 SUMMITi=AVAILABLEi+ NEEDci; cout<<""<<endl; cout<<"初始化后状态显示:"<<endl; cout<<"每个进程最多所需的各资源数"<<endl; for(i=0;i<m;i+) for(j=0;j<n;j+) cout<<""<<MAXij<<" "if(j=n-1)cout<<" "<<endl; cout<<"每个进程已分配的各资源数"<<endl; for(i=0;i<m;i+) for(j=0;j<n;j+)cout<<""<<ALLOCATIONij<<" "if(j=n-1)cout<<" "<<endl; cout<<"各个资源现有的数目:"<<endl; for(i=0;i<n;i+)cout<<""<<AVAILABLEi<<" " cout<<" "<<endl; cout<<""<<endl;void Bank() /*银行家算法*/ int i,j,cusneed; char again; int sum=0; /*监测某一进程资源是否分配完毕*/int add=0; while(1) cout<<"请输入要申请资源的进程号(注:第1个进程号为0,依次类推)"<<endl; cin>>cusneed; cout<<"请输入进程所请求的各资源的数量"<<endl; for(i=0;i<n;i+) cin>>REQUESTcusneedi; if(REQUESTcusneedi>NEEDcusneedi) cout<<"您输入的本个请求数超过进程的需求量!请重新输入!"<<endl; i-;continue; if(REQUESTcusneedi>AVAILABLEi) cout<<"您输入的本个请求数超过系统有的资源数!请重新输入!"<<endl; i-;continue; for(i=0;i<n;i+) /资源分配 AVAILABLEi-=REQUESTcusneedi; ALLOCATIONcusneedi+=REQUESTcusneedi; NEEDcusneedi-=REQUESTcusneedi; if(Safe() cout<<""<<endl; cout<<"同意分配请求!"<<endl; cout<<"此次分配后状态显示:"<<endl; cout<<"当前每个进程最多尚需的各资源数"<<endl; for(i=0;i<m;i+)for(j=0;j<n;j+)cout<<""<<NEEDij<<" "if(j=n-1)cout<<" "<<endl; cout<<"当前每个进程已分配过的各资源数"<<endl; for(i=0;i<m;i+) for(j=0;j<n;j+)cout<<""<<ALLOCATIONij<<" "if(j=n-1)cout<<" "<<endl; for(i=0;i<m;i+) for(j=0;j<n;j+) add=NEEDij+add; /是否已分配完毕 if(add!=0)for(i=0;i<n;i+) sum=NEEDcusneedi+sum; cout<<"sum值:"<<sum<<""<<endl;cout<<" "<<endl; if (sum=0) for(i=0;i<n;i+) AVAILABLEi= ALLOCATIONcusneedi+AVAILABLEi; sum=0; cout<<"各个资源现有的数目:"<<endl; for(i=0;i<n;i+)cout<<""<<AVAILABLEi<<" " cout<<" "<<endl;add=0; elsecout<<"各个资源现有的数目:"<<endl; for(i=0;i<n;i+)cout<<""<<SUMMITi<<" " cout<<" "<<endl; cout<<""<<endl; else cout<<"您的请求被拒绝!"<<endl; /撤消资源分配 for(i=0;i<n;i+) AVAILABLEi+=REQUESTcusneedi; ALLOCATIONcusneedi-=REQUESTcusneedi; NEEDcusneedi+=REQUESTcusneedi; for(i=0;i<m;i+) FINISHi=false; cout<<"您还想再次请求分配吗?是请按y/Y,否请按其它键"<<endl; cin>>again; if(again='y'|again='Y') continue; break; /跳出while bool Safe() /*安全性算法*/ int i,j,k,l=0; int WorkMAXRESOURCE; /*工作数组*/ for(i=0;i<n;i+) Worki=AVAILABLEi; for(i=0;i<m;i+) FINISHi=false; for(i=0;i<m;i+) if(FINISHi=true) continue; else for(j=0;j<n;j+) if(NEEDij>Workj) break; if(j=n) FINISHi=true; /FINISH在此被赋值,表进程i可顺利进行 for(k=0;k<n;k+) /并假设已执行完成 Workk+=ALLOCATIONik; pl+=i; i=-1; /再从i=0开始判断 else continue; if(l=m) /所有进程都可完成 cout<<"系统是安全的"<<endl; cout<<"安全序列:"<<endl; for(i=0;i<l;i+) cout<<pi; if(i!=l-1) /最后一项不输-> cout<<"->" cout<<""<<endl; return true; cout<<"系统是不安全的"<<endl; return false;