Jakob Jenkov 2021-03-08
在某些情况下，死锁是可以被预防的。本文将介绍三种技术：
- 锁排序（Lock Ordering）
- 锁超时（Lock Timeout）
- 死锁检测（Deadlock Detection）
锁排序（Lock Ordering）
当多个线程需要相同的锁但以不同的顺序获取它们时，就会发生死锁。
如果你确保所有线程总是按照相同的顺序获取锁，那么死锁就不可能发生。看下面这个例子：
线程 1：获取锁 A → 获取锁 B
线程 2：等待锁 A → 获取锁 C（当 A 被锁定时）
线程 3：等待锁 A → 等待锁 B → 等待锁 C
如果一个线程（例如线程 3）需要多个锁，它必须按照预定的顺序获取这些锁。在获取序列中靠后的锁之前，它必须先获得前面的所有锁。
例如，线程 2 和线程 3 都不能在未先获取锁 A 的情况下去获取锁 C。由于线程 1 持有锁 A，线程 2 和 3 必须先等待锁 A 被释放。然后它们必须成功获取锁 A，才能尝试获取锁 B 或 C。
锁排序是一种简单而有效的死锁预防机制。然而，它仅在你事先知道所有需要的锁的前提下才适用——而这并不总是可行的。
锁超时（Lock Timeout）
另一种死锁预防机制是为锁的获取操作设置超时时间。也就是说，尝试获取锁的线程只会等待一段指定的时间，如果超时仍未获取到锁，就放弃。
如果一个线程在给定的超时时间内未能成功获取所有必需的锁，它会回退（back up）：释放已经获取的所有锁，随机等待一段时间，然后重试。这种随机等待是为了给其他也在竞争相同锁的线程一个机会，从而让应用程序继续运行而不陷入死锁。
下面是一个两个线程以不同顺序尝试获取相同两个锁的例子，其中线程会在超时后回退并重试：
线程 1 获取锁 A
线程 2 获取锁 B
线程 1 尝试获取锁 B，但被阻塞
线程 2 尝试获取锁 A，但被阻塞
线程 1 对锁 B 的请求超时
→ 线程 1 回退，同时释放锁 A
→ 线程 1 随机等待（例如 257 毫秒）后重试
线程 2 对锁 A 的请求超时
→ 线程 2 回退，同时释放锁 B
→ 线程 2 随机等待（例如 43 毫秒）后重试
在上述例子中，线程 2 大约会比线程 1 早 200 毫秒重试，因此很可能成功获取两个锁。当线程 2 完成后，线程 1 也能成功获取两个锁（除非在此期间有其他线程介入）。
注意事项：
- 锁超时并不一定意味着发生了死锁。也可能是持有锁的线程执行任务耗时较长。
- 高并发下仍可能反复死锁：如果有大量线程（如 10 或 20 个）竞争相同资源，即使使用随机退避，它们仍可能反复同时重试，导致持续冲突。
- Java 的
synchronized块不支持超时。你必须使用自定义锁类，或 Java 5 引入的java.util.concurrent包中的并发工具（如ReentrantLock.tryLock(timeout)）。编写自定义锁并不困难，但超出了本文范围。
死锁检测（Deadlock Detection）
死锁检测是一种更重量级的死锁预防机制，适用于无法使用锁排序或锁超时不现实的场景。
每当一个线程获取一个锁时，系统会在一个数据结构（如图或映射）中记录“线程–锁”关系。同样，当线程请求一个锁时，该请求也会被记录。
当一个线程请求锁但被拒绝时，它可以遍历这个“锁图”来检查是否发生了死锁。
举例说明：
- 线程 A 请求锁 7，但锁 7 被线程 B 持有。
- 线程 A 检查：线程 B 是否请求了线程 A 当前持有的任意一个锁？
- 如果是，则发生死锁（例如：A 持有锁 1 并请求锁 7；B 持有锁 7 并请求锁 1）。
当然，真实死锁可能更复杂：
线程 A 等待 B → B 等待 C → C 等待 D → D 等待 A。
此时，线程 A 需要递归地检查 B 请求的所有锁，再从 B 的请求中找到 C，依此类推，直到发现 D 请求了 A 持有的某个锁——从而确认死锁。
下图展示了四个线程（A、B、C、D）所持有和请求的锁关系，这种数据结构可用于死锁检测：
（注：原文此处有一张锁依赖图，此处省略）
检测到死锁后怎么办？
全部回退策略：所有涉及线程释放锁、随机等待后重试。
- 缺点：与锁超时类似，在高竞争下可能反复死锁。
优先级策略（推荐）：为线程分配优先级，只有低优先级线程回退，高优先级线程继续执行。
- 若优先级固定，可能导致某些线程总是被牺牲。
- 改进：每次检测到死锁时随机分配优先级，避免不公平。