死锁以及如何解决

一、死锁的定义

死锁是指两个或多个进程（或线程）因竞争资源而陷入相互等待的永久阻塞状态，若无外部干预，无法继续推进 。例如，线程A持有资源X并等待资源Y，而线程B持有资源Y并等待资源X，形成循环等待的僵局。

二、死锁的必要条件

死锁的产生需同时满足以下四个条件，缺一不可 ：

  1. 互斥条件：资源一次仅能被一个进程独占使用（如打印机）。
  2. 占有并等待：进程已持有至少一个资源，同时请求其他被占用的资源。
  3. 不可剥夺：资源只能由持有者主动释放，不可被强制剥夺。
  4. 循环等待：存在进程间的资源等待环路（如进程A→B→C→A）。
三、死锁的解决方法
1. 预防死锁

通过破坏四个必要条件之一来避免死锁发生 ：

  • 破坏互斥条件：将资源改造为可共享（如SPOOLing技术对打印机的虚拟化）
  • 破坏占有并等待：要求进程一次性申请所有所需资源（静态分配），但可能导致资源浪费
  • 破坏不可剥夺：允许系统强制回收资源（如优先级调度），但实现复杂且可能影响进程状态
  • 破坏循环等待：规定资源申请顺序（如按资源编号递增），避免环路
2. 避免死锁

通过动态判断资源分配的安全性，确保系统始终处于安全状态 ：

  • 银行家算法：检查资源分配后是否存在安全序列，若不存在则拒绝分配 。
    • 算法核心概念
      1. 可用资源向量（Available）：表示当前系统中每类资源的可用数量。
      2. 最大需求矩阵（Max）：表示每个进程对每类资源的最大需求量。
      3. 分配矩阵（Allocation）：表示每个进程当前已分配的资源数量。
      4. 需求矩阵（Need）：表示每个进程还需要的资源数量，计算公式：Need = Max - Allocation。
    • 安全状态判断步骤
      1. 初始化：
        • 计算Need矩阵。
        • 设置工作向量Work = Available，表示当前可用资源。
        • 设置标记向量Finish，初始值为False，表示所有进程尚未完成。
      2. 寻找可执行的进程：
        • 遍历所有进程，找到一个满足以下条件的进程P_i：
          • Finish[i] == False（进程未完成）。
          • Need[i] <= Work（进程所需的资源不超过当前可用资源）。
        • 如果找到，执行步骤3；否则，执行步骤4。
      3. 模拟资源分配与回收：
        • 假设进程P_i执行完毕并释放资源，更新：
          • Work = Work + Allocation[i]（可用资源增加）。
          • Finish[i] = True（标记进程完成）。
        • 返回步骤2。
      4. 判断系统是否安全：
        • 如果所有进程的Finish[i] == True，说明所有进程都能顺利完成，系统处于安全状态。
        • 否则，系统处于不安全状态，可能导致死锁。
    • 示例

假设系统有3类资源（A、B、C），初始可用资源Available = [3, 3, 2]，有5个进程，资源分配如下：

进程

Allocation

Max

Need (Max - Allocation)

P0

0 1 0

7 5 3

7 4 3

P1

2 0 0

3 2 2

1 2 2

P2

3 0 2

9 0 2

6 0 0

P3

2 1 1

2 2 2

0 1 1

P4

0 0 2

4 3 3

4 3 1

步骤：

  • 初始化：Work = [3, 3, 2]，Finish = [False, False, False, False, False]。
  • 找到P1（Need[1] = [1, 2, 2] <= Work），执行并更新：
    • Work = [3, 3, 2] + [2, 0, 0] = [5, 3, 2]。
    • Finish[1] = True。
  • 找到P3（Need[3] = [0, 1, 1] <= Work），执行并更新：
    • Work = [5, 3, 2] + [2, 1, 1] = [7, 4, 3]。
    • Finish[3] = True。
  • 找到P4（Need[4] = [4, 3, 1] <= Work），执行并更新：
    • Work = [7, 4, 3] + [0, 0, 2] = [7, 4, 5]。
    • Finish[4] = True。
  • 找到P0（Need[0] = [7, 4, 3] <= Work），执行并更新：
    • Work = [7, 4, 5] + [0, 1, 0] = [7, 5, 5]。
    • Finish[0] = True。
  • 找到P2（Need[2] = [6, 0, 0] <= Work），执行并更新：
    • Work = [7, 5, 5] + [3, 0, 2] = [10, 5, 7]。
    • Finish[2] = True。
  • 所有Finish为True，系统处于安全状态。
  1. 总结

银行家算法通过模拟资源分配过程，确保系统始终处于安全状态，避免死锁。其核心是找到一个安全序列，使所有进程都能顺利完成。虽然算法严谨，但由于需要预知进程的最大资源需求，实际应用中主要用于理论研究和特定场景（如数据库管理系统）。

  • 超时机制：设置锁的等待超时（如Monitor.TryEnter），超时后释放已有资源
3. 检测与恢复

允许死锁发生，但通过检测和恢复机制处理 ：

  • 检测方法：
    • 资源分配图：检查图中是否存在环路
    • 矩阵算法：通过标记进程资源请求与分配状态判断死锁 。
  • 恢复方法：
    • 终止进程：强制终止部分进程以释放资源（如终止环路中的进程）
    • 资源抢占：强制回收资源并分配给其他进程（需处理进程状态回滚问题）
    • 进程回滚：利用检查点（Checkpoint）恢复进程到无死锁状态 。
4. 实际应用中的优化策略
  • 数据库场景：
    • 调整事务隔离级别（如READ COMMITTED）以减少锁冲突 。
    • 统一资源访问顺序，避免交叉加锁
    • 使用SHOW ENGINE INNODB STATUS分析死锁日志并优化SQL
  • 编程实践：
    • 减少锁的嵌套使用，缩短锁的持有时间
    • 使用无锁数据结构或原子操作（如CAS）替代显式锁
四、总结

方法

核心思想

适用场景

预防

破坏必要条件，牺牲部分灵活性和效率

对实时性要求较低的系统

避免

动态判断资源分配的安全性（如银行家算法）

资源类型固定的批处理系统

检测恢复

允许死锁发生，事后通过终止进程或抢占资源恢复

复杂系统或无法预知的场景

注：实际系统中常结合多种方法。例如，数据库通过超时机制（避免）和死锁检测（恢复）综合应对 ，而编程中则优先通过顺序加锁（预防）和减少锁粒度来降低风险