考研笔记

死锁的概念

2.3.5 的哲学家进餐已经演示过一次：5 人同时拿起左边的筷子，每人持一根、等一根，全体卡死。这一节把那个现象一般化。

本节的核心是四个必要条件——2.4 后面三节（预防、避免、检测）全部围绕它们展开。

机制

什么是死锁

死锁：多个进程各自占有一部分资源，同时又在等待其他进程占有的资源，导致所有进程都无法向前推进的僵局。

三个要素缺一不可：多个进程、互相持有对方所需的资源、都进入阻塞且无法自行解除。

产生死锁的原因

疑问点：教材列举的死锁成因应如何把握，是否有一条稳妥的表述

教材列出”系统资源的竞争""进程推进顺序非法""信号量使用不当”等成因， 这些条目彼此并列却层次不一，需要一条稳妥可用的口径。

最稳妥的口径是：死锁的成因只有一条——“进程各自持有一部分资源，同时又在等待别人持有的资源，形成了环”。教材列的那几项，是这个环得以形成的不同途径。

按这条口径重读教材的三项，层次就清楚了：

① 系统资源的竞争——这是最直接的途径。资源数量不足以同时满足多个进程，于是各自抢到一部分后互相僵持。

这一项里有一句必须单独记住的话：

只有对不可剥夺资源的竞争才可能产生死锁；对可剥夺资源（CPU、主存）的竞争不会引起死锁。

理由很直白：可剥夺资源随时能被操作系统收回再分配，环随时可以被打破。CPU 被时间片轮转不断收回，主存可以被换出，它们永远不会成为死锁的成因。这一点是选择题的固定考点。

② 进程推进顺序非法——同样一组请求，换一个交错顺序就不死锁。

比如 P₁ 持有 R₁ 要 R₂，P₂ 持有 R₂ 要 R₁ 时死锁；但若 P₁ 先完整地跑完再让 P₂ 跑，就完全没事。死锁不是必然发生的，它取决于推进的时序——这正好呼应了 2.1.1 的”并发进程失去可再现性”。

③ 信号量使用不当——本质上是②的一个特例。

2.3.4 讲的”P 操作顺序写反导致抱着锁睡觉”就是典型例子。此外进程间互相等待对方发来的消息也属此类——注意这种情况下它们并非竞争同一个资源，而是互相等待对方产出的东西，但环的结构完全一样。

三项的关系：①说的是”为什么会争”，②说的是”为什么争会出事”，③是②在同步机制上的具体表现。它们不是三个并列的原因，而是同一件事的三个观察角度。

四个必要条件

死锁发生时，以下四个条件必然同时成立：

① 互斥条件——资源在一段时间内只能由一个进程占有。

② 不可剥夺条件——进程已获得的资源在使用完之前不能被其他进程强行夺走，只能由自己主动释放。

③ 请求并保持条件——进程已经保持了至少一个资源，又提出新的请求；新资源被占有而请求被阻塞时，它对自己已有的资源保持不放。

④ 循环等待条件——存在一个进程-资源的环形链，链中每个进程都在等待下一个进程所占有的资源。

这四条是必要条件：死锁发生 ⟹ 四条全部成立。因此破坏其中任意一条，就能保证不发生死锁——这正是 2.4.2 死锁预防的全部思路。

死锁的处理策略

四种策略，按”什么时候管”排列：

策略什么时候管对应节
鸵鸟策略（不理睬）不管—
死锁预防事前：破坏四个必要条件之一2.4.2
死锁避免事中：每次分配前判断是否进入不安全状态2.4.3
死锁检测与解除事后：允许发生，定期检测并解除2.4.4

从上到下，对资源分配的限制越来越宽松，资源利用率越来越高，但处理代价也越来越大。

边界

不可剥夺条件 vs 请求并保持条件

疑问点：如何区分不可剥夺条件与请求并保持条件

两个条件都涉及”资源留在持有者手中”，其区别何在？

判据是看问题的视角：不可剥夺是”别人抢不走”，请求并保持是”自己不放手”。

不可剥夺条件请求并保持条件
视角外部——其他进程和 OS自身——持有者本人
说的是别人无权强行拿走自己主动攥着不放
场景进程正在正常使用资源时进程因新请求而阻塞时
破坏方法申请不到新资源时，释放（或被剥夺）已有的全部资源一次性申请全部所需资源（静态分配）

关键差别在于它们描述的是不同时刻：

  • 不可剥夺描述的是平时——只要我还在用，谁都拿不走。
  • 请求并保持描述的是阻塞时——我已经因为要不到新资源而卡住了，明明自己也没在用手里的东西，却依然占着不放。

这个时刻上的区别，直接决定了两者的破坏方法完全不同：破坏”不可剥夺”是让资源能被拿走，破坏”请求并保持”是让进程不产生”边持有边等待”的状态。

死锁 vs 饥饿 vs 死循环

三者都表现为”进程推进不了”，但机制完全不同，是高频辨析点：

死锁饥饿死循环
涉及进程数至少 2 个1 个即可1 个
进程状态阻塞态通常阻塞（也可能忙等）运行态
是否占用 CPU否通常否是
成因循环等待，资源分配不当调度策略不公平程序自身的逻辑错误
能否自行解除绝无可能理论上可能（概率极低）否
归属操作系统问题操作系统问题程序员的 bug

最容易混的是死锁与饥饿：死锁的进程在等待一个”永远不会被释放”的资源；饥饿的进程等待的资源会被释放，只是每次都轮不到它。

而死循环是唯一一个不属于操作系统问题的——进程一直在正常运行、一直在占用 CPU，操作系统看不出任何异常。

循环等待是必要条件，但不是充分条件

这是本节最容易出错的一点。

“发生死锁 ⟹ 存在循环等待”成立，但反过来不成立。

反例出现在每类资源有多个实例时。设有 3 台打印机，P₁、P₂ 各持 1 台并互相等待对方的，形成了环；但此时还有第 3 台空闲着，或者存在 P₃ 用完后会释放一台——环虽然画得出来，但资源足以让某个进程推进下去，死锁并未发生。

因此准确的表述是：

  • 每类资源只有一个实例时：循环等待 ⟺ 死锁（环即死锁）
  • 每类资源有多个实例时：循环等待是死锁的必要不充分条件（有环未必死锁）

这条边界直接决定了 2.4.4 为什么不能只靠”图里有没有环”来判断死锁，而必须用资源分配图化简。

只有不可剥夺资源才会导致死锁

CPU 和主存是可剥夺资源，对它们的竞争不会产生死锁。

  • CPU：时间片一到就被收回，永远不可能被某个进程永久占有。
  • 主存：可以通过对换把进程整个换出到外存，从而收回其内存。

只有打印机、磁带机这类用一半不能中途拿走的资源，才具备构成死锁的资格。

对照速查

四个必要条件含义破坏方法
① 互斥资源一次只能给一个进程改造成可共享（通常无法实现）
② 不可剥夺别人抢不走申请不到就释放已有全部资源
③ 请求并保持自己不放手一次性申请全部资源
④ 循环等待存在环形等待链顺序资源分配法（按编号递增申请）
处理策略时机限制程度资源利用率
预防事前最严最低
避免事中中中
检测与解除事后最松最高

考点

  • 四个必要条件的名称与含义（一切的基础）
  • 不可剥夺 = 别人抢不走；请求并保持 = 自己不放手
  • 只有不可剥夺资源的竞争才可能死锁；CPU、主存不会
  • 循环等待是必要不充分条件（多实例资源时有环未必死锁）
  • 死锁 / 饥饿 / 死循环的三方辨析
  • 四种处理策略的时机与宽松程度排序

链接

反向链接