操作系统大作业-银行家算法

编程验证银行家算法一、实验目的银行家算法是避免死锁的一种重要方法，本设计要求编程实现银行家算法程序。了解银行家算法运行的规律币，加深对银行家算法的了解。二、实验原理银行家算法的思路:1)、进程一开始向系统提出最大需求量.2)、进程每次提出新的需求(分期贷款)都统计是否超出它事先提出的最大需求量.3)、若正常，则判断该进程所需剩余剩余量(包括本次申请)是否超出系统所掌握的剩余资源量,若不超出,则分配,否则等待.银行家算法的数据结构.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资源尚需的数目.银行家算法流程:当某时刻,某进程时,提出新的资源申请,系统作以下操作:1)、判定E[n]是否大于D[j][n],若大于,表示出错.2)、判定E[n]是否大于系统剩余量A[n],若大于,则该进程等待.3)、若以上两步没有问题,尝试分配,即各变量作调整.4)、按照安全性推测算法,判断,分配过后,系统是否安全,若安全,则实际分配,否则,撤消分配,让进程等待.安全性检测算法1)、先定义两个变量,用来表示推算过程的数据.F[n]=A[n],表示推算过程中,系统中剩余资源量的变化.J[n]=False表示推算过程中各进程是否假设已完成2)、流程:在剩余的进程中(在推算)过程中,一些进程假设已完成,查找D[j][n]=F[n]的进程,找到后令J[j]=True(假设该进程完成),F[n]+D[j][n](该进程所占资源释放),如此循环执行.若最后,所有的F[n]=True(在推算过程中,所有进程均可以完成),则表示(分配过后)系统是安全的,否则系统是不安全的.三、实验内容在codeblock编译器下编写代码首先现编写一个库文件‘s.h’，定义一个结构体：typedefstruct{intA;intB;intC;}RESOURCE;结构体里面的三个域分别表示三种资源的数量。按书中的数据初速化三个矩阵RESOURCEMax[PROCESSES_NUMBER]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};//最大需求矩阵RESOURCEAllocation[PROCESSES_NUMBER]={{0,1,0},{2,0,0},{3,0,2},{2,1,1},{0,0,2}};//已分配资源数矩阵RESOURCENeed[PROCESSES_NUMBER]={{7,4,3},{1,2,2},{6,0,0},{0,1,1},{4,3,1}};//需求矩阵RESOURCEAvailable={3,3,2};//可用资源向量intsafe[PROCESSES_NUMBER];上面定义好数据后就可以开始运行代码。运行后如图：可以得到T0时刻的安全序列是(P1,P3,P4,P2,P0)这里选择输入0110，使Request0为(1,1,0)输出结果为可以得到安全序列为（P1,P3,P0,P2,P4）继续输入2157，使Request2为（1,5,7）输出结果为因为请求向量大于需求向量，所以此时分配失败。继续输入1102，使Request1为(1,0,2)此时系统进入不安全状态，有可能导致死锁。附录：主函数代码#includestdio.h#includestring.h#includes.h//进行试探分配voidProbeAlloc(intprocess,RESOURCE*res){Available.A-=res-A;Available.B-=res-B;Available.C-=res-C;Allocation[process].A+=res-A;Allocation[process].B+=res-B;Allocation[process].C+=res-C;Need[process].A-=res-A;Need[process].B-=res-B;Need[process].C-=res-C;}//若进入不安全状态，则返回voidRollBack(intprocess,RESOURCE*res){Available.A+=res-A;Available.B+=res-B;Available.C+=res-C;Allocation[process].A-=res-A;Allocation[process].B-=res-B;Allocation[process].C-=res-C;Need[process].A+=res-A;Need[process].B+=res-B;Need[process].C+=res-C;}//安全性检查boolSafeCheck(){RESOURCEWork=Available;boolFinish[PROCESSES_NUMBER]={false,false,false,false,false};inti;intj=0;for(i=0;iPROCESSES_NUMBER;i++){//是否已检查if(Finish[i]==false){//是否有足够的资源分配if(Need[i].A=Work.A&&Need[i].B=Work.B&&Need[i].C=Work.C){//有则完成分配，并将资源全部回收Work.A+=Allocation[i].A;Work.B+=Allocation[i].B;Work.C+=Allocation[i].C;Finish[i]=true;safe[j++]=i;i=-1;}}}//如果所有的Finish向量都为true则处于安全状态，否则为不安全状态for(i=0;iPROCESSES_NUMBER;i++){if(Finish[i]==false){returnfalse;}}returntrue;}//资源分配请求boolrequest(intprocess,RESOURCE*res){//request向量需小于Need矩阵中对应的向量if(res-A=Need[process].A&&res-B=Need[process].B&&res-C=Need[process].C){//request向量需小于Available向量if(res-A=Available.A&&res-B=Available.B&&res-C=Available.C){ProbeAlloc(process,res);if(SafeCheck()){returntrue;}else{printf(安全性检查失败：系统将进入不安全状态，将有可能引起死锁。\n);RollBack(process,res);}}else{printf(安全性检查失败：请求向量大于可利用资源向量。\n);}}else{printf(安全性检查失败：请求向量大于需求向量。\n);}returnfalse;}//输出资源分配表voidPrint(){printf(ProcessMaxAllocationNeedAvailable\n);printf(ABCABCABCABC\n);printf(P0%d%d%d%d%d%d%d%d%d%d%d%d\n,Max[0].A,Max[0].B,Max[0].C,Allocation[0].A,Allocation[0].B,Allocation[0].C,Need[0].A,Need[0].B,Need[0].C,Available.A,Available.B,Available.C);printf(P1%d%d%d%d%d%d%d%d%d\n,Max[1].A,Max[1].B,Max[1].C,Allocation[1].A,Allocation[1].B,Allocation[1].C,Need[1].A,Need[1].B,Need[1].C);printf(P2%d%d%d%d%d%d%d%d%d\n,Max[2].A,Max[2].B,Max[2].C,Allocation[2].A,Allocation[2].B,Allocation[2].C,Need[2].A,Need[2].B,Need[2].C);printf(P3%d%d%d%d%d%d%d%d%d\n,Max[3].A,Max[3].B,Max[3].C,Allocation[3].A,Allocation[3].B,Allocation[3].C,Need[3].A,Need[3].B,Need[3].C);printf(P4%d%d%d%d%d%d%d%d%d\n,Max[4].A,Max[4].B,Max[4].C,Allocation[4].A,Allocation[4].B,Allocation[4].C,Need[4].A,Need[4].B,Need[4].C);printf(\n);}intmain(){intch;printf(检查初始状态:);if(SafeCheck()){printf(系统处于安全状态。\n);printf(T0时刻的存在安全序列是{P%d,P%d,P%d,P%d,P%d}。\n,safe[0],safe[1],safe[2],safe[3],safe[4]);}else{printf(系统处于不安全状态。程序退出\n);gotoover;}do{intprocess;RESOURCEres;Print();printf(请输入数据（如输入0123则为P0[123])：);scanf(%d%d%d%d,&process,&res.A,&res.B,&res.C);if(request(process,&res)){printf(分配成功。\n);printf(安全序列是{P%d,P%d,P%d,P%d,P%d}。\n,safe[0],safe[1],safe[2],safe[3],safe[4]);}else{printf(分配失败。\n);}printf(是否继续分配？(Y/N):);fflush(stdin);ch=getchar();}while(ch=='Y'||ch=='y');over:printf(执行完毕。);return0;}