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

1、操作系统实验五实验报告内容 （用二维数组实现银行家算法）组长：赖建明组员：赖建明（34号） 何文成（26号） 莫善坤（9号） 李居林（13号） 黄小龙（23号） 高大旺（29号）一、 实验题目与要求：1、用二维数组实现银行家算法（避免死锁）。二、总的设计思想及：1、设计思想：避免分配资源也称作Banker(银行家)算法。Banker算法的主要思想： 若进程Pi的申请超过了其申报的最大需求数，则报错； 若进程Pi的申请超过了可用资源数，则Pi必须等待； 系统暂时为进程Pi分配其所需要的资源，修改资源分配状态； 调用安全算法检查系统当前状态，若导致不安全状态，则推迟这种分配。三、 数据结构与模块说

2、明（功能与框图）： 数据结构：安全性算法：（参考课本P102页）Available：向量（一维数组），指出当前每种类型资源可用实例的总数量。Max：每个进程对每种资源类型实例的最大需求，它是 n x m 矩阵（二维数组）。Allocation：每个进程当前已分配的各种资源类型的实例数量，它是 n x m 矩阵（二维数组）。Need：每个进程还需要的剩余的资源，它是 n x m 矩阵（二维数组）need = max allocation。向量 Work ：是临时的资源使用数组，它初始化为当前可用的资源数。向量 Finish： 是布尔型数组，每个进程一个单元并初始化为 false。模块说明：安全性

3、算法流程图Work=Available;Finish=falsefalse;Needi<=Work&&Finishi=falsetrueWork+=Availablei;Finishi=true;输入错误请检查后重新输入!false所有进程的Finish=true否则true安全序列为:return ture资源分配失败!资源分配成功!功能： 银行家算法主要有两部分：资源请求部分和安全检测部分。对于资源请求部分，首先检查进程的本次请求是否超过它的最初资源要求总量；如果本资源共享进程请求有效，下一步确定系统是否可以满足进程的这次请求；如果不能满足；挂起进程，如果可以满足，调

4、用安全检测算法。对于资源请求算法如下情况：1、 如果AllocationI,*+Rquest*<=NeedI,*,则转（2），否则因进程i已起出其最大需求，系统出错。2、 如果Request*<=Available*，则转（3），否则进程i因没有可用资源面等待。3、 假定系统可以分配给进程i所请求的资源，并按如下方式修改状态：Allocationi,*=Allocationi,*+Request*;Available*=Avlaiable*-Request*;4、系统安全检测算法。查看此时系统状态是否安全。如果是安全的，就实际分配资源，满足进程的此次请求；否则若新状态不安全。则进程

5、等待，对所申请的资源暂不予分配，并且把资源分配状态恢复到（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

6、<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） 设长度为的

7、工作向量：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 的个数*/ in

8、t 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

9、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 =

10、 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

11、 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+) fi

12、nishi=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+

13、; 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) /打

14、印安全路径 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

15、; 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);

16、 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<&l

17、t;"请输入进程的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;

18、 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&l