《软件技术课程设计报告-模拟银行家算法原理.doc》由会员分享，可在线阅读，更多相关《软件技术课程设计报告-模拟银行家算法原理.doc（16页珍藏版）》请在三一文库上搜索。
1、中南大学软件技术课程设计报告课程名称：模拟银行家算法原理班级： 学号： 姓名： 指导老师： 2009年5月2日一 设计目的模拟实现银行家算法，用银行家算法实现资源分配。二 问题描述在死锁的避免中，银行家算法把系统状态分为安全状态和不安全状态，只要能使系统始终处于安全状态，便可以避免发生死锁。所谓安全状态，是指系统能按某种顺序为每个进程分配所需资源，直到最大需求，使每一个进程都可以顺利完成，即可找到一个安全资源分配序列。模拟实现这个工作过程。三 设计思路我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制
2、定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。四 详细设计1、初始化由用户输入数据，分别对可利用资源向量矩阵AVAILABLE、最大需求矩阵MAX、分配矩阵ALLOCATION、需求矩阵NEED赋值。2、银行家算法在避免死锁的方法中，
3、所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。设进程cusneed提出请求REQUEST i，则银行家算法按如下规则进行判断。(1)如果REQUEST cusneed i= NEEDcusneedi，则转(2)；否则，出错。(2)如果REQUEST cusneed i= AVAILABLEcusneedi，则转(3)；否则，出错。(3)系统试探分配资源，修改相关数据： AVAILABLEi-=REQUESTcusnee
4、di; ALLOCATIONcusneedi+=REQUESTcusneedi; NEEDcusneedi-=REQUESTcusneedi;(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。(5)对于某一进程i，若对所有的j，有NEEDij=0，则表此进程资源分配完毕，应将占用资源释放。3、安全性检查算法(1)设置两个工作向量Work=AVAILABLE;FINISH(2)从进程集合中找到一个满足下述条件的进程，FINISH=false;NEEDNEEDi或者REQUESTiAVAILABLEi报错，重新输入AVAILABLEi-=REQUEST i
5、;ALLOCATIONi+=REQUEST i;NEEDi-=REQUESTi;初始化安全性检查安全AVAILABLEi+=REQUEST i;ALLOCATIONi-=REQUEST i;NEEDi+=REQUESTi;保持原分配进程执行完释放资源继续分配结束YESNOYESNOYESYESNONO四 源程序：#include #include #include /#include /#includeusing namespace std;#define MAXPROCESS 50 /*最大进程数*/ #define MAXRESOURCE 100 /*最大资源数*/int AVAILABL
6、EMAXRESOURCE; /*可用资源数组*/int MAXMAXPROCESSMAXRESOURCE; /*最大需求矩阵*/int ALLOCATIONMAXPROCESSMAXRESOURCE; /*分配矩阵*/int NEEDMAXPROCESSMAXRESOURCE; /*需求矩阵*/int REQUESTMAXPROCESSMAXRESOURCE; /*进程需要资源数*/int SUMMITMAXRESOURCE=0 ; /*各种资源总量*/int NEEDcMAXRESOURCE=0; /*辅助向量*/bool FINISHMAXPROCESS; /*系统是否有足够的资源分配*/
7、int pMAXPROCESS; /*记录序列*/int m,n; /*m个进程,n个资源*/void Init();bool Safe();void Bank();void main() /textbackground(0); /* 设置屏幕背景色 */ Init(); Safe(); Bank();void Init() /*初始化算法*/int i,j; cout endl; cout 银行家算法模拟endl; cout endl;cout 通信0602 唐敏 0401060223 endl; cout endl;cout endl;cout 算法简介：endl;cout 在避免死锁的方
8、法中，所施加的限制条件较弱，有可能获得令人满意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; couten
9、dl;cout请输入进程的数目:m; cout请输入资源的种类:n; cout请输入每个进程最多所需的各资源数,按照mxn矩阵输入endl; for(i=0;im;i+) for(j=0;jMAXij; cout请输入每个进程已分配的各资源数,也按照mxn矩阵输入endl; for(i=0;im;i+) for(j=0;jALLOCATIONij; NEEDij=MAXij-ALLOCATIONij; if(NEEDij0) cout您输入的第i+1个进程所拥有的第j+1个资源数错误,请重新输入:endl; j-; continue; for(j=0;jn;j+) /已分配各资源总数for(i
10、=0;im;i+) NEEDcj=ALLOCATIONij+NEEDcj; / for(i=0;in;i+) /此四行用于检验 / / coutNEEDci ; / cout请输入各个资源现有的数目:endl; for(i=0;iAVAILABLEi; for(i=0;in;i+) /总资源数 SUMMITi=AVAILABLEi+ NEEDci; /for(i=0;in;i+) /检验用/coutSUMMITi ; / cout endl;coutendl; cout初始化后状态显示:endl;cout每个进程最多所需的各资源数endl; for(i=0;im;i+) for(j=0;jn;
11、j+) coutMAXij ;if(j=n-1)cout endl; cout每个进程已分配的各资源数endl; for(i=0;im;i+) for(j=0;jn;j+) coutALLOCATIONij ;if(j=n-1)cout endl; cout各个资源现有的数目:endl; for(i=0;in;i+)coutAVAILABLEi ; cout endl; coutendl;void Bank() /*银行家算法*/ int i,j,cusneed; char again; int sum=0; /*监测某一进程资源是否分配完毕*/int add=0; while(1) cout
12、请输入要申请资源的进程号(注:第1个进程号为0,依次类推)cusneed; cout请输入进程所请求的各资源的数量endl; for(i=0;iREQUESTcusneedi; / / for(i=0;iNEEDcusneedi) cout您输入的本个请求数超过进程的需求量!请重新输入!AVAILABLEi) cout您输入的本个请求数超过系统有的资源数!请重新输入!endl; i-;continue; for(i=0;in;i+) /资源分配 AVAILABLEi-=REQUESTcusneedi; ALLOCATIONcusneedi+=REQUESTcusneedi; NEEDcusne
13、edi-=REQUESTcusneedi; if(Safe() coutendl; cout同意分配请求!endl; cout此次分配后状态显示:endl; cout当前每个进程最多尚需的各资源数endl; for(i=0;im;i+)for(j=0;jn;j+) coutNEEDij ;if(j=n-1)cout endl; cout当前每个进程已分配过的各资源数endl; for(i=0;im;i+) for(j=0;jn;j+) coutALLOCATIONij ;if(j=n-1)cout endl; for(i=0;im;i+) for(j=0;jn;j+) add=NEEDij+a
14、dd; /是否已分配完毕 if(add!=0)for(i=0;in;i+) sum=NEEDcusneedi+sum; coutsum值:sumendl;/coutsum ;cout endl; if (sum=0) for(i=0;in;i+) AVAILABLEi= ALLOCATIONcusneedi+AVAILABLEi; sum=0; cout各个资源现有的数目:endl; for(i=0;in;i+)coutAVAILABLEi ; cout endl;add=0; /coutadd endl;elsecout各个资源现有的数目:endl; for(i=0;in;i+)coutSU
15、MMITi ; cout endl; coutendl; else cout您的请求被拒绝!endl; /撤消资源分配 for(i=0;in;i+) AVAILABLEi+=REQUESTcusneedi; ALLOCATIONcusneedi-=REQUESTcusneedi; NEEDcusneedi+=REQUESTcusneedi; for(i=0;im;i+) FINISHi=false; cout您还想再次请求分配吗?是请按y/Y,否请按其它键again; if(again=y|again=Y) continue; break; /跳出while bool Safe() /*安全性
16、算法*/ int i,j,k,l=0; int WorkMAXRESOURCE; /*工作数组*/ for(i=0;in;i+) Worki=AVAILABLEi; for(i=0;im;i+) FINISHi=false; for(i=0;im;i+) if(FINISHi=true) continue; else for(j=0;jWorkj) break; if(j=n) FINISHi=true; /FINISH在此被赋值,表进程i可顺利进行 for(k=0;kn;k+) /并假设已执行完成 Workk+=ALLOCATIONik; pl+=i; i=-1; /再从i=0开始判断 el
17、se continue; if(l=m) /所有进程都可完成 cout系统是安全的endl; cout安全序列:endl; for(i=0;il;i+) cout cout; coutendl; return true; cout系统是不安全的endl; return false; 五 运行调试及结果说明初始化时若已分配资源多于最多所需资源则会报错，需重新输入（如上图所示）初始化后状态显示资源分配时请求量超过需求量或现有资源数同样会报错（如上图）特殊情况：若申请资源数既不大于资源需求量，又不大于现有资源数，但仍有可能导致死锁，如上图所示。此时会显示系统不安全，请求被拒绝。（为便于说明，以上均采
18、用二阶矩阵。其他类型矩阵原理相同）Sum=0，表某一进程资源分配完毕，资源释放（请结合第四个图）六 总结本次设计中首先要解决的问题是对所做题目的理解。简单的文字描述总是生涩难懂，像银行家算法这一问题，如果单看题目要求往往不知如何下手，更不要谈下一步的设计过程。但倘若联系实际生活中银行贷款这一现象，再来看问题时，一切开始显得清晰，再加上老师的指点，便可以把自己究竟该作何工作搞清楚。这也给我一启示，我们要解决的诸多问题都源自生活，若要解决它，联系实际是个很不错的选择。明白了需求，下一个难点是如何通过软件实现。我所做的银行家算法这一题目，为了防止死锁，需要进行大量的判断，这也导致了一个问题，即在进行调试时，一旦出现问题，往往难以找到问题所在，针对这一问题，我编写了一些监测行（请参看源程序），这样能比较容易的找到问题的原因所在，这也是此次课程设计中在编程方面的一个收获。通过本次课程设计，我对软件的开发的过程有了较为深入的了解，虽然只是对一个问题的简单模拟，但麻雀虽小五脏俱全，我对相关问题的解决已经有了一定的认识，对软件技术这门课程也有了更为透彻的感悟。本次课程设计，锻炼了我分析问题和解决问题的能力，为今后相关问题的解决积累了宝贵经验，也增强了自己的耐心与自信，受益匪浅。