编程模拟银行家算法

1、湖南工业大学课 程 设 计资 料 袋 计算机与通信学院 学院（系、部） 2013 2014 学年第 1 学期 课程名称 计算机操作系统 指导教师 左新娥 职称 讲师 学生姓名 梁鑫明 专业班级 网络1102班 学号 11408400219 题 目 进程管理 成 绩 起止日期 2013 年 12 月 9 日 2013 年 12 月 15 日目 录 清 单序号材 料 名 称资料数量备 注1课程设计任务书12课程设计说明书13456课程设计任务书2013 2014学年第 1 学期学院（系、部） 计算机与通信学院 专业 网络工程 班级 111-2 课程名称： 计算机操作系统 学生姓名： 梁鑫明 设计题

2、目： 进程管理 指导教师： 左新娥 完成期限：自 2013 年 12 月 9 日至 2013 年 12 月 15 日 共 1 周内容及任务一、 设计内容进程管理程序，即实现初始化系统中的资源类别及数量以及系统中各进程对资源的已分配量及最大需求量；能够检测所给状态的系统安全性。 某个进程提出对各资源的申请，能够判断是否给予满足。二、设计任务课程设计说明书(纸质+电子版)，内容包括：设计内容、系统分析(包括可行性分析、需求分析等)及功能分析；系统设计(要求画出系统整体功能框图、流程图、并给出相应地关键的代码且对所使用的主要数据结构进行说明等。)、设计总结(评价/遇到的问题/体会/建议等)、使用说明

3、等。三、设计要求1. 按功能要求开发系统，能正确运行。程序代码书写规范，有充足的注释。2. 课程设计所使用的编程语言任选，但建议使用C或C+；3. 绿色软件：程序运行不需安装，避免写系统和注册表；进度安排起止日期工作内容课程设计前一周召开动员大会，学生选题；2013-12-92013-12-10系统分析和设计；2013-12-112013-11-13熟悉软件开发工具、编码系统、系统测试以及中期答辩；2013-12-142013-12-15撰写并提交课程设计说明书 (含电子文档)、源程序等。主要参考资料1罗宇、邹鹏、邓胜兰等著操作系统M北京：电子工业出版社，20112 Andrew S.Tane

4、nbaum 著陈向群等译现代操作系统M北京：机械工业出版社，20073 邓胜兰编著操作系统基础M北京：机械工业出版社，20094 Dave Probert著，陈向群等译Windows操作系统原理M北京：机械工业出版 ，20065 罗宇 褚瑞等等著操作系统课程设计M北京：机械工业出版，2004指导教师（签字）： 年 月 日系（教研室）主任（签字）： 年 月 日课程设计说明书 课程名称： 计算机操作系统 设计题目： 进程管理 专 业： 网络工程 班级： 1102 学生姓名: 梁鑫明 学 号: 11408400219 指导教师: 左新娥 2013年 12 月 7 日目录1 课程设计简介51.1 课目

5、的程设计的51.2 课程设计内容51.2 课程设计原理52课程设计实现过程62.1算法实现62.2系统结构框图与各模块流程图92.3 测试运行结果与分析133设计总结16参考文献17源代码18 1 课程设计简介1.1 课程设计的目的(1)掌握死锁的产生的原因、产生死锁的必要条件和处理死锁的基本方法。(2)了解多道程序系统中，多个进程并发执行的资源分配。(3)掌握预防死锁的方法，系统安全状态的基本概念(4)理解死锁避免在当前计算机系统不常使用的原因。(5)掌握银行家算法，了解资源在进程并发执行中的资源分配策略。1.2 课程设计内容编制银行家算法程序，即实现(1)初始化系统中的资源类别及数量以及系

6、统中各进程对资源的已分配量及最大需求量；(2)能够检测所给状态的系统安全性。 (3)某个进程提出对各资源的申请，能够判断是否给予满足。1.3 课程设计原理我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。 为保证资金的安全,银行家规定: (1) 当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客; (2) 顾客可以分歧贷款,但贷款的总数不能超过最大需求量; (3) 当银行家现有的资金不能满足顾客尚需的贷款数额时,对顾客的贷款可推迟支付,但总能使顾客在有限的时间里得到贷款; (4) 当顾客得到所需的全部资金

7、后,一定能在有限的时间里归还所有的资金. 操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。2课程设计实现过程2.1算法实现（1） 初始化这组进程的最大资源请求和依次申请的资源序列。把各进程已占用和需求资源情况记录在进

8、程控制块中。假定进程控制块的内容包括：进程名，状态，当前申请量，资源需求总量，已占资源量，能执行完标志。其中，进程的状态有：就绪、等待和完成。当系统不能满足进程的资源请求时，进程处于等待态。资源需求总量表示进程运行过程中对资源的总的需求量。 已占资源量表示进程目前已经得到但还未归还的资源量。因此，进程在以后还需要的剩余资源量等于资源需要总量减去已占资源量。显然每个进程的资源需求总量不应超过系统拥有的资源总量。 （2） 银行家算法分配资源的原则是：当某个进程提出资源请求时，假定先分配资源给它，然后查找各进程的剩余请求，检查系统的剩余资源量是否由于进程的分配而导致系统死锁。若能，则让进程等待，否则

9、，让进程的假分配变为真分配。 a) 查找各进程的剩余请求，检查系统的剩余资源量是否能满足其中一进程。如果能，则转b)。 b) 将资源分配给所选的进程，这样，该进程已获得资源最大请求，最终能运行完成。标记这个进程为终止进程，并将其占有的全部资源归还给系统。 重复第a)步和第b)步，直到所有进程都标记为终止进程，或直到一个死锁发生。若所有进程都标记为终止进程，则系统的初始状态是安全的，否则为不安全的。若安全，则正式将资源分配给它，否则，假定的分配作废，让其等待。数据结构：#define MAXPROCESS 50 /*最大进程数*/#define MAXRESOURCE 100 /*最大资源数*/

10、int AVAILABLEMAXRESOURCE; /*可用资源数组*/int MAXMAXPROCESSMAXRESOURCE; /*最大需求矩阵*/int ALLOCATIONMAXPROCESSMAXRESOURCE; /*分配矩阵*/int NEEDMAXPROCESSMAXRESOURCE; /*需求矩阵*/int REQUESTMAXPROCESSMAXRESOURCE; /*进程需要资源数*/bool FINISHMAXPROCESS; /*系统是否有足够的资源分配*/int pMAXPROCESS; /*记录序列*/int WorkMAXRESOURCE; /*工作数组*/in

11、t m,n; /*m个进程,n个资源*/string showdata14=max ,allo,need,aval;/*绘制资源以及进程状态时使用*/string showdata25=work,need,allo,w+al,finish;/*绘制银行家算法过程时使用*/关键代码：void Bank() /*银行家算法*/ int i,cusneed; /*cusneed为进程*/ char again; while(1) coutcusneed; coutn请输入进程所请求的各资源的数量endl; for(i=0;iREQUESTcusneedi; for(i=0;iNEEDcusneedi

12、) cout您输入的请求数超过进程的需求量!请重新输入!AVAILABLEi) cout您输入的请求数超过系统有的资源数!请重新输入!endl; continue; for(i=0;in;i+)/*先分配资源*/ AVAILABLEi-=REQUESTcusneedi; ALLOCATIONcusneedi+=REQUESTcusneedi; NEEDcusneedi-=REQUESTcusneedi; if(Safe() cout同意分配请求!endl; else cout您的请求被拒绝!endl; for(i=0;in;i+)/*资源分配后不安全，回滚分配资源操作*/ AVAILABLEi

13、+=REQUESTcusneedi; ALLOCATIONcusneedi-=REQUESTcusneedi; NEEDcusneedi+=REQUESTcusneedi; for(i=0;im;i+) FINISHi=false; cout您还想再次请求分配吗?是请按y/Y,否请按其它键again; if(again=y|again=Y) continue; break; 2.2系统结构框图与各模块流程图（1）系统结构框图：结束开始调用初始化函数(Init)图1系统结构框图安全性检测(Safe)银行家算法(Bank)安全YN(2)初始化流程图：结束返回Init()开始输入进程的数目m图2初始

14、化流程图输入资源的种类n输入AVAILABLEi输入正确YN输入MAXij输入ALLOCATIONij 显示当前系统状态(iShow)提示错误，重新输入相应数据（3）安全性检测流程图结束返回Safe()开始绘制结果表格头部(fShow)图3安全性检测流程图Worki=AVAILABLEi;FINISHi=false;输出找到的安全序列，返回trueNEEDi=Work&FINISHi=falseYNWorki+=ALLOCATIONiFINISHi=true输出进程及资源变化结果系统不安全，返回false所有进程FINISHi=ture;YN（4）银行家算法流程图结束返回Bank()开始输入请

15、求资源的进程cusneed图4银行家算法流程图输入进程请求资源REQUESTcusneedi提示安全,允许请求REQUESTcusneedi=NEEDcusneediYNAVAILABLEi-=REQUESTcusneedi;ALLOCATIONcusneedi+=REQUESTcusneedi;NEEDcusneedi-=REQUESTcusneedi;分配资源分配资源操作回滚，恢复到未分配REQUESTcusneedi= AVAILABLEiYNNSafe();继续分配？YN2.3 测试运行结果与分析（1）运行结果：（2）结果分析：图1为初始化函数段执行的结果，输入相应数据如下后：请输入进

16、程的数目:5请输入资源的种类:3请输入每个进程最多所需的各资源数,按照3x5矩阵输入7 5 33 2 29 0 22 2 24 3 3请输入每个进程已分配的各资源数,也按照3x5矩阵输入0 1 02 0 03 0 22 1 10 0 2请输入各个资源现有的数目:332得到一个安全状态，然后对安全状态进行检测，如果不是安全状态，重新初始化。验证了各种安全与不安全申请。3设计总结在设计“编程模拟银行家的算法”程序的过程中，我遇到过许多问题，可是也学到了许多东西。本程序的设计实现主要是用C+语言实现，通过对程序算法的设计优化、输出显示的格式设计、输入过程中的异常处理等一些设计过程中的问题的考虑解决，

17、在C+学习上也有了很大的进步。银行家算法属于操作系统中一个比较经典的算法，这个算法主要是为了预防操作系统出现死锁，保证系统的安全。通过本次课程设计，我通过翻书与查阅资料，理解了死锁产生的原因与解决死锁的基本方法，通过对银行家算法的设计，了解了资源在进程并发执行中的资源分配策略。加深了对操作系统知识概念的理解。通过此次课程设计，虽然花了许多时间，但是我的收获也挺多的，做课程设计的过程是一个学习的过程，也是一个长见识的过程，通过各种查阅资料，可以了解到更多的专业知识和大家对其中遇到的一些问题的解决方法。通过对程序的不断调试与改错，使程序最终能完整运行，这个过程虽然比较苦，但是结果比较令人开心。总之

18、，这次课程设计我比较满意，自己不但加强了对本课程知识的理解，也加强了对前面课程C+和数据结构的学习，而且还学习到了更多的知识，为以后专业方面的发展打好了一个好的基础。参考文献1罗宇、邹鹏、邓胜兰等著操作系统M北京：电子工业出版社，20112 Andrew S.Tanenbaum 著陈向群等译现代操作系统M北京：机械工业出版社，20073 邓胜兰编著操作系统基础M北京：机械工业出版社，20094 Dave Probert著，陈向群等译Windows操作系统原理M北京：机械工业出版 ，20065 罗宇 褚瑞等等著操作系统课程设计M北京：机械工业出版，2004源代码#include #include

19、 #include using namespace std;#define MAXPROCESS 50 /*最大进程数*/#define MAXRESOURCE 100 /*最大资源数*/int AVAILABLEMAXRESOURCE; /*可用资源数组*/int MAXMAXPROCESSMAXRESOURCE; /*最大需求矩阵*/int ALLOCATIONMAXPROCESSMAXRESOURCE; /*分配矩阵*/int NEEDMAXPROCESSMAXRESOURCE; /*需求矩阵*/int REQUESTMAXPROCESSMAXRESOURCE; /*进程需要资源数*/b

20、ool FINISHMAXPROCESS; /*系统是否有足够的资源分配*/int pMAXPROCESS; /*记录序列*/int WorkMAXRESOURCE; /*工作数组*/int m,n; /*m个进程,n个资源*/string showdata14=max ,allo,need,aval;/*输出表格用标题*/string showdata25=work,need,allo,w+al,finish;/*输出表格用标题*/void iShow()int size,size2;cout系统;for(int k=0;k4;k+)size=showdata1k.length();size

21、2=(n*3+5-size)/2; /*计算出字符前端的空格*/coutsetw(size2+size)showdata1ksetw(size2) ;/*使得文字在资源标志ABC总宽度下剧中*/coutendl;cout资源;for(k=0;k4;k+)char sourcename=A; /*资源命名，从A开始*/cout ;for(int kk=0;kkn;kk+)cout sourcename;sourcename+;cout ;coutendl;for(int ii=0;iim;ii+)coutPii ;/*输出进程名及状态*/for(int jj=0;jjn;jj+)coutsetw

22、(3)MAXiijj;cout ;for(jj=0;jjn;jj+)coutsetw(3)ALLOCATIONiijj;cout ;for(jj=0;jjn;jj+)coutsetw(3)NEEDiijj;cout ;if(ii=0)for(int iii=0;iiin;iii+)coutsetw(3)AVAILABLEiii;cout endl;void fShow()/*显示表格*/cout系统;for(int k=0;k5;k+)int size=showdata2k.length();int size2=(n*3+5-size)/2;coutsetw(size2+size)showda

23、ta2ksetw(size2) ;coutendl;cout资源;for(k=0;k4;k+)char sourcename=A;cout ;for(int kk=0;kkn;kk+)coutsetw(3)sourcename;sourcename+;cout ;coutendl;void Init() /*初始化算法*/ int i,j; coutm; coutn; cout请输入每个进程最多所需的各资源数,按照mxn矩阵输入endl; for(i=0;im;i+) for(j=0;jMAXij; cout请输入每个进程已分配的各资源数,也按照mxn矩阵输入endl; for(i=0;im;

24、i+) for(j=0;jALLOCATIONij; NEEDij=MAXij-ALLOCATIONij; if(NEEDij0) cout您输入的第i+1个进程所拥有的第j+1个资源数错误,请重新输入:endl; j-; continue; cout请输入各个资源现有的数目:endl; for(i=0;iAVAILABLEi; iShow();bool Safe() /*安全性算法*/fShow(); int i,j,k,l=0; for(i=0;in;i+) Worki=AVAILABLEi; for(i=0;im;i+) FINISHi=false; for(i=0;im;i+) if(

25、FINISHi=true) continue; else for(j=0;jWorkj) break; if(j=n) FINISHi=true;coutPi ;for(k=0;kn;k+)coutsetw(3)Workk;cout ;for(k=0;kn;k+)coutsetw(3)NEEDik;cout ;for(k=0;kn;k+)coutsetw(3)ALLOCATIONik;cout ;for(k=0;kn;k+)coutsetw(3)Workk+ALLOCATIONik;cout ;coutsetw(3)trueendl; for(k=0;kn;k+) Workk+=ALLOCATIONik; pl+=i; i=-1; /*再次由进程从小到大遍历*/ else continue; if(l=m) /*进程记录p的数量等于资源总量，全部进程均已经满足*/ cout系统是安全的endl; cout安全序列:endl; for(i=0;il;i+) cou