编程序模拟银行家算法1

1武汉理工大学华夏学院课程设计报告书课程名称：操作系统原理题目：编程序模拟银行家算法系名：信息工程系专业班级：计算机1111班姓名：学号：10210411131指导教师:苏永红2013年6月28日2课程设计任务书学生姓名：专业班级：计算机1111班指导教师：苏永红工作单位：信息工程系设计题目：编程序模拟银行家算法初始条件：Linux操作系统，GCC编译环境要求完成的主要任务：主要任务：银行家算法是避免死锁的一种重要方法，本实验要求用用c/c++语言在Linux操作系统环境下编写和调试一个简单的银行家算法程序。加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。思想：将一定数量的资金供多个用户周转使用，当用户对资金的最大申请量不超过现存资金时可接纳一个新客户，客户可以分期借款，但借款总数不能超过最大的申请量。银行家对客户的借款可以推迟支付，但是能够使客户在有限的时间内得到借款，客户得到所有的借款后能在有限的时间内归还。用银行家算法分配资源时，测试进程对资源的最大需求量，若现存资源能满足最大需求就满足当前进程的申请，否则推迟分配，这样能够保证至少有一个进程可以得到所需的全部资源而执行到结束，然后归还资源，若OS能保证所有进程在有限的时间内得到所需资源则称系统处于安全状态。设设计计报报告告撰撰写写格格式式要要求求：：1设计题目与要求2设计思想3系统结构4数据结构的说明和模块的算法流程图5使用说明书（即用户手册）：内容包含如何登录、退出、读、写等操作说明6运行结果和结果分析（其中包括实验的检查结果、程序的运行情况）7自我评价与总结8附录：程序清单，注意加注释（包括关键字、方法、变量等），在每个模块前加注释；时间安排6月24日布置课程设计任务；分配题目后，查阅资料、准备程序；6月25～6月27日上机调试程序、书写课程设计报告；6月28日提交课程设计报告及相关文档。指导教师签字：2013年6月28日系主任签字：2013年6月28日3目录1设计题目与要求.............................................................41.1设计题目...............................................................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附录：程序清单............................................................1641设计题目与要求1．1设计题目编程序模拟银行家算法1.2要求完成的任务银行家算法是避免死锁的一种重要方法，本实验要求用用c/c++语言在Linux操作系统环境下编写和调试一个简单的银行家算法程序。加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。1.3主要任务银行家算法就是对每一个请求进行检查，检查如果满足它是否会导致不安全状态。若是，则不满足该请求；否则便满足。检查状态是否安全的方法是看他是否有足够的资源满足一个距最大需求最近的客户。如果可以，则这笔投资认为是能够收回的，然后接着检查下一个距最大需求最近的客户，如此反复下去。如果所有投资最终都被收回，则该状态是安全的，最初的请求可以批准。1.4提示将一定数量的资金供多个用户周转使用，当用户对资金的最大申请量不超过现存资金时可接纳一个新客户，客户可以分期借款，但借款总数不能超过最大的申请量。银行家对客户的借款可以推迟支付，但是能够使客户在有限的时间内得到借款，客户得到所有的借款后能在有限的时间内归还。用银行家算法分配资源时，测试进程对资源的最大需求量，若现存资源能满足最大需求就满足当前进程的申请，否则推迟分配，这样能够保证至少有一个进程可以得到所需的全部资源而执行到结束，然后归还资源，若OS能保证所有进程在有限的时间内得到所需资源则称系统处于安全状态。52设计思想2．1算法思路：先对用户提出的请求进行合法性检查，即检查请求是否大于需要的，是否大于可利用的。若请求合法，则进行预分配，对分配后的状态调用安全性算法进行检查。若安全，则分配；若不安全，则拒绝申请，恢复到原来的状态，拒绝申请。2．2银行家算法：我们可以把操作系统看做是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求资源相当于客户向银行家贷款。操作系统按银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程尚需求的资源量，若是系统现存的资源可以满足它尚需求的资源量，则按当前的申请量来分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程申请的资源量是否超过了它尚需的资源量。若超过则拒绝分配，若没有超过则再测试系统尚存的资源是否满足该进程尚需的资源量，若满足即可按当前的申请量来分配，若不满足亦推迟分配。3系统结构3．1主要用到的数据结构：(1)最大需求矩阵Max[][](2)已分配矩阵Allocation[][](3)仍需求矩阵Need[][]=Max[][]-Allocation[][](4)可利用资源向量Available[](5)申请各类资源向量Request[](6)工作向量work[],Finish[]3．2程序模块：publicstaticvoidmain(String[]args)//系统的主函数publicvoidprintFrame()//初始化publicvoidprint()//打印输出publicvoidSafty()//利用安全性算法进行安全性检测publicvoidchangdata(inti)//进行资源分配voidjudge()//利用银行家算法对申请资源进行判定63．3各模块间的调用关系：主函数voidmain()要调用：printFrame()，print()，Safty()，judge()安全性检测函数Safty()要调用：print()银行家算法函数judge()要调用print()、Safty()、和judge()本身4数据结构的说明和模块的算法流程图4.1数据结构说明（1）进行初始化输入的函数（2）打印输出的函数（3）利用安全性算法进行检测的函数（4）进行资源分配的函数(5)利用行家算法进行判定的函数74.2算法流程图1.系统主要算法流程图开始清除所有进程“能运行完”标志对申请者预分配系统剩余资源数与“能运行完”标志为0的进程尚需资源数比较，找出一个系统能满足要求的进程找到检查是否有“能运行完”标志尚未设置的进程设置该进程“能运行完”标志并假设它归还全部资源有？分配不安全不能分配分配安全进行实际分配结束NNY82.银行家算法流程图93.安全性算法流程图5．使用说明该程序是用c/c++语言在Linux操作系统环境下编写和调试一个简单的银行家算法程序并在终端中运行。使用方法是,在终端输入./a.out按下enter键后显示出来，然后在编译执行程序后按照提示输入进程数量和资源数，然后程序会自动判断能否生成安全序列，使得资源得倒合理分配。结果输出后还可以继续选择其他的例如增加、删除、修改资源种类和数量的功能。按N数字键可以退出程序。按Y数字键可以退出程序。106测试结果截图：6.1开始界面图1输入./a.out6.2输出结果图2输入./a.out后的界面11图3输入进程号和资源数后的界面图4按Y键后继续执行的界面12图5按N键后的界面图6申请不合理时的界面13图7分配成功的界面147自我评价与总结第一次课程设计的时候，老师要求我们写文档，需求分析啊，系统测试啊，项目管理啊等等，那时候觉得写这么多没用的纸上的东西干什么啊，而且又什么都不明白。现在又一次的写文档，突然才明白，有些东西，写多了自然就会有经验，有收获的。在本程序设计中，我深深的感受到一个程序的总体设计是多么的重要了，以前写的小程序都是想到哪写到哪，无论怎样都能搞定，这次因为设计了图形界面，虽然说程序也不是很大，但因为当初考虑的不周全，导致最后，不得不通过删减程序功能，来达到完成任务的目的。在银行家算法这个系统之中，所采用的数据结构应是最基本的部分。银行家算法的数据结构我们采用了一维数组与二维数组来存储，比如最大需求量Max[][]、已分配资源数Allocation[][]、仍需求资源数Need[][]、以及系统可利用的资源数、申请各类资源等数组。数据结构虽然重要但却只是基础，而最主要的用以实现系统功能的应该有两个部分，一是用银行家算法来判断，二是用安全性算法来检测系统的安全性。在本程序代码中，银行家算法用judge()函数来实现。首先，输入欲申请资源的进程以及其所申请的资源数，存放在Request数组中。然后，判断进程请求的资源数是否大于其所需的资源数，若大于则报错并返回，若不大于则继续判断它是否大于系统在此时刻可利用的资源数，同样，如果大于则报错并反回，如果不大于