Theory · OS · Deadlock
四个必要条件 → 四种处理策略 —— 从教科书银行家算法到 MySQL/Go 里的真实死锁现场
互斥、占有并等待、不可剥夺、循环等待——四条同时成立才死锁，破一即活
鸵鸟（不处理）→ 预防（破坏条件）→ 避免（银行家）→ 检测恢复（事后补救），约束越强开销越大
真实系统几乎都选"预防 + 检测"：锁排序写进规范，数据库内置死锁检测回滚，Go 用 runtime 崩溃暴露死锁
Why Deadlock Matters
// 两个 goroutine，两把锁；单独看谁都没写错 var muA, muB sync.Mutex // G1：先拿 A，再拿 B go func() { muA.Lock() muB.Lock() // ← 停住：B 在 G2 手上 doWork() muB.Unlock(); muA.Unlock() }() // G2：先拿 B，再拿 A（顺序反了） go func() { muB.Lock() muA.Lock() // ← 停住：A 在 G1 手上 doWork() muA.Unlock(); muB.Unlock() }()
t0 G1 拿到 A，G2 拿到 B —— 一切正常
t1 G1 想要 B（被 G2 占着）→ 停住等；G2 想要 A（被 G1 占着）→ 停住等
t2 G1 等的是 G2 手里的东西，G2 等的是 G1 手里的东西 —— 互相等，而且谁也不会先放手
t3 永久停住。注意不是"慢"，是永远：没有任何外部事件能把它们唤醒
① 它不会自愈：数据竞争、偶发超时这类 bug 重试一下可能就绕过去了；死锁一旦成立就是 100% 停在那，只能人为介入。
② 它完全可预测：只要四个条件同时成立，死锁必然发生——所以它有标准化的判定方法和应对菜单，不需要玄学调试。
③ 面试与线上双高频：从"四条件"一直问到"MySQL 报 1213 怎么办"，既是必答题，也是线上 P0 的常见来源。
先给死锁一个能判定的定义（四条件）→ 再给一套应对菜单（四策略）→ 最后落到数据库与 Go 的真实现场。读完你应该能回答："它为什么必死"以及"我该选哪个策略"。
Prerequisites & Glossary
| 术语 | 一句话理解（先记住这个，细节后面展开） |
|---|---|
| 资源 | 一次只允许一个执行流使用的东西：一把锁、一行数据库记录、一台打印机 |
| 执行流 | "正在跑的一段程序"的统称——本 deck 里进程、线程、goroutine 都算，谁在等谁才是重点 |
| 临界区 | 加锁和解锁之间的那段代码，同一时刻只允许一个执行流在里面 |
| 互斥 | 保证"同一时刻只有一个执行流能进临界区"的性质 |
| 阻塞 | 想要的东西拿不到，就停下来等；停着的时候不消耗 CPU |
| 可剥夺 | 资源能不能被系统从持有者手里强行收走再给别人；锁不行，内存可以 |
| 事务 | 数据库里"要么全做完、要么全不做"的一组操作 |
| 回滚 | 把已经做过的操作撤销，退回到之前的状态——事务天生支持 |
| 等待图 | 一张画"谁在等谁"的图：A→B 表示 A 在等 B 持有的资源；图里有环 = 可能死锁 |
先读这两篇再回来，本 deck 默认你已经知道锁的基本用法：
同步与互斥 → 锁、信号量、条件变量怎么用
进程 · 线程 · 协程 → "谁在等"里的"谁"到底是谁
为了不纠结名词，后面统一说执行流在争抢资源；只有涉及具体系统时才换成"事务""goroutine"。你只需要记住一件事：死锁是两个以上的执行流，互相攥着对方要的东西，且谁都不肯先放手。
既然死锁需要"四个条件同时成立"，那应对思路天然分成两类：让条件凑不齐（预防/避免，死锁不可能发生），或者让它发生然后拆掉（检测/恢复）。后面四策略就是这两类的展开。
Coffman Conditions
开场那段程序"必死"不是运气差——它同时满足了四个条件。四个条件由 Coffman 等人在 1971 年给出：四个同时成立才死锁，破坏任意一个就不可能死锁。
Ostrich · Prevention · Avoidance · Detection
| 策略 | 思路 | 代价 | 现实采用 |
|---|---|---|---|
| 鸵鸟策略 | 假装看不见：死锁概率极低时重启解决 | 零设计成本；出事靠人肉 | 多数通用 OS（Linux/Windows）对用户态进程的态度 |
| 死锁预防 | 静态设计：破坏四条件之一，让死锁不可能发生 | 资源利用率低（一次性申请）、吞吐受损 | 工程规范：锁排序、trylock；最常用 |
| 死锁避免 | 动态判断：每次分配前确认仍处安全状态（银行家算法） | 要预知最大需求 + 每次分配做 O(m·n²) 检查 | 教科书多、现实少（需求难预知） |
| 检测 + 恢复 | 放任发生：周期性跑死锁检测，发现后回滚/抢占/杀进程 | 检测开销 + 回滚损失（事务白做） | 数据库：InnoDB 等待图检测 + 回滚代价小的事务 |
Prevention: Break One Condition
资源本性决定（写锁必须独占）。可行的间接做法：把独占资源改造成共享/虚拟化（假脱机打印队列把打印机变成队列）——只对特殊资源成立。
开始工作前一次性申请全部资源，拿不齐就全释放重试。代价：利用率低（很多资源闲着被占）、可能饥饿（凑不齐一直重试）。工程变体：进入大事务/复杂流程前集中拿锁。
申请新资源失败时，释放已持有的（或被系统强制剥夺）。要求资源状态可保存恢复——锁做不到（临界区状态复杂），事务可以（回滚即恢复）。
给全部锁全局编号，所有人只能按升序申请；持有高号锁时不得再申请低号锁——环在数学上不可能闭合。哲学家"奇偶分组"、Go 的"map+slice 不嵌套锁规范"都是它的实例。
// 资源有序的最小实现：按地址排序加锁 func LockTwo(a, b *sync.Mutex) { if uintptr(unsafe.Pointer(a)) > uintptr(unsafe.Pointer(b)) { a, b = b, a // 先低后高 } a.Lock() b.Lock() } // 全进程内所有两锁路径都走它 // → 循环等待条件被破坏 // trylock 变体：拿不齐就退回 if !b.TryLock() { a.Unlock() // 拿不到 B 就放 A 重试 time.Sleep(...) }
Avoidance · Banker's Algorithm
存在一个调度序列让所有进程都能拿到最大需求并完成——系统就处于安全状态。安全 ≠ 不死锁的超集关系：不安全状态可能死锁，安全状态必然不死锁。避免策略 = 每次分配前检查"分配后是否仍安全"，不安全就拒绝或让进程等待。
每个进程预先声明最大需求 Max。分配请求来时：① 请求 ≤ 剩余需求；② 请求 ≤ 可用资源；③ 试分配后跑安全性检查：在剩余资源里找"剩余需求都能被满足"的进程，假装它完成并归还资源，重复直到全部完成——找不到则回滚本次分配。
三个硬前提：① 进程要预知 Max（业务写不出"最多用多少内存"）；② 进程数与资源固定；③ 每次分配都要 O(m·n²) 检查。它证明了"动态避免可行"，但只适合资源类型少、需求可声明的封闭系统。
| 进程 | 已分配 | 最大需求 | 还需 |
|---|---|---|---|
| P1 | 2 | 9 | 7 |
| P2 | 3 | 4 | 1 |
| P3 | 2 | 7 | 5 |
可用 3 ≥ P2 还需 1 → 满足 P2，P2 完成归还已分配的 3 份 → 可用 3+3=6；6 ≥ P3 还需 5 → P3 完成归还 2 份 → 可用 6+2=8；8 ≥ P1 还需 7 → P1 完成。安全序列 <P2, P3, P1> 存在 → 安全。若把剩余 3 份全部借给 P1（可用变 0），P2 还需 1、P3 还需 5 都无法满足，谁也完不成 → 不安全，银行家会拒绝该请求。
Detection & Recovery
维护等待图（进程→所等进程的边，由资源分配图化简而来）：单实例资源，图中有环即死锁；多实例则要做资源分配图的可简化性检查（不断找"需求都能满足"的进程消去，剩不下图即无死锁）。周期性或"请求长时间不满足"时触发——数据库就是后者。
① 剥夺资源：强制抢占，把资源给别的进程（需要状态可保存）；② 进程回滚：回退到检查点重跑（事务天然支持——回滚即恢复）；③ 终止进程：杀一个或全部环上进程，选代价最小的（运行时间短、产出少、优先级低的先杀）。
恢复时"总是杀同一个倒霉蛋"会造成该进程饥饿——现实实现会在选择受害者时把回滚次数计入代价（InnoDB 的受害者权重考量类似）。
Deadlock · Livelock · Starvation
| 维度 | 死锁 | 活锁 | 饥饿 |
|---|---|---|---|
| 状态 | 互相等待，阻塞不动 | 一直在动（让路重试），但无进展 | 其他人在跑，自己排不上 |
| CPU 占用 | 低（睡眠等待） | 高（忙着重试） | 取决于谁在跑 |
| 典型成因 | 循环等待（嵌套锁） | 谦让式重试：两个线程同时退避再同时重试 | 无公平性的调度/锁（读者饿写者） |
| 解法 | 破坏四条件 / 检测回滚 | 随机退避（指数 backoff + jitter） | FIFO 队列、老化提权、公平锁 |
① trylock 重试风暴：A 拿 1 失败 2，B 拿 2 失败 1，双双释放重试且节奏同步——固定 sleep 会撞车，随机化退避是标准解；② 分布式系统的选举/重试协议风暴；③ 消息处理失败立即重投，两个消费者来回踢皮球。
① 读写锁读者川流不息饿死写者（Go RWMutex 用"写者阻塞新读者"解决）；② 优先级队列无老化，低优先级永远轮空；③ 公平性缺失的内核调度（CFS/EEVDF 的 lag 机制本质就是反饥饿）。
看状态：阻塞不动 = 死锁或饥饿（有环死锁、无环饥饿）；在动但无进展 = 活锁。看CPU：忙转 = 活锁；闲挂 = 死锁/饥饿。两问定位三兄弟。
Deadlock in the Wild
两个事务交叉更新两行即经典死锁：T1 锁行 A 求行 B，T2 锁行 B 求行 A。InnoDB 默认开启等待图检测（innodb_deadlock_detect），秒级发现并回滚 undo 量小的事务，客户端收到 1213 Deadlock found——应用应捕获并重试。高并发热点行还有优化点：关闭检测配合 innodb_lock_wait_timeout 兜底（超时派），减少检测开销。
① sync 死锁：所有 goroutine 都睡在锁/channel 上 → runtime 检测到 all-asleep，直接 fatal error: all goroutines are asleep - deadlock! 崩溃暴露；② channel 死锁：无缓冲 channel 自己发自己收、对 nil channel 收发——同样触发。但部分 goroutine 互相等待（还有人活着）runtime 不管，要靠 pprof goroutine 画像排查。
// InnoDB 死锁的标准应用侧姿势 for i := 0; i < 3; i++ { err := tx.UpdateTwoRows(a, b) if mysql.IsDeadlock(err) { time.Sleep(time.Millisecond * time.Duration(rand.Intn(50))) continue // 随机退避后重试 } break } // 预防侧：统一按主键顺序更新 // （两个事务都先改 id 小的行）
Cheat Sheet
| 四条件同时成立 | 互斥 + 占有并等待 + 不可剥夺 + 循环等待 —— 缺一即不可能死锁 |
| 单实例资源 | 等待图有环 ⇔ 死锁 |
| 多实例资源 | 有环未必死锁，但死锁必有环 |
| 银行家视角 | 安全状态 ⇒ 不会死锁；不安全状态可能死锁 |
| 破循环等待 ★★★ | 锁全局排序（按 ID / 用途 / 对象地址），升序申请 —— 最实用 |
| 破占有并等待 ★★ | 一次性申请全部资源；代价是利用率低、可能饥饿 |
| 破不可剥夺 ★★ | TryLock 拿不到就放手重试；必须配随机退避防活锁 |
| 破互斥 ★ | 把独占资源改造成共享（假脱机队列），只对特殊资源可行 |
| 通用 OS 用户进程 | 只能杀进程，代价大 → 鸵鸟（假装看不见） |
| 数据库事务 | 回滚即可，代价小 → 检测 + 回滚 |
| 自己的业务代码 | 出事要人肉查 → 预防为主（锁排序写进规范） |
| 资源可声明上界的封闭系统 | 能预知 Max → 银行家避免（教科书为主） |
| 在动吗 | 不动（阻塞、CPU 闲）= 死锁或饥饿；在动但无进展（CPU 忙）= 活锁 |
| 有环吗 | 互相等待成环 = 死锁；不成环只是轮不到 = 饥饿 |
pprof goroutine 画像Interview QA · Part 1
先盖住答案自己答一遍，再展开对照——想不起来比看得顺眼记得牢；答不出的直接翻回速查页。
互斥、占有并等待、不可剥夺、循环等待——同时成立才死锁，破坏任一即不可能。追问"哪个最容易破坏"：循环等待（锁排序），哪个最难：互斥（资源本性）。
鸵鸟（零成本、靠重启）、预防（破坏条件，伤利用率）、避免（银行家，要预知 Max + 每次分配检查）、检测恢复（放任发生事后回滚/杀进程，需要便宜恢复手段）。策略 = 恢复成本的函数。
每次分配前模拟：剩下的资源能否支持某个完成序列让所有进程毕业（安全序列）。安全则分配，不安全则拒绝。局限：Max 不可预知、检查开销 O(m·n²)，现实少用。
不一定。不安全 = 找不到保证所有人都完成的安全序列，但进程实际需求可能小于声明（Max 是上界），可能仍然顺利跑完。安全状态必不死锁，不安全状态可能死锁——精确性考点。
把资源分配图化简成等待图（进程间"谁等谁"）：单实例资源有环即死锁；多实例需做可简化性检查。实现上周期性跑，或请求等待超阈值时触发（InnoDB 的做法）。
死锁：阻塞互等无进展；活锁：不停重试无进展（忙）；饥饿：别人有进展自己排不上。判定：看是否阻塞 + 看是否忙。解法各不同：破坏条件/检测、随机退避、公平调度。
Interview QA · Part 2
同样建议先自答。这一页的题都需要"结论 + 一句代价/边界"才完整——只答结论会被追问。
核心是破坏循环等待：锁全局排序（按 ID/用途/对象地址）。配套：临界区最小化、锁内不做 I/O、能不嵌套就不嵌套、拿不到用 TryLock 退避、死锁错误路径必配重试。
InnoDB 默认自动检测并回滚其中一个事务，客户端收 1213。应用侧：捕获该错误 → 随机退避 → 重试（事务要整体重做）。预防侧：批量更新按主键排序、事务尽量短、热点行考虑排队更新。
当所有 goroutine 都阻塞（锁/channel/syscall 等待）且没有 timer/netpoller 唤醒来源时，runtime 判定全局死锁直接崩溃。注意：只是子集互等时 runtime 不报——用 pprof 的 goroutine profile 排查。
ch := make(chan int) 后同一 goroutine 写 ch 再读 ch：发送阻塞等接收者，但接收者就是自己——永远等不到，若全体 goroutine 如此则触发 all-asleep 崩溃；解法：带缓冲、另一 goroutine 消费，或 select + default。
有：A 节点的事务等 B 节点持有的资源，B 又等 A——跨进程/跨网的资源分配图。单机检测看不到全局环，需要分布式死锁检测或设计上规避：资源全序、超时重试（把死锁退化为可重试失败）、Saga 补偿。
先看状态：抓 goroutine/线程 dump，若互相阻塞成环（彼此的栈都在对方持有的锁上）= 死锁；若都在等外部资源（连接池耗尽、下游不回）= 依赖卡死。Go 用 pprof goroutine + 按等待原因分组；通用手段：超时兜底让问题显性化。
Related & References
InnoDB 锁体系 →（等待图检测的工业实现）
sync 并发原语 →（Go 侧锁与 all-asleep 检测）
分布式锁 →（跨节点死锁与超时设计）
参考来源（本 deck 结论可溯源至下列一手材料）
| OSTEP ch.32（Deadlock） | 四条件、四策略框架、银行家算法与安全状态 |
| Coffman et al., 1971（System Deadlocks） | 四个必要条件的原始出处 |
| MySQL 8.0 Reference Manual: InnoDB Locks / Deadlocks | 等待图检测、1213 错误、innodb_deadlock_detect 语义 |
| Go src/runtime/proc.go（gopark / all-asleep check） | 全局死锁判定与 fatal error 触发条件 |
| Dijkstra, 1965（哲学家就餐原始论文） | 资源分层/有序解法的历史源头 |
| xiaolincoding.com《图解系统》deadlock.html | 死锁处理策略的中文叙述 |