死锁
死锁是一组线程或进程相互等待对方持有的资源,谁都无法继续执行的状态。判断死锁,不能只看一个线程等了多久,而要找出谁持有什么、又在等谁。理解这条等待关系,才能解释四个必要条件,判断统一加锁顺序和超时为什么有效、各有什么限制。
1. 面试核心
先记住这几条,再读正文2. 等待环
死锁的关键是等待关系形成了无法自行解除的环。假设 A、B 两把锁各只能由一个线程持有,两个线程执行到下面的状态:
线程 T1:持有 A,等待 B
线程 T2:持有 B,等待 A
T1 要等 T2 释放 B,T2 又要等 T1 释放 A。如果两者都坚持拿到第二把锁后才释放第一把,就没有任何一方能先向前执行,形成 T1 → T2 → T1 的等待环。这同时满足四个必要条件:
| 必要条件 | 含义 |
|---|---|
| 互斥 | 同一资源实例不能同时分配给多个主体。 |
| 占有并等待 | 持有资源时继续等待其他资源。 |
| 不可剥夺 | 资源由持有者主动释放。 |
| 循环等待 | 每个主体等待环中下一个主体持有的资源。 |
当每类资源只有一个实例时,等待图中的环就意味着死锁。如果一类资源有多个实例,资源图中出现环还不足以下结论:环外任务可能释放另一个实例,让某个等待者继续执行。
3. 预防与恢复
死锁预防是预先制定规则,破坏至少一个必要条件。例如所有线程都先获取 A,再获取 B,任何线程都不会拿着 B 等 A,循环等待就无法形成。对多个业务对象加锁时,可以先按稳定的对象 ID 排序,再依次获取。
另一种办法是要求一次取得所需的全部资源,无法取得就不保留部分资源,从而破坏占有并等待。实际用逐个尝试的方式实现时,中途失败要释放已经拿到的资源再重试。代价是任务可能等得更久,一些本可使用的资源也可能闲置。
如果系统允许死锁发生,就需要收集等待关系来检测,再中止某个任务或回滚操作,释放资源让其他任务继续。不能简单地强制停止持锁线程:它可能已经把共享数据改到一半,恢复时还要处理这些中间状态。
4. 安全状态与死锁避免
安全状态是指存在一种任务完成顺序:系统用当前可用资源和前面任务完成后释放的资源,就能满足后面任务的需求,让所有任务最终完成。这个顺序叫作安全序列。死锁避免在每次分配资源时检查是否会失去这种保证,银行家算法就是一种做法。
假设系统共有 10 份同类资源,P1 已有 5 份、最多需要 7 份,P2 已有 3 份、最多需要 9 份。当前还剩 2 份,先给 P1,它就能完成并释放手中的 7 份。P2 还需要 6 份,这时也够用了,所以 P1 → P2 是一个安全序列。
如果先把剩余 2 份给 P2,两个任务就都持有 5 份,系统没有资源可分配。按声明的最大需求,P1 还缺 2 份,P2 还缺 4 份,谁都无法保证先完成。因此,银行家算法会拒绝这次分配。
不安全只表示无法保证所有任务完成,还不能据此断言已经死锁。比如 P2 实际拿到 5 份就完成了,并没有用到声明的上限,系统仍能继续运行。
银行家算法需要任务提前声明最大资源需求。通用服务往往难以准确给出这个上限,所以在加锁代码中,统一顺序通常更容易落实。
5. 使用边界
长时间等待本身不能证明死锁,它也可能来自慢 I/O 或资源不足。排查时,要用线程栈、资源持有者和完整等待链确认有没有无法解除的相互依赖。
活锁是线程仍在运行,却因相互干扰一直没有进展,例如双方都不断释放、重试,又反复碰撞;退避和随机抖动可以减少这种碰撞。饥饿则是某个任务长期得不到资源,其他任务却能正常推进,公平排队可以改善这种情况。
超时后,如果仍拿着第一把锁,只重试第二把锁,原来的等待条件就没有消失。失败路径应先释放已取得的资源、恢复必要状态,再开始新一轮尝试。
6. 面试题卡片
7. 参考资料
来源:Coding 101 原文 · 免费阅读,引用请保留出处。内容使用说明