操作系统课程设计报告-银行家算法的模拟实现.doc

操作系统课程设计报告题目： 银行家算法的模拟实现 专业计算机科学与技术学生姓名班级计算机131学号指导教师完成日期2015.7.10信 息 工 程 学 院15操作系统课程设计（2015）目 录1 概述21.1 设计目的21.2 设计要求22 设计原理22.1 银行家算法22.2 安全性算法33 概要设计33.1 功能结构33.2 模块划分34 详细设计44.1 初始化模块设计44.2 银行家算法模块设计44.3 安全性检查模块设计55 测试与分析65.1 测试方案65.2 测试结果65.3 结果分析76 设计小结77 参考文献8附录 源程序代码9题目：银行家算法的模拟实现1 概述1.1 设计目的a).进一步了解进程的并发执行。b).加强对进程死锁的理解。c).是用银行家算法完成死锁检测。1.2 设计要求a).初始状态没有进程启动；b).计算每次进程申请是否分配，如：计算出预分配后的状态情况（安全状态、不安全状态），如果是安全状态，输出安全序列；c).每次进程申请被允许后，输出资源分配矩阵a和可用资源向量v；d).每次申请情况应可单步查看，如：输入一个空格，继续下个申请。2 设计原理2.1 银行家算法设requesti是进程pi的请求向量，如果requestij=k，表示进程pi需要k个ri类型的资源。当pi发出资源请求后，系统按下述步骤进行检查：a)如果requestij= needi,j，便转向步骤b)；否则认为出错，因为它所需的资源数已经超过了它所宣布的最大值。b)如果requestij= availablej，便转向步骤c)；否则表示尚无足够资源，pi需等待。c)系统试探着把资源分配给进程pi，并修改下面数据结构中的数值。availablej=available-requestij;allocationi,j=allocationi,j+requestij;needi,j=needi,j-requestj; d)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来资源的分配状态，让进程pi等待。2.2 安全性算法系统所执行的安全性算法可描述如下：a)设置两个向量：一个是工作向量work；它表示系统可提供给进程继续运行所需要的各类资源的数目，它含有m个元素，在执行安全性算法开始时，work=availalbe；另一个是 finish：它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做finishi=false；当有足够资源分配给进程时，再令finishi=rue；b)从进程集合中找到一个能满足下述条件的进程：一是finishi=false；二是 needi,j=workj；若找到，执行步骤c)，否则，执行步骤d)；c)当进程pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：workj=workj+allocationi,j；finishi=true；go to step b)；d)如果所有进程的finishi=true都满足，则表示系统处于安全状态，否则系统处于不安全状态。3 概要设计3.1 功能结构 银行家算法功能结构图如图3-1所示： 图3-13.2 模块划分 a)初始化 b)银行家算法 c)安全性检查4 详细设计4.1 初始化模块设计由用户输入数据，分别对运行的进程数、总的资源种类数、总资源数、各进程所需要的最大资源数量（max），已分配的资源数量（allowcation），可利用的资源数量（available）赋值。如图5-1所示，代码如下。 int i,j,p=0,q=0;char c;int requestm,allocation1mm,need1mm,available1m;printf(*n);printf(* 银行家算法的设计与实现 *n); printf(*n);printf(请输入进程总数:n);scanf(%d,&no1);printf(请输入资源种类数:n);scanf(%d,&no2); printf(请输入max矩阵:n);for(i=0;ino1;i+)for(j=0;jno2;j+)scanf(%d,&maxij); /输入已知进程最大资源需求量printf(请输入allocation矩阵:n);for(i=0;ino1;i+)for(j=0;jno2;j+)scanf(%d,&allocationij); /输入已知的进程已分配的资源数 for(i=0;ino1;i+)for(j=0;jno2;j+)needij=maxij-allocationij; /根据输入的两个数组计算出need矩阵的值 printf(请输入available矩阵n);for(i=0;ino2;i+)scanf(%d,&availablei); /输入已知的可用资源数4.2 银行家算法模块设计设requesti是进程pi的请求向量，如果requestij=k，表示进程pi需要k个ri类型的资源。当pi发出资源请求后，系统按下述步骤进行检查：a)如果requestij= needi,j，便转向步骤b)；否则认为出错，因为它所需的资源数已经超过了它所宣布的最大值。b)如果requestij= availablej，便转向步骤c)；否则表示尚无足够资源，pi需等待。c)系统试探着把资源分配给进程pi，并修改下面数据结构中的数值。availablej=available-requestij;allocationi,j=allocationi,j+requestij;needi,j=needi,j-requestj;d)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来资源的分配状态，让进程pi等待。如图5-3,5-4,5-5,5-6所示，代码如下。 q=0; p=0; printf(n请输入请求资源的进程号(04)：n); for(j=0;j=no1)printf(输入错误，请重新输入：n);continue; else break; printf(n请输入该进程所请求的资源数requestj:n); for(j=0;jno2;j+)scanf(%d,&requestj); for(j=0;jneedij) p=1; /判断请求是否超过该进程所需要的资源数 if(p)printf(请求资源超过该进程资源需求量，请求失败！n); else for(j=0;javailablej) q=1; /判断请求是否超过可用资源数if(q) printf(没有做够的资源分配，请求失败！n);else /请求满足条件for(j=0;jno2;j+) available1j=availablej; allocation1ij=allocationij;need1ij=needij; /保存原已分配的资源数，仍需要的资源数和可用的资源数availablej=availablej-requestj; allocationij+=requestj;needij=needij-requestj; /系统尝试把资源分配给请求的进程print();check(); /检测分配后的安全性if(r=0) /如果分配后系统不安全for(j=0;jno2;j+)availablej=available1j; allocationij=allocation1ij;needij=need1ij; /还原已分配的资源数，仍需要的资源数和可用的资源数printf(返回分配前资源数n);print();4.3 安全性检查模块设计系统所执行的安全性算法可描述如下：a)设置两个向量：一个是工作向量work；它表示系统可提供给进程继续运行所需要的各类资源的数目，它含有m个元素，在执行安全性算法开始时，work=availalbe；另一个是 finish：它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做finishi=false；当有足够资源分配给进程时，再令finishi=true；b)从进程集合中找到一个能满足下述条件的进程：一是finishi=false；二是 needi,j=workj；若找到，执行步骤c)，否则，执行步骤d)；c)当进程pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：workj=workj+allocationi,j；finishi=true；go to step b)；d)如果所有进程的finishi=true都满足，则表示系统处于安全状态，否则系统处于不安全状态。void check() /安全算法函数int k,f,v=0,i,j;int workm,am;bool finishm;r=1;for(i=0;ino1;i+)finishi=false; / 初始化进程均没得到足够资源数并完成for(i=0;ino2;i+) worki=availablei;/worki表示可提供进程继续运行的各类资源数k=no1;dofor(i=0;ino1;i+)if(finishi=false)f=1;for(j=0;jworkj)f=0;if(f=1) /找到还没有完成且需求数小于可提供进程继续运行的资源数的进程finishi=true;av+=i; /记录安全序列号for(j=0;j0);f=1;for(i=0;ino1;i+) /判断是否所有的进程都完成if(finishi=false) f=0;break;if(f=0) /若有进程没完成，则为不安全状态printf(系统处在不安全状态！);r=0;elseprintf(n系统当前为安全状态，安全序列为：n);for(i=0;ino1;i+)printf(p%d ,ai); /输出安全序列5 测试与分析5.1 测试方案假定系统中有五个进程：p0，p1，p2，p3，p4和三种类型的资源a，b，c，每一种资源的数量分别为10、5、7，输入相应数据。5.2 测试结果 程序初始化如图5-1所示： 图5-1t0时刻的资源分配情况如图5-2所示： 图5-2p1请求资源以及分配情况图如图5-3所示： 图5-3p4请求资源以及分配情况图如图5-4所示： 图5-4p0请求资源以及分配情况图如图5-5，5-6所示： 图5-5 图5-65.3 结果分析图示为初始化函数执行的结果，输入相应数据，得到一个安全状态，然后对安全状态进行检测，如果不是安全状态，重新初始化。验证了各种安全与不安全申请。6 设计小结 一周的课程设计结束了。在这一周里，我做一个模拟银行家算法。我觉得在着手设计前设计的思路是很重要的。只有思路清晰才能进行下一阶段的设计。这样才能完成整个程序的设计，完成整个文报告的书写。 课程设计这几天学到的东西还真不少。以前不清楚的现在都暴露出来了。以前认为学了没用的东西现在也用到了。这次的课程设计使我进一步了解了调度与死锁的问题。以及有关资源申请的问题、避免死锁的具体实施方法。深入了解了银行家算法的资源申请和资源分配的过程及原则。保证系统处于安全状态。7 参考文献1 韩立毛，李先锋. 计算机操作系统实践教程m，南京：南京大学出版社，2011.10.2 严蔚敏，吴伟民. 数据结构m，北京：清华大学出版社，1997.4.3 张尧学，史美林. 计算机操作系统教程m，北京：清华大学出版社，2000.8.4 孙静宇. 计算机操作系统课程设计指导书m，山西：太原理工出版社，2006.4.附录 源程序代码#include #include #include # define m 50 int no1; /进程数int no2; /资源数int r;int allocationmm,needmm,availablem,maxmm; char name1m,name2m; /定义全局变量void main()void check();void print();int i,j,p=0,q=0;char c;int requestm,allocation1mm,need1mm,available1m;printf(*n);printf(* 银行家算法的设计与实现 *n); printf(*n);printf(请输入进程总数:n);scanf(%d,&no1);printf(请输入资源种类数:n);scanf(%d,&no2); printf(请输入max矩阵:n);for(i=0;ino1;i+)for(j=0;jno2;j+)scanf(%d,&maxij); /输入已知进程最大资源需求量printf(请输入allocation矩阵:n);for(i=0;ino1;i+)for(j=0;jno2;j+)scanf(%d,&allocationij); /输入已知的进程已分配的资源数 for(i=0;ino1;i+)for(j=0;jno2;j+)needij=maxij-allocationij; /根据输入的两个数组计算出need矩阵的值 printf(请输入available矩阵n);for(i=0;ino2;i+)scanf(%d,&availablei); /输入已知的可用资源数print(); /输出已知条件check(); /检测t0时刻已知条件的安全状态if(r=1) /如果安全则执行以下代码do q=0; p=0;printf(n请输入请求资源的进程号(04)：n);for(j=0;j=no1)printf(输入错误，请重新输入：n); continue; else break;printf(n请输入该进程所请求的资源数requestj:n);for(j=0;jno2;j+)scanf(%d,&requestj);for(j=0;jneedij) p=1; /判断请求是否超过该进程所需要的资源数if(p)printf(请求资源超过该进程资源需求量，请求失败！n);elsefor(j=0;javailablej) q=1; /判断请求是否超过可用资源数if(q) printf(没有做够的资源分配，请求失败！n);else /请求满足条件for(j=0;jno2;j+) available1j=availablej; allocation1ij=allocationij;need1ij=needij; /保存原已分配的资源数，仍需要的资源数和可用的资源数availablej=availablej-requestj; allocationij+=requestj;needij=needij-requestj; /系统尝试把资源分配给请求的进程print();check(); /检测分配后的安全性if(r=0) /如果分配后系统不安全for(j=0;jno2;j+)availablej=available1j; allocationij=allocation1ij; needij=need1ij; /还原已分配的资源数，仍需要的资源数和可用的资源数printf(返回分配前资源数n);print();printf(n你还要继续分配吗？y or n ?n); /判断是否继续进行资源分配c=getche();while(c=y|c=y);void check() /安全算法函数int k,f,v=0,i,j;int workm,am;bool finishm;r=1;for(i=0;ino1;i+)finishi=false; / 初始化进程均没得到足够资源数并完成for(i=0;ino2;i+) worki=available