银行家算法课程设计.doc

武汉工程大学 计算机科学与工程学院综合设计报告设计名称： 操作系统综合设计 设计题目： 进程死锁 学生学号： 专业班级： 学生姓名： 学生成绩： 指导教师（职称）： 张立（讲师） 完成时间： 15年6月8日 至 15年6 月12日 武汉工程大学计算机科学与工程学院 制说明：1、报告中的第一、二、三项由指导教师在综合设计开始前填写并发给每个学生；四、五两项（中英文摘要）由学生在完成综合设计后填写。2、学生成绩由指导教师根据学生的设计情况给出各项分值及总评成绩。3、指导教师评语一栏由指导教师就学生在整个综合设计期间的表现、设计完成情况、报告的质量及答辩等方面，给出客观、全面的评价。4、所有学生必须参加综合设计的答辩环节。凡不参加答辩者，其成绩一律按不及格处理。答辩小组成员应由2人及以上教师组成。5、报告正文字数一般应不少于5000字，也可由指导教师根据本门综合设计的情况另行规定。6、平时表现成绩低于6分的学生，其综合设计成绩按不及格处理。7、此表格式为武汉工程大学计算机科学与工程学院提供的基本格式（适用于学院各类综合设计），各教研室可根据本门综合设计的特点及内容做适当的调整，并上报学院批准。答辩记录表学生姓名： 学号： 班级：2 答辩地点： 计算机大楼8号机房 答辩内容记录：答辩成绩合计分值各项分值评分标准实际得分合计得分备注2510在规定时间内能就所设计的内容进行阐述，言简意明，重点突出，论点正确，条理清晰。15在规定时间内能准确、完整、流利地回答教师所提出的问题。答辩小组成员（签字）： 2015 年 6 月 12 日成绩评定 类别合计分值各项分值评分标准实际得分合计得分备注平时表现1010遵守学习纪律，表现良好，积极完成综合设计任务，无旷课、迟到、早退等情况。设计完成情况3020按照要求完成设计内容，方案合理，功能完善，设计工作量饱满，能运用专业知识和技能去发现与解决实际问题。10在设计过程中展现出了较强的学习能力、动手实践能力、团队协作能力和创新意识。报告质量3510报告格式规范，表述清晰，章节内容组织恰当。符号统一，图表完备，符合规范要求。参考文献数量在5篇以上，格式及引用符合要求。15报告内容翔实，结构严谨合理。课题背景介绍清楚，综述充分。设计与实现等主要过程完整，论述具体透彻。能运用所学专业知识对问题加以分析和求解。无抄袭现象。10设计报告对整个设计过程进行了全面总结，体现了收获，得出了有价值的结论或结果。答辩情况2510在规定时间内能就所设计的内容进行阐述，言简意明，重点突出，论点正确，条理清晰。15在规定时间内能准确、完整、流利地回答教师所提出的问题。总评成绩指导教师评语指导教师： （签字） 日期： 2015 年 6 月 12 日一、综合设计目的、条件、任务和内容要求：操作系统在计算机科学中是一门核心专业基础课，涉及较多硬件和软件知识。在计算机软、硬件课程的设置上，它起着承上启下的作用。其特点是概念多、较抽象、涉及的知识面广。操作系统综合设计是计算机科学与技术专业学生的一门实践课程，是学习完操作系统课程后的课程设计，本课程的教学目的是，通过学习，使学生了解计算机操作系统的发展特点；理解操作系统的基本概念、组成和各部分的功能；掌握计算机操作系统设计的基本原理和方法；理解常见操作系统的结构原理并能熟练使用。进程死锁课题，要求学生熟悉windows中的线程及进程的创建，掌握利用windows中的同步机制实现线程同步，掌握用银行家算法进行死锁的避免避免亮的。培养学生的抽象思维能力、逻辑推理能力和形式化思维方法，增强分析问题和解决问题的能力。设计任务和内容要求：利用银行家算法实现进程的死锁避免。二、进度安排：第1周(6.8-6.8) ：学生熟悉课题的任务和要求，查阅相关文献和资料，并做好编码准备第1周(6.8-6.10) ：程序编码、调试第1周(6.10-6.11) ：程序编码、调试和测试，书写报告 第1周(6.12) ：答辩、检查、验收、递交设计报告三、应收集资料及主要参考文献：应收集的资料：面向对象程序设计思想和方法高级程序设计语言参考手册操作系统、软件工程方面参考书籍主要参考文献：1 汤子瀛，哲凤屏，汤小丹计算机操作系统m西安电子科技大学出版社，2007 2 谭浩强c语言程序设计m清华大学出版社，20103 苏仕华数据结构课程设计m机械工业出版社，2005四、摘要：银行家算法是一个避免死锁的著名算法，是由艾兹格迪杰斯特拉在1965年为t.h.e系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。在银行家算法执行过程中，首先判断申请资源的进程所申请的资源数目是否合法，若是合法的，则可以为其进行试分配，再利用安全性算法求出安全序列，如果存在安全序列，则说明可以给申请资源的进程分配资源，分配成功，继续为其它进程服务。如果找不到安全序列，则说明为该进程分配资源后系统会进入不安全状态，所以不能为该进程分配资源，使该进程进入阻塞状态。若申请资源的进程申请的资源数目不合法，则不需要进行试分配，直接使其进入阻塞状态，处理其他申请资源的进程。关键词：计算机操作系统；安全性算法；银行家算法 五、abstract：banker algorithm is a famous algorithm to avoid deadlock, by ezra pound, dijkstra in 1965 to t.h.e system design of a kind of avoid deadlock algorithm. it is based on bank lending system allocation strategy, determine and ensure the safe operation of the system. in the execution of a banker algorithm, first determine the number to apply for the application of the process of resources is legal, if it is legal, you can try to carry out distribution, recycling security algorithm and security sequence, if there is a safe sequence, then to apply for the process of resource allocation of resources, distribution of success, to continue to serve other processes. if you cannot find security sequence, after the allocation of resources for the process system will enter the unsafe condition, so cant for the process allocation of resources, blocking the process into the state. if applying for the process of resource for the number of resources, illegal trial distribution is not required, and make it into the blocked state directly, to handle the applications for other resources.keywords：banker algorithm；os；security algorithm目录摘 要 i第一章 课题概述11.1 课题背景11.2 课题意义1第二章 设计简介及设计方案论述 22.1 设计描述22.2 设计思想22.3 设计要求22.4 设计流程图 3第三章 详细设计43.1 银行家算法的算法思想43.2 安全性检查算法 43.3算法整体设计与调用 5第四章 设计结果及分析 64.1 程序输入部分 64.3 资源分配成功结果输出74.4 资源分配失败结果输出8总 结8致 谢9参考文献10附录：11武汉工程大学计算机科学与工程学院 综合设计报告摘 要银行家算法是一个避免死锁的著名算法，是由艾兹格迪杰斯特拉在1965年为t.h.e系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。在银行家算法执行过程中，首先判断申请资源的进程所申请的资源数目是否合法，若是合法的，则可以为其进行试分配，再利用安全性算法求出安全序列，如果存在安全序列，则说明可以给申请资源的进程分配资源，分配成功，继续为其它进程服务。如果找不到安全序列，则说明为该进程分配资源后系统会进入不安全状态，所以不能为该进程分配资源，使该进程进入阻塞状态。若申请资源的进程申请的资源数目不合法，则不需要进行试分配，直接使其进入阻塞状态，处理其他申请资源的进程。关键词：计算机操作系统；安全性算法；银行家算法 abstractbanker algorithm is a famous algorithm to avoid deadlock, by ezra pound, dijkstra in 1965 to t.h.e system design of a kind of avoid deadlock algorithm. it is based on bank lending system allocation strategy, determine and ensure the safe operation of the system. in the execution of a banker algorithm, first determine the number to apply for the application of the process of resources is legal, if it is legal, you can try to carry out distribution, recycling security algorithm and security sequence, if there is a safe sequence, then to apply for the process of resource allocation of resources, distribution of success, to continue to serve other processes. if you cannot find security sequence, after the allocation of resources for the process system will enter the unsafe condition, so cant for the process allocation of resources, blocking the process into the state. if applying for the process of resource for the number of resources, illegal trial distribution is not required, and make it into the blocked state directly, to handle the applications for other resources.keywords：banker algorithm；os；security algorithm- 17 -第一章 课题概述1.1 课题背景在预防死锁的各种算法中，总的来说，都是施加了较强的限制条件，从而使实现简单，但却严重地损害了系统的性能。在避免死锁的算法中，施加的条件较较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统处于安全状态，便可避免死锁的发生。最具有代表性的避免死锁的算法是dijkstra的银行家算法。这是因为该算法能用于银行系统现金贷款的发放而得名，在这一次的课程设计中就要对银行家算法从分析到实现，整体做一个详细的描述。1.2 课题意义从课程设计上讲，该课程设计可以提高自己的分析问题，解决问题和动手能力，并对银行家算法有更深刻的理解。从银行家算法上本身讲，通过算法可以判断系统的安全性，对申请资源的进程进行限制，从而避免系统进入死锁状态。第二章 设计简介及设计方案论述2.1 设计描述当系统在进行资源管理时，如果对进城申请的资源分配不当，可能会使系统进入死锁状态，因而后面到来的进程也无法顺利执行。银行家算法中，要对当前申请资源的进程申请资源的数目进行判断，如果可以试分配，则试求出一个安全序列，如果可以求出，则说明给这个进程分配资源后系统不会进入不安全状态，将该进程申请的资源分配给他，若求不出安全序列，则说明将资源分配给该进程后系统会进入不安全状态，所以就使该进程进入阻塞状态，等待以后可以分配资源时再执行该进程，然后系统继续服务其它进程。通过这样一个过程，可以有效避免系统进入死锁状态。2.2 设计思想在避免死锁的算法中，允许进程动态地申请资源，系统在进行资源分配之前，先计算资源分配的安全性。若此次分配不会使系统进入不安全状态，便将资源分配给该进程否则进程等待。所谓安全状态是指系统能按某种顺序如，就这样来为每个进程分配资源，直至最大需求。使每个进程都可以顺序地执行完毕。若系统不存在这样一个安全序列，那么系统此时会进入不安全状态。虽然并非所有的不安全状态都会产生死锁状态，但当系统进入不安全状态后，便可能进而进入死锁状态；反之，只要系统处于安全状态，系统便可避免进入死锁状态。因此，避免死锁的实质在于，如何使系统不进入不安全状态，银行家算法就是用来判断某种情况会不会进入不安全状态。2.3 设计要求（1）对各个进程的进程名，最大需求资源，已分配资源，系统可用资源等进行的输入。（2）对申请资源的进程要有合法性判断（如进程名，申请资源数等）。（3）若有进程申请资源，首先要对它申请的资源数进行判断。（4）在上面判断合法的前提下进行试分配，利用银行家算法求出安全序列。如果可以求出安全序列，则为该进程分配资源，否则使它进入阻塞状态。2.4 设计流程图开始初始化资源矩阵检查初始状态是否安全按用户需求为进程分配资源检查现状态是否安全为该进程分配资源退出？结束不安全安全不安全否安全 是图2.4 程序总体流程图第三章 详细设计3.1 银行家算法的算法思想先对用户提出的请求进行合法性检查，即检查请求的是不大于需要的，是否不大于可利用的。若请求合法，则进行试分配。最后对试分配后的状态调用安全性检查算法进行安全性检查。若安全，则分配，否则，不分配，恢复原来状态，拒绝申请。当进程i发出申请资源请求： (1)调用分配检查函数检查申请量是否不大于需求量再检查检查申请量是否小于系统中的可利用资源数量：若条件不符重新输入，不允许申请大于需求量。(2)若以上条件都满足，则系统试探着将资源分配给申请的进程，并修改available，allocation和need中的数值。3.2 安全性检查算法首先设置变量：工作数组work，它表示系统可提供给进程继续运行所需的各类资源数目，在执行安全性算法开始时，work= available。finish，它表示系统是否有足够的资源分配给每个进程，使之运行完成。开始时先做finishi=0；当有足够的资源分配给进程时，再令finishi=1。然后再在进程中查找符合以下条件的进程：条件1：finishi=0；条件2：needij=workj若找到，则执行步骤(3)否则，执行步骤(4)。当进程获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：workj= workj+ allocationij；finishi=1；最后循环检查是否所有的finishi=1都满足，如果是，则返回1表示系统处于安全状态，否则，返回0表示系统处于不安全状态。3.3算法整体设计与调用主函数void main()，首先输入每个进程信息，然后判断是否有进程申请资源，若有，则调用int check_distribution(int* p,int k)函数判断是否可以进行试分配，如果满足试分配条件，调用int check_safe()函数求安全序列，如果可以求出安全序列，则说明分配后系统不会进入不安全状态，正式将资源分配给申请资源的进程，最后用void print()函数输出分配资源后每个进程的信息。如果求不出安全序列，说明分配后系统会处于不安全状态，则不能将资源分配给该进程，让其等待，系统恢复原始状态。如果申请资源的数量不满足条件，则让该进程等待。继续判断其他申请资源的进程。其他函数：（1）int check_distribution(int* p,int k)：这个函数用来判断是否可以进行试分配，如果函数结果返回1，说明可以进行试分配，如果函数返回0，说明申请资源的进程申请的资源数目不满足request =need或request =available条件，不能为该进程进行试分配。（2）int check_safe()：这个函数用来求安全序列，首先初始化work0i= availablei，然后循环找满足条件 finishi=0 & needi0 = workk0的进程，k表示最近执行的进程的进程号，找到后将进程i 加入sequence数组，再将finishi=1，表示进程可以顺利执行则workkj=workk-1j+allocationij，k表示同上。再继续找下一个满足条件的进程。如果单循环结束时每个进程的finishi都等于1，则说明可以找到安全序列，返回1，如果不是每个finishi都等于1，则说明找不到一个安全序列，返回0( 3 ) void print()：这个函数用来输出进程信息，按表格形式输出，并且输出顺序和安全序列相同，便于查看进程执行的执行过程，并且在执行过程中各矩阵信息变化也很容易跟踪查看。第四章 设计结果及分析4.1 程序输入部分图4.1 程序输入部分如图4.1所示，输入进程名向量processneman，输入系统现有各类资源数量availablem向量，输入每个进程对各类资源的最大需求数maxnm矩阵，输入系统给每个进程已分配的各类资源数allocationnm矩阵。4.2 输出资源分配矩阵图4.2 输出资源分配矩阵进程信息输入完成后，初始状态各进程信息输出如图4.2所示。4.3 资源分配成功结果输出图4.3 资源分配成功结果如果申请资源的进程申请的资源数目满足试分配条件，则再用check_safe()函数来求试分配后的安全序列，如果可以求出安全序列，则说明这次分配不会使系统进入不安全状态，正式将资源分配给该进程，修改系统资源信息。如果求不出安全序列，说明这次分配后系统会进入不安全状态，不能给该进程分配资源，系统恢复初始状态，打印出提示信息，执行结果如图4.3所示。4.4 资源分配失败结果输出 图4.4 资源分配失败结果由图4.1、图4.2、图4.3、图4.4运行结果举例可以看出本系统界面简洁明了大方，而且在人机交互上化繁为简。结果输出准确无误，自然得体，让用户一目了然。总 结课程设计是每一个大学生在大学生涯中都不可或缺的，它使我们在实践中了巩固了所学的知识、在实践中锻炼自己的动手能力；实习又是对每一位大学生所学专业知识的一种拓展手段，它让我们学到了很多在课堂上根本就学不到的知识,不仅开阔了自己的视野，增长了自己的见识，也为我们以后进一步走向社会打下了坚实的基础，是我们走向以后走向工作岗位的奠基石。在这一个星期的课程设计的时间中，我得到了很多收获，这是一次难得的经历。我的编程技巧和能力在这一次的设计中进步了很多。致 谢在课程设计中，要特别感谢张老师给予我这次设计的机会，并且在他的悉心的监督和指导下，本次课程设计才能圆满完成。同时也要感谢各位同学们的指导，和同学们的讨论和交流是完成我这次课程设计不可忽视的一部分。还要感谢给我提供良好实验环境的学校。如果没有老师们和同学们还有学校的支持与帮助，本次课程设计不能这么顺利的完成。再次感谢老师和同学的帮助，使我能够圆满完成这次课程设计，为我以后的专业学习打下了良好的基础。参考文献1 汤子瀛，哲凤屏，汤小丹计算机操作系统m西安电子科技大学出版社，2007 2 谭浩强c语言程序设计m清华大学出版社，20103 苏仕华数据结构课程设计m机械工业出版社，2005附录：#include#include #define n 5 /进程个数#define m 3 /资源种类数void print();int check_safe();int check_distribution(int* p, int k);char process_namen; /进程名int requestm; /请求数组int finishn; /标记某一个进程是否可以执行int worknm; /初始为available,随寻找安全序列而变化，防止安全序列未找到而丢了初始状态的值int availablem; /资源清单系统中现有各资源空闲个数int work_allocationnm;int maxnm; /最大需求矩阵每个进程对各类资源的最大需求数int allocationnm; /分配矩阵系统给每个进程已分配的各类资源数int neednm; /需求矩阵每个进程还需要每种资源的个数int sequencen = 0 ; /存放安全序列号void main()int i = 0, j = 0, k = 0; /记录申请资源的进程的序列号int flag = 0; /标记输入的进程名是否存在int safe = 0; /标志系统是否出于安全状态,0表示不安全，1表示安全int distribution = 0; /标志是否可以进行试分配0表示可以，1表示不可以char flag1; /标记是否有进程申请资源 char name; /要请求资源的进程名printf(-n);printf(* 银行家算法 *n);printf(-nn);printf(-请输入各进程的进程名:n); /进程名连续输入for (i = 0; i请输入现有各资源空闲个数:n);for (i = 0; i请分别输入每个进程对各类资源的最大需求数:n);for (i = 0; in; i+)for (j = 0; j请分别输入系统给每个进程已分配的各类资源数n);for (i = 0; in; i+)for (j = 0; jm; j+)scanf(%d, &allocationij);/计算每个进程还需要每种资源的数for (i = 0; in; i+)for (j = 0; jm; j+)needij = maxij - allocationij;printf(n初始化终了。n);printf(-nnn);for (i = 0; in; i+)sequencei = i;/输出界面print();/检查初始状态是否安全safe = check_safe();if (0 = safe)printf(系统现处于不安状态，不能为进程分配资源，进入死锁状态。n);exit(0);else if (1 = safe)printf(系统处于安全状态，可以为进程分配资源。n);while (1)safe = 0;getchar();printf(是否有进程请求系统资源.? (y/n) n);flag1 = getchar();if (y = flag1 | y = flag1)printf(请输入进程名:);getchar();while (1)scanf(%c, &name);for (i = 0; in; i+) /检查进程名输入是否正确if (name = process_namei)flag = 1; /输入的进程名存在k = i;break;/找到申请资源的进程序列号跳出getchar();/将在此之前的一个回车接收了，不然会影响输入if (flag != 1)/进程名输入不合法printf(你输入的进程不存在，请重新输入:);continue;elsebreak;/进程名输入合法，则执行下面操作else if (n = flag1 | n = flag1)printf(进程执行完毕，退出系统。n);break;else if (n != flag1 & y != flag1 & n != flag1 & y != flag1)printf(你的输入有误，请重新输入: );continue;printf(请输入该进程请求各类资源的数量n);for (i = 0; im; i+)scanf(%d, &requesti);distribution = check_distribution(request, k); /检查是否可以试分配if (1 = distribution) safe = check_safe(); /可以试分配，则求安全序列if (1 = safe) /试分配成功printf(试分配成功，可以为该进程分配资源。n); /是否给申请资源的进程分配资源for (i = 0; im; i+)allocationki = allocationki + requesti; /为进程分配资源后修改该进程的有关资源数needki = needki - requesti;printf(分配后各资源数量如下:n);print();printf(分配成功!n);printf(系统剩余资源数各为: );for (i = 0; im; i+)printf(%d , availablei);printf(n);continue;else /试分配失败printf(试分配失败，有可能进入死锁状态，请等待。n);/未求出安全序列continue;else /试分配失败printf(该进程申请的资源太多，无法分配，请等待。n);continue;void print()int i, j;printf( 资源 work needtallocationtwork+allocationt finishn);printf( 进程名 a b c