操作系统实验报告-银行家算法

1、操作系统实验报告 银行家算法班级： 计算机 03(7) 班 姓名： 李君益 学号： (61 号 )_提交日期：06.7.11指导老师: 林穗 一、设计题目加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。 要求编写和调试一个系统动态分配资源的简单模拟程序，观察死锁产生的条件，并采用银行家算法，有 效的防止和避免死锁的发生。二、设计要求内容：编制银行家算法通用程序，并检测思考题中所给状态的安全性。要求： TOC o 1-5 h z (1) 下列状态是否安全？(三个进程共享12 个同类资源)进程已分配资源数最大需求数114(状态a)244358114243(2)考虑下

2、列系统状态分配矩阵0 0 1 26最大需求矩阵0 0 1 21 0 0 01 7 5 01 3 5 42 3 5 60 6 3 20 6 5 20 0 1 40 6 5 66(状态b)8可用资源矩阵1 5 2 02 请求 (0420)，可否立即分配？关于操作系统的死锁死锁的产生计算机系统中有许多独占资源，他们在任一时刻只能被一个进程使用，如磁带机，绘图仪等独占型外围设备，或进程表，临界区等软件资源。两个进程同时向一台打印机输出将导致一片混乱，两个进程同时进入临界区将导致数据库错误乃至程序崩溃。正因为这些原因，所有操作系统都具有授权一个进程独立访问某一辞源的能力。一个进程需要使用独占型资源必须通

3、过以下的次序：申请资源使用资源归还资源若申请施资源不可用，则申请进程进入等待状态。对于不同的独占资源，进程等待的方式是有差别的，如申请打印机资源、临界区资源时，申请失败将一位这阻塞申请进程；而申请打开文件文件资源时，申请失败将返回一个错误码，由申请进程等待一段时间之后重试。只得指出的是，不同的操作系统对于同一种资源采取的等待方式也是有差异的。在许多应用中，一个进程需要独占访问多个资源，而操作系统允许多个进程并发执行共享系统资源时，此时可能会出现进程永远被阻塞的现象。这种现象称为“死锁”。死锁的定义一组进程处于死锁状态是指：如果在一个进程集合中的每个进程都在等待只能由该集合中的其他一个进程才能引

4、发的时间，则称一组进程或系统此时发生了死锁。3死锁的防止a.死锁产生的条件：互斥条件占有和等待条件不剥夺条件循环等待条件以上三个条件是死锁存在的必要条件，胆不是充分条件。第四个条件是钱唢呐个条件同时存在时产生的结果，所以，这些条件并不完全独立。但单独考虑每个条件是有用的，只要能破坏这四个必要条件之一，死锁就可以防止。b.实用死锁防止方法静态分配策略层次分配策略4 死锁的避免破坏死锁的四个条件之一能防止系统发生死锁，但这会导致低效率的进程运行和资源使用率。死锁的避免则相反，他允许系统中同时存在三个必要条件，如果能掌握并发进程中与每个进程有关的资源动态申请情况，做出明智和合理的选择，仍然可以避免死

5、锁的发生。每当在为申请者分配资源前先测试系统状态，若把资源分配个申请者会产生死锁的话，则拒绝分配，否则接受申请，为它分配资源。死锁避免不是通过队进程随意强加一些规则，而是通过对每一次资源申请进行认真的分析来判断它是否能安全的分配。问题是：是否存在一种算法总能做出正确的选择从而避免死锁？单种资源的银行家算法Dijkstra（ 1965）提出了一种能够避免死锁的调度方法，称为一银行家算法。它的模型基于一个小城镇的银行家，现将该算法描述如下：假定一个银行家拥有资金，数量为，被 N 个客户共享。银行家对 客户提出下列约束条件：每个客户必须预先说明自己所要求的最大资金量；每个客户每次提出部分资金量申请和

6、获得分配；如果银行满足了客户对资金的最大需求量，那么，客户在资金运作后，应在有限时间内归还银行。只要每个客户遵守上述约束，银行家将保证做到：若一个客户所要求的最大资金量不超过，则银行一定接纳该客户，并可处理他的资金需求；银行在受到一个客户的资金申请是，可能因资金不足而让客户等待，但保证在有限时间内让客户获得现金。在银行家算法中，客户可看作进程，资金可看作资源，银行家可看作操作系统名字最大Andy06Barbara05Marvin04Suzanne07名字 已使用 最大名字 已使用 最大10Andy16Barbara15Marvin24Suzanne47Andy16Barbara25Marvin

7、24Suzanne47安全安全不安全银行家算法就是对每一个请求进行检查，检查这次资源申请是否会导致不安全状态，若是，则不满足该请求， 否则便满足。检查状态是否安全的方法是看他是否有足够的资源满足一个距最大需求最近的客户，如此反复下去。如果所有投资都最终被收回，则该状态是安全的，最初的请求可以批准。多种资源的银行家算法银行家算法可以被推广用来处理系统中有任意数目的进程，任意种类的资源，并且每种资源有多个实例的情况。下图示出了其工作原理：进程 磁带机绘图仪 打印机 cd romA3011B0100C1110D1101E0000进程 磁带机绘图仪打印机 c d romA1100B0112C3100D

8、0010E2110仍需要的资源检查一个状态是否安全的步骤如下：查找右边矩阵是否有一行，其未被满足的设备数均小于或等于向量A。如果找不到，则系统将死锁，因为任何进程都无法运行结束。若找到这样一行，则可以假设它获得所需的资源并运行结束，将该进程标记为结束，并将资源加到向量 A 上。重复以上两步，知道所有的进程都标记为结束。若达到所有进程结束，则状态示安全的，否则将发生死锁。如果在第一步中同时存在若干进程均符合条件，则不管挑选哪一个运行都没有关系，因为，可用资源或者将增多，或者在最坏的情况下保持不变。图中所示的状态示安全的，进程B 现在再申请一台打印机，可以满足它的请求，而且保持系统状态仍然示安全的

9、（进程D 可以结束，然后是A 或 E，剩下的进程最后结束）。假设进程B 获得一台打印机后， E 试图获得最后的一台打印机，若分配给E，可用资源向量将减到1000，这时将导致死锁，显然E的请求不能立即满足，必须延迟一段时间。该算法最早由Dijkstra 于 1965 年发表。从那以后几乎每本操作系统的专著都详细的描述它，许多论文的内容也围绕该算法讨论，其主要优点是不需要死锁预防中加上的种种限制，如资源剥夺或重新运行进程。但很少由作者指出该算法缺乏实用价值。因为，进程很难在运行前就知道其所需资源的最大量；而且系统中的进程必须是无关的，相互之间没有同步要求；进程的个数和分配的资源数目应该是固定的。这

10、些要求往往事先难以满足。.实现原理1 数据结构假设有 n 个进程 m 类资源，则有如下数据结构：MAXn*m n 个进程对m 类资源的最大需求量AVAILABLEm 系统可用资源数ALLOCATIONn*m n 个进程已经得到m 类资源的资源量NEEDn*m n 个进程还需要m 类资源的资源量2银行家算法设进程 I 提出请求Requestm，则银行家算法按如下规则进行判断。(1)如果Requestm=NEEDI ， m，则转(2)；否则，出错。(2)如果Requestm=A VAILABLE ，则转(3)；否则，出错。(3)系统试探分配资源，修改相关数据：AVAILABLE=A VAILABL

11、E-REQUESTALLOCATION=ALLOCATION+REQUESTNEED=NEED-REQUEST(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。3安全性检查(1)设置两个工作向量WORK=A VAILABLE ； FINISHn=FALSE(2)从进程集合中找到一个满足下述条件的进程，FINISHi=FALSENEED=WORK如找到，执行(3)；否则，执行(4)(3)设进程获得资源，可顺利执行，直至完成，从而释放资源。WORK=WORK+ALLOCATIONFINISH=TRUEGO TO 2(4)如所有的进程Finishn=true

12、 ，则表示安全；否则系统不安全。2、程序执行过程typedef struct Allocation1四、程序代码设计思路设计进程对各在资源最大申请表示及初值确定。设定系统提供资源初始状态。设定每次某个进程对各类资源的申请表示。编制程序，依据银行家算法，决定其申请是否得到满足。主要数据结构假设有M个进程N类资源，则有如下数据结构：MAXM*N M个进程对N类资源的最大需求量AVAILABLEN 系统可用资源数ALLOCATIONM*N M个进程已经得到N类资源的资源量NEEDM*N M个进程还需要N类资源的资源量主要代码结构void main()void init()int fenpei()in

13、t shq()源程序#include#include#includetypedef struct Max1int m_a;int m_b;int m_c;int m_d;Max;int a_a;int a_b;int a_c;int a_d;Allocation;typedef struct Need1int n_a;int n_b;int n_c;int n_d;Need;struct Available1int av_a;int av_b;int av_c;int av_d; q;struct prchar name;Max max;Allocation allocation;Need n

14、eed;int finishflag;p5;char na5;/*void init()/ 读入printf( 各进程的NEED： n);FILE *fp;fp=fopen(,r+);for(int i=0;i5;i+)fscanf(fp,%c,%d,%d,%d,%d,%d,%d,%d,%dn,&,&pi.max.m_a,&pi.max.m_b,& pi.max.m_c,&pi.max.m_d,&pi.allocation.a_a,&pi.allocation.a_b,&pi.allocation.a_c,&pi. allocation.a_d );pi.need.n_a=pi.

15、max.m_a-pi.allocation.a_a;pi.need.n_b=pi.max.m_b-pi.allocation.a_b;pi.need.n_c=pi.max.m_c-pi.allocation.a_c;pi.need.n_d=pi.max.m_d-pi.allocation.a_d;printf(%c:%d,%d,%d,%dn,,pi.need.n_a,pi.need.n_b,pi.need.n_c,pi.need.n _d);fclose(fp);/*int fenpei()/ 分配printf(Available:n);printf(%d,%d,%d,%dn,q

16、.av_a,q.av_b,q.av_c,q.av_d);int finishcnt=0,k=0,count=0;for(int j=0;j5;j+)pj.finishflag=0;while(finishcnt5)for(int i=0;i=pi.need.n_a&q.av_b=pi.need.n_b&q.av_c=pi.need.n_c&q.av_d=pi.need.n_d) q.av_a+=pi.allocation.a_a;q.av_b+=pi.allocation.a_b;q.av_c+=pi.allocation.a_c;q.av_d+=pi.allocation.a_d;pi.fi

17、nishflag=1;finishcnt+;nak+=;break;count+;/ 禁止循环过多if(count5)return 0;return 1;/*int shq()int m,i,j,k,l;printf( 请输入进程号和请求资源！例如:题目要求：10 4 2 0( 进程号和资源之间3 个空格 )n);scanf(%d%d%d%d%d,&m,&i,&j,&k,&l);if(i=pm.need.n_a&j=pm.need.n_b&k=pm.need.n_c&l=pm.need.n_d)if(i=q.av_a&j=q.av_b&k=q.av_c&l=q.av_d)pm.a

18、llocation.a_a+=i;pm.allocation.a_b+=j;pm.allocation.a_c+=k;pm.allocation.a_d+=l;pm.need.n_a=pm.max.m_a-pm.allocation.a_a;pm.need.n_b=pm.max.m_b-pm.allocation.a_b;pm.need.n_c=pm.max.m_c-pm.allocation.a_c;pm.need.n_d=pm.max.m_d-pm.allocation.a_d;printf( 各进程的NEED:n);for(int w=0;wAvailablen 让 %c 等待 n,pm

19、.name); else printf(RequestNeedn 让 %c 等待 n,);return 0;/*void main()int flag;char c;coutnnnnnnnnntfor(int i=0;i30;i+)cout*;coutendlt 操作系统nendl;coutendlt 银行家算法nendl;coutendlt姓名:李君益nendl;coutendlt学号 :nendl;coutendlt日期:06.7.11nendl;printf(t);for( i=0;i30;i+)printf(*);printf(nnnnn);getch();printf(

20、t 请确认已经在 中正确输入各进程的有关信息n);getch();init();q.av_a=3;q.av_b=14;q.av_c=12;q.av_d=12;while(flag)for(i=0;i5;i+)q.av_a-= pi.allocation.a_a;q.av_b-= pi.allocation.a_b;q.av_c-= pi.allocation.a_c;q.av_d-= pi.allocation.a_d;if(fenpei()printf(n 这样配置资源是安全的n);printf( 其安全序列是：);for(int l=0;l%c,nal);printf(n);printf( 有进程发出Request 请求向量吗？(Enter y or Y)n);c=getch();if(c=y|c=Y)if(shq()continue;else break;else flag=0;else flag=0;printf( 不安全 n);五、执行结果和结果分析1. 程序运行还是介面如下2 单资源状态a 情况 TOC o 1-5 h z （三个进程共享12 个同类资源）进程最大需求数4（状态a）48在文件里面输入以上内容,点击单资源状态a.exe 运行,显示如下: