编程序模拟银行家算法

1、武汉理工大学华夏学院课程设计报告书课程名称：操作系统原理目:系 名: 专业班级: 姓 名: 学 号: 指导教师:编程序模拟银行家算法信息工程系软件1121钟伟10212812120苏永红2014年6月13日武汉理工大学华夏学院信息工程系课程设计任务书课程名称：操作系统原理课程设计指导教师：苏永红班级名称：软件1121开课系、教研室：软件与信息安全一、课程设计目的与任务操作系统课程设讣是操作系统原理课程的后续实践课程，旨在通过一周的实践训练， 加深学生对理论课程中操作系统概念，原理和方法的理解，加强学生综合运用操作系统原理、 Linux系统、C语言程序设计技术进行实际问题处理的能力，进一步提髙学

2、生进行分析问题 和解决问题的能力，包含系统分析、系统设计、系统实现和系统测试的能力。学生将在指导老师的指导下，完成从需求分析，系统设计，编码到测试的全过程。二、课程设计的内容与基本要求1、课程设计题目编程序模拟银行家算法2、课程设计内容本课程设计要求在Linux操作系统，GCC编译环境下开发。银行家算法是避免死锁的一种重要方法，本实验要求用用c/c+语言在Linux操作系统 环境下编写和调试一个简单的银行家算法程序。加深了解有关资源申请、避免死锁等概念， 并体会和了解死锁和避免死锁的具体实施方法。思想：将一泄数疑的资金供多个用户周转使用，当用户对资金的最大申请量不超过现存 资金时可接纳一个新客

3、户，客户可以分期借款，但借款总数不能超过最大的申请量。银行家 对客户的借款可以推迟支付，但是能够使客户在有限的时间内得到借款，客户得到所有的借 款后能在有限的时间内归还。用银行家算法分配资源时，测试进程对资源的最大需求量，若 现存资源能满足最大需求就满足当前进程的申请，否则推迟分配，这样能够保证至少有一个 进程可以得到所需的全部资源而执行到结束，然后归还资源，若OS能保证所有进程在有限 的时间内得到所需资源则称系统处于安全状态。3、设计报告撰写格式要求：1设计题目与要求 2设计思想3系统结构 4数据结构的说明和模块的算法流程图5使用说明书（即用戸手册）：内容包含如何登录、退岀、读、写等操作说明

4、6运行结果和结果分析（其中包括实验的检査结果、程序的运行情况）7自我评价与总结8附录：程序淸单，注意加注释（包括关键字、方法、变量等），在每个模块前加注释:三、课程设计步骤及时间进度和场地安排本课程设计将安排在第17周，教育技术中心。具体安排如下:第一天，下发任务书，学生査阅资料第二天，系统设计和原型开发第三，四天系统功能实现第五天，系统调试测试打包和验收星期一星期二星期三星期四星期五第17周第 1-8 |7第1$节第1-8节第1-8节第1-8节地点现教241现教241现教241现教241现教241四、课程设计考核及评分标准课程设讣考核将综合考虑学生考勤和参与度，系统设计方案正确性，系统设计和

5、开发效 果以及课程设计报告书的质量。具体评分标准如下：设置六个评分点（1）设计方案正确，具有可行性、创新性；25分（2）系统开发效果较好；25分（3）态度认真、刻苦钻研、遵守纪律；10分（4）设计报告规范.课程设计报告质量髙、参考文献充分20分（5）课程设计答辩概念淸晰，内容正确10分（6）课程设计期间的课堂考勤.答疑与统筹考虑。10分按上述六项分别记分后求和，总分按五级记分法记载最后成绩。优秀（10090分），良好（8089分），中等（7079分）,及格（6069分），不及格（059分）目录1设计题目与要求51.1设计题目51.2实验要求52设计思想54数据结构的说明和模块的算法流程图64.

6、1死锁避免:64.1.1破坏“不可剥夺”条件64.1.2破坏“请求和保持”条件64.1.3破坏“循环等待”条件64.2安全状态与不安全状态64.3数据结构：64.4安全性检查算法74.5程序流程图85使用说明书96运行结果和结果分析96.1输入96.2输出106.3结果分析117自我评价与总结118附录：12源程序清单121设计题目与要求1.1设计题目编程序模拟银行家算法1.2实验要求本实验要求用用C/C+语言在Linux操作系统环境下编写和调试一个简单的 银行家算法程序。加深了解有关资源申请、避免死锁等概念，并体会和了解死锁 和避免死锁的具体实施方法。2设计思想将一定数量的资金供多个用户周转

7、使用，当用户对资金的最大申请量不现存 资金时可接纳一个新客户，客户可以分期借款，但借款总数不能超过最大的申请 量。银行家对客户的借款可以推迟支付，但是能够使客户在有限的时间内得到借 款，客户得到所有的借款后能在有限的时间内归还。用银行家算法分配资源时， 测试进程对资源的最大需求量，若现存资源能满足最大需求就满足当前进程的申 请，否则推迟分配，这样能够保证至少有一个进程可以得到所需的全部资源而执 行到结束，然后归还资源，若OS能保证所有进程在有限的时间内得到所需资源 则称系统处于安全状态。3.实验环境系统平台：LINUX开发语言：C开发工具：PC机一台4数据结构的说明和模块的算法流程图4.1死锁

8、避免:定义:：系统设计时确定资源分配算法，保证不发生死锁。具体的做法是破坏产生死锁的四个必要条件之一4.1.1破坏“不可剥夺”条件在允许进程动态申请资源前提下规定，一个进程在申请新的资源不能立即 得到满足而变为等待状态之前，必须释放已占有的全部资源，若需要再重新 申请4.1.2破坏“请求和保持”条件要求每个进程在运行前必须一次性申请它所要求的所有资源，且仅当该进 程所要资源均可满足时才给予一次性分配413破坏“循环等待”条件采用资源有序分配法：把系统中所有资源编号，进程在申请资源时必须严格按资源编号的递增次、 序进行，否则操作系统不予分配。4.2安全状态与不安全状态安全状态：如果存在一个曲系统

9、中所有进程构成的安全序列Pl，-Pn,则系统 处于安全状态。一个进程序列P1，Pn是安全的，如果对于每一个进程Pi(l WiWn),它以后尚需要的资源量不超过系统当前剩余资源量与所有进程PjGi) 当前占有资源量之和，系统处于安全状态(安全状态一定是没有死锁发生的) 不安全状态:不存在一个安全序列，不安全状态一定导致死锁。43数据结构：(1) 可利用资源向量Available是个含有in个元素的数组，其中的每一个元素代表一类可利用的资源数 Ho如果Availablej=K,则表示系统中现有Rj类资源K个。(2) 最大需求矩阵Max这是一个nxm的矩阵，它定义了系统中n个进程中的每一个进程对m类

10、 资源的最大需求。如果Maxi,j=K,则表示进程i需要Rj类资源的最大数忖 为K。(3) 分配矩阵 Allocation这也是一个nxm的矩阵，它定义了系统中每一类资源当前已分配给每一进 程的资源数。如果AllocationiJ=K,则表示进程i当前已分得Rj类资源的 数 目为K。(4) 需求矩阵Need。这也是一个nxm的矩阵，用以表示每一个进程尚需的各类资源数。如果 Needizj=K,则表示进程i还需要Rj类资源K个，方能完成其任务。Need i,j =Max i,j - Allocationi,j4.4安全性检查算法4.4.1 设置两个工作向量 Work=AVAILABLE;FINI

11、SH 4.4.2从进程集合中找到一个满足下述条件的进程，FINISH二二false;NEEDents and SettingsAdaiiiistrat or桌面Debug2. eze*请百先碱蓉统可供资源科类的数呈詔闿原13彌?牙9陡源的M：3资馳綽3资感3 3勺务酥3请输入作业的数呈汚時输人各逬程的最大需求量知档矩阵LMaxJ：3 2 2? 5 39 0 24 3 32 2 2请输入各逬程已经申i肓的资涯虽5*3电阵Sllocdt ion 1:2 G D0 103 0 20 0 22 1 162输出we-ln| x请输入要求分配的资源进程号: 010 2qwe安全性检查WopkMeedAll

12、ocationWork+fillocationFinish逬程名q w eq v/ e：q w eq w e02 3 00 2 03 0 25 3 2t rue35 3 213 13 0 28 3 4t rue48 3 40 112 1110 4 5tpue110 4 57 4 20 1010 5 5七rue210 5 59 0 00 0 210 5 7trueLd此时刻阿资源分配情况为：Max1AllocationNeedftualiable逬程名q w ei w eC(w eq w e03 2 2302G202 3 017 5 3&1074329 0 200290034 3 3302131

13、42 2 22110ii6.3结果分析这次的设讣数据是通过一道实际的题LI来体现银行家算法避免死锁的问题，先 用银行家算法给其中一个进程分配资源，看它所请求的资源是否大于它的需求 量，才和系统所能给的资源相比较让进程形成一个安全队列，看系统是否安全. 再利用安全性算法检查此时系统是否安全。7自我评价与总结在本次实验中我们使用了 liunx变成环境，让我们更加系统深入的了解了 liunx, gcc编程思路和思想，同时让我更加深刻的了解银行家算法，了解死锁的 避免和预防，对操作系统对资源的申请和释放有了更加深刻的理解，同时在编程 过程中积极的向老师同学请教问题与他们一起探讨在系统中存在的问题和漏洞

14、。 深入了解了银行家算法的资源申请和资源分配的过程及原则。保证系统处于安全 状态。 经过本周的课程设计，我对操作系统的掌握乂进了一步，收获了很多知 识。,终于我了苗于对c语言不够熟练，在试验过程中，进行了反复的修改和 调试，解银行家算法的基本原理，并且在此次的课程设计中我乂复习了一下c语 言，加深了对它的了解，而且在课程设计的过程中我们同样学会了如何简单的操 作与使用Linux操作系统，学习到了许多Linux操作系统中常用的一些密令。 这次的设计数据是通过一道实际的题L1来体现银行家算法避免死锁的问题，先用 银行家算法给其中一个进程分配资源，看它所请求的资源是否大于它的需求量， 才和系统所能给

15、的资源相比较让进程形成一个安全队列看系统是否安全再利用 安全性算法检查此时系统是否安全。操作系统的基本特征是并发与共享。系统 允许多个进程并发执行，并且共享系统的软、硬件资源。为了最大限度的利用计 算机系统的资源，操作系统应釆用动态分配的策略，但是这样就容易因资源不足, 分配不出而引起“死锁J而我本次课程设讣就是得用银行家算法来避免“死锁J 银行家算法就是一个分配资源的过程，使分配的序列不会产生死锁。此算法的中 心思想是：按该法分配资源时，每次分配后总存在着一个进程，如果让它单独运 行下去，必然可以获得它所需要的全部资源，也就是说，它能结束，而它结束后 可以归还这类资源以满足其他申请者的需要。

16、通过这次实验，我体会到银行家 算法的重要性，银行家算法是避免死锁的主要方法，其思路在很多方面都非常值 得我来学习借鉴。通过这次实践，我知道，要做一个课程设计，如果知识面只是 停留在书本上，是不可能把课成设计完全地做好。在课程设计中，很多C语言的知识都忘了，每次的课程设计中都能将以前的 知识顺便再复习一遍，课程设计是给了我们一个机会去动手和主动复习，同时也 是提醒我们应该注重平时的积累。从课程设计以后还是要多多的动手，在实践中 体会理论知识，才能吸取经验教训。经过这次实验训练，我对这门课程有了更好 的了解。8附录： 源程序清单#include#include#mclude#define Fals

17、e 0#define True 1mtMax100100=0);/各进程所需各类资源的最大需求iiit Available100=0);/系统可用资源char name100=0;/ / 资源的名称iiit Allocation100100=0;/系统已分配资源int Need100100=0); /还需要资源iiit Request100=0);/请求资源向量int temp100=0;/存放安全序歹ljmtVVork100=0j;/存放系统可提供资源iiit p100=0;iiitq100100=0;iiitz100100=0;mt M=100;/作业的最大数为100int N=100;/

18、资源的最大数为100iiit gg=l;void showdata()/显示资源矩阵int i,j；coutendl此时刻的资源分配情况为：endl;NeedcoutMaxAllocationAvaliableendl;cout进程名for(j=0;j4;j+)for(i=0;iN;i+)coutnaine in H;coutH n;)coutendl;for(i=0;iM; i+)coutHH；for(j=0;jN;j+)coutMaxij H;coutH n;for(j=0;jN;j+)coutAllocationi j n H;coutHfor(j=0;jN;j+)coutNeedij,

19、 H;if(i=0)coutH H;for (j=O;jN;j+) coutAvaliablej;/输出分配资源 1coutendl;mt changdata(mt i)/进行资源分配int j；for (j=O;jM;j+) /pj=Avaliablej;Available j=Avaliable j-Requestj;/qi j =Allocationi j;Allocationi j = Allocationi j +Requestj;/zij=Needij; Needij=Needij-Requestj;return 1;Iint safe。/安全性算法iiit i/d,k=0,m,h

20、,szapply,Finish100=0;intj;iiit flag=0;for(i=0;iN;i+)Worki=Available i;coutendl安全性检查endl;W ork+AllocationcoutWork Need AllocationFiiiishendl;cout进程名for(h=0;h4;h+)for(s=0;sN;s+)cou tnaine s11H;coutH n;I coutendl;for(i=0;iM;i+)apply=0;for(j=0;jvN;j+)if (HnishHHHF 巴 se&r&TNeedmuAHworks apply+;if(applyHH

21、N)-8aa- -AA7A- =j fol.(dHO;dANjd+) coutworkdAA5 8aa= =;fol.(dHO;dAN;d+)coufAANeedi=dAA=;noAA= fol.(dHO;dANK+) coufAAAllocaHor4i=dAA-JnoAA= for(mHO;mAN;m+) W olxsMW orkB+ Allocationi=mcourA Awol,krnAA=-xr 匸、熾莎黑磨FinishullTruej remp-kHij 8aa= =;courAA-tlue 二人二COUKAendlj711;k+flag+;fol,(llgAM;i+)( if (F

22、irdshHllHFalse) f fol.G6AN;j+)亠A valiablefjH A valiable CT 一+RequestE; j AllocationullAlocationzsRequestEZi:NeedsllNeedis+RequesfscoutendlH系统进入不安全状态！此时系统不分配资源！ Hendl;/不 成功系统不安全return 0;coutendlH此时系统是安全的!vVendl;/如果安全，输出成功 coutH安全序列为:；for(i=0;iM;计+)/输出运行进程数组 couttempi;if(i;Icoutendl;return 0;Ivoid sha

23、re()/利用银行家算法对申请资源对进行判定char ch;iiit i=0,j=0;ch=y;coutendl请输入要求分配的资源进程号cini；/输入须申请的资源号coutendlH请输入进程vvivv申请的资源:Mendl;for(j=0;j Request j；/ /输入需要申请的资源for (j=O;jvN;j+)if (Request j Needi j)/ /判断申请是否大于需求，若大于则出错coutendlna程yvivv”申请的资源大于它需要的资源“； coutH分配不合理，不予分配！ VVendl;ch=n;break;Ielse if(RequestjAvaliablej

24、)/判断申请是否大于当前资源，若大于 则出错coutvvendlvv”进程yvivv”申请的资源大于系统现在可利用的资源“； coutH分配出错，不予分配!vendl;ch=,n; break;Iif(ch=,y,) changdata(i); /根据进程需求量变换资源 showdata();/根据进程需求量显示变换后的资源 safe();/根据进程需求量进行银行家算法判断iiit t=li jnuinbechoicenrvflag;char ming；coutv家算去 的 设 计与实现六endlcoutendl请首先输入系统可供资源种类的数量:”；ciiin;N=n;for(i=0;in;i+)coutn 资源 y i+in 的名称:”; ciiiniing;namei=niiiig;cout资源的数量:”； ciiinuiiiber;Available i =num