银行家算法要点

1、福建农林女修东方禽院DONGFANG COLLEGE , FUJIAN AGRICULTURE AND FORESTRY UNIVERSITY筱计说鋼吊课程名称：操作系统系别：计算机科学系年级专业：计算机科学与技术学 号:姓 名:任课教师：成绩：2015 年 11 月 25 日目录一、本选题课程设计的目的 3二、本选题课程设计的要求 3三、本选题课程设计报告内容 31. 前言 32. 银行家算法的环境 43. 系统技术分析 44. 算法描述及数据结构模型 55. 运行结果： 18四、 总结 1920参考文献银行家算法一、本选题课程设计的目的了解掌握银行家算法，学会模拟实现资源分配，同时有要求编

2、写和调试一个 系统分配资源的简单模拟程序，观察死锁产生的条件，并使用适当的算法，有效 的防止和避免死锁的发生二、本选题课程设计的要求（1）模拟一个银行家算法；（2）初始化时让系统拥有一定的资源；（3）用键盘输入的方式申请资源；（4）如果预分配后，系统处于安全状态，则修改系统的资源分配情况；（5）如果预分配后，系统处于不安全状态，则提示不能满足请求，三、本选题课程设计报告内容1 前言Dijkstra （1965） 提出了一种能够避免死锁的调度算法，称为银行家算法。它的模型基于一个小城镇的银行家，他向一群客户分别承诺了一定的贷款额 度，每个客户都有一个贷款额度，银行家知道不可能所有客户同时都需要最

3、大贷 款额，所以他只保留一定单位的资金来为客户服务， 而不是满足所有客户贷款需 求的最大单位。这里将客户比作进程，贷款比作设备，银行家比作系统。客户们各自做自己的生意，在某些时刻需要贷款。在某一时刻，客户已获得 的贷款和可用的最大数额贷款称为与资源分配相关的系统状态。一个状态被称为 是安全的，其条件是存在一个状态序列能够使所有的客户均得到其所需的贷款。 如果忽然所有的客户都申请，希望得到最大贷款额，而银行家无法满足其中任何 一个的要求，则发生死锁。不安全状态并不一定导致死锁，因为客户未必需要其 最大贷款额度，但银行家不敢抱这种侥幸心理。银行家算法就是对每一个请求进行检查，检查如果满足它是否会导

4、致不安全 状态。若是，则不满足该请求；否则便满足。检查状态是否安全的方法是看他是否有足够的资源满足一个距最大需求最 近的客户。如果可以，则这笔投资认为是能够收回的，然后接着检查下一个距最 大需求最近的客户，如此反复下去。如果所有投资最终都被收回，则该状态是安 全的，最初的请求可以批准。2 银行家算法的环境Window7系统下的Visual C+ 6.0 中运行3. 系统技术分析设计的主要内容是模拟实现动态资源分配。同时编写和调试一个系统动态 资源的简单模拟程序，观察死锁产生的条件，并使用适当的算法，有效的防止和 避免死锁的发生。银行家算法.顾名思义是来源于银行的借贷业务，一定数量的本金要应多

5、个客户的借贷周转，为了防止银行加资金无法周转而倒闭， 对每一笔贷款，必须 考察其是否能限期归还。在操作系统中研究资源分配策略时也有类似问题，系统 中有限的资源要供多个进程使用，必须保证得到的资源的进程能在有限的时间内 归还资源，以供其他进程使用资源。如果资源分配不得到就会发生进程循环等待 资源，则进程都无法继续执行下去的死锁现象。把一个进程需要和已占有资源的情况记录在进程控制中，假定进程控制块 PCB其中“状态”有就绪态、等待态和完成态。当进程在处于等待态时，表示系 统不能满足该进程当前的资源申请。“资源需求总量”表示进程在整个执行过程 中总共要申请的资源量。显然，每个进程的资源需求总量不能超

6、过系统拥有的 资源总数，银行算法进行资源分配可以避免死锁.4. 算法描述及数据结构模型银行家算法：设进程i提出请求Requestn，则银行家算法按如下规则进行判断。如果RequestnNeedi ， n，则报错返回。如果RequestnAvailable，则进程i进入等待资源状态，返回。(3) 假设进程i的申请已获批准，于是修改系统状态：Available=Available-RequestAllocatio n= Allocatio n+RequestNeed=Need-Request(4) 系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统 恢复原状，进程等待。安全性检查(

7、1) 设置两个工作向量 Work=Available ； FinishM=False(2) 从进程集合中找到一个满足下述条件的进程，Fi nish i=FalseNeed=Work如找到，执行；否则，执行(4)(3) 设进程获得资源，可顺利执行，直至完成，从而释放资源。Work=Work+Allocati onFini sh=TrueGO TO 2如所有的进程FinishM=true ，则表示安全；否则系统不安全。数据结构#defi ne False 0#defi ne True 1int Max100100=0;各进程所需各类资源的最大需求int Avaliable100=0;系统可用资源c

8、har name100=0;资源的名称int Allocatio n 100100=0;系统已分配资源int Need100100=0; 还需要资源int Request100=0;请求资源向量int temp100=0;存放安全序列int Work100=0;存放系统可提供资源int M=100; 作业的最大数为100int N=100; 资源的最大数为100void showdata()显示资源矩阵源程序代码实现#i nclude#i ncludevstri ng.h#i nclude#defi ne False 0#defi ne True 1int Max100100=0;各进程所需各

9、类资源的最大需求int Avaliable100=0;系统可用资源char name100=0;资源的名称int Allocatio n100100=0;系统已分配资源int Need100100=0; 还需要资源int Request100=0;请求资源向量int temp100=0;存放安全序列int Work100=0;存放系统可提供资源int M=100; 作业的最大数为100int N=100; 资源的最大数为100void showdata()显示资源矩阵int i,j;cout系统目前可用的资源Avaliable:endl;for(i=0;iN;i+)cout n amei;co

10、ute ndl;for (j=0;jN;j+)coutAvaliablej ;/输出分配资源coute ndl;coutMaxAllocatio nNeede ndl;coutvv进程名 ;for(j=0;j3;j+)for(i=0;iN;i+)cout n amei;cout;coute ndl;for(i=0;iM;i+)cout i;for(j=0;jN;j+)coutMaxijvv;cout;for(j=0;jN;j+)coutAllocatio nij;cout;for(j=0;jN;j+)coutNeedij;coute ndl;in t cha ngdata(i nt i) 进行

11、资源分配int j;for (j=O;jM;j+) Avaliablej=Avaliablej-Requestj;Allocatio nij=Allocatio n ij+Requestj;Needij=Needij-Requestj;return 1;int safe()安全性算法int i,k=O,m,apply,Fi ni sh100=0;int j;int flag=0;Work0=Avaliable0;Work1=Avaliable1;Work2=Avaliable2;for(i=0;iM;i+)apply=0;for(j=0;jN;j+)if (Fi ni shi=False&Ne

12、edijv=Workj) apply+;if(apply=N)for(m=0;mN;m+)变分配数Workm=Workm+Allocatio n im;Fini shi=True;tempk=i;i=-1;k+;flag+;for(i=0;iM;i+)if(Fi ni shi=False)coutvv系统不安全endl;不成功系统不安全return -1;coutvv系统是安全的!endl;如果安全，输出成功cout分配的序列：；for(i=0;iM;i+)输出运行进程数组couttempi;if(iM-1) cout;coutvve ndl;return 0;void share()利用银行

13、家算法对申请资源对进行判定char ch;int i=0,j=0;ch=y;coutvv请输入要求分配的资源进程号(0-vvM-1 i; 输入须申请的资源号coutvv请输入进程vvivv 申请的资源:endl;for(j=0;jN;j+)coutv n amejRequestj;/ 输入需要申请的资源for (j=0;jNeedij)/判断申请是否大于需求，若大于则出错coutvv进程vvivv申请的资源大于它需要的资源;cout分配不合理，不予分配！Avaliablej)判断申请是否大于当前资源，若大于则/出错coutvv进程vvivv申请的资源大于系统现在可利用的资源;coutvv分配出

14、错，不予分配!vvendl;ch= n;break;if(ch=y) cha ngdata(i);/根据进程需求量变换资源showdata();/根据进程需求量显示变换后的资源safe();/根据进程需求量进行银行家算法判断void addresources()添加资源int n, flag;coutvv请输入需要添加资源种类的数量cinn;flag=N;N=N+n;for(i nt i=0;in ameflag;cout数量:;cin Avaliableflag+;showdata();safe();void delresources()删除资源char ming;int i,flag=1;

15、coutvv请输入需要删除的资源名称：docinming;for(i=0;iN;i+)if(ming=n amei)flag=0;break;if(i=N)coutvv该资源名称不存在，请重新输入:while(flag);for(i nt j=i；jN-1;j+)n amej=n amej+1;Avaliablej=Avaliablej+1;N=N-1;showdata();safe();void cha ngeresources()修改资源函数cout系统目前可用的资源Avaliable:endl;for(i nt i=0;iN;i+)cout n ameivv:vAvaliableivve

16、 ndl;cout输入系统可用资源Avaliable:Avaliable0Avaliable1Avaliable2;coutvv经修改后的系统可用资源为endl;for (i nt k=0;kN;k+)cout n amek:Avaliableke ndl; showdata();safe();void addprocess()添加作业int flag=M;M=M+1;coutvv请输入该作业的最打需求量Maxvendl; for(i nt i=0;iN;i+)cout n ameiMaxflagi;Needflagi=Maxflagi-Allocatio nflagi;showdata();

17、safe();int mai n()主函数 int i,j, nu mber,choice, m,n, flag;char ming;coutvv*单处理机系统进程调度实现*、n;N=n;for(i=0;i ming;n amei=ming;coutvv资源的数量:;cinnu mber;Avaliablei=nu mber;coutvve ndl;coutvv请输入作业的数量:;cinm;M=m; coutvv请输入各进程的最大需求量(m*矩阵)Max:vendl; for(i=0;im;i+)for(j=0;j Maxij;doflag=0;coutvv请输入各进程已经申请的资源量(m*矩

18、阵)Allocati on :e ndl;for(i=0;im;i+)for(j=0;j Allocati on ij;if(Allocati on ijMaxij)flag=1;Needij=Maxij-Allocatio n ij;if(flag)coutvv申请的资源大于最大需求量，请重新输入!n;while(flag);showdata(); 显示各种资源safe();用银行家算法判定系统是否安全while(choice)coutvv*银行家算法演示 *endl;coutvv1:增加资源vve ndl;coutvv2:删除资源vve ndl;coutvv3:修改资源vve ndl;co

19、utvv4:分配资源vve ndl;cout5:增加作业e ndl;cout0:离开e ndl;coutv*v choice;switch(choice)case 1: addresources();break;case 2: delresources();break;case 3: cha ngeresources();break;case 4: share();break;case 5: addprocess();break;case 0: choice=0;break;default: coutvv请正确选择功能号(0-5)!endl;break;return 1;作系统银行家算法流程图：初始化函数chushihua()开始输入进程的数量输入资源种类数输入个资源当前可用资源数输出提示：同意分配请求AVAILABLEi-=REQUE STi；ALLOCATIONi-=REQU ESTi;NEEDi+=REQUESTi退出程序，银行家算法Bank()结束;安全性算法Safe()开始Work+=ALLOCATIONi; FINISHi=ture;安全，输出安全序列Retur n ture ；5 运行结果:T时