实验报告四 银行家算法

实验报告三——银行家算法姓名：丛菲学号：20100830205班级：信息安全二班一、实习内容运用某种高级语言（如C或C++）模拟银行家算法的处理过程。二、实习目的银行家算法是避免死锁的代表性算法。本实习旨在加深了解有关资源申请、避免死锁、状态安全性等概念，并体会和运用避免死锁的具体实施方法。然后依照本实习，自行设计模拟程序。三、实习题目银行家算法的模拟提示1我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源。当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。提示2安全状态：如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。不安全状态:不存在一个安全序列。不安全状态一定导致死锁。安全序列：一个进程序列{P1，…，Pn}是安全的，如果对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj(j<i)当前占有资源量之和。提示3设requesti为进程p[i]的请求向量，如果requesti[j]=K，表示进程p[i]需要K个Rj资源。当系统发出请求后，系统按下述步骤开始检查：1）如果requesti[j]<=need[i][j],转向步骤2；否则报告出错，申请的资源已经大于它需要的最大值。2）如果requesti[j]<=available[j],转向步骤3；否则报告出错，尚无足够的资源。3）系统试探着把资源分配给p[i]，并修改下列数据结构中的值：available[j]=available[j]-request[j]allocation[i][j]=allocation[i][j]+request[j]need[i][j]=need[i][j]-request[j]4）系统进行安全性算法，检查此次分配后，系统是否还处于安全状态，若安全，把资源分配给进程p[i]；否则，恢复原来的资源分配状态，让进程p[i]等待。提示4安全性算法：intwork[RESOURCE_NUMBER]；boolfinish[PROCESS_NUMBER]；1)Work=Available;Finish=false;2)寻找满足条件的i：A、Finish[i]=false;B、Need[i]≤Work;如果不存在，则转4)3)Work:=Work+Allocation[i]；Finish[i]:=true；转2)4)若对所有i,Finish[i]=true,则系统处于安全状态，否则处于不安全状态

提示5(银行家算法的程序流程图)四、实现代码为：#include<stdio.h>#include<stdlib.h>#defineN100intsource[N];intprocessMax[N][N];intprocessNeed[N][N];intallocation[N][N];intavailable[N];intavailable1[N];intwork[N];intrequire[N]={0};voidprint(inta,intb);voidreq(inta,intb);voidcheck(inta,intb);voidyhj(inta,intb){ inti=0,j=0,k=0,z=0; printf("Pleaseinputthe%dsources'number:\n",a); for(i=0;i<a;i++) { printf("thenumberofsource%d:",i+1); scanf("%d",&source[i]); work[i]=source[i]; available[i]=source[i]; } for(j=0;j<b;j++) { printf("pleaseinputthenumberofeveryresourceofprocess%d\n",j+1); for(k=0;k<a;k++) { printf("Thenumberofmaxresource%d:",k+1); scanf("%d",&processMax[j][k]); } } //是否出现单个需要资源大于当个总资源 for(i=0;i<b;i++) { for(j=0;j<a;j++) { if(processMax[i][j]>source[j]) { printf("\n"); break; } } if(j!=a) break; } //出现 if(i!=b) { printf("Emergenceofindividualneedsresourcesthanthatofsingleresource,cannotundertakeallocation\n"); return; } //没出现 else { for(j=0;j<b;j++) { printf("pleaseinputthenumberofeveryresourceofprocess%d\n",j+1); for(k=0;k<a;k++) { printf("Thenumberofallocatedresource%d:",k+1); scanf("%d",&allocation[j][k]); processNeed[j][k]=processMax[j][k]-allocation[j][k]; available[k]-=allocation[j][k]; } } } //银行家算法 print(a,b); req(a,b);}voidprint(inta,intb) //各个矩阵的打印{ inti=0,j=0,k=0,z=0; printf("\n\nresourceavailablesource\n"); for(i=0;i<a;i++) { printf("%4d%4d\n",source[i],available[i]); } printf("processMaxallocationNeed\n"); for(i=0;i<b;i++) { printf("P%d",i); for(j=0;j<a;j++) { printf("%2d",processMax[i][j]); } printf(""); for(j=0;j<a;j++) { printf("%2d",allocation[i][j]); } printf(""); for(j=0;j<a;j++) { printf("%2d",processNeed[i][j]); } printf("\n"); } for(i=0;i<b;i++) { for(j=0;j<a;j++) { if(processNeed[i][j]<0) printf("TheallocatedsourceislagerthanmaxofP%d\n",i); } }}voidreq(inta,intb){ inti=0,j=0,k=0,z=0; intjch=0; intshuxu[N]={0}; do{ printf("Pleaseinputthenumberofprocesswhichwanttoaskforsource(1~%d):",b); scanf("%d",&jch); if(!(jch-1>=0&&jch-1<=b)) printf("error,pleaseinputagain"); }while(!(jch-1>=0&&jch-1<b)); for(i=0;i<a;i++) { printf("Pleaseinputthenumberofsource%dyouwanttoaskfor:",i+1); scanf("%d",&require[i]); if(require[i]<=processNeed[jch-1][i]&&require[i]<=available[i]) { available[i]-=require[i]; allocation[jch-1][i]+=require[i]; processNeed[jch-1][i]-=require[i]; work[i]-=require[i]; } else { printf("therequiresourceoftheprocessislargerthanneedorexisting,pleaseinputagain:\n"); i--; } } for(i=0;i<a;i++) available1[i]=available[i]; check(a,b); printf("\n");}voidcheck(inta,intb){ inti=0,j=0,k=0,z=0; intjch=0; intx; intshuxu[N]={0}; intfinish[N]={0}; for(i=0;i<b;i++) { for(j=0;j<b;j++) { if(finish[j]==1) continue; else { for(k=0;k<a;k++) { if(processNeed[j][k]>available[k]) break; } if(k==a) { finish[j]=1; shuxu[j]=++z; for(x=0;x<a;x++) { available[x]+=allocation[j][x]; } j=0; } } for(k=0;k<b;k++) { if(finish[k]==0) break; } if(k==b) break; } } printf("\n"); for(i=0;i<a;i++) available[i]=available1[i]; for(j=0;j<b;j++) { if(shuxu[j]==0) { printf("Thereisarisk,donotagreewiththeresourcerequest\n"); for(i=0;i<a;i++) { available[i]+=require[i]; allocation[jch-1][i]-=require[i]; processNeed[jch-1][i]+=require[i]; work[i]+=require[i]; } return; } } printf("Agreetotheresourcerequest,Safesequenceis(accordingtotheprocessofsignalsorting):\n"); //安全序列打印 for(j=1;j<b+1;j++) { for(i=0;i<b;i++) { if(shuxu[i]==j) { p