实验二：死锁的检测和预防

实验二：死锁的检测和预防一、实验目的1、进一步了解进程的并发执行。2、加强对进程死锁的理解3、是用银行家算法完成死锁检测二、实验内容给出进程需求矩阵C、资源向量R以及一个进程的申请序列。使用进程启动拒绝和资源分配拒绝（银行家算法）模拟该进程组的执行情况。要求：初始状态没有进程启动计算每次进程申请是否分配？如：计算出预分配后的状态情况（安全状态、不安全状态），如果是安全状态，输出安全序列。每次进程申请被允许后，输出资源分配矩阵A和可用资源向量V。每次申请情况应可单步查看，如：输入一个空格，继续下个申请三、实验环境VC++四、实验原理及实验思路1、安全状态：如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。2、不安全状态:不存在一个安全序列。不安全状态一定导致死锁。安全序列：一个进程序列{P1，…，Pn}是安全的，如果对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj(ji)当前占有资源量之和。3、银行家算法：我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。4、银行家算法的思路：1),进程一开始向系统提出最大需求量.2),进程每次提出新的需求(分期贷款)都统计是否超出它事先提出的最大需求量.3),若正常,则判断该进程所需剩余剩余量(包括本次申请)是否超出系统所掌握的剩余资源量,若不超出,则分配,否则等待.5、银行家算法的数据结构：1),系统剩余资源量A[n],其中A[n]表示第I类资源剩余量.2),各进程最大需求量,B[m][n],其中B[j][i]表示进程j对i类资源最大需求.3),已分配资源量C[m][n],其中C[j][i]表示系统j程已得到的第i资源的数量.4),剩余需求量.D[m][n],其中D[j][i]对第i资源尚需的数目.五、流程图银行家算法：提出进程i的请求向量Resquest[*]Resquest[*]=available[*]ERRORalloc[i][*]+Request[*]=claim[i][*]YesNoERRORnoavailable[*]-=Request[*]alloc[i][*]+=Request[*]yesis_safe()available[*]+=Request[*]alloc[*]-=Request[*]No同意本次分配拒绝本次分配yes安全检测：tmp_avail[*]=available[*]寻找进程k满足Claim[k][*]-alloc[k][*]tmp_avail[*]是否存在这样的进程返回FALSEtmp_avail[*]+=alloc[*]标记进程k是否所有的进程都被标记返回TRUE六、源代码#includestring.h#includestdio.h#includestdlib.h#defineM5#defineN3#defineFALSE0#defineTRUE1/*M个进程对N类资源最大资源需求量*/intMAX[M][N]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};/*系统可用资源数*/intAVAILABLE[N]={10,5,7};/*M个进程对N类资源已经分配数量*/intALLOCATION[M][N]={{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0}};/*M个进程还需要N类资源的资源量*/intNEED[M][N]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};/*M个进程还需要N类资源的资源量*/intRequest[N]={0,0,0};voidmain(){inti=0,j=0;charflag='Y';charfinishFlag='Y';voidshowdata();voidchangdata(int);voidrstordata(int);intchkerr(int);showdata();while(finishFlag=='Y'||finishFlag=='y')//可以分配资源{i=-1;while(i0||i=M)//判断申请的资源号是否有效{printf(请输入需申请资源的进程号（从0到%d，否则重输入!）:,M-1);scanf(%d,&i);if(i0||i=M)printf(输入的进程号不存在，重新输入!\n);}printf(请输入进程%d申请的资源数\n,i);for(j=0;jN;j++){printf(资源%d:,j);scanf(%d,&Request[j]);if(Request[j]NEED[i][j])//进程申请资源数大于进程还需要的资源{printf(进程%d申请的资源数大于进程%d还需要%d类资源的资源量!申请不合理，出错!请重新选择!\n,i,i,j);flag='N';break;}else{if(Request[j]AVAILABLE[j])//进程申请资源数大于系统可用该类资源量{printf(进程%d申请的资源数大于系统可用%d类资源的资源量!申请不合理，出错!请重新选择!\n,i,j);flag='N';break;}}}if(flag=='Y'||flag=='y'){intresult;changdata(i);result=chkerr(i);if(result==1){rstordata(i);showdata();}elseshowdata();}//else//showdata();printf(\n);printf(是否继续银行家算法演示,按'Y'或'y'键继续,按'N'或'n'键退出演示:);getchar();scanf(%c,&finishFlag);}}voidshowdata()//显示各类资源的分配情况{inti,j;printf(系统可用的资源数为:\n);printf();for(j=0;jN;j++){printf(资源%d:%d,j,AVAILABLE[j]);}printf(\n);printf(各进程还需要的资源量:\n);for(i=0;iM;i++){printf(进程%d,i);for(j=0;jN;j++){printf(资源%d:%d,j,NEED[i][j]);}printf(\n);}printf(各进程已经得到的资源量:\n);for(i=0;iM;i++){printf(进程%d,i);for(j=0;jN;j++)printf(资源%d:%d,j,ALLOCATION[i][j]);printf(\n);}}voidchangdata(intk){intj;for(j=0;jN;j++){AVAILABLE[j]=AVAILABLE[j]-Request[j];ALLOCATION[k][j]=ALLOCATION[k][j]+Request[j];NEED[k][j]=NEED[k][j]-Request[j];}}voidrstordata(intk){intj;for(j=0;jN;j++){AVAILABLE[j]=AVAILABLE[j]+Request[j];ALLOCATION[k][j]=ALLOCATION[k][j]-Request[j];NEED[k][j]=NEED[k][j]+Request[j];}}intchkerr(ints)//检查是否能够分配该资源{intWORK,FINISH[M],temp[M];inti,j,k=0;for(i=0;iM;i++)FINISH[i]=FALSE;for(j=0;jN;j++){WORK=AVAILABLE[j];i=s;while(iM){if(FINISH[i]==FALSE&&NEED[i][j]=WORK){WORK=WORK+ALLOCATION[i][j];FINISH[i]=TRUE;temp[k]=i;k++;i=0;}else{i++;}}for(i=0;iM;i++)if(FINISH[i]==FALSE){printf(\n系统不安全!!!本次资源申请不成功!!!\n\n);return1;}}printf(\n经安全性检查，系统安全，本次分配成功。\n\n);printf(本次安全序列：);for(i=0;iM;i++){printf(进程%d-,temp[i]);}printf(\n);return0;}七、运行结果及其分析初始状态资源1的申请数2大于原可用资源数1，分配不成功资源分配成功的情况安全检测出可能的死锁问题，拒绝分配资源八、实验总结通过使用银行家算法，完成了死锁检测和资源分配，了解了进程的并发执行情况