银行家算法课程设计报告

1、若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量,若能满足则中南大学 软件技术课程设计报告 课程名称：模拟银行家算法原理 班级： 学号： 姓名： 指导老师：2009 年 5 月 2 日一 设计目的模拟实现银行家算法，用银行家算法实现资源分配。二 问题描述 在死锁的避免中，银行家算法把系统状态分为安全状态和不安全状态，只要能使系统 始终处于安全状态，便可以避免发生死锁。所谓安全状态，是指系统能按某种顺序为每个 进程分配所需资源，直到最大需求，使每一个进程都可以顺利完成，即可找到一个安全资 源分配序列。模拟实现这个工作过程。三 设计思路我们可以把操作系统看作是银行家， 操作系统管理的

2、资源相当于银行家管理的资 金，进程向操作系统请求分配资源相当于用户向银行家贷款。 操作系统按照银行家制 定的规则为进程分配资源， 当进程首次申请资源时， 要测试该进程对资源的最大需求 量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源， 否则 就推迟分配。 当进程在执行中继续申请资源时， 先测试该进程已占用的资源数与本次 申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源， 按当前的申请量分配资源，否则也要推迟分配。四详细设计1初始化由用户输入数据，分别对可利用资源向量矩阵AVAILABLE最大需求矩阵MAX分配矩阵ALLOCATION需求矩阵NEED武

3、值。2、银行家算法在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。银行家算法的基本思想是分配资源之前，判断系统是否是安全的；若 是,才分配。设进程cusneed提出请求REQUEST i,贝U银行家算法按如下规则进行判断。(1) 如果 REQUEST cusneed i= NEEDcusneedi，则转(2);否则，出错。(2) 如果 REQUESTusneed i= AVAILABLEcusneedi，则转(3);否则，出错。(3) 系统试探分配资源，修改相关数据：AV

4、AILABLEi-=REQUESTcus needi;ALLOCATIONcus needi+=REQUESTcus needi;NEEDcus needi-=REQUESTcus needi;(4) 系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复 原状，进程等待。(5) 对于某一进程i，若对所有的j，有NEEDij=O ，则表此进程资源分配完毕，应 将占用资源释放。3、安全性检查算法 设置两个工作向量 Work=AVAILABLE;FINISH(2) 从进程集合中找到一个满足下述条件的进程，FINISH=false;NEED=Work;如找到，执行；否则，执行(4)(

5、3) 设进程获得资源，可顺利执行，直至完成，从而释放资源。Work+=ALLOCATION;Fini sh=true;GOTO 2如所有的进程Finish= true ，则表示安全；否则系统不安全4、流程图序:四源程#include #include #include /#include /#include最大进程数 */ 最大资源数 */ 可用资源数组 */ /* 最大需求矩阵 */using namespace std;#define MAXPROCESS 50 /* #define MAXRESOURCE 100/*int AVAILABLEMAXRESOURCE; /* int MAX

6、MAXPROCESSMAXRESOURCE;int ALLOCATIONMAXPROCESSMAXRESOURCE; 分/*配矩阵 */int NEEDMAXPROCESSMAXRESOURCE; /* 需求矩阵 */ int REQUESTMAXPROCESSMAXRESOURCE; 进/*程需要资源数 */int SUMMITMAXRESOURCE=0 ; int NEEDcMAXRESOURCE=0; bool FINISHMAXPROCESS;int pMAXPROCESS;int m,n; /*m/* 各种资源总量 */* 辅助向量 */* 系统是否有足够的资源分配 */* 记录序列

7、 */个进程 ,n 个资源 */void Init();bool Safe();void Bank();void main()/textbackground(0); /*Init();Safe();Bank();void Init() /*设置屏幕背景色 */初始化算法 */int i,j;cout endl;cout银行家算法模拟 endl;coutendl;cout通信 0602唐敏 0401060223endl;coutcout endl;cout 算法简介： endl;cout 在避免死锁的方法中， 所施加的限制条件较弱， 有可能获得令人满 意e ndl;cout的系统性能。在该方法中

8、把系统的状态分为安全状态和不安全状态，只要e ndl;cout能使系统始终都处于安全状态，便可以避免发生死锁 endl;cout 银行家算法的基本思想是分配资源之前 , 判断系统是否是安全的 若是e ndl;cout , 才分配。它是最具有代表性的避免死锁的算法。 endl;cout endl;coutendl;coutendl;cout endl;cout请稍候 .6 秒后跳入主界面 endl;Sleep(6000);system(cls);cout endl;cout 运行界面 endl;cout endl;cout 请输入进程的数目 :m;cout 请输入资源的种类 :n;coutvv请

9、输入每个进程最多所需的各资源数,按照vvmvvxvv*矩阵输入endl;for(i=0;im;i+)for(j=0;jMAXij;cout请输入每个进程已分配的各资源数,也按照vvmvxvv*矩阵输入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=0;im;i+)NEEDcj=ALLOCATIONij+NEEDcj

10、;/ 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;j+) coutMAXij ;if(j=n-1)cout en

11、dl;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;cout endl;银行家算法 */void Bank() /*int i,j,cusneed;char again;int sum=0; /* 监测某一进程资源是否分配完毕 */int add=0;while(1)cout 请输入要申请资源的进程号 (注: 第 1个进程号为 0, 依次类

12、推 )cusneed;cout 请输入进程所请求的各资源的数量 endl; for(i=0;iREQUESTcusneedi;/ / for(i=0;iNEEDcusneedi)cout 您输入的本个请求数超过进程的需求量 ! 请重新输入 !AVAILABLEi)cout 您 输 入 的 本 个 请 求 数 超 过 系 统 有 的 资 源 数 ! 请 重 新 输 入!e ndl;i-; continue;for(i=0;in;i+)/资源分配AVAILABLEi-=REQUESTcusneedi; ALLOCATIONcusneedi+=REQUESTcusneedi;NEEDcusneedi

13、-=REQUESTcusneedi;if(Safe() endl;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+add; / 是否已分配完毕

14、 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+)coutSUMMITi ;cout endl

15、;endl; elsecout 您的请求被拒绝 !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; / 跳出 whilebool Safe() /* 安全性算法 */int i,j,k,l=0;int

16、 WorkMAXRESOURCE; /*工作数组 */for(i=0;in;i+)Worki=AVAILABLEi;for(i=0;im;i+)FINISHi=false;for(i=0;im;i+)if(FINISHi=true)continue;elsefor(j=0;jWorkj)break;if(j=n)FINISHi=true; /FINISH 在此被赋值 , 表进程 i 可顺利进行 for(k=0;kn;k+) / 并假设已执行完成Workk+=ALLOCATIONik;pl+=i;i=-1; / 再从 i=0 开始判断elsecontinue;if(l=m) / 所有进程都可完成

17、cout系统是安全的 endl;cout安全序列 :endl;for(i=0;il;i+)coutcout; coutendl;return true;cout 系统是不安全的 endl;return false;五 运行调试及结果说明 初始化时若已分配资源多于最多所需资源则会报错，需重新输入(如上图所示) 初始化后状态显示 资源分配时请求量超过需求量或现有资源数同样会报错(如上图) 特殊情况：若申请资源数既不大于资源需求量，又不大于现有资源数，但仍有可能导致死 锁，如上图所示。此时会显示系统不安全，请求被拒绝。(为便于说明，以上均采用二阶矩阵。其他类型矩阵原理相同)Sum=0表某一进程资源分配完毕，资源释放(请结合第四个图)六总结本次设计中首先要解决的问题是对所做题目的理解。简单的文字描述总是生涩难懂， 像银行家算法这一问题，如果单看题目要求往往不知如何下手，更不要谈下一步的设计过 程。但倘若联系实际生活中银行贷款这一现象，再来看问题时，一切开始显得清晰，再加 上老师的指点，便可以把自己究竟该作何工作搞清楚。这也给我一启示，我们要解决的诸 多问题都源自生活，若要解决它，联系实际是个很不错的选择。明白了需求，下一个难点是如何通过软件实现。我所做的银行家算法