计算机操作系统实验五二维数组实现银行家...(1).doc

精品文档，仅供学习与交流，如有侵权请联系网站删除操作系统实验五实验报告内容 （用二维数组实现银行家算法）组长：赖建明组员：赖建明（34号） 何文成（26号） 莫善坤（9号） 李居林（13号） 黄小龙（23号） 高大旺（29号）一、 实验题目与要求：1、用二维数组实现银行家算法（避免死锁）。二、总的设计思想及：1、设计思想：避免分配资源也称作Banker(银行家)算法。Banker算法的主要思想： 若进程Pi的申请超过了其申报的最大需求数，则报错； 若进程Pi的申请超过了可用资源数，则Pi必须等待； 系统暂时为进程Pi分配其所需要的资源，修改资源分配状态； 调用安全算法检查系统当前状态，若导致不安全状态，则推迟这种分配。三、 数据结构与模块说明（功能与框图）： 数据结构：安全性算法：（参考课本P102页）Available：向量（一维数组），指出当前每种类型资源可用实例的总数量。Max：每个进程对每种资源类型实例的最大需求，它是 n x m 矩阵（二维数组）。Allocation：每个进程当前已分配的各种资源类型的实例数量，它是 n x m 矩阵（二维数组）。Need：每个进程还需要的剩余的资源，它是 n x m 矩阵（二维数组）need = max allocation。向量 Work ：是临时的资源使用数组，它初始化为当前可用的资源数。向量 Finish： 是布尔型数组，每个进程一个单元并初始化为 false。模块说明：安全性算法流程图Work=Available;Finish=falsefalse;Needi<=Work&&Finishi=falsetrueWork+=Availablei;Finishi=true;输入错误请检查后重新输入!false所有进程的Finish=true否则true安全序列为:return ture资源分配失败!资源分配成功!功能： 银行家算法主要有两部分：资源请求部分和安全检测部分。对于资源请求部分，首先检查进程的本次请求是否超过它的最初资源要求总量；如果本资源共享进程请求有效，下一步确定系统是否可以满足进程的这次请求；如果不能满足；挂起进程，如果可以满足，调用安全检测算法。对于资源请求算法如下情况：1、 如果AllocationI,*+Rquest*<=NeedI,*,则转（2），否则因进程i已起出其最大需求，系统出错。2、 如果Request*<=Available*，则转（3），否则进程i因没有可用资源面等待。3、 假定系统可以分配给进程i所请求的资源，并按如下方式修改状态：Allocationi,*=Allocationi,*+Request*;Available*=Avlaiable*-Request*;4、系统安全检测算法。查看此时系统状态是否安全。如果是安全的，就实际分配资源，满足进程的此次请求；否则若新状态不安全。则进程等待，对所申请的资源暂不予分配，并且把资源分配状态恢复到（3）之前的情况。资源请求的主要代码如下： bool request(int pid,int *r,int n) int i;int sl4; if(compare(Needpid,r,n)=true && compare(Available,r,n) subtract(Available,r,N); add(Allocationpid,r,N); subtract(Needpid,r,N); if(safe(sl) cout<<"安全序列为:"<<endl; for(i=0;i<M;i+) printf("p%d",sli); cout<<endl; return true; else add(Available,r,N); subtract(Allocationpid,r,N); add(Needpid,r,N); return false; else return false;void print(int *a,int n) int i; for(i=0;i<n;i+)cout<<" "<<ai;cout<<endl;对于安全算法情况如下：（1） 设长度为的工作向量：Work=(w1,w2 ,wm)和长度为n的工作向量Finish=(F1,F2,Fn),并令Work*=Available*;Finishi=false;（2） 查找这样的进程i使其满足：Finishi=false;Needi,*<=work*（3） 令：Work*=Work*+Allocationi,*;Finishi=true;（4） 如果对于所有i，Finishi=ture则系统处于安全状态；否则系统处于不安全状态。安全检查的主要算法如下： bool safe(int *sl) int i; int count=0; /*记录finishi = true 的个数*/ int n=0; int workN; bool finishM;assign(work,Available,N);for(i=0;i<M;i+) finishi=false;n=M; while(n-) for(i=0;i<M;i+) if(count>=M) return true; if(finishi=false&&compare(work,Needi,N) add(work,Allocationi,N); finishi=true; slcount=i; count+; if(count>=M) return true; else return false;四、源程序#include <stdio.h>#include <stdlib.h>#include <conio.h>#include<iostream.h>#define M 4 /*进程数*/#define N 3 /*资源数*/int AvailableN = 1,1,2; /系统可用资源向量int MaxMN = 3,2,2, 6,1,3, 3,1,4, 4,2,2, ; /最大需求向量int AllocationMN = 1,0,0, 5,1,1, 2,1,1, 0,0,2, ; /资源已分配向量int NeedMN = 2,2,2, 1,0,2, 1,0,3, 4,2,0, ; /需求向量/比较两个一维数组,判断 a >= b ?bool compare(int *a,int *b,int n) int i=0; for(i=0;i<n;i+) if(ai<bi) return false; return true;/一维数组加法/a = a + bvoid add(int *a,int *b,int n) int i=0; for(i=0;i< n;i+) ai+=bi;/一维数组减法/a = a - bvoid subtract(int *a,int *b,int n) int i=0; for(i=0;i<n;i+) ai-=bi;/将数组b的值赋给a，n为数组的大小void assign(int *a,int *b,int n) int i=0; for(i=0;i<n;i+) ai=bi;/sl 记录安全序列bool safe(int *sl) int i; int count=0; /*记录finishi = true 的个数*/ int n=0; int workN; bool finishM; /work = av; assign(work,Available,N); /初始化标记 finish for(i=0;i<M;i+) finishi=false;/n为进程的个数/循环最多执行n次 n=M; while(n-) for(i=0;i<M;i+) /判断是否安全 if(count>=M) /全部进程都可安全执行（finish = true） return true; /判断能否满足进程i的要求 /work >= Needi ? if(finishi=false&&compare(work,Needi,N) /分配，待进程完成后再释放 add(work,Allocationi,N); finishi=true; /记录安全路径 slcount=i; /能满足的进程数+1 count+; if(count>=M) return true; else return false;/请求分配/pid进程，r请求向量，n资源个数bool request(int pid,int *r,int n) int i; /记录安全路径 int sl4; if(compare(Needpid,r,n)=true && compare(Available,r,n) /尝试分配资源 subtract(Available,r,N); add(Allocationpid,r,N); subtract(Needpid,r,N); /判断是否是安全状态 if(safe(sl) /打印安全路径 cout<<"安全序列为:"<<endl; for(i=0;i<M;i+) printf("p%d",sli); cout<<endl; /可以分配 return true; else /不分配 /恢复到分配前的状态 add(Available,r,N); subtract(Allocationpid,r,N); add(Needpid,r,N); return false; else /error return false;/打印一维数组void print(int *a,int n) int i; for(i=0;i<n;i+)cout<<" "<<ai;cout<<endl;/显示系统信息void init() int i; cout<<"该系统共有进程4个,"<<'n'<<"其对资源的需求和分配情况分别是:"<<endl; for(i=0;i<M;i+) cout<<"进程"<<i<<"资源最大需求:" print(Maxi,N);cout<<endl; for(i=0;i<M;i+)cout<<"进程"<<i<<"已经分配资源:" print(Allocationi,N); cout<<endl; cout<<"系统可用资源数量:"<<'n'<<'t'<<endl; print(Available,N);/输入void input(int *r,int n,int *id) char ch; cout<<"请输入进程的id(0 3):"<<endl; ch=getche(); *id=ch-0x30; cout<<"n请输入对0类资源的申请数量:"<<endl; ch=getche(); r0=ch-0x30;cout<<"n请输入对1类资源的申请数量:"<<endl; ch=getche(); r1=ch-0x30; cout<<"n请输入对2类资源的申请数量:"<<endl; ch=getche(); r2=ch-0x30; printf("n您输入的是：Request%d(%d,%d,%d)n",*id,r0,r1,r2);/检查输入bool check(int id,int r1,int r2,int r3) if(id>3|id<0|r1<0|r2<0|r3<0) return false; else return true;int main() /进程id int id; /控制字符 int r3; char es; char control; /显示开始信息 init(); /输入申请信息 input(r,N,&id); /检查输入 if(check(id,r0,r1,r2) = false) cout<<"输入错误请检查后重新输入!"<<endl; /continue; /执行 if(request(id,r,N) cout<<"资源分配成功!"<<endl; else cout<<"资源分配失败!"<<endl; /显示当前系统资源和进程情况 cout<<"系统可用资源:"<<endl; print(Available,N); cout<<"进程"<<id<<"的最大资源需求:"<<endl; print(Maxid,N); cout<<"进程"<<id<<"已经分配资源:"<<endl; print(Allocationid,N); cout<<"是否继续输入?(Y/N)"<<endl; control=getch(); if(control='Y'|control='y') es=main(); return 0;五、运行结果与运行情况六、分析运行结果 运行程序：首先选择进程1，因为进程1的Need=1 0 2。如上图所看到输出一个安全序列：P1P2P3P0，所以输入1 0 2 满足进程1，程序接着循环检查有没有进程的需求比剩下的资源小的（这一步是反复进行的），若有，则断续分配，反之则挂起等待。等到前面的进程结束后，把所占资源释放再分配给其他等待中的进程，让其完成作业。如上面第一张图片中所示，首先是进程1获得资源，分配成功。接着完成其他的进程，所以能避免死锁，输出一个安全序列。七、总结： 通这次实验对银行家算法设计与调试，我们本小组对操作系统的各程序代码有了较深的理解，同时也懂得如何设计程序来解决现实中的死锁问题，收益良多。【精品文档】第 8 页