死锁、饥饿与优先级反转 — 专题笔记

基本概念

概念	一句话
死锁	多个进程互相等待对方持有的资源，谁也无法推进
饥饿	某个进程因资源分配策略不公平，长期得不到所需资源
安全序列	一个进程执行顺序（比如 $P_{2} \to P_{1} \to P_{3} \dots$ ），按此顺序每个进程执行时，前面进程释放的资源足够满足它的剩余需求，最终所有进程都能完成
优先级反转	高优先级任务被低优先级任务阻塞（低优先级持有锁，中优先级抢走 CPU）

死锁四必要条件（缺一不可）：

条件	含义	破坏方式
互斥	资源只能被一个进程独占	难破坏，很多资源本质就是互斥的
不可剥夺	已分配资源不能被强制抢走	允许系统抢占（如 CPU、内存换出）
请求并保持	拿着旧资源等新资源	一次性申请全部所需资源
循环等待	形成 $P_{0} \to P_{1} \to ... \to P_{n} \to P_{0}$ 的等待环	资源编号，强制按递增顺序申请

每类资源只有一个实例时，资源分配图中的环 ⇔ 死锁的充要条件。多实例时环是必要但不充分。

避免死锁 — 银行家算法

安全状态：存在一个执行序列，序列中每个进程执行时，前面所有进程释放的资源总量能满足它剩余的 Need。

核心变量

变量	维度	含义	关系
`Max`	n×m 矩阵	进程最多需要各类资源的数量	已知常量
`Allocation`	n×m 矩阵	进程当前已占用的各类资源数	初值给定，分配时增加
`Need`	n×m 矩阵	进程还需要的各类资源数	`Need = Max - Allocation`
`Available`	m 维向量	系统当前空闲的各类资源数	分配时减少，归还时增加

安全性检测

题目形式：给 Max + Allocation + 若干候选 Available，判断哪些安全。

操作流程：

① Need = Max - Allocation               // 逐进程减，得需求表
② 找 Need[i] ≤ Available 的进程（每个分量都要 ≤）
   ├─ 找到 → ③
   └─ 找不到 → 不安全，死锁
③ 执行该进程：Available += Allocation[i]   // 归还全部已分配资源
④ 重复②~③，直到所有进程都执行完 → 安全

演练速查：

Available 初始	首步可执行	归还后 Available	能否走完
`(1, 4, 0)`	$P_{2}$	`(2, 7, 5)`	✅ 安全
`(0, 6, 2)`	$P_{0}$	`(0, 6, 5)`	❌ $P_{1}$ 需 B=7、 $P_{2}$ 需 A=1 都无法满足
`(1, 1, 1)`	$P_{0}$ , $P_{2}$	`(2, 4, 9)`	❌ 剩下进程 B 类需求 ≥6，可用 B=4
`(0, 4, 7)`	$P_{0}$	`(0, 4, 10)`	❌ $P_{2}$ 需 A=1，可用 A=0

死锁检测（资源分配图化简法）

不断找当前能继续执行的进程（Need ≤ Available），假设它执行完释放资源，删去它所有的边。最终图可完全化简 → 无死锁；不可化简 → 有死锁。

与安全性检测的区别：检测不关心 Max，只看当前 Allocation 和 Available。

死锁解除

方法	做法	代价
资源剥夺	从其他进程强制抢资源给死锁进程	被剥夺进程受损
撤销进程	终止死锁中的一个或多个进程	丢失已完成的工作
进程回退	回滚到死锁前的检查点	需检查点机制支持

优先级反转

产生条件：低优先级任务持有锁 → 中优先级任务抢占 CPU → 高优先级任务等锁，被中优先级任务阻塞。

解决方法：

优先级继承：持锁的低优先级任务临时继承等待者的高优先级，防止中优先级任务插队
优先级天花板：进入临界区后，任务优先级直接提到临界区能进入的最高优先级

evil0knight's Blog

探索

死锁、饥饿与优先级反转