死锁：四个条件、银行家算法与工程对策

一句话定义

死锁（deadlock）是一组执行流各自持有资源、又互相等待对方持有的资源、且都不肯释放，导致永远无法推进的僵局；其成立的充要结构由四个必要条件共同刻画。

为什么重要

kp-013 已经演示过一次亲手制造的死锁。它是最隐蔽的生产事故类型之一：数据库的锁表、内核的双锁结构、微服务间的调用环，都能触发。死锁一旦发生通常只能重启，因此防御必须前置于设计——而防御的全部思路，就是破坏四个必要条件之一。

前置知识

kp-013（信号量与多锁场景）。

核心概念

• 四个必要条件：互斥、持有并等待、不可剥夺、循环等待。
• 资源分配图：节点为进程与资源，边为"请求"与"分配"，环是死锁的必要信号（单实例资源时为充要）。
• 死锁预防：静态破坏某一必要条件（如全局加锁顺序破坏循环等待）。
• 死锁避免（银行家算法）：动态判断"这次分配会不会进入不安全状态"。
• 死锁检测与恢复：允许发生，定期找环并杀进程/回滚（数据库的经典做法）。
• 活锁（livelock）与饥饿（starvation）：不死的"忙等礼让循环"与"永远轮不上"，与死锁并列的两种活性故障。

原理与机制

四个必要条件与对应破坏手段：

锁序法是工程主力：kp-013 的 AB-BA 死锁中，线程1 拿 A 等 B、线程2 拿 B 等 A；规定"永远先锁 A 再锁 B"，环就无法闭合。Linux 内核用 lockdep 工具在运行时捕捉锁序违规，正是把纪律自动化。

银行家算法（Dijkstra，避免策略）：系统维护 Available、Max、Allocation、Need 四组向量/矩阵；进程请求时先试探性分配，然后检查是否存在一个安全序列——即能找到一个进程其 Need ≤ Available，模拟其完成归还资源，重复直至全部可完成。找不到安全序列则拒绝本次请求让进程等待。

例: Available = [3,3,2]  (资源类型 A/B/C)
    P1 Need=[1,0,2] ≤ [3,3,2] -> P1 可完成 -> 归还后 Available 增加
    依次验证 P3, P4, P0, P2 均可 -> 存在安全序列 <P1,P3,P4,P0,P2> -> 批准请求

直观类比

死锁像四辆车队在十字路口互不相让形成闭环。预防是装红绿灯（全局顺序）；避免是交警每次放行前判断"放他过去后是否人人都有出路"（银行家算法）；检测恢复是堵死后叫拖车（杀进程回滚）。

实例或案例

制造并诊断一次死锁：

/* 线程1: lock(A); usleep(100); lock(B);   线程2: lock(B); usleep(100); lock(A); */

程序挂死后：ps -Lo stat -p <pid>（多线程同显）、pstack <pid> 或 gdb -p 查看各线程栈，可见两个线程分别停在两个不同的 pthread_mutex_lock 上——资源分配图的环在栈快照里肉眼可见。数据库场景用 SHOW ENGINE INNODB STATUS 能看到死锁检测器自动回滚的记录。

常见误区

• 死锁 = 系统卡死：卡死也可能只是活锁（都在动但无进展）或无限循环，诊断时要区分。
• 认为锁少就不会死锁：两个锁加一个时序窗口就够；文件锁 + 数据库锁的跨系统组合同样成环。
• 认为"运行时加个超时"万能：超时破坏的是不可剥夺条件，代价是回滚与重试风暴，高频触发即性能灾难。

与其他知识点的关系

kp-012 的锁是实现载体；kp-032 的"加锁顺序纪律"与"微内核 IPC 死锁"是工程化延伸；数据库事务隔离把同一套理论商业化到极致。

延伸阅读

《操作系统概念》第 7 章（含银行家算法完整矩阵演算）；Coffman 等 1971 年死锁理论综述。

自测题

1. 四个必要条件中，工程上最常用哪个的破坏来防死锁？为什么？

答：循环等待——通过规定全局统一的加锁顺序即可静态消除，成本最低、无需运行时判断。

1. 银行家算法为什么"保守"？

答：它要求分配后仍存在安全序列才放行，即使系统实际可能不会死锁也会拒绝请求，牺牲资源利用率换取确定性安全。

1. 死锁与活锁的区别？

答：死锁中的进程全部阻塞不消耗 CPU；活锁中的进程仍在运行（如不断重试礼让），有 CPU 消耗但同样无进展。