[!info] related notes 操作系统 MOC 内存管理

死锁

1) 定义

多个进程因竞争资源而相互等待，若无外力作用均无法推进。

2) 四个必要条件（必背）

1. 互斥：资源一次只能被一个进程使用。
2. 请求并保持：进程持有资源的同时请求新资源。
3. 不可剥夺：已分配的资源不能被强制回收。
4. 循环等待：存在进程环，每个进程等待下一个持有的资源。

破坏任意一个条件即可预防死锁。

3) 资源分配图（Resource Allocation Graph）

用有向图表示进程与资源的关系：

P1 → R1    （P1 请求 R1）
R1 → P2    （R1 已分配给 P2）
P2 → R2    （P2 请求 R2）
R2 → P1    （R2 已分配给 P1）

→ 形成环路 P1→R1→P2→R2→P1 = 死锁

• 有环不一定死锁（每类资源只有一个实例时，有环 = 死锁）。
• 无环一定无死锁。

4) 哲学家就餐问题（经典示例）

5 位哲学家围坐圆桌，每人左右各一只筷子，需同时拿起两只才能就餐。

  P0 -- P1
 /        \
P4        P2
 \        /
  P3 -- ...

• 问题：每人先拿左筷再拿右筷 → 可能死锁（所有人同时拿起左筷）。
• 解决方案：
  • 限制同时就餐人数（最多 4 人）→ 破坏”请求并保持”
  • 一次性申请所有资源 → 破坏”请求并保持”
  • 编号策略：奇数先拿左、偶数先拿右 → 破坏”循环等待”

5) 死锁检测：等待图（Wait-For Graph）

简化版资源分配图，只保留进程节点。若图中存在环路则检测到死锁。

P1 → P2 → P3 → P1  （环，死锁）

检测算法：定期对等待图做环检测，复杂度 $O(n^2)$。

6) 处理方法

策略	时机	方法
预防	事前	破坏四个必要条件之一
避免	事中	银行家算法，不进入不安全状态
检测+解除	事后	允许发生，检测到后解除

7) 银行家算法（常考点）

系统有 $m$ 类资源、$n$ 个进程。核心数据结构：

• Max：每个进程的最大需求
• Allocation：已分配给每个进程的资源
• Need = Max - Allocation：每个进程还需要多少
• Available：系统当前可用资源

算法流程

收到进程 $P_i$ 的请求 $Request_i$：

1. 检查 $Request_i \leq Need_i$，否则报错
2. 检查 $Request_i \leq Available$，否则等待
3. 试探分配：修改 Available、Allocation、Need
4. 执行安全性算法：检查是否存在安全序列
5. 若安全，正式分配；否则回滚，让 $P_i$ 等待

安全性算法

Work = Available
Finish[i] = false for all i

while 存在 Finish[i]==false 且 Need[i] <= Work:
    Finish[i] = true
    Work += Allocation[i]

若所有 Finish[i]==true → 安全状态

示例

进程	Allocation	Max	Need	Available
P0	(1,0,2)	(4,3,5)	(3,3,3)	(2,3,3)
P1	(2,1,1)	(3,2,2)	(1,1,1)
P2	(1,0,2)	(2,1,3)	(1,1,1)

安全序列：P1 → P2 → P0（P1 先完成释放资源，依次推进）。

易错点

• 安全状态 != 立刻可执行：安全序列中排在后面的进程需要等待。
• 不安全状态 != 已死锁：只是可能死锁，如果进程后续不请求更多资源仍可完成。
• 银行家算法开销大（$O(mn^2)$），实际系统多用检测+解除。

相关笔记

• 操作系统 MOC

内存管理