进程死锁

死锁概述

• 定义：同组中的 ==每个进程== 正在等待某个 ==只能够由同组其他进程== 执行的事件发生，称 ==操作系统== 处于死锁状态

  死锁指的是操作系统的状态而不是某个进程的状态

• ==必要条件==

  • 条件内容：

    • 互斥(mutual exclusion)：==至少存在一个== 资源实例 ==不能共享==
    • 持有并等待(hold and wait)：拥有进程的资源申请新的资源时 ==必须等待该资源的释放==
    • 不可抢占(no preemption)：被其他进程使用的资源不可以被抢占使用
    • 循环等待(circular wait)： 存在一个进程链，使得每个进程都占有下一个进程所需的至少一种资源

    

  • 细节：四个条件是死锁发生的必要条件而不是充分条件

    解释：死锁发生时必定满足上述四个条件；四个条件同时存在时不能保证死锁一定发生，可能还需要更多的条件

    注：不满足四个条件中的其中之一就不可能发生死锁

• 资源：

  • 资源分类：

  • 资源实例

  • 资源分配图

    • 边：分配边 + 申请边
    • 点：进程节点 + 资源节点
    • 资源实例：每个资源中的原点

    单实例资源图中存在环一定会导致死锁发生；多实例资源图中存在环不一定导致死锁发生

    

死锁处理

死锁预防 & 避免

• 定义：制定相应的 ==协议或者规则== 阻止死锁的发生

死锁预防

• 核心：直接确保四个必要条件至少一个不发生

• 方式：

  • 阻止互斥：允许资源被进程共享

    注：通过阻止互斥发生来预防死锁是不现实的 -> 大多数的资源都是不共享的

  • 阻止持有并等待：

    • 两种方式：

      1. 每个进程在进入处理器执行前申请并获得所有需要的资源

         解释：不允许在执行过程中再申请资源，即使释放资源再申请也不行

      2. 每个进程在执行过程中申请资源必须先释放拥有的资源

         解释：并不需要在执行前就获取所有资源，只不过再次申请资源前需要先释放拥有的资源

    • 缺陷：

      1. 进程 ==长时间占用== 某种资源但是暂时并没有使用

      2. 进程申请的资源被其余进程占用导致进程处于 ==饥饿状态==

         注：饥饿和死锁是有区别的

  • 阻止不可抢占：某个进程在申请资源后没有得到满足就必须 ==释放拥有的资源== 提供给其他进程使用

    解释：因为当前进程没有获得必需的资源那么就无法运行，那么进程当前拥有的资源也是没有意义的，就应该允许其余进程抢占（释放）

    注：阻止不可抢占容易导致释放资源的进程丢失之前的任务进度（处理器和寄存器可以），进程间反复的相互抢占资源会导致进程的执行被无限推迟

  • 阻止循环等待：每个资源递增编号，每个进程只能按照编号的顺序 ==递增申请== 每项资源

    解释：P1 拥有资源 R1 后才可以申请 R2，获得 R2 之后才可以申请 R3；P2 如果拥有 R3 ，此时是不允许申请 R1，除非释放 R3 资源

    1. 进程只可以顺序申请比自己拥有的资源编号大的资源；如果申请资源编号小的，必须释放自己拥有的资源

    2 资源的编号必须尽可能考虑到资源使用的顺序，否则会出现先申请编号较大的资源，再申请编号较小的资源的情况 -> 资源利用效率较低

    

• 细节：

  • 四种方式只需要采用一种就可以防止死锁的发生
  • 可以确保操作系统永远不会出现死锁的状态 <-> 导致操作系统效率变低

死锁避免

• 定义：每个进程交付 ==必要信息== 给操作系统，操作系统利用相应的算法 ==动态检查== 资源分配的状态

  必要信息：进程需要申请的资源，想要如何申请资源…

• 核心：利用死锁算法避免死锁的发生

• 安全状态：操作系统可以按照 ==特定的顺序== 为进程分配资源并且避免死锁发生，称操作系统处于 ==安全状态==

  • 解释：每个进程需要按照特定的顺序执行，即等待其余进程执行结束释放资源后再继续执行 -> <P0 P1 P2> => <P1 P2 P0>(执行顺序)

  • 安全序列：进程执行的特定顺序就是安全序列 & 非安全状态：不存在这样的特定序列

  • 安全状态不会安全状态一定不会出现死锁状态

  • 非安全状态不一定导致死锁状态；死锁状态一定属于非安全状态

    死锁和非安全状态

  

• 算法：

  • 资源分配图法：仅适用于单实例的资源

    • 核心：引入 ==需求边==：需求边表示进程在将来某个时刻可能会需要的资源

    • 规定：进程在执行前在图中的所有边都是需求边；进程在获取到相应资源后由 ==需求边转为分配边== ；进程结束后 ==分配边再次变为需求边==

    • 检测：如果需求边在转为分配边后会产生环，那么操作系统就不会给当前的进程分配该资源

      检测环是否存在可以使用拓扑排序检测

    

  • 银行家算法：适用于多实例的资源

    • 数据结构：

      参数名	描述
      Available[n]	该数组每个元素表示每种不同类型资源的 ==可分配== 的资源实例数量
      Max[n][m]	该数组第一个参数表示每个不同的进程；第二个参数表示每个进程正常运行需要的每种类型的 ==全部== 资源实例数
      Allocation[n][m]	该数组第一个参数表示每个不同的进程；第二个参数表示每个进程 ==已经被分配== 的每种类型的资源实例数
      Need[n][m]	该数组第一个参数表示每个不同的进程；第二个参数表示每个进程 ==还需要== 的每种类型的资源实例数

      Need = Max - Allocation；之后提到的 Request 并不是 Need

    • 安全性算法

      1. 定义并初始化变量：

         定义 Work[] & Finish[] 数组；令 Work = Available & Finish[i] = false (i=0,1,2...n)

         问题：为什么不直接使用 Availalbe 变量?

      2. 循环遍历进程集合，判断进程还需要的资源实例数和可分配的资源实例数的关系

         • Finish[i] = true 证明该进程已经执行过并且结束了，开始遍历下一个进程

         • Finish[i] = false

           Need[i] ≤ Work[i] 就执行第 3 步

           Need[i] ＞ Work[i] 就略过当前进程，开始遍历下一个进程

         • 如果没有下一个进程可以遍历了就执行第 4 步

      3. 进程获取资源并执行，执行结束后释放资源

      `Work[i] = Work[i] + Allocation[i]` 更新当前可以分配的资源实例数
      
      `Finish[i]` = `true`
      

      4. 如果 Finish[] 数组中所有元素都为 true，证明系统处于安全状态；如果存在至少一个 false 元素，证明系统处于不安全状态

    • 资源分配算法

      • 引入：

        安全性算法只能够判断进程依靠当前拥有的资源是否可以正常执行

        如果进程需要更多的资源才能够正常进行，显然就需要申请资源，那么安全性算法显然就是不够用的

      • 过程：引入变量 Request[n]：表示当前进程申请的每种类型的资源实例数量

        1. 判断进程 ==申请== 的资源实例数量和 ==还需要== 的资源实例数量
           • Request[i] ≤ Need[i] 就执行第 2 步
           • Request[i] ＞ Need[i] 将会提示出错；进程申请的资源实例数量超过了正常执行还需要的资源实例数
        2. 判断进程 ==申请== 的资源实例数量和 ==可分配== 的资源实例数量
           • Request[i] ≤ Available[i] 就执行第 3 步
           • Request[i] ＞ Available[i] 证明当前可分配资源不足以支撑进程的执行，该进程就需要 ==等待==
        3. 操作系统 ==假设== 分配给进程相应的资源实例数量
           • Available[i] = Available[i] - Request[i]
           • Need[i] = Need[i] - Request[i]
           • Allocation[i] = Allocation[i] + Request[i]
        4. 执行安全性算法判断在进程申请资源后系统是否处于安全状态
           • 如果系统处于安全状态，那么系统就真正将资源分配给进程
           • 如果系统处于非安全状态，那么系统就恢复原来的资源分配状态，并且让该进程处于 ==等待==

      • 细节：

• 死锁避免 & 死锁预防：

  • 死锁预防：死锁预防是从一开始就不允许进程进行某种操作（比如破坏循环等待就不允许申请编号小的资源）

  • 死锁避免：死锁避免则是在一定程度上允许这些操作，通过设计好的算法在运行过程中协调进程，避免死锁的发生

  • 死锁避免允许四个必要条件一起发生 <-> 死锁预防根本不会允许四个条件一起发生

    解释：因为即使四个必要条件一起发生也不一定会导致死锁的出现，所以死锁避免只要采用相应的算法避免就好

  • 死锁避免限制条件弱，但是难以实现相应的算法 <-> 死锁预防限制条件强，容易实现相应的限制

死锁检测 & 恢复

• 定义：检测系统是否处于死锁状态并且能够从死锁状态中恢复

死锁检测

• 核心：并不是阻止死锁发生的算法，只能够用于检测死锁是否发生

• 算法：

  • 等待图：仅适用于单实例的资源

    • 核心：去除资源分配图中的所有资源节点，仅剩下进程节点

    • 规定：只有当 Pi ->Rj && Rj -> Pk 时，两个进程之间才会存在边

    • 检测：仍然检测等待图中是否存在环结构

      检测环是否存在可以使用拓扑排序检测

    

  • 类银行家算法：适用于多实例的资源

    • 数据结构：和之前的银行家算法有些微区别

      参数	描述
      Available[n]	该数组每个元素表示每种不同类型资源的 ==可分配== 的资源实例数量
      Allocation[n][m]	该数组第一个参数表示每个不同的进程；第二个参数表示每个进程 ==已经被分配== 的每种类型的资源实例数
      Request[n][m]	该数组的每个元素表示每个进程 ==申请== 的资源实例数量

    • 过程：

      1. 定义并初始化变量，根据

         定义 Work[] & Finish[] 数组；令 Work = Available

         如果 Allocation[i] = 0 就令 Finish[i] = true

         如果 Allocation[i] ≠ 0 就令 Finish[i] = false

         如果当前进程没有被分配任何资源，那么该进程不可能是造成死锁的原因，相当于破坏了持有并等待的条件

      2. 循环遍历进程集合，判断每个进程申请的资源实例数量和可分配的资源实例数量

         Request[i] ≤ Work 证明当前资源足够支撑该进程运行；令 Finish[i] = true ；再执行第 3 步

         如果申请的资源大于可分配的，也不可以立刻断言当前系统处于死锁，如果之后有进程执行结束释放资源，说不定当前进程就可以执行了

      3. 操作系统 ==假设== 分配给进程相应的资源实例数量

         Work = Work + Allocation[i]

      4. 循环遍历 Finish[] ，如果存在元素值仍未 false，证明当前系统处于死锁状态（注意不是非安全状态）

         这里是直接断言系统处于死锁状态，而不是非安全状态，因为多个进程同时提出申请，的确非常容易造成死锁

    • 细节：

      1. 死锁避免银行家算法 vs 死锁检测银行家算法
         • 死锁避免：每次 ==只有一个进程== 提出申请，然后执行安全性检测，如果不安全就会驳回进程的申请
         • 死锁检测：所有进程都可以 ==同时== 提出申请，这就很容易直接造成死锁，该算法是利用所有进程的申请在计算

• 细节：死锁检测通常都是配合而死锁恢复一起使用

死锁恢复

• 资源抢占

  • 核心：允许进程抢占资源打破死锁

  • 细节：

    • 回滚：被抢占资源的进程需要回滚到到足够打破死锁的状态

      进程在回滚的过程中会不断地释放资源 (主动释放资源)

    • 牺牲进程：选择被抢占资源的进程，尽可能使得代价最小 (被动释放资源)

    • 饥饿：不能够无限次地选择同一个进程被抢占资源

      通常将进程回滚的次数作为考虑牺牲进程的因素

    注：资源抢占的核心，就是一个进程释放资源，一个进程获取这个释放的资源，考虑上述的三个细节仅仅只是能够更好抢占，避免抢占造成严重后果

• 进程终止

  • 核心：终止造成死锁的进程来打破死锁

  • 方式

    • 终止 ==所有== 进程：（几乎类似于重启系统）

      • 缺陷：==代价== 非常大，容易导致被终止的进程之前的 ==任务进程丢失==

        代价：这里的代价应该是对于进程而言的，因为可能会造成很多有效数据的丢失

    • 终止 ==部分== 进程

      • 方式：每次终止一个进程后都需要继续调用死锁检测算法判断当前系统是否仍处于死锁

        解释：需要不断尝试当前系统是否处于死锁状态，如果仍然处于死锁状态，也需要继续死锁检测算法寻找造成死锁的进程

      • 缺陷： ==代价== 非常大

        代价：这里的代价应该是在每次都要执行死锁检测算法确定终止进程所造成的开销

忽略

• 定义：操作系统认为死锁不可能在系统中发生

• 细节：

  • Linux & Windows 等大多数现代操作系统都是采用 ==忽略死锁== 的方式

    每个应用程序需要编写相应的算法避免和其他进程之间发生死锁，而不是依靠操作系统来避免