Sherfiter's wiki for fun

第 5 章 · 死锁

死锁最可怕的地方在于它有「人间蒸发」式的临床表现:系统不出错、不报异常、不崩,只是越来越慢,然后彻底安静。我第一次抓死锁用的是最笨的办法,程序卡死后直接 jstack 打线程栈,输出末尾赫然一段:

Found one Java-level deadlock:
"Thread-A":
  waiting to lock monitor 0x... (object 0x..., a java/lang/Object),
  which is held by "Thread-B"
"Thread-B":
  waiting to lock monitor 0x... (object 0x..., a java/lang/Object),
  which is held by "Thread-A"

两个线程,互相持着对方想要的锁,互相等着对方放手,而且是「永远」。JVM 直接替你把死锁点出来了(这是 Java 生态对新手友好的一面)。本章讲清楚死锁的成病机理(四个必要条件)、三类对策(预防、避免、检测解除)、以及银行家算法那道年年考的送分题。

5.1 死锁是怎么成的:四个必要条件

死锁成立要求四个条件同时成立,缺一不可。逐条看它们各自「赖以生存的现实土壤」:

  1. 互斥:资源一次只能被一个进程用。这是很多资源的天性(打印机、锁、数据库行),没得商量。
  2. 占有并等待:进程握着手里已有的资源,还伸手要新的。转账是标准案例:事务 A 冻结了账户 1,还想冻结账户 2;事务 B 反过来,冻结了 2 等 1。
  3. 不可剥夺:已到手的资源不能被硬抢。锁不能从持锁线程手里抠出来,抢了它内部状态就烂了。
  4. 循环等待:等待关系成环。A 等 B 的、B 等 A 的,或者更长的环。

前三个是资源的天然属性,基本动不了;第四个是结构,可以设计掉。这个洞察决定了下文所有对策的走向:要么砸钱破坏前三个之一,要么管住第四个。

画成资源分配图(圆圈是进程,方块是资源,箭头是请求/分配)一眼能判:单实例资源下,环即死锁;多实例时环只是嫌疑,还要看环外的资源能不能解围(教材喜欢在这里设判断题)。

P1 ──请求──▶ R2(1份) ──分配给──▶ P2
P2 ──请求──▶ R1(1份) ──分配给──▶ P1     环:死锁

5.2 对策一:预防(事前破坏条件)

破坏循环等待:全局锁排序。给所有锁编号,规定所有人只能按编号升序拿锁,要拿小号就得先放掉大号。环在数学上就不可能成立(等待链只能从小到大,回不到起点)。这是真实世界最常用的方案:Linux 内核的锁有编号约定,数据库按表 ID 排序加锁,转账代码先冻 ID 小的账户再冻 ID 大的。代价是要全组人守纪律,一处破例就前功尽弃(这也是为什么它最好封装在基础设施层)。

破坏占有并等待:一次性申请。开工前把要用的资源一次要齐,要不全给要不不给。数据库的「两段锁协议」广义上算这一路。缺点是资源利用率差(申请了一时用不上的),还可能自己把并发卡死。

破坏不可剥夺:可抢占。拿不到就放手重来(trylock 失败就释放自己已有的全部锁,睡一会儿再试)。活着,但引入「活锁」风险:两个进程同时放手、同时重来、无限错峰。实际工程里加个随机退避(backoff)就能压住。

破坏互斥基本不现实,教材列出来只为完整性。

5.3 对策二:避免(银行家算法)

预防是「一刀切」,避免是「逐笔审批」:每次资源申请都当场判断,批了之后系统还处于安全状态才放行。安全状态的定义:存在一个分配顺序,让所有进程都能依次跑完(哪怕大家全都要到最大需求)。

审批流程就是著名的银行家算法,拿经典例子完整走一遍,这道题考试年年出:

3 个进程,10 个资源。当前状态:
        Max   已分配  还需要(=Max-已分配)
P1       9      3         6
P2       4      2         2
P3       7      2         5
剩余 Available = 10 - 3 - 2 - 2 = 3

安全性检查:反复找「还需要 ≤ 剩余」的进程,假设它跑完并还清:

  • 剩 3:P2 还需 2 ≤ 3,放 P2 跑完,回收 2,剩 3+2=5;
  • 剩 5:P3 还需 5 ≤ 5,跑完,剩 5+2=7;
  • 剩 7:P1 还需 6 ≤ 7,跑完。全员完成,序列 P2→P3→P1 就是安全序列,状态安全。

现在 P1 请求 1 个资源:试探分配后剩 2,P2 还需 2 可以跑,P3 还需 5 > 2 跑不了,P1 还需 5 > 2 也不行,P2 跑完剩 4,P3 仍要 5,卡死。找不到安全序列,拒绝请求,让 P1 等着。整套逻辑就这么朴素,考试只考细心。

它的死穴也在例子里:必须有 Max(每个进程的最大需求),这在现实里几乎拿不到(哪个服务知道自己峰值要多少资源?),而且每次申请都要跑一遍 O(m×n²) 的检查。所以银行家算法在教学里的地位远高于工程里的地位,真实系统几乎都选第三条路。

5.4 对策三:检测与解除(鸵鸟的艺术)

容忍死锁发生,但定期体检:构建「进程等待图」,有环就报死锁。发现后解除,手段从轻到重:挑一个受害进程回滚(数据库最擅长,事务回滚天然可用)、或者干脆杀进程。数据库是这个策略的模范生:MySQL InnoDB 用「等待图 + 挑回滚代价小的牺牲者」自动解死锁,你偶尔会在日志里看到 Deadlock found when trying to get lock; try restarting transaction,那就是它杀了一个事务让你重试。

三种策略选型一句话:锁顺序能守就守(预防),守不住就指望底层的自动检测(数据库、JVM 都有),银行家算法留给考试。

死锁、饥饿、活锁:三个长得像的病

死锁是全员永久停车(互相等待成环);饥饿是个别人永远排不上队(第 3 章 SJF 饿死长任务,资源没被锁死,只是轮不到);活锁是全员礼貌地反复让路,谁都没走成(5.2 的 trylock 退避过火)。判别方法:死锁的线程栈是静止的,活锁的线程栈在动(CPU 在烧),饥饿的系统其他部分一切正常。

常见错误

  • 以为锁得多才安全,给每个函数都加锁还不定序。这是死锁的标准配方。锁要少、要粗粒度起步、要全局排序。
  • 把「不崩」当「没病」。死锁的线程还活着,监控全绿,只有业务超时。排查靠线程栈(jstack、gdb bt、pstack),不要靠看日志。
  • 忘了分布式版本的死锁。两台机器各持一把分布式锁互等,单机的检测器帮不了你;分布式死锁要靠超时 + 重试幂等(配合数据库课的事务章)。

练习

  1. 手算:5.3 的例子里,若 P3 请求 1 个资源(而不是 P1),安全状态检查结论是什么?写全过程。
  2. 手算:构造一个「有环但没死锁」的多实例例子:两个资源类各 2 实例,三个进程,等待图成环但有人能解围。
  3. 动手:写一个必然死锁的 C 程序(两个线程各拿一把锁再要对方的),跑起来后 pstack <pid>(或 gdb attach)两次,观察线程栈纹丝不动,再给代码加锁序修复,验证程序跑通。
  4. 思考:数据库遇到死锁会杀事务重试,但如果重试代码本身不幂等(比如扣款没做「先查后扣」的保护),会发生什么?这题把本章和数据库的事务章连起来了。
豫ICP备2026027944号