编程序模拟银行家算法1(共25页)

1、PAGE PAGE 4 需求分析 5武汉理工大学华夏(Huxi)学院课程设计报告书课程名称： 操作系统(co zu x tn)原理 题 目： 编程序模拟(mn)银行家算法 系 名： 信 息 工 程 系 专业班级： 计算机1111班 姓 名： 学 号： 10210411131 指导教师: 苏 永 红 2013 年 6 月 28 日课程设计任务书学生(xu sheng)姓名： 专业(zhuny)班级： 计算机1111班 指导(zhdo)教师： 苏永红 工作单位： 信息工程系 设计题目：编程序模拟银行家算法初始条件：Linux操作系统，GCC编译环境要求完成的主要任务：主要任务：银行家算法是避免死锁

2、的一种重要方法，本实验要求用用c/c+语言在Linux操作系统环境下编写和调试一个简单的银行家算法程序。加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。思想：将一定数量的资金供多个用户周转使用，当用户对资金的最大申请量不超过现存资金时可接纳一个新客户，客户可以分期借款，但借款总数不能超过最大的申请量。银行家对客户的借款可以推迟支付，但是能够使客户在有限的时间内得到借款，客户得到所有的借款后能在有限的时间内归还。用银行家算法分配资源时，测试进程对资源的最大需求量，若现存资源能满足最大需求就满足当前进程的申请，否则推迟分配，这样能够保证至少有一个进程可以得到所需的全

3、部资源而执行到结束，然后归还资源，若OS能保证所有进程在有限的时间内得到所需资源则称系统处于安全状态。设计报告撰写格式要求：1设计题目与要求 2 设计思想 3系统结构 4 数据结构的说明和模块的算法流程图 5 使用说明书（即用户手册）：内容包含如何登录、退出、读、写等操作说明6 运行结果和结果分析（其中包括实验的检查结果、程序的运行情况）7 自我评价与总结 8 附录：程序清单，注意加注释（包括关键字、方法、变量等），在每个模块前加注释； 时间安排 6月24日 布置课程设计任务；分配题目后，查阅资料、 准备程序； 6月 256月27 日上机调试程序、书写课程设计报告；6月28 日 提交课程设计报

4、告及相关文档。指 导 教 师 签 字： 2013年 6月 28日系 主 任 签 字： 2013年 6月 28日目录(ml)1设计(shj)题目与要求41.1设计(shj)题目41.2要求完成的任务41.3主要任务41.4提示42设计思路52.1算法思路52.2银行家算法53系统结构53.1主要用到的数据结构53.2程序模块53.3各模块间的调用关系64数据结构的说明和模块的算法流程图64.1数据结构说明64.1算法流程图75使用说明96测试结果截图106.1开始界面106.2输出界面107自我评价与总结148参考文献159附录：程序清单16PAGE 151设计(shj)题目与要求11设计(sh

5、j)题目编程序模拟(mn)银行家算法1.2要求完成的任务银行家算法是避免死锁的一种重要方法，本实验要求用用c/c+语言在Linux操作系统环境下编写和调试一个简单的银行家算法程序。加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。1.3主要任务银行家算法就是对每一个请求进行检查，检查如果满足它是否会导致不安全状态。若是，则不满足该请求；否则便满足。检查状态是否安全的方法是看他是否有足够的资源满足一个距最大需求最近的客户。如果可以，则这笔投资认为是能够收回的，然后接着检查下一个距最大需求最近的客户，如此反复下去。如果所有投资最终都被收回，则该状态是安全的，最初的请求

6、可以批准。1.4提示将一定数量的资金供多个用户周转使用，当用户对资金的最大申请量不超过现存资金时可接纳一个新客户，客户可以分期借款，但借款总数不能超过最大的申请量。银行家对客户的借款可以推迟支付，但是能够使客户在有限的时间内得到借款，客户得到所有的借款后能在有限的时间内归还。用银行家算法分配资源时，测试进程对资源的最大需求量，若现存资源能满足最大需求就满足当前进程的申请，否则推迟分配，这样能够保证至少有一个进程可以得到所需的全部资源而执行到结束，然后归还资源，若OS能保证所有进程在有限的时间内得到所需资源则称系统处于安全状态。2 设计(shj)思想21算法(sun f)思路：先对用户提出的请求

7、进行合法性检查，即检查请求是否大于需要的，是否大于可利用的。若请求合法，则进行预分配，对分配后的状态调用安全性算法进行检查。若安全，则分配；若不安全，则拒绝申请，恢复(huf)到原来的状态，拒绝申请。22银行家算法 ：我们可以把操作系统看做是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求资源相当于客户向银行家贷款。操作系统按银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程尚需求的资源量，若是系统现存的资源可以满足它尚需求的资源量，则按当前的申请量来分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程申请的资源量是否超过了它尚需的资源量。若

8、超过则拒绝分配，若没有超过则再测试系统尚存的资源是否满足该进程尚需的资源量，若满足即可按当前的申请量来分配，若不满足亦推迟分配。3 系统结构31主要用到的数据结构：最大需求矩阵Max已分配矩阵Allocation仍需求矩阵Need=Max-Allocation可利用资源向量Available申请各类资源向量Request工作向量 work , Finish32程序模块： public static void main(String args) /系统的主函数public void printFrame() /初始化public void print() /打印输出public void Saf

9、ty() /利用(lyng)安全性算法进行安全性检测public void changdata(int i) /进行(jnxng)资源分配 void judge() /利用银行家算法对申请资源(zyun)进行判定33各模块间的调用关系：主函数void main()要调用： printFrame()，print()，Safty()，judge()安全性检测函数Safty()要调用：print()银行家算法函数judge()要调用print()、Safty()、和judge()本身4 数据结构的说明和模块的算法流程图4.1数据结构说明（1）进行初始化输入的函数（2）打印输出的函数（3）利用安全性算

10、法进行检测的函数（4）进行资源分配的函数(5)利用行家算法进行判定的函数4.2算法(sun f)流程图 1.系统主要(zhyo)算法流程图YNN结束分配安全进行实际分配分配不安全不能分配有？设置该进程“能运行完”标志并假设它归还全部资源找到系统剩余资源数与“能运行完”标志为0的进程尚需资源数比较，找出一个系统能满足要求的进程对申请者预分配清除所有进程“能运行完”标志开始检查是否有“能运行完”标志尚未设置的进程 2.银行家算法(sun f)流程图3.安全性算法(sun f)流程图5使用(shyng)说明 该程序(chngx)是用c/c+语言在Linux操作系统环境下编写和调试(dio sh)一个

11、简单的银行家算法程序并在终端(zhn dun)中运行。使用方法是,在终端输入./a.out按下enter键后显示出来，然后在编译执行程序后按照提示输入进程数量和资源数，然后程序会自动判断能否生成安全序列，使得资源得倒合理分配。结果输出后还可以继续选择其他的例如增加、删除、修改资源种类和数量的功能。按N数字键可以退出程序。按Y数字键可以退出程序。6测试结果截图：6.1开始界面 图1 输入./a.out 6.2输出结果图2输入(shr)./a.out后的界面图3 输入(shr)进程号和资源数后的界面 图4 按Y键后继续执行的界面(jimin)图5 按N键后的界面(jimin)图6 申请(shnqn

12、g)不合理时的界面图7分配(fnpi)成功的界面PAGE 267 自我(zw)评价与总结第一次课程设计的时候，老师要求我们写文档，需求分析啊，系统测试啊，项目管理啊等等，那时候觉得写这么多没用的纸上的东西干什么啊，而且又什么都不明白。现在又一次的写文档，突然才明白，有些东西，写多了自然就会有经验(jngyn)，有收获的。在本程序设计中，我深深的感受到一个程序的总体设计是多么的重要了，以前写的小程序都是想到哪写到哪，无论怎样都能搞定，这次因为设计了图形界面，虽然说程序也不是很大，但因为当初考虑的不周全，导致最后，不得不通过删减程序功能，来达到完成任务的目的。在银行家算法这个系统之中，所采用的数据

13、结构应是最基本的部分。银行家算法的数据结构我们采用了一维数组与二维数组来存储(cn ch)，比如最大需求量Max、已分配资源数Allocation、仍需求资源数Need、以及系统可利用的资源数、申请各类资源等数组。数据结构虽然重要但却只是基础，而最主要的用以实现系统功能的应该有两个部分，一是用银行家算法来判断，二是用安全性算法来检测系统的安全性。在本程序代码中，银行家算法用judge( )函数来实现。首先，输入欲申请资源的进程以及其所申请的资源数，存放在Request数组中。然后，判断进程请求的资源数是否大于其所需的资源数，若大于则报错并返回，若不大于则继续判断它是否大于系统在此时刻可利用的资

14、源数，同样，如果大于则报错并反回，如果不大于则调用changedata( )函数来进行预分配，之后再调用安全型算法safty检查。最后，无论此次分配是否成功，我们都可以选择继续分配或者退出系统。安全性检测我们是用safty( )函数来实现的。首先，Finish为布尔型，默认是False，即该进程未完成。而Work即该系统中可以用来工作的资源数最开始为系统最初可以用的资源数。然后，我们从第一个进程开始判断该进程未完成且其所需求的资源量不大于该系统中可以用来工作的资源量这个条件是否成立，即Finish=False且Need=Work是否成立。成立的话则将当前在工作的资源量与该进程已分配的资源量相加

15、，存放于当前可用来工作的资源量当中，即Work=Work+Allocation，并将Finish的值改为True。否则便将此进程的优先级减一，排在队位，然后开始往后循环。待所有的进程循环完毕，我们再次判断是否还存在进程的Finish=False，如果仍存在，则说明系统没有安全序列，处于不安全状态，不可以进行分配；否则，系统处于安全状态，将预分配变为实际分配，求出安全序列并且将实际分配后的资源分配情况打印输出。除此之外，在程序当中，我们也得强调一下对输入的合法性的判断。比如，我们输入的欲申请资源的进程号没有在系统已存在的进程当中，或者进程号定义为整型，但是却错输成字母等情况，我们需要对这些情况进

16、行(jnxng)判断，让程序报错返回而并非因错误而中断。这样的情况处理起来比较麻烦，相当于对每次输入针对各种不同的情况都得做判断。我也没有涵盖全部的输入，仅仅只是对输入的进程号不在已存在进程当中、以及输入的操作选择不存在两种情况分别作了判断，并且针对第二种情况设定了五次输入错误的话(dehu)系统关闭的功能。而因为对于某些比如(br)进程号本来设定就是整型，因此对输入的是字母的判别因比较复杂而未能加上。总之，银行家算法是避免死锁的主要方法，其思路在很多方面都非常值得我们来学习借鉴。8.参考文献汤小丹，梁红兵，哲凤屏，汤子瀛.计算机操作系统. 西安：西安电子科技大学出版社，2007.严蔚敏，吴伟

17、民.数据结构. 北京：清华大学出版社，2006.赵莉，杨国梁，孙喁喁，徐飞. Java程序设计教程. 西安：西安科技大学出版社，2009. HYPERLINK /view/32d7df73f242336c1eb95efa.html /view/32d7df73f242336c1eb95efa.html (百度文库：银行家算法报告) HYPERLINK /default.asp?id=204 /default.asp?id=204 （志文工作室： 银行家算法模拟实现）9. 附录(fl)：程序清单#include string.h #include #include #define M 7 #de

18、fine N 5 #define FALSE 0 #define TRUE 1 /*M个进程(jnchng)对N类资源最大资源需求量*/ int MAXMN=9,7,5,5,4,4,11,0,4,4,4,4,6,5,5; /*系统(xtng)可用资源数*/ int AVAILABLEN=12,7,9; /*M个进程对N类资源最大资源需求量*/ int ALLOCATIONMN=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0; /*M个进程已经得到N类资源的资源量 */ int NEEDMN=9,7,5,5,4,4,11,0,4,4,4,4,6,5,5; /*M个进程还需要N类资源的

19、资源量*/ int RequestN=0,0,0; int main() int i=0,j=0; char flag=Y; void showdata(); void changdata(int); void rstordata(int); int chkerr(int); showdata(); while(flag=Y|flag=y) i=-1; while(i=M) printf(请您输入想要申请资源(zyun)的进程号（从0至); printf(%d,M-1); printf(，请您重新(chngxn)输入!）:); scanf(%d,&i); if(i=M)printf(不好意思，

20、你所输入的进程号不存在(cnzi)，请重新输入!n); printf(请您输入进程号); printf(%d,i); printf(申请的资源数n); for (j=0;jNEEDij) printf(进程(jnchng); printf(%d,i); printf(申请的资源(zyun)数大于进程); printf(%d,i); printf(如果(rgu)还需要); printf(%d,j); printf(类资源的资源量!您所提出的申请的不合理，出现错误!请您重新选择!n); /*printf(您所提出的申请的不合理，出现错误!请您重新选择!n);*/ flag=N; break; el

21、se if(RequestjAVAILABLEj) printf(进程); printf(%d,i); printf(申请的资源数大于系统可用); printf(%d,j); printf(类资源的资源量!您所提出的申请不合理，出现错误!请您重新选择!n); /*printf(您所提出的申请不合理，出现错误!请您重新选择!n);*/ flag=N; break; if(flag=Y|flag=y) changdata(i); if(chkerr(i) rstordata(i); showdata(); else showdata(); else showdata(); printf(n); p

22、rintf(请问是否继续(jx)银行家算法演示,按Y或y键继续,按N或n键退出演示: ); scanf(%c,&flag); void showdata() int i,j; printf(注意！系统(xtng)可用的资源数为:n); printf( ); for (j=0;jN;j+) printf( 资源(zyun); printf(%d,j); printf(:); printf(%d,AVAILABLEj); /*printf(n);*/ /* coutendl; / cout各进程(jnchng)资源的最大需求量:endlendl; / for (i=0;iM;i+) / / cou

23、t进程(jnchng)i:; / for (j=0;jN;j+)cout 资源(zyun)j: MAXij; / coutendl; */ printf(n); printf(各进程还需要的资源量:n); for (i=0;iM;i+) printf( 进程); printf(%d,i); printf(:); for (j=0;jN;j+) printf(资源); printf(%d,j); printf(:); printf(%d,NEEDij); /*printf(n);*/ printf(n); printf(各进程已经得到的资源量: n); for (i=0;iM;i+) print

24、f( 进程(jnchng); printf(%d,i); /*printf(:n);*/ for (j=0;jN;j+) printf(资源(zyun); printf(%d,j); printf(:); printf(%d,ALLOCATIONij); /*printf(n);*/ printf(n); void changdata(int k) int j; for (j=0;jN;j+) AVAILABLEj=AVAILABLEj-Requestj; ALLOCATIONkj=ALLOCATIONkj+Requestj; NEEDkj=NEEDkj-Requestj; ; void rstordata(int k) int j; for (j=0;jN;j+) AVAILABLEj=AVAILABLEj+Requestj; ALLOCATIONkj=ALLOCATIONkj-Requestj; NEEDkj=NEEDkj+Requestj; int chkerr(int s) int WORK,FINISHM,tempM; int i,j,k=0; for(i=0;iM;i+)FINISHi=FALSE; for(j=0;jN;j+) WORK=AVAILABLEj; i=s; whi