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

1、操作系统课程设计说明书题目: 银行家算法模拟 院 系： 计算机科学与工程学院 专业班级： 计算机10-5班 学 号： 2010303157 学生姓名： 张 绪 磊 指导教师： 刘 惠 临 2013年 1月 9日安徽理工大学课程设计（论文）任务书 计算机科学与工程学院 计算机科学与技术系 学 号2010303157学生姓名张绪磊专业（班级）计算机10-5班设计题目 银行家算法模拟设计技术参数系统平台：Windows 7开发工具：vc+ 6.0 开发语言：c/c+语言设计要求1.系统基本实现安全性、添加资源、修改资源、配置资源等算法。2.要求系统能实现人机交互，界面友好。3.当输入一组资源和作业的

2、数量时，可以根据其需求量判断系统安全性。工作量1.设计报告要求不少于4000字。2.源程序要求不少于300行工作计划算法的分析及系统的功能分析92012.12.03 系统的总体设计42012.12.10 系统功能的详细设计12012.12.24 系统的编码设计和界面设计52013.01.01 系统的调试及测试22013.01.09 撰写课程设计报告参考资料1汤小丹，梁红兵，哲凤屏，汤子瀛.计算机操作系统.第三版.西安：西安电子科技大学出版社，20072 谭浩强. C程序设计.第三版.北京：清华大学出版社，20053张海藩.软件工程导论.第五版.北京：清华大学出版社，20084 冯博琴.Visu

3、al C+与面向对象程序设计教程.第三版. 高等教育出版社; 2010指导教师签字系主任签字 2013年 1月 9日安徽理工大学课程设计（论文）成绩评定表学生姓名： 张 绪 磊 学号： 2010303157 专业班级： 计算机10-5班 设计题目： 银行家算法模拟 指导教师评语：成绩： 指导教师： 年 月 日 摘 要银行家算法是一个用来预防系统进入死锁状态的算法，用它可以判断系统的安全性，如果系统当前处于安全状态，则可以为申请资源的进程分配资源；如果不是安全状态，则不能为申请资源的进程分配资源。 银行家算法执行过程中，首先判断申请资源的进程所申请的资源数目是否合法，若是合法的，则可以为其进行试

4、分配，再利用安全性算法求出安全序列，如果存在安全序列，则说明可以给申请资源的进程分配资源，分配成功，继续为其它进程服务。如果找不到安全序列，则说明为该进程分配资源后系统会进入不安全状态，所以不能为该进程分配资源，使该进程进入阻塞状态。若申请资源的进程申请的资源数目不合法，则不需要进行试分配，直接使其进入阻塞状态，处理其他申请资源的进程。 关键词：可用资源，最大需求矩阵，分配矩阵，需求矩阵，安全性算法，安全序列目 录1.绪论11.1系统分工11.2课题背景11.3死锁11.4安全性21.5算法设计思想22.需求分析32.1基本要求32.2模块划分33.总体设计43.1算法设计43.2模块设计54

5、.详细设计64.1程序流程图64.2主要函数的核心代码65.程序测试125.1界面设计125.2数据测试135.3操作提示146.总结16参考文献171.绪论1.1系统分工银行家算法模拟设计内容及其说明本人设计内容主要和组员张鑫设计MFC界面和代码的调试，涉及主要功能代码，包括其他组员设计的主要函数代码嵌入到MFC中，主要编写了银行家算法。对MFC程序遇到的错误修改、功能缺失及算法不健壮等问题作了修改。之后和其他组员一起将其他的功能嵌入到程序里，主要是添加资源，删除资源，修改资源，分配资源和增加作业功能，最终完成了了一个整体的银行家算法。其他组员设计内容添加资源，修改资源，删除资源，分配资源，

6、增加作业。1.2课题背景在多道程序系统中，虽可以借助多个进程的并发执行来改善系统的资源利用率，提高系统吞吐量，但可能发生一种危险死锁，即多个进程在运行过程中因争夺资源而造成的一种僵局，若无外力作用，将无法再向前推进。如此，寻求一种避免死锁的方法便显得有为重要。死锁的产生一般的原因有两点：竞争资源和进程间推进顺序非法。因此，我们只需在当前的有限资源下，找到一组合法的执行顺序，便能很好的避免死锁，我们称它为安全序列。而银行家算法起源于银行系统的发放贷款，和计算机操作系统的资源分配完全符合，因此可以借鉴该算法的思想，设计出一种有效的算法程序，解决该问题。1.3死锁所谓死锁： 是指两个或两个以上的进程

7、在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。 由于资源占用是互斥的，当某个进程提出申请资源后，使得有关进程在无外力协助下，永远分配不到必需的资源而无法继续运行，这就产生了一种特殊现象：死锁。在计算机系统中，涉及软件，硬件资源都可能发生死锁。例如：系统中只有一台CD-ROM驱动器和一台打印机，某一个进程占有了CD-ROM驱动器，又申请打印机；另一进程占有了打印机，还申请CD-ROM。结果，两个进程都被阻塞，永远也不能自行解除。1.4安全性全序列的的实际意义在于：系统每次进行资

8、源分配后，如果对于系统中新的资源状况，存在一个安全序列，则至少存在一条确保系统不会进入死锁的路径。按照该序列，银行家可以实施一个有效的分配过程使得所有客户得到满足，行家算法的核心在于安全序列的产生。安全序列正是一种安全的进程推进顺序。1.5算法设计思想我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已

9、占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。2.需求分析2.1基本要求（1）从键盘输入当前系统的资源信息，包括当前可用资源，每个进程对各类资源的最大需求量，每个进程当前已分配的各个资源量和每个进程尚需要的各个资源量，输出结果显示在界面上。 （2）输入进程请求，按照设计好的安全性算法进行检查，得到结果并输出整个执行过程的相关信息和最终结果（主要包括资源分配表和安全序列）。 （3）要求要有各种异常的处理，程序的可控制性和可连续性执行。包

10、括对进程的存在有无检查，请求向量的不合法检查，试分配失败后的数据恢复和重新接受进程请求等。2.2模块划分（1）分配模块输入一组资源及作业的数量，分配资源及作业的各项属性。再配置作业的资源最大需求量及已申请的资源属性。以及资源的添加、修改、删除和分配功能，此外，还有对作业的添加。(2)判定模块通过银行家算法对已经分配完毕的资源及作业的属性进行判断，判断申请是否大于需求，若大于则出错，则提示出错信息；判断申请是否大于当前资源，若大于则出错，则提示出错信息。（3）检查模块根据银行家算法进行资源分配后，检查资源分配后的系统状态是否处于安全状态之中，以避免死锁的发生。当资源分配可行时，则分配；若安全性算

11、法不能通过，则不予分配，以保证系统的安全和死锁的不发生。3.总体设计3.1算法设计(1)银行家算法的实现，需要用到以下主要数据：int Max100100=0;/各进程所需各类资源的最大需求int Avaliable100=0;/系统可用资源CString name100=""/资源的名称int Allocation100100=0;/系统已分配资源int Need100100=0;/还需要资源int Request100=0;/请求资源向量int temp100=0;/存放安全序列int Work100=0;/存放系统可提供资源int M=100;/作业的最大数为100i

12、nt N=100;/资源的最大数为100int dqzysl=3,zysl=0,worksl=0;int sign;a)资源及作业属性配置:这是对资源和作业的分配过程，在实现银行家算法之前，需有资源和作业的属性信息，才可以验证银行家算法及安全性算法，最终实现银行家算法。b)银行家算法:银行家算法是对资源分配进行判断，判断资源分配的可行性，以免导致死锁的发生，是避免死锁的重要一步。c) 安全性算法:安全性算法是对于安全性检查算法主要是根据银行家算法进行资源分配后，检查资源分配后的系统状态是否处于安全状态之中。(2) 银行家算法中用到的主要数据结构:可利用资源向量 int Availablej j

13、为资源的种类。最大需求矩阵 int Maxij i为进程的数量。 分配矩阵 int Allocationij 需求矩阵 int needij= Maxij- Allocationij 申请各类资源数量 int Request ij i进程申请j资源的数量 工作向量 int Workx int Finishy3.2模块设计银行家算法系统（1）主要模块如图3-1。信息显示模块安全性算法判断模块银行家算法判断模块资源及作业分配模块 图3-1主要模块（2）子模块如图3-2。银行家算法及安全性算法判断银行家算法及安全性算法判断配置最大资源需求量配置已申请资源删除资源增加作业分配资源修改资源添加资源添加作

14、业数量配置资源及作业属性 图3-2子模快4.详细设计4.1程序流程图YYY处理请求开始分配资源及作业银行家算法判断输出结果安全性算法判断YNNNN图4-1系统流程图4.2主要函数的核心代码（1）添加资源此处代码的实现的功能是添加资源名称，资源数量和作业数量，并且在下一步操作后提示资源是否成功添加。由于输入的资源数不止一个，输入的数据可能会出错，因此这里用到了if条件语句和for循环语句。当输入的数据不合法时，弹出对话框提示出错。void CBank123Dlg:Onaddzy() / TODO: Add your control notification handler code hereUp

15、dateData(TRUE);CString str=""； if(dqzysl>0) sign=1; for(int i=0;i<3;i+)if(namei=m_zymc && m_zymc!="") sign=0; str="该资源已存在！" if(m_zymc!="" && m_zysl!=0 && sign=1 ) Avaliable3-dqzysl=m_zysl; name3-dqzysl=m_zymc; zysl+; MessageBox(&q

16、uot;数据输入成功！若不配置资源，请配置作业数量！n系统现在共有"+conver(4-dqzysl)+"个资源。n当前输入资源名称为："+name3-dqzysl+"t数量为："+conver(Avaliable3-dqzysl),"提示", MB_OK ); dqzysl-; else MessageBox("输入数据不合法！"+str,"提示", MB_OK ); else MessageBox("错误！当前系统支持资源数目为3个！您已经分配3个了！请配置作业数量！&q

17、uot;,"提示", MB_ICONEXCLAMATION );UpdateData(FALSE);（2）银行家算法a.如果RequestjNeed or Requestj=Need,则转向步骤b；否则，认为出错，因为它所需要的资源数已超过它所宣布的最大值。 b如果RequestAvailable or Request=Available,则转向步骤c；否则，表示系统中尚无足够的资源，进程必须等待。c.系统试探把要求的资源分配给进程Pi,并修改下面数据结构中的数值： Available=Available-Requesti; Allocation=Allocation+Re

18、quest; Need=Need-Request; d.系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。for (j=0;j<zysl;j+) if(Requestj>Needij) /判断申请是否大于需求，若大于则出错 msg="进程 "+conver(i)+"申请的资源大于它需要的资源n" msg+=" 分配不合理，不予分配！n" MessageBox(msg,"提示",MB_OK); ch='n' break; else if(Requestj>Avaliabl

19、ej) /判断申请是否大于当前资源，若/大于则出错 msg="进程"+conver(i)+"申请的资源大于系统现在可利用的资源n"msg+=" 分配出错，不予分配!n"MessageBox(msg,"提示",MB_OK);ch='n' break; （3）安全性算法a.设置两个向量 工作向量Work。它表示系统可提供进程继续运行所需要的各类资源数目，执行安全算法开始时，Work=Allocation; 布尔向量Finish。它表示系统是否有足够的资源分配给进程，使之运行完成，开始时先做Finishi

20、=false，当有足够资源分配给进程时，令Finishi=true。b.从进程集合中找到一个能满足下述条件的进程： Finishi=false Need<or=Work 如找到，执行步骤c；否则，执行步骤d。 c.当进程P获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行： Work=Work+Allocation; Finishi=true; 转向步骤b。 d.如果所有进程的Finishi=true,则表示系统处于安全状态；否则，系统处于不安全状态。 CString safe()/安全性算法int i,k=0,m,apply,Finish100=0;int j;int

21、flag=0;CString str3;Work0=Avaliable0;Work1=Avaliable1;Work2=Avaliable2;for(i=0;i<worksl;i+) apply=0; for(j=0;j<zysl;j+) if (Finishi=False&&Needij<=Workj) apply+; if(apply=zysl)for(m=0;m<zysl;m+) Workm=Workm+Allocationim;/变分配数Finishi=True;tempk=i;i=-1; k+;flag+; for(i=0;i<works

22、l;i+) if(Finishi=False) CString str2="系统不安全" return str2; str3="系统是安全的！分配的序列:n"for(i=0;i<worksl;i+)/输出运行进程数组 str3=str3+conver(tempi)+"t" if(i<worksl-1) str3=str3+"->" str3+="n"return str3;（4）修改资源输入的资源可能不符合自己的需要，或者需要用到其他的资源，这时可以不必重新输入资源数量，在原有

23、的基础进行修改即可，此段代码的作用就是修改资源的名称和数量。void CBank123Dlg:Onxgzy() / TODO: Add your control notification handler code hereUpdateData(TRUE); int sign=0; if(m_zymc!="" && m_zysl!=0 ) for(int i=0;i<zysl;i+)if(namei=m_zymc) Avaliablei=m_zysl; MessageBox("资源修改成功！","提示",MB_OK

24、); sign=1; CBank123Dlg:Onfinish(); if(sign=0) MessageBox("资源不存在！","提示",MB_OK);else MessageBox("请在资源的名称和资源数量输入合法数据！","提示",MB_OK);UpdateData(FALSE);（5）删除资源资源不需要的时候应该删除，当资源名称不存在和输入的资源名称为空时，提示重新进行操作。void CBank123Dlg:Onsczy() / TODO: Add your control notification h

25、andler code hereUpdateData(TRUE);CString ming; ming=m_zymc;int i,flag=1,sign=0;if(ming!="")for(i=0;i<zysl;i+) if(ming=namei) flag=0;else sign+;if(sign=zysl) MssageBox("该资源名称不存在，请重新输入!","提示",MB_OK); if(flag=0) for(int j=i;j<zysl-1;j+) namej=namej+1; Avaliablej=Aval

26、iablej+1; zysl=zysl-1; CBank123Dlg:Onfinish(); CBank123Dlg:Onshow();else MessageBox("资源名称不能为空，请重新输入!","提示",MB_OK); UpdateData(FALSE);（6）增加资源和输出矩阵资源的数量不够时，需要再次输入，增加成功后提示下一步操作。在输入框里输入矩阵数据，然后配置资源最大需求量，可以在系统状态显示区看到系统状态信息。void CBank123Dlg:Onzjwork() UpdateData(TRUE);worksl+;int flag=2

27、;if(m_data!="") CString str=m_data;char *csInput; csInput=str.GetBuffer(str.GetLength(); /提取字符串，把单词存放在数组csInput中 char seps= "," /字符串以空格分隔符 char *token; token = strtok( csInput, seps ); char *csEditInput100; int index=0; /全局变量 while( token != NULL ) /把提取到的单词存放到数组csEditIput中 csEdit

28、Inputindex=token; /* 把单词存放在数组csEditInput中" */ index+; token = strtok( NULL, seps ); /* Get next token: */ int count=0; for(int j=0;j<zysl;j+) Maxworksl-1j=atoi(csEditInputcount); Needworksl-1j=Maxworksl-1j-Allocationworksl-1j;count+; flag=0; else MessageBox("请按配置说明在数据输入区输入相关矩阵数据！","