计算机操作系统实验五二维数组实现银行家...(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;im;i+) printf(p%d,sli); coutendl; return true; el

6、se 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;in;i+) cout ai; coutendl;对于安全算法情况如下：（1） 设长度为的工作向量：work=(w1,w2 ,wm)和长度为n的工作向量finish=(f1,f2,fn),并令work*=available*;精品.finishi=false;（2） 查找这样的进程i使其满足：finishi

7、=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;im;i+) finishi=false; 精品.n=m; while(n-) for(i=

8、0;i=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 #include #include #include#define m 4 /*进程数*/#define n 3 /*资源数*/int availablen = 1,1,2; /系统可用资源向量int maxmn = 3,2,2, 6,1,3

9、, 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;in;i+) if(aibi) return false; return true;精品./一维数组加法/a = a + bvoid add(int *a,int *b,int n) int

10、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;in;i+) ai-=bi; /将数组b的值赋给a，n为数组的大小精品.void assign(int *a,int *b,int n) int i=0; for(i=0;in;i+) ai=bi; /sl 记录安全序列bool safe(int *sl) int i; int count=0; /*记录finishi = true 的个数*/ int n=0; int workn; bool fin

11、ishm; /work = av; assign(work,available,n); /初始化标记 finish for(i=0;im;i+) finishi=false;精品. /n为进程的个数/循环最多执行n次 n=m; while(n-) for(i=0;i=m) /全部进程都可安全执行（finish = true） return true; /判断能否满足进程i的要求 /work = needi ? if(finishi=false&compare(work,needi,n) /分配，待进程完成后再释放 add(work,allocationi,n); finishi=true; /

12、记录安全路径精品. 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,

13、n); /判断是否是安全状态 if(safe(sl) /打印安全路径 cout安全序列为:endl; for(i=0;im;i+) printf(p%d,sli); coutendl; /可以分配 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;in;i+) co

14、ut ai; 精品.coutendl;/显示系统信息void init() int i; cout该系统共有进程4个,n其对资源的需求和分配情况分别是:endl; for(i=0;im;i+) cout进程i资源最大需求:; print(maxi,n); coutendl; for(i=0;im;i+) cout进程i已经分配资源:; print(allocationi,n); coutendl; cout系统可用资源数量:ntendl; print(available,n);精品./输入void input(int *r,int n,int *id) char ch; cout请输入进程的i

15、d(0 3):endl; ch=getche(); *id=ch-0x30; coutn请输入对0类资源的申请数量:endl; ch=getche(); r0=ch-0x30;coutn请输入对1类资源的申请数量:endl; ch=getche(); r1=ch-0x30; coutn请输入对2类资源的申请数量:3|id0|r10|r20|r30) return false; else return true; int main() /进程id int id; /控制字符 int r3; char es; char control; /显示开始信息 init(); /输入申请信息 input(

16、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，所以