操作系统课程设计(银行家算法的模拟实现)剖析

1、操作系统课程设计（银行家算法的模拟实现）一、设计目的1、进一步了解进程的并发执行。2、加强对进程死锁的理解。3、用银行家算法完成死锁检测。二、设计内容给出进程需求矩阵c、资源向量r以及一个进程的申请序列。使 用进程启动拒绝和资源分配拒绝（银行家算法）模拟该进程组的执行 情况。三、设计要求1、初始状态没有进程启动。2、计算每次进程申请是否分配，如：计算出预分配后的状态情况 （安全状态、不安全状态），如果是安全状态，输出安全序列。3、每次进程申请被允许后，输出资源分配矩阵 a和可用资源向 量v。4、每次申请情况应可单步查看，如：输入一个空格，继续下个申 请。四、算法原理1、银行家算法中的数据结构(

2、1)、可利用资源向量available,这是一个含有m个元素的数组, 其中的每个元素代表一类可利用资源的数目，其初始值是系统中所配置的该类全部资源的数目，其数值随该类资源的分配和回收而动态 改变。如果availablej=k ,则表示系统中现有 rj类资源k个。(2)、最大需求矩阵max,这是一个n*m的矩阵，它定义了系 统中n个进程中的每一个进程对 m类资源的最大需求。如果 maxi,j=k ,则表示进程i需要rj类资源的最大数目为k。(3)、分配矩阵allocation。这也是一个n*m的矩阵，它定义了 系统中每一类资源当前已分配给每一进程的资源数。如果allocationi,j=k ,则

3、表示进程i当前已经分得rj类资源的数目为k(4)、需求矩阵need。这也是一个n*m的矩阵，用以表示每个 进程尚需要的各类资源数。如果 needi,j=k ,则表示进程i还需要 rj类资源k个，方能完成其任务。上述三个矩阵间存在以下关系：needi,j=maxi,j-allocationi,j2、银行家算法应用模拟实现dijkstra的银行家算法以避免死锁的出现，分两部分组成：一是银行家算法(扫描)；二是安全性算法。(1)银行家算法(扫描)设requesti是进程pi的请求向量，如果 requestij=k,表 示进程pi需要k个ri类型的资源。当pi发出资源请求后，系统按 下述步骤进行检查：

4、如果requestij=needi,j,便转向步骤；否则认为出错, 因为它所需的资源数已经超过了它所宣布的最大值。如果requestij=allocationi,j,便转向步骤；否则表示 尚无足够资源，pi需等待。系统试探着把资源分配给进程 pi,并修改下面数据结构中 的数值。availablej=available-requestij;allocationi,j=allocationi,j+requestij;needi,j=needi,j-requestij;系统执行安全性算法，检查此次资源分配后，系统是否处 于安全状态。若安全，才正式将资源分配给进程pi,已完成本次分配； 否则，将本次的

5、试探分配作废，恢复原来资源的分配状态，让进程 pi等待。(2)安全性算法系统所执行的安全性算法可描述如下：设置两个向量：一个是工作向量 work;它表示系统可提供 给进程继续运行所需要的各类资源的数目，它含有m个元素，在执行安全性算法开始时，work=available;另一个是finish;它表示系 统是否有足够的资源分配给进程，使之运行完成。开始时先做 finishi=false ;当有足够资源分配给进程时，再令 finishi=true ;从进程集合中找到能满足下述条件的进程：一是 finishi=false ;二是 needi,j=workj;若找到，执 行步骤，否则，执行步骤；当进程

6、pi获得资源后，可顺利执行，直至完成，并释放出 分配给它的资源，故应执行：workj=workj+allocationi,j;finishi=true ;go to step;如果所有进程的finishi=true都满足，则表示系统处于 安全状态，否则系统处于不安全状态。五、设计思路1、进程一开始向系统提出最大需求量；2、进程每次提出新的需求（分期贷款）都统计是否超出它事先提 出的最大需求量；3、若正常，则判断该进程所需剩余量（包括本次申请）是否超出 系统所掌握的剩余资源量，若不超出，则分配，否则等待。六、程序运行调试结果1、程序初始化k银行家算法的设计与实现苴mi耳彳m菖m m -；彳m菖m

7、麓；彳mm； ：）；： ji耳片片一；）胃耳*：十1*1- 请输入进程总数二 营输入资源种类数：请输入max矩阵：7 5 33 2 29 0 22 2 24 3 3请输入rllocation矩阵：0 10b日3 0 22 11b02靖输入的nl&ble矩阵1心底面田质zxq 比无七： 尔目3 引人l k ke程名，号1 flflax allocation1 1needv 1p0/0753810743pl/132220&122p2z29023a2600p3/32222i1011p4/4433002431悟类资源可利用的资源数为二3 3 2系统当前为安全状态，安全序列为,pl p3 p4p p22

8、、检测系统资源分配是否安全结果请输入请求资源的进程号1请输入该进程所请求的资源数request e j b10 2此时刻资源分*配1情 1况 m h x m x 翼 m m h m m x mx x nx x xx x进程名/号!m我xi allocat ion eneedt tp0/0753010743pl/1322302020p2/29023132600p3/3222211ft11p4/4433002431各类资源可利用的资源数为：2 ? 0 系统当前为安全状态，安全序列为:plp4 g p2你还要继续分配呜？ v ot* n ?你还要继续分配吗？ 丫 口/n ?,输入请求资源的进程号4f

9、, 4请输入该进程所请求的资源数#的娘右at jl：3 3 0好有做够的资源分配，请求失败f 你还要继续分配吗？ v or n ?你还要继续分配吗？ y ” n ?套输入请求资源的进程号：博输入该进程所请求的资源数rwe3 t rj ： 2 8lr . . ，此时刻 资源分酉iw况xh*h*hx*hxxhr*hxxh进程名/号1 tmax allocat ioni ineed1 ip0/0753030723pl /i322302020p2/2902302600p3 /322221101ip4/4433002431各类资源可狎用的资源数为二2 1 0 系统如在不安筌状态i返回分配前资源数系统处在

10、不安全状态！返回分配前资源数xlfifjihifk止匕时奔 i r青；浜丁酉 3 | 青 i 兄 kkioixiofjfjfaimjf进程名/号 ； max ； allocation ： need tp0/07530pi/i3223p2/2?023p3/32222p4/44330107430202026001101102431各类资源可利用的资源数为：2你还要续分配吗？ v or n ?npress atny key to continue七、小结“银行家算法的模拟实现”是本学期操作系统课程的课程设计。在设计此程序的过程中 况我们遇到过许多问题 况也学到了很多东西。通过这周的课程设 计，我加深

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

12、逐渐解决了大部分问题。 让我收获很多，相信在今 后的生活中也有一定帮助。附：程序源代码:#include #include #include # 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)

13、;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”,&alloc

14、ationij); /for(i=0;ino1;i+)for(j=0;jno2;j+)need皿=maxij-allocationij; 算出need矩阵的值printf(请输入 available 矩阵n); for(i=0;ino2;i+)scanf(%d”,&availablei); /print(); /输出已知条件check(); /检测t0时刻已知条件的安全状态if(r=1) /如果安全则执行以下代码doq=0;p=0;printf(n请输入请求资源的进程号(04) ： n);for(j=0;j=no1)printf(输入错误，请重新输入：n);continue;else brea

15、k;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=allocation

16、ij; 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;/还原已分配的资源数，仍需要的资源数和可用的资源数

17、 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=availablei;/worki表示可提供进程继续运行的各类资源数k=no1;do for(i=0;ino1;i+) if(finis

18、hi=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); / 输出安全序列 void print() / 输出函数 int i,j；止匕时刻资源分酉己t青况*n)；printf(n);printf(*allocation | need |n);printf(进程名/