操作系统-实验四

实验四银行家算法（一）教学要求掌握处理死锁的方法，掌握银行家算法的实现（二）知识点提示死锁的概念，死锁产生的原因和条件，处理死锁的方法，银行家算法，安全状态和不安全状态，安全性算法（三）教学内容银行家算法的模拟实现实验步骤:（1）定义数据结构:allocation[][];//分配矩阵available[];//可用资源向量need[][];//需求矩阵request[];//资源请求向量（2）定义函数：voidbank_arithmetic(inti,intrequest[])//银行家算法voidisSafe();//安全性算法主函数中对可用资源向量，分配矩阵和需求矩阵进行初始化（输入数据参照课本P113的例题），输入请求资源的进程编号以及请求的资源向量，通过调用银行家算法判断是否可以把资源分配给请求资源的进程。（3）银行家算法的执行步骤：设Requesti是进程Pi的请求向量。若Requesti[j]=k，表示进程Pi需要k个j类资源。当Pi发出资源请求后，系统按下述步骤进行检查：①若Requesti≤Needi，则转②；否则，认为出错。因为它所需要的资源数已超过它所宣布的最大值。②若Requesti≤Available，则转③；否则，表示系统中尚无足够的资源，Pi必须等待。③系统试探把要求的资源分配给进程Pi，并修改下面数据结构中的数值。Available=Available–RequestiAllocationi=Allocationi+RequestiNeedi=Needi–Requesti④系统执行安全性算法，检测此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分给进程Pi；否则，将试探分配作废，恢复资源状态，让Pi等待。（4）安全性算法的执行步骤：①设置两个向量work和finish工作向量work，它表示系统可提供给进程继续运行的各类资源数，含有m个元素，其初始值为：work[j]=available[j]。完成向量finish，它表示系统是否有足够资源使进程推进完成，开始执行安全性算法时，Finish[i]=false;当有足够资源分配给进程Pi，Pi推进完成时，令Finish[i]=true。②从进程集合中找到一个进程，其满足：Finish[i]=falseNeed[i,j]≤Work[j]如找到则执行步骤③，找不到则执行步骤④。③当进程Pi获得资源后，便可以向前推进，直至完成，并释放出分配给它的全部资源，故应执行：Work[j]=Work[j]+Allocation[i,j];Finish[i]=true;执行步骤②。④若所有进程的Finish都为true，则系统为安全状态；否则，系统为不安全状态。实验程序：#includestdio.h#defineM3#defineN5intavailable[]={3,3,2};intallocation[N][M]={{0,1,0},{2,0,0},{3,0,2},{2,1,1},{0,0,2}};intneed[N][M]={{7,4,3},{1,2,2},{6,0,0},{0,1,1},{4,3,1}};voidbanker_arithmetic(inti,intrequest[]){intisSafe();intj,k,l;printf(进程P%d请求资源，资源请求向量为:\n,i);for(j=0;jM;j++)printf(%d,request[j]);printf(\n);j=0;while(jM){if(request[j]=need[i][j])j++;elsebreak;}if(j==M){k=0;while(kM)if(request[k]=need[i][k])k++;elsebreak;if(k==M){for(l=0;lM;l++){available[l]=available[l]-request[l];allocation[i][l]=allocation[i][l]+request[l];need[i][l]=need[i][l]-request[l];}if(isSafe())printf(分配是安全的，可以把资源分配给p%d\n,i);else{printf(分配是不安全的，不能把资源分配给P%d\n,i);for(l=0;lM;l++){available[l]=available[l]+request[l];allocation[i][l]=allocation[i][l]-request[l];need[i][l]=need[i][l]+request[l];}}}}printf(Allocation:);for(j=0;jN;j++){for(k=0;kM;k++)printf(%d,allocation[j][k]);printf(\n);}printf(Need:);for(j=0;jN;j++){for(k=0;kM;k++)printf(%d,need[j][k]);printf(\n);}printf(Available:\n);for(j=0;jM;j++)printf(%d,available[j]);printf(\n);i++;}intisSafe(){intwork[M];inti,j,k,l=0,a=0;intfinish[]={0,0,0,0,0};for(i=0;iM;i++){work[i]=available[i];}while(lN||aN){i=0;while(iN){if(finish[i]==0){j=0;while(jM)if(need[i][j]=work[j])j++;elsebreak;if(j==M){printf(P%d,i);for(k=0;kM;k++){work[k]=work[k]+allocation[i][k];}printf(\n);finish[i]=1;l++;}}i++;}a++;}for(i=0;iN;i++)if(finish[i]==0)return0;return1;}intmain(){inti=1;intrequest[]={1,0,2};banker_arithmetic(i,request);return0;}实验结果：进程p1请求资源，资源请求向量为：102p1p3p4p0p2分配是安全的，可以把资源分配给p1Allocation:010302302211002Need:743020600011431Available:230Pressanykeytocontinue.（四）思考题1、死锁产生的原因是什么？死锁产生的原因有竞争不可抢占型资源引起死锁竞争可消耗资源引起死锁进程推进顺序不当引发死锁2、处理死锁的方法有哪些？预防死锁：通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个。避免死锁：在系统的资源分配过程中，用某种方法去防止系统进入不安全状态（可能会导致思索的状态），从而避免发生死锁。检测和解除死锁：当进程申请资源时，不进行任何限制，即允许死锁发生。但要求系统定期或不定期检测是否有死锁发生。当检测到系统中已发生死锁时，将进程从死锁状态中解脱出来