实验2.2 银行家算法

实验2.2 银行家算法一、 实验目的死锁会引起计算机工作僵死，因此操作系统中必须防止。本实验的目的在于让学生独立的使用高级语言编写和调试一个系统动态分配资源的简单模拟程序，了解死锁产生的条件和原因，并采用银行家算法有效地防止死锁的发生，以加深对课堂上所讲授的知识的理解。二、 实验要求设计有n个进程共享m个系统资源的系统，进程可动态的申请和释放资源，系统按各进程的申请动态的分配资源。系统能显示各个进程申请和释放资源，以及系统动态分配资源的过程，便于用户观察和分析；三、 数据结构1 可利用资源向量Available ，它是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源的数目，其初始值是系统中所配置的该类全部可用资源数目。其数值随该类资源的分配和回收而动态地改变。如果Available（j）=k，标是系统中现有Rj类资源k个。2 最大需求矩阵Max，这是一个nm的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max（i，j）=k，表示进程i需要Rj类资源的最大数目为k。3 分配矩阵Allocation，这是一个nm的矩阵，它定义了系统中的每类资源当前一分配到每一个进程的资源数。如果Allocation（i，j）=k，表示进程i当前已经分到Rj类资源的数目为k。Allocation i表示进程i的分配向量，有矩阵Allocation的第i行构成。4 需求矩阵Need，这是一个nm的矩阵，用以表示每个进程还需要的各类资源的数目。如果Need（i，j）=k，表示进程i还需要Rj类资源k个，才能完成其任务。Need i表示进程i的需求向量，由矩阵Need的第i行构成。上述三个矩阵间存在关系：Need（i，j）=Max（i，j）-Allocation（i，j）；四、 银行家算法Request i 是进程Pi 的请求向量。Request i （j）=k表示进程Pi请求分配Rj类资源k个。当Pi发出资源请求后，系统按下述步骤进行检查：1 如果Request i Need，则转向步骤2；否则，认为出错，因为它所请求的资源数已超过它当前的最大需求量。2 如果Request i Available，则转向步骤3；否则，表示系统中尚无足够的资源满足Pi的申请，Pi必须等待。3 系统试探性地把资源分配给进程Pi，并修改下面数据结构中的数值：Available = Available - Request iAllocation i= Allocation i+ Request iNeed i= Need i - Request i4 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。如果安全才正式将资源分配给进程Pi，以完成本次分配；否则，将试探分配作废，恢复原来的资源分配状态，让进程Pi等待。假定系统有5个进程（p0,p1,p2,p3,p4）和三类资源（A，B，C），各种资源的数量分别为10，5，7，在T0时刻的资源分配情况如下图： Max Allocation Need Available A B C A B C A B C A B CP0 7 5 3 0 1 0 7 4 3 3 3 2 ( 2 3 0 )P1 3 2 2 2 0 0 1 2 2 (3 0 2 ) (0 2 0 )P2 9 0 2 3 0 2 6 0 0P3 2 2 2 2 1 1 0 1 1P4 4 3 3 0 0 2 4 3 1五、 安全性算法1 设置两个向量。Work：它表示系统可提供给进程继续运行的各类资源数目，它包含m个元素，开始执行安全性算法时，Work = Available。Finish：它表示系统是否有足够的资源分配给进程，使之运行完成，开始Finish（I）=false；当有足够资源分配给进程Pi时，令Finish（i）=true；2 从进程集合中找到一个能满足下述条件的进程。Finish（i）= = false；Need i work；如找到则执行步骤3；否则，执行步骤4；3 当进程Pi获得资源后，可顺利执行直到完成，并释放出分配给它的资源，故应执行Work = work + Allocation i Finish（i）=true；转向步骤2；4 若所有进程的Finish（i）都为true，则表示系统处于安全状态；否则，系统处于不安全状态。六、 系统流程图开 始输入资源数m, 及各类资源总数，初始化Available向量输入进程数n，i=1输入进程i的最大需求向量max。inmax资源总数提示错误重新输入i加1任选一个进程作为当前进程输入该进程的资源请求量Request 调用银行家算法，及安全性算法，完成分配，或并给出提示该进程的Need向量为0该进程已运行结束Need矩阵为0所有进程运行都结束结 束NYYNNY初始化need 矩阵NY 七银行家算法程序代码#include#include#includeusing namespace std;typedef struct Max1 / 资源的最大需求量int m_a;int m_b;int m_c;Max; typedef struct Allocation1 /已分配的资源数int a_a;int a_b;int a_c;Allocation; typedef struct Need1 /还需要的资源数int n_a;int n_b;int n_c;Need; struct Available1 /可利用的资源量int av_a;int av_b;int av_c; q;struct pr /定义一个结构char name;Max max;Allocation allocation;Need need;int finishflag;p5;char na5;/*void init() /读入文件1.txtcout各进程还需要的资源数NEED：endl;FILE *fp;fp=fopen(1.txt,r+); / 打开文件1.txtfor(int i=0;i5;i+)fscanf(fp,%c,%d,%d,%d,%d,%d,%dn,&,&pi.max.m_a,&pi.max.m_b,&pi.max.m_c,&pi.allocation.a_a,&pi.allocation.a_b,&pi.allocation.a_c);pi.need.n_a=pi.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_a pi.need.n_b pi.need.n_cendl;fclose(fp); /关闭文件/*int fenpei()/分配资源coutAvailable:;coutq.av_a q.av_b q.av_cendl;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_a+=pi.allocation.a_a;q.av_b+=pi.allocation.a_b;q.av_c+=pi.allocation.a_c;pi.finishflag=1;finishcnt+;nak+=;break;count+;/禁止循环过多if(count5)return 0;return 1;/*int shq() /申请资源int m=0,i=0,j=0,k=0; /m为进程号; i,j,k为申请的三类资源数 cout请输入进程号和请求资源的数目!endl;cout如：进程号 资源A B Cendl;cout 0 2 0 2mijk;if(i=pm.need.n_a&j=pm.need.n_b &k=pm.need.n_c)if(i=q.av_a&j=q.av_b&k=q.av_c)pm.allocation.a_a+=i;pm.allocation.a_b+=j;pm.allocation.a_c+=k;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;cout各进程还需要的资源数NEED:n;for(int w=0;w5;w+) : pw.need.n_a pw.need.n_b pw.need.n_cendl;return 1;elsecoutAvailable让进程m等待.endl;else coutNeed,让进程m等待.endl;return 0;/*void main()int flag;char c;cout /* 银 行 家 算 法*/ endl;cout确认已经在1.txt文档中正确输入各进程的有关信息后按回车键endl;getch();init();q.av_a=10; /各种资源的数量q.av_b=5;q.av_c=7;while(flag)for(int 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;if(fenpei()cout这样配置资源是安全的!endl;cout其安全序列是： ;for(int k=0;k5;k+)coutnak;coutendl;cout有