💀 死锁

死锁的必要条件 · 资源分配图 · 银行家算法 · 死锁预防 · 检测与恢复
必要条件 资源分配图 银行家算法 死锁预防 检测与恢复
🔐 死锁四个必要条件
四个条件同时满足时，死锁一定发生（必要条件 = 死锁 → 四个条件都成立）
🔒
互斥条件
进程对资源的访问是互斥的，资源同时只能被一个进程使用。
注：非共享资源（如打印机）才有互斥性。
✋
不剥夺条件
进程获得的资源，在主动释放前不能被其他进程夺走。
OS不能强行回收已分配资源。
🤲
请求并保持
进程已持有至少一个资源，又请求新资源，且不释放已持有的资源。
一边拿着筷子，一边等另一根。
🔄
循环等待条件
存在一个进程等待链：P₀→P₁→P₂→…→Pₙ→P₀。
资源分配图中有环（且环上每个资源只有一个实例时，环 ↔ 死锁）。
记忆口诀：「互相不让，请你循环」（互斥、不剥夺、请求并保持、循环等待）
处理死锁的三种策略：死锁预防（破坏条件）、死锁避免（银行家算法）、死锁检测与恢复
🕸️ 资源分配图（RAG）
观察三种场景：安全无死锁 · 有环但无死锁 · 死锁
安全场景
有环无死锁
死锁场景
✅ 安全：资源分配图无环，或虽有环但资源有多实例可以分配。此场景中P₁持有R₂、申请R₁；P₂持有R₁、申请R₂——但R₁和R₂各有两个实例，所以有安全序列。
⚠️ 有环但无死锁：当资源有多实例时，环不一定意味着死锁。此场景中R₁有两个实例，P₁和P₂各持有一个，可以都继续执行。
❌ 死锁！每个资源只有一个实例，且形成环路P₀→R₁→P₁→R₂→P₀。化简结果：无法完全化简，剩余环即为死锁进程。
图化简算法（死锁检测）：
1. 找非阻塞进程（所有请求边都能满足）→ 去掉它的所有边
2. 重复步骤1，直到没有可化简的进程
3. 若所有进程都能被化简→ 无死锁；若剩余进程无法化简→ 剩余进程处于死锁状态
🏦 银行家算法
动态检测系统是否处于安全状态 · 点击预定义请求或手动输入
算法思想（Dijkstra）：进程申请资源时，系统先试探分配，然后检查分配后系统是否处于安全状态。 若安全则批准申请；否则让进程等待。
安全状态：存在一个进程执行序列，使得每个进程都能获得所需的最大资源。
安全检测
资源请求模拟
点击「运行安全检测」开始
模拟请求：点击下方按钮模拟不同进程的资源请求，观察系统是否批准。
P₁申请(1,0,2)：P₁已持有(2,0,0)，再申请(1,0,2)，共需(3,3,2) ≤ 最大需求 ✅
P₃申请(3,3,0)：P₃已持有(3,0,2)，再申请(3,3,0)，超过最大需求(5,3,2) ❌
点击上方按钮模拟资源请求
🛡️ 死锁预防
破坏四个必要条件之一，使死锁不可能发生 · 点击卡片查看动画
🔓
破坏互斥
将互斥资源改为共享资源（如SPOOLing）
⚡
破坏不剥夺
允许抢占资源（代价：可能饥饿）
📦
破坏请求与保持
预先一次性申请所有资源
🔢
破坏循环等待
资源有序编号，按序申请
预防 vs 避免 vs 检测：
· 预防：静态策略，破坏必要条件，在资源分配前就阻止死锁（限制严格，资源利用率低）
· 避免：动态策略，分配时检查安全状态（如银行家算法，开销中等）
· 检测：允许死锁发生，定期检查并恢复（开销最小，但需恢复机制）
🔍 死锁检测与恢复
允许死锁发生，通过资源分配图化简判断是否存在死锁 · 点击下一步逐步检测
检测算法（资源分配图化简法）：
1. 在资源分配图中找既无请求边又无分配边的节点
2. 若找到可消去的节点 → 删除其所有边
3. 重复直到无法消去
4. 若图为空 → 无死锁；若仍有节点 → 存在死锁

本例：P1→R2→P2→R3→P3→R1→P1，形成环！
初始状态：P1持有R1请求R2，P2持有R2请求R3，P3持有R3请求R1 — 形成循环等待
🔧 死锁恢复策略
🛑
终止进程
方案一：终止所有死锁进程（代价大）
方案二：逐个终止，直到死锁解除（需选择牺牲者）
⏮️
资源剥夺
逐步剥夺死锁进程的资源，分配给其他进程
关键：选择代价最小的进程剥夺
🔄
进程回滚
让进程回退到某个检查点，释放资源
前提：系统需建立检查点机制（Rollback）
⚖️
牺牲者选择
优先级低 / 执行时间短 / 已耗资源少 / 恢复代价小的进程优先牺牲