【OS学习笔记】死锁总结（含银行家算法的实现Java版）

小鱼儿 2022-10-14 13:52 127阅读 0赞

一、背景

> 作为一个合格的程序员，必然会涉及到进行代码的规范以及对性能的调优，而调优主要是除了负载均衡、缓存优化、数据库优化（例如建立索引）非代码层面外，还要代码层面的调用，那必须做到对OS比较熟悉，尽量少写烂代码，合理调用OS提供的库函数以及计算机所提供的CPU、内存等重要资源。

二、死锁的基本概念

> 1.概念：多个并发进程因争夺系统资源而产生相互等待的现象。

> 2.原理： 当一组进程中的每个进程都在等待某个事件发生，而只有这组进程中的其他进程才能触发该事件，这就称这组进程发生了死锁。  
> 本质原因：  
> 1）、系统资源有限。  
> 2）、进程推进顺序不合理。

> 3.死锁产生的4个必要条件  
> 1、互斥： 某种资源一次只允许一个进程访问，即该资源一旦分配给某个进程，其他进程就不能再访问，直到该进程访问结束。  
> 2、占有且等待： 一个进程本身占有资源（一种或多种），同时还有资源未得到满足，正在等待其他进程释放该资源。  
> 3、不可抢占： 别人已经占有了某项资源，你不能因为自己也需要该资源，就去把别人的资源抢过来。  
> 4、循环等待： 存在一个进程链，使得每个进程都占有下一个进程所需的至少一种资源。

> 4.破坏死锁的方法  
> 原理：破坏以上四个条件之一，即可。

<table> 
 <thead> 
  <tr> 
   <th>`</th> 
   <th>分配策略</th> 
   <th>可能存在的模式</th> 
   <th>优点</th> 
   <th>缺点</th> 
   <th>代表策略</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>死锁预防</td> 
   <td>保守，宁可资源闲置</td> 
   <td>一次性请求所有资源，按序分配</td> 
   <td>使用于突发处理，不必进行掠夺</td> 
   <td>效率低，剥夺次数过多</td> 
   <td>资源有序分配法</td> 
  </tr> 
  <tr> 
   <td>死锁避免</td> 
   <td>折中，在运行时判断是否死锁</td> 
   <td>寻找可能的安全允许顺序</td> 
   <td>不必进行掠夺</td> 
   <td>必须知道将来的资源</td> 
   <td>银行家算法（破坏循环等待条件）</td> 
  </tr> 
  <tr> 
   <td>死锁检测</td> 
   <td>宽松，允许则分配</td> 
   <td>定期检测死锁是否已经发生</td> 
   <td>允许对死锁进行现场处理</td> 
   <td>通过剥夺解除死锁，造成损失</td> 
   <td>死锁检测算法、资源分配图化简法、资源剥夺法（解除法，破坏请求保持条件）、死锁定理</td> 
  </tr> 
 </tbody> 
</table>

三、银行家算法实现

银行家算法中的数据结构  
为了实现银行家算法，必须设置以下四个数据结构:  
（1）可利用资源向量Available:其初始值是系统中所配置的该类全部可用资源的数目。  
（2）最大需求矩阵Max:它定义了系统中n个进程中的每一个进程对m类资源的最大需求。  
（3）分配矩阵Allocation:它定义了系统中每一类资源当前已分配给每一个进程的资源数。  
（4）需求矩阵Need：用一表示每一个进程尚需的各类资源数。

private final int maxPNum = 100;//最大进程数量
        private final int maxRNum = 100;//最大资源数量
        private int curPNum=0;
        private int curRNUm=0;
        //最大需求矩阵,0位需要空出来
        private int[][] maxMatrix={ 
                { 0,7,5,3},
                { 0,3,2,2},
                { 0,9,0,2},
                { 0,2,2,2},
                { 0,4,3,3}
        };
                //new int[maxPNum][maxRNum];
        // 分配矩阵,第一位空出来判断该进程是否已经分配成功无需再进行分配
        private int[][] allocateMatrix = { 
                { 0,0,1,0},
                { 0,2,0,0},
                { 0,3,0,2},
                { 0,2,1,1},
                { 0,0,0,2}
        };// 若第一位等于0则未成功完成该进程分配，若为1则表示该进程已经成功分配）申请
    
        private int[] allResources = { 10,5,7};
                        //new int[maxPNum][maxRNum];
        private int[] availableVector;

1.  安全性算法  
    （1）初始化安全序列为空  
    （2）从Need中寻找符合要求的进程请求，并将其加入安全序列  
    （3）在步骤（2）如出现无法寻找，并且安全序列并未满，则不安全，反之安全。若步骤（2）能够能够找到一个安全的进程请求，则加入安全序列，继续扫描，并设立一个flag标志表示还可以进行下一波扫描
2.  银行家算法  
    Request(i)是进程P(i)的请求向量。如果Requst(i)\[j\] = K,表示进程P(i)需要K个R(j)类型的资源。  
    （1）如果Request(i)\[j\] <= Need\[i,j\],便转向步骤2,否则出错；  
    （2）如果Request(i)\[j\] <= Available\[j\],便转向步骤3，否则出错；  
    （3）系统试探着把资源分配给进程P,并修改下面数据结构中的数值:  
    Available\[j\] = Avaliable\[j\] - Request(i)\[j\];  
    Allocation\[i,j\] = Allocation\[i,j\] + Request(i)\[j\];  
    Need\[i,j\] = Need\[i,j\] - Request(i)\[j\];  
    （4）执行\*\*安全性算法\*,检查此次资源分配后系统是否处于安全状态\*。安全则分配，否则分配作废
3.  代码实现

package practice.os.practice.threadmodule.deadlock;
    
    import java.util.ArrayDeque;
    import java.util.Queue;
    import java.util.Random;
    
    /** * @AUTHOR LYF * @DATE 2021/5/19 * @VERSION 1.0 * @DESC * */
    
    public class BankerDemo { 
        private final int maxPNum = 100;//最大进程数量
        private final int maxRNum = 100;//最大资源数量
        private int curPNum=0;
        private int curRNUm=0;
        //最大需求矩阵,0位需要空出来
        private int[][] maxMatrix={ 
                { 0,7,5,3},
                { 0,3,2,2},
                { 0,9,0,2},
                { 0,2,2,2},
                { 0,4,3,3}
        };
                //new int[maxPNum][maxRNum];
        // 分配矩阵,第一位空出来判断该进程是否已经分配成功无需再进行分配
        private int[][] allocateMatrix = { 
                { 0,0,1,0},
                { 0,2,0,0},
                { 0,3,0,2},
                { 0,2,1,1},
                { 0,0,0,2}
        };// 若第一位等于0则未成功完成该进程分配，若为1则表示该进程已经成功分配）申请
    
        private int[] allResources = { 10,5,7};
                        //new int[maxPNum][maxRNum];
        private int[] availableVector;
    
    
        //断点
        // 最大需求矩阵不会变，无需保存
    // private int[][] breakPointMaxMatrix={ 
    // {0,7,5,3},
    // {0,3,2,2},
    // {0,9,0,2},
    // {0,2,2,2},
    // {0,4,3,3}
    // };
        private int[][] breakPointAllocateMatrix;// 若第一位等于0则未成功完成该进程分配，若为1则表示该进程已经成功分配）申请
        private int[] breakPointAllResources;
        private int[] breakPointAvailableVector;
    
        void init(){ 
               curPNum = 5;//5个进程
               curRNUm = 3;//三个资源
               //allResources = new int[curRNUm];
               breakPointAllResources = new int[curRNUm];
               breakPointAvailableVector=new int[curRNUm];
               breakPointAllocateMatrix = new int[curPNum][curRNUm+1];
               availableVector=new int[curRNUm];
               System.out.println("init successfully...");       //...已初始化
        }
        // need矩阵无必要再设立？
        int[][] getNeedMatrix(){ 
            int [][]needMatrix = new int[maxPNum][maxRNum];
            for(int i = 0;i < curPNum;i++){ 
                for(int j = 0;j < curRNUm+1;j++){ //空了一位，因此需要加1
                    if(j==0){ 
                        if(allocateMatrix[i][j]==1){  //表示已经成功分配，无需再分配
                            needMatrix[i][j]=0;//表示该进程等待分配,若为1则说明已经成功分配，无需考虑再进行分配资源
                        }else{ 
                            // 表示该进程还未成功分配，还需要资源
                            needMatrix[i][j]=1;//表示该进程等待分配,若为1则说明已经成功分配，无需考虑再进行分配资源
                        }
                    }
                    else { 
                        needMatrix[i][j]=maxMatrix[i][j]-allocateMatrix[i][j];
                    }
                }
            }
            return needMatrix;
        }
    
        int[] getAvailableVector(){ 
            if(availableVector==null){ 
               System.err.println("System has‘nt allocated the resources,which is available.Please check " +
                       "the operator of init...");
            }
            int []availableV = new int[curRNUm];
            for(int j=1;j<curRNUm+1;j++){ 
                int sum=0;
                for(int i =0;i<curPNum;i++){ 
                   if(allocateMatrix[i][j]==1){ 
                       sum+=0;//已成功分配，（该进程无需资源）
                   }else{ 
                       sum+=allocateMatrix[i][j];
                   }
                }
    
                availableV[j-1]=allResources[j-1]-sum;//
                System.out.println("has allocated resource"+(j-1)+":"+sum+";available :"+availableV[j-1]);
            }
            return availableV;
        }
    
        void workCheck(){ 
             int[][] tempNeed = getNeedMatrix();
             int[] tempAvailable=getAvailableVector();
             System.out.println("check variable...");
             System.out.println("maxNeed is...");
             for(int[] i:maxMatrix){ 
                 for(int j:i){ 
                     System.out.print(j+"->");
                 }
                 System.out.println();
             }
             System.out.println("allocateMatrix is...");
             for(int[] i:allocateMatrix){ 
                for(int j:i){ 
                    System.out.print(j+"->");
                }
                System.out.println();
             }
             System.out.println("allResources is...");
             for(Integer i:allResources){ 
                 System.out.print(i+"->");
             }
             System.out.println();
             System.out.println("available is...");
             for(Integer i:tempAvailable){ 
                 System.out.print(i+"->");
             }
             System.out.println();
             System.out.println("need is ...");
             for(int i=0;i<curPNum;i++){ 
                 for(int j=0;j<curRNUm+1;j++){ 
                     System.out.print(tempNeed[i][j]+" ");
                 }
                 System.out.println();
             }
        }
    
        int counter =1;
        boolean isSafe(){ 
            Queue<String> queue = new ArrayDeque();//序列, 直接P+no即可，无需map映射
    
            //检查序列
            while (queue.size()!=curPNum){ //当序列未满时则一直检查 &&isContinueAllocate
                boolean isContinueAllocate=false; //无需设置标志位，直接找出口即可？,每次扫描前都置为false，判断该次扫描有无获取可成功分配的
                System.out.println("第"+counter+"次扫描");
                System.out.println();
    
                // 检查need矩阵与可获取资源对比
                for(int i=0;i<curPNum;i++)
                { 
                    int[] tempAvailable = getAvailableVector();
                    int[][] tempNeed = getNeedMatrix();//每进行进程分配之前都需要更新一下
                    if(tempNeed[i][0]==0){ //表示已经成功分配该进程，无再需资源
                        ///queue.add("P"+i); ,已添加过无需重复添加
                        if(!queue.contains("P"+i))
                            queue.add("P"+i);
                        if(queue.size()==curPNum){ 
                            while(!queue.isEmpty()){ 
                                System.out.print(queue.poll());
                            }
                            System.out.println();
                            return true;
                        }
                        continue;
                    }
    
    
                    boolean curFlag = true;// 判断当前进程是否可以成功分配
                    for(int j=0;j<curRNUm;j++)
                    { 
                         if(tempNeed[i][j+1]>tempAvailable[j]){ 
                             curFlag=false;
                         }
                        //if(tempNeed[i][j+1])
                    }
    
                    if(curFlag){ //可成功分配,进行序列添加,allocate调整 (有点贪心》)
    
                        // update allocateTable 和 available
                        allocateMatrix[i][0]=1;
                        for(int j=0;j<curRNUm;j++)
                        { 
                            availableVector[j]= allocateMatrix[i][j+1]+availableVector[j];
                            allocateMatrix[i][j+1]=0;//置零
                        }
                         queue.add("P"+i);
                         if (i==curPNum-1&&queue.size()==curPNum){ 
                             System.out.println("safe...");
                             System.out.println("safe sequence is ...");
                             while(!queue.isEmpty()){ 
                                 System.out.print(queue.poll());
                             }
                             System.out.println();
                             return true;
                         }
    
                         isContinueAllocate =true;//一旦出现成功分配的，则可以再进行一波扫描
                    }else{ // 不可成功分配，检查是否为最后一个且序列未满，若是则不安全，若不是则继续
                          // 不可分配，size必然不满
                         if(i==curRNUm-1&&queue.size()!=curRNUm)
                         { 
                             counter++;
                             if(isContinueAllocate)
                                 continue;
                             System.err.println("unsafe...");
                             return false;
                         }
                    }
                }
            }
            return false;
        }
    
        boolean saveBreakPoint(){ 
            for(int i =0;i<curPNum;i++){ 
                for(int j =0;j<curRNUm+1;j++){ 
                    breakPointAllocateMatrix[i][j]=allocateMatrix[i][j];
                }
            }
    
            for (int i =0;i<curRNUm;i++){ 
                breakPointAllResources[i]=allResources[i];
                breakPointAvailableVector[i]=availableVector[i];
            }
    
            return true;
        }
    
        boolean recoveryBreakPoint(){ 
    
            for(int i = 0;i < curPNum;i++){ 
                for(int j =0;j<curRNUm+1;j++){ 
                    allocateMatrix[i][j]=breakPointAllocateMatrix[i][j];
                }
            }
    
            for (int i =0;i<curRNUm;i++){ 
                allResources[i] =  breakPointAllResources[i];
                availableVector[i]=breakPointAvailableVector[i];
            }
    
            return true;
        }
    
        // 判断是否能够安全分配
        boolean bankerHandle(int[] req,int pId){ 
              // 判断need
              //boolean flag = true;
              int[][] tempNeed = getNeedMatrix();
              int[] tempAvailable=getAvailableVector();
    
              for(int i=0;i<req.length;i++){ 
                  if(req[i]>tempNeed[pId][i+1]){ 
                      System.err.println("request is unreasonable!!!");
                      return false;
                  }
              }
    
              //保存当前状态
              saveBreakPoint();
              if(isSafe()){ 
                  recoveryBreakPoint();
                  return true;
              }else { 
                  recoveryBreakPoint();
                  return false;
              }
        }
    
    
        void mockReq(){ 
              final int reqNum = 10;
              int[][] reqs= new int[reqNum][curRNUm];// 若无需该资源则为0
    
              for(int i =0;i<reqNum;i++){ 
                int pId = new Random().nextInt(5);
    
                System.out.println("Attention! process"+pId+" will request resource");
                for(int j = 0;j<curRNUm;j++){ 
                    reqs[i][j]=new Random().nextInt(5);
                    System.out.print(reqs[i][j]+">>");
                }
                bankerHandle(reqs[i],pId);
    
    
                try { 
                    Thread.sleep(2000);
                }catch (Exception e){ 
                    e.printStackTrace();
                }
            }
        }
    
        public static void main(String[]args){ 
             BankerDemo bankerDemo = new BankerDemo();
             bankerDemo.init();
             bankerDemo.workCheck();
             //bankerDemo.isSafe();
             bankerDemo.mockReq();
        }
    
    }