死锁的检测与解除

操作系统(实验报告)死锁的检测与解除姓名：*****学号：****专业班级：***学验日期：2011/12/2指导老师：***一、实验名称：死锁的检测和解除二、实验内容：编程实现对操作系统死锁的检测和解除，利用数据的动态输入，解锁时采用的是释放占用系统资源最大的进程的方法来实现。三、实验目的：熟悉死锁检测与的解除的算法，深入理解死锁的检测与解锁的具体方法，加深对死锁问题深刻记意。并且进一步掌握死锁的条件，死锁定理等相关知识。四、实验过程1.基本思想：利用资源分配图来理解此问题，可以认为此图就是由一组结点N和一组边E所组成的一个对偶G=(N1E)；把N分为互斥的两个子集进程P结点和资源R结点，进程结点集和资源结点集，凡是属于E中的一个边，都连接着P中的一个结点和R中的一个结点由P中的一个结点指向R中的一个结点是资源请求边，而由R中的一个结点指向P中的一个结点的边称为资源分配边，在这个图中找到一个既不阻塞又不独立的结点Pi，如果是在顺利的情况下，则该进程可以获得足够资源而继续运行，运行完释放所有资源，这就可以说是消除了它的请求边和分配边，让它成为一个孤立的点，再继续，分配给请求资源的进程……这样循环下去直到所有的进程都能成为孤立的点，或是出现了无法消除的环状，若是出现了环状，即出现了死锁，采取释放占用资源最多的进程的方法来解决问题，直到最后所有的进程结点P均成为孤立的点。解锁才算成功，程序才能结束。2.主要数据结构：(1)可利用资源向量Available.这是一个含有m类资源的数组，用来表示每种资源可用的的数量。(2)把不占用任何资源，且没有申请资源的进程，列入数组finish中，并赋值true。(3)从进程集合中找到一个Request=Work的进程，做如下的处理：将其资源分配图简化，释放出资源，增加Work的量，做Work=Work+Allocation并将它的标志位finish也设为true.(4)如果不能把所有的进程标志位都赋值为true，则出现了死锁，开始采取解锁的方案。在此我选用的是释放占用资源最多的进程的方法，如果某个进程的Request=Work则可以做Work=Work+Allocation运算并将该进程标志位改成true。这样循环下去，若还不能解锁，则按上述方式再撤消一个进程，如此反复，直到死锁解除。3.输入输出每次开始运行程序，则要求用户开始输入进程的个数，资源源种类，可用资源量Available，及各个进程占有的各个资源的数量和请求数量，最后用循环将此时的状态输出，并判断是否有死锁，若有，则自动撤消进程解锁，若无，则直接输出无死锁的提示，并询问用户是否还要继续运行成序。4.程序流程图5.截屏有死锁的情况：有死锁的情况6.源程序：packagecom.Deadlock;importjava.util.*;publicclassDeadlock{publicintAvailable[];publicbooleanp[],L[];intm,n,k=0,c;publicstaticintcount=0;publicintWork[];publicintRequest[][];publicintAllocation[][];booleanfinish[];publicDeadlock()无死锁的情况{m=15;n=15;k=0;c=0;finish=newboolean[15];Available=newint[15];p=newboolean[15];L=newboolean[15];//publicstaticintcount=0;Work=newint[15];Request=newint[15][15];Allocation=newint[15][15];}booleancompare(intindex){booleanf=false;intt=0;for(inti=0;im;i++){if(Request[index][i]Work[i]){t++;break;}}if(t==0){f=true;}else{f=false;}returnf;}voidInput(){Scannersc=newScanner(System.in);System.out.println(请输入进程数：);n=sc.nextInt();System.out.println(请输入资源的各类数：);m=sc.nextInt();Available=newint[m];Request=newint[n][m];Allocation=newint[n][m];System.out.println(请输入各资源可用的数量：);for(inti=0;im;i++){Available[i]=sc.nextInt();}System.out.println(请输入各个进程占有的资源数量的+n+*+m+的矩阵：);for(inti=0;in;i++){for(intj=0;jm;j++){Allocation[i][j]=sc.nextInt();}}System.out.println(请输入各进程请求各资源的数量+n+*+m+的矩阵:);for(inti=0;in;i++){for(intj=0;jm;j++){Request[i][j]=sc.nextInt();}}for(inti=0;im;i++)Work[i]=Available[i];}voidOutput(){System.out.println(您输入各资源的可用数量是：);for(inti=0;im;i++){System.out.print(Available[i]+);}System.out.println();System.out.println(各个进程占有的资源分别是+n+*+m+的矩阵：);for(inti=0;in;i++){System.out.print(P+(i+1)+:);for(intj=0;jm;j++){System.out.print(Allocation[i][j]+);}System.out.println();}System.out.println(各个进程请求各资源的数量分别是+n+*+m+的矩阵：);for(inti=0;in;i++){System.out.print(P+(i+1)+:);for(intj=0;jm;j++){System.out.print(Request[i][j]+);}System.out.println();}}booleancheck(){inti,j,k=0;booleanff=false;for(i=0;in;i++){finish[i]=true;for(j=0;jm;j++){if(Allocation[i][j]0||Request[i][j]0)finish[i]=false;}}booleanflag=true;while(flag){flag=false;for(i=0;in;i++){if(!finish[i]&&compare(i)){for(j=0;jn;j++){Work[j]+=Allocation[i][j];}finish[i]=true;p[i]=false;flag=true;break;}}}if(!flag){for(i=0;in;i++)if(!finish[i]){k++;}}if(k0)ff=false;elseif(k==0)ff=true;returnff;}voiddelock(){inti,j,flag=0;int[]sum=newint[n];for(i=0;in;i++)sum[i]=0;for(i=0;in;i++)if(p[i]){for(j=0;jm;j++)sum[i]=sum[i]+Allocation[i][j];//Allocation[i][j]=0;}intmax=sum[0];for(i=1;in;i++){if(maxsum[i]){max=sum[i];flag=i;}}System.out.println(撤消占资源源最大的进程：+flag);System.out.println();for(j=0;jm;j++)Work[j]+=Allocation[flag][j];finish[flag]=true;p[flag]=false;if(check()){System.out.println(成功解锁！);}else{delock();}}voidoperate(){booleanflag=check();if(flag){System.out.println(不会发生死锁！);}else{System.out.println(死锁进程如下：);for(inti=0;in;i++)if(!p[i])System.out.println(i+);delock();}}publicstaticvoidmain(String[]args){//TODOAuto-generatedmethodstubScannerin=newScanner(System.in);Deadlockdl=newDeadlock();booleanflag=true;while(flag){dl.Input();dl.Output();dl.operate();System.out.println(请问还要继续玩么？);System.out.println(继续按Y，否则请按N?);Strings=in.nextLine();if(s.equals(Y)){flag=true;}elseif(s.equals(N)){flag=false;}else{System.out.println(输入异常，被破停止！);System.exit(0);}}}}7.实验小结：通过对死锁的检测与解除的深入学习，我更加清晰的了解了死锁的运行机制，及产生死锁的必要条件，以及死锁会带来的种种问题，同时，我不光是认识到了问题的存在，也学会了用几种方法去解决死锁的问题，提高了我的逻辑思维的缜密性，为我今后在此方面能做的更细致思考打下了良好的基础，另一方面，也让我懂得了，要用学过的知识去联系实际问题，用所学的知识去分析，去解决现实中的问题，才能更加深入的学习，真正做到学以致用。