死锁简介 (Introduction to Deadlock)

  • 定义 (Definition): 线程因循环等待资源 (Cyclical Resource Waiting) 而无限期阻塞的状态.
  • 为了确保程序合理运行的必要条件:
    • 安全性 (Safety): 所有操作必须正确 (避免非法交错).
    • 活性 (Liveness): 操作必须持续进行; 死锁违反活性.

[!Fix Attempts]

  1. Ignore: 1. 0S会自己完成的; 2. 这个方法占用cpu时间为0;
  2. Detect and Fix:
  1. Kill the deadlock threads:会导致一定!的 invariant条件破裂
  2. Rollback actions and then try again:某些指令如 output 并不能 roll back
  1. Prevent: 得知道有哪些造成 deadlock 的必要条件

[!Concept] 等待图 (Wait-for Graph):

  • 顶点 (Vertices): 线程和资源.
  • 边 (Edges):
    • 线程 → 资源 (线程等待资源).
    • 资源 → 线程 (资源被线程持有).
  • 循环检测 (Cycle Detection): 图中存在循环即表明死锁.

死锁的构成要素 (Components of Deadlock)

  • 有限资源 (Limited Resources): 线程所需的实体 (如锁 Locks, CPU, Memory).
  • 不可剥夺 (No Preemption): 不能强制线程放弃资源. Preemption: no
    indefinite waiting, 系统不能强制从资源占有者处释放资源
  • 获取且等待 (Hold and Wait): 线程持有资源同时等待其他资源.
  • 循环等待 (Circular Wait): 线程A等待线程B, 线程B等待线程C, 线程C等待线程A.

[!Fix Attempts]

  1. Limited Resources: increase the number of resources
  2. No Preemption: Enable preemption,
  3. Hold and Wait: 1. Move the resources acquisition to the first step; 2.
    Acquire all the resources atomically, if not, release all its resources and retry

[!Note] 仍然会导致问题:
如果对于中间用户左右资源被左右用户轮流占用,则中间用户本身也无法获取资源.
解决方案: 定义一个 Global Ordering 来规定资源的获取顺序.

3. 死锁示例 (Examples of Deadlock)

  • 锁顺序问题 (Lock Ordering):
    • 线程A: x.lock() → y.lock().
    • 线程B: y.lock() → x.lock().
    • 结果 (Result): 锁顺序相反可能导致循环依赖.

4. 哲学家就餐问题 (Dining Philosophers Problem)

  • 场景 (Setup):

    • 5位哲学家 (Philosophers)、5根筷子 (Chopsticks).
    • 每位需两根筷子就餐.

  • 朴素算法 (Naive Algorithm):

    1
    2
    3
    4
    5
    6
    7
    while (true) {
        think();
        acquire(right_chopstick);
        acquire(left_chopstick);
        eat();
        release(both);
    }

  • 死锁风险 (Deadlock Risk): 所有哲学家同时拿一根筷子, 导致循环等待 (Circular Wait).

  • 解决方案 (Solutions):

    • 原子获取 (Atomic Acquisition): 使用全局锁 (Global Lock) 同时获取两根筷子.
    • 资源排序 (Resource Ordering): 按固定顺序获取 (如先拿编号较小的筷子 Lower-numbered Chopstick First).

死锁处理策略 (Handling Deadlocks)

  • 忽略 (Ignore):
    • 操作系统常忽略应用级死锁 (低CPU消耗).
  • 检测与恢复 (Detect and Recover):
    • 检测 (Detection): 监控等待图中的循环.
    • 恢复 (Recovery):
      • 终止线程 (Kill Threads): 杀死部分参与线程.
      • 回滚 (Rollback): 回退操作并重试 (需事务支持 Transactional Support).
  • 预防 (Prevent): 打破必要条件之一.

死锁预防策略 (Prevention Strategies)

  • 消除持有并等待 (Eliminate Hold and Wait):
    • 原子获取 (Atomic Acquisition): 预先获取所有资源 (如 acquire_all(resources)).
    • 释放重试 (Release-and-Retry): 若资源忙则释放已持有资源.
  • 消除循环等待 (Eliminate Circular Wait):
    • 全局排序 (Global Ordering): 强制按固定顺序获取资源 (如先锁1后锁2).
  • 消除不可抢占 (Eliminate No Preemption):
    • 允许资源抢占 (如CPU调度 CPU Scheduling、内存回收 Memory Reclamation).
  • 消除互斥 (Eliminate Mutual Exclusion):
    • 使用非独占资源 (对硬件资源如锁不适用).

实际考量 (Practical Considerations)

  • 饥饿 vs 死锁 (Starvation vs Deadlock):
    • 饥饿 (Starvation): 线程被无限延迟 (未必因死锁).
  • 回滚的挑战 (Challenges in Rollback):
    • 不可逆操作 (如I/O动作 I/O Actions) 无法回滚.
  • 性能权衡 (Performance Trade-offs):
    • 原子获取降低并发性 (Concurrency); 全局排序限制灵活性.

案例研究: 哲学家就餐问题再探 (Case Study: Dining Philosophers Revisited)

  • 原子方案 (Atomic Solution):
    • 使用中央锁协调筷子获取.
  • 排序方案 (Ordering Solution):
    • 哲学家按编号顺序拿筷子, 打破对称性.
  • 并发 vs 公平 (Concurrency vs Fairness):
    • 方案可能降低吞吐量 (Throughput), 但确保进展 (Progress).

核心总结 (Key Takeaways)

  • 死锁源于资源获取的循环依赖 (Cyclical Dependency).
  • 预防需打破四个必要条件之一.
  • 检测与恢复需系统支持 (System Support).
  • 实际案例 (如哲学家就餐问题) 诠释理论概念.