银行家算法的模拟实现（精）

1、操作系统课程设计报告题目： 银行家算法的模拟实现 专业计算机科学与技术学生姓名姜雯班级计算机131学号1310704112指导教师韩 立 毛完成日期2015.7.10信 息 工 程 学 院目 录1 概述21.1 设计目的21.2 设计内容21.3 设计要求22 设计原理22.1银行家算法中的数据结构22.2 银行家算法应用33 设计思路44 程序运行调试结果54.1程序初始化54.2检测系统资源分配是否安全结果65 设计小结86 参考文献8附录 源程序代码9题目：银行家算法的模拟实现1 概述1.1 设计目的 1.进一步了解进程的并发执行。2.加强对进程死锁的理解。3.是用银行家算法完成死锁检测

2、。1.2 设计内容给出进程需求矩阵C、资源向量R以及一个进程的申请序列。使用进程启动拒绝和资源分配拒绝（银行家算法）模拟该进程组的执行情况。1.3 设计要求1.初始状态没有进程启动；2.计算每次进程申请是否分配，如：计算出预分配后的状态情况（安全状态、不安全状态），如果是安全状态，输出安全序列；3.每次进程申请被允许后，输出资源分配矩阵A和可用资源向量V；4.每次申请情况应可单步查看，如：输入一个空格，继续下个申请。2 设计原理2.1 银行家算法中的数据结构(1)、可利用资源向量Available，这是一个含有m个元素的数组，其中的每个元素代表一类可利用资源的数目， 其初始值是系统中所配置的该

3、类全部资源的数目，其数值随该类资源的分配和回收而动态改变。如果Availablej=K，则表示系统中现有Rj类资源K个。（2）、最大需求矩阵Max，这是一个n*m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Maxi,j=K，则表示进程i需要Rj类资源的最大数目为K。（3）、分配矩阵Allocation。这也是一个n*m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocationi,j=K，则表示进程i当前已经分得Rj类资源的数目为K。（4）、需求矩阵Need。这也是一个n*m的矩阵，用以表示每个进程尚需要的各类资源数。如果Needi,j=K，

4、则表示进程i还需要Rj类资源K个，方能完成其任务。上述三个矩阵间存在以下关系：Needi,j=Maxi,j-Allocationi,j2.2 银行家算法应用模拟实现Dijkstra的银行家算法以避免死锁的出现，分两部分组成：一是银行家算法(扫描)；二是安全性算法。(1) 银行家算法(扫描) 设Requesti是进程Pi的请求向量，如果Requestij=K，表示进程Pi需要K个Ri类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：如果Requestij<= Needi,j，便转向步骤2；否则认为出错，因为它所需的资源数已经超过了它所宣布的最大值。如果Requestij<=

5、Availablej，便转向步骤3；否则表示尚无足够资源，Pi需等待。系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值。Availablej=Available-Requestij;Allocationi,j=Allocationi,j+Requestij;Needi,j=Needi,j-Requestj;系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来资源的分配状态，让进程Pi等待。(2)安全性算法系统所执行的安全性算法可描述如下：设置两个向量：一个是工作向量Work；它表示系统可

6、提供给进程继续运行所需要的各类资源的数目，它含有m个元素，在执行安全性算法开始时，work=Availalbe；另一个是 Finish：它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finishi=false；当有足够资源分配给进程时，再令Finishi=rue；从进程集合中找到一个能满足下述条件的进程：一是Finishi=false；二是 Needi,j<=Workj；若找到，执行步骤，否则，执行步骤；当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Workj=Workj+Allocationi,j；Finishi=true；go to s

7、tep；如果所有进程的Finishi=true都满足，则表示系统处于安全状态，否则系统处于不安全状态。3 设计思路1.进程一开始向系统提出最大需求量；2.进程每次提出新的需求(分期贷款)都统计是否超出它事先提出的最大需求量；3.若正常，则判断该进程所需剩余剩余量(包括本次申请)是否超出系统所掌握的剩余资源量，若不超出，则分配，否则等待。银行家算法流程如图16-4所示：图16-4 银行家算法流程银行家算法安全检测流程如图16-5所示：图16-5 银行家算法安全检测流程4 程序运行调试结果4.1 程序初始化4.2检测系统资源分配是否安全结果5 设计小结“银行家算法的模拟实现”是本学期操作系统课程的

8、课程设计。在设计此程序的过程中我们遇到过许多问题也学到了很多东西。通过这周的课程设计，我加深了对银行家算法的理解，掌握了银行家算法避免死锁的过程和方法，理解了死锁产生的原因和条件以及避免死锁的方法。所编写程序基本实现了银行家算法的功能，并在其基础上考虑了输出显示格式的美观性，使界面尽可能友好。并且在编程时将主要的操作都封装在函数中，这样使程序可读性增强，使程序更加清晰明了。在算法的数据结构设计上考虑了很长时间。在程序设计中先后参考了很多网络资料也参考了一些别人写的的程序综合这些算法思想和自己的思路对程序做了很好的设计方式对一些算法的优越性等也作了一些考虑。当然，在编写和调试过程中我遇到了许多的

9、问题，通过网上查询资料、翻阅课本、向同学请教、多次调试等方法逐渐解决了大部分问题。让我收获很多，相信在今后的生活中也有一定帮助。6 参考文献1 韩立毛，李先锋. 计算机操作系统实践教程M，南京：南京大学出版社，2011.10.2 严蔚敏，吴伟民. 数据结构M，北京：清华大学出版社，1997.43 张尧学，史美林. 计算机操作系统教程M，北京：清华大学出版社，2000.8.4 孙静宇. 计算机操作系统课程设计指导书M，山西：太原理工出版社，2006.4.附录 源程序代码#include <stdio.h>#include <stdlib.h>#include <co

10、nio.h> # define m 50int 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(&

11、quot;*n");printf("请输入进程总数:n");scanf("%d",&no1);printf("请输入资源种类数:n");scanf("%d",&no2); printf("请输入Max矩阵:n");for(i=0;i<no1;i+)for(j=0;j<no2;j+)scanf("%d",&maxij); /输入已知进程最大资源需求量printf("请输入Allocation矩阵:n");for(

12、i=0;i<no1;i+)for(j=0;j<no2;j+)scanf("%d",&allocationij); /输入已知的进程已分配的资源数 for(i=0;i<no1;i+)for(j=0;j<no2;j+)needij=maxij-allocationij; /根据输入的两个数组计算出need矩阵的值 printf("请输入Available矩阵n");for(i=0;i<no2;i+)scanf("%d",&availablei); /输入已知的可用资源数print(); /输出

13、已知条件check(); /检测T0时刻已知条件的安全状态if(r=1) /如果安全则执行以下代码do q=0; p=0;printf("n请输入请求资源的进程号(04)：n");for(j=0;j<=10;j+)scanf("%d",&i);if(i>=no1)printf("输入错误，请重新输入：n"); continue; else break;printf("n请输入该进程所请求的资源数requestj:n");for(j=0;j<no2;j+)scanf("%d&quo

14、t;,&requestj);for(j=0;j<no2;j+)if(requestj>needij) p=1; /判断请求是否超过该进程所需要的资源数if(p)printf("请求资源超过该进程资源需求量，请求失败！n");elsefor(j=0;j<no2;j+)if(requestj>availablej) q=1; /判断请求是否超过可用资源数if(q) printf("没有做够的资源分配，请求失败！n");else /请求满足条件for(j=0;j<no2;j+) available1j=availablej

15、; allocation1ij=allocationij;need1ij=needij; /保存原已分配的资源数，仍需要的资源数和可用的资源数availablej=availablej-requestj; allocationij+=requestj;needij=needij-requestj; /系统尝试把资源分配给请求的进程print();check(); /检测分配后的安全性if(r=0) /如果分配后系统不安全for(j=0;j<no2;j+)availablej=available1j; allocationij=allocation1ij; needij=need1ij;

16、/还原已分配的资源数，仍需要的资源数和可用的资源数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;i<no1;i+)finishi=false; / 初始化进程均没得到足够资源数并完成for(i=0;i<no2;

17、i+) worki=availablei;/worki表示可提供进程继续运行的各类资源数k=no1;dofor(i=0;i<no1;i+)if(finishi=false)f=1;for(j=0;j<no2;j+)if(needij>workj)f=0;if(f=1) /找到还没有完成且需求数小于可提供进程继续运行的资源数的进程finishi=true;av+=i; /记录安全序列号for(j=0;j<no2;j+)workj+=allocationij; /释放该进程已分配的资源k-; /每完成一个进程分配，未完成的进程数就减1while(k>0);f=1;fo

18、r(i=0;i<no1;i+) /判断是否所有的进程都完成if(finishi=false) f=0;break;if(f=0) /若有进程没完成，则为不安全状态printf("系统处在不安全状态！");r=0;elseprintf("n系统当前为安全状态，安全序列为：n");for(i=0;i<no1;i+)printf("p%d ",ai); /输出安全序列void print() /输出函数int i,j;printf("n");printf("*此时刻资源分配情况*n");printf("进程名/号 | Max | Allocation | Need |n"); for (i = 0; i < no1; i+)printf(" p%d/%d ",i,i); for (j = 0; j < no2; j+) printf("%d ",maxij);for