死锁
→ 返回计算机基础
死锁（Deadlock）是指多个进程/线程因互相等待对方持有的资源而永久阻塞的状态。
四个必要条件（Coffman 条件）
死锁发生当且仅当以下四个条件同时成立：
| 条件 | 说明 |
|---|---|
| 互斥 | 资源一次只能被一个进程使用 |
| 占有并等待 | 进程持有资源的同时等待其他资源 |
| 不可抢占 | 资源只能由持有者主动释放，不能被强制剥夺 |
| 循环等待 | 存在进程等待链形成环路：P1 等 P2，P2 等 P3，…，Pn 等 P1 |
破坏任意一个条件即可预防死锁。
资源分配图（RAG）
用有向图表示进程与资源的分配/请求关系：
P1 ──请求──→ R1
R1 ──分配──→ P2
P2 ──请求──→ R2
R2 ──分配──→ P1
上图形成环路 → 死锁
图中存在环路是死锁的必要条件（每种资源只有一个实例时也是充分条件）。
处理策略
1. 死锁预防（Prevention）
静态策略，破坏四个条件之一：
| 破坏条件 | 做法 | 代价 |
|---|---|---|
| 互斥 | 尽量使用无锁结构 | 不适用所有资源 |
| 占有并等待 | 一次性申请所有资源，或申请新资源前释放已有资源 | 资源利用率低 |
| 不可抢占 | 允许强制剥夺资源（如 CPU 时间片） | 需保存/恢复状态 |
| 循环等待 | 对资源编号，进程只能按序申请 | 限制申请灵活性 |
2. 死锁避免（Avoidance）
动态策略，分配前判断是否会导致不安全状态。
银行家算法：每次分配前检查是否存在安全序列（按该顺序分配，所有进程都能完成）：
安全状态 → 存在安全序列 → 不会死锁
不安全状态 → 可能死锁（拒绝本次分配）
示例（3 个进程，共 10 个资源）：
| 进程 | 最大需求 | 已分配 | 还需 |
|---|---|---|---|
| P0 | 7 | 0 | 7 |
| P1 | 3 | 2 | 1 |
| P2 | 9 | 3 | 6 |
剩余可用：5。安全序列：P1（需 1≤5，完成后可用 7）→ P0（需 7≤7）→ P2（需 6≤9）✓
3. 死锁检测与恢复（Detection & Recovery）
允许死锁发生，定期检测，发现后恢复：
检测：定期运行资源分配图的环路检测（DFS）。
恢复方式：
| 方式 | 说明 |
|---|---|
| 进程终止 | 终止死锁环中的一个或所有进程 |
| 资源抢占 | 强制剥夺某进程的资源，将进程回滚到安全状态 |
选择目标的原则：优先级最低、已运行时间最短、占用资源最多。
4. 鸵鸟策略（Ostrich Algorithm）
假装死锁不会发生，出现时重启系统。适用于死锁概率极低的系统（如大多数桌面 OS）。
实际场景
数据库死锁
两个事务互相持有对方需要的行锁：
T1：lock(Row A) → 等待 lock(Row B)
T2：lock(Row B) → 等待 lock(Row A)
数据库通过超时或等待图检测发现死锁，回滚代价较小的事务。
Java 死锁示例
// 线程 1
synchronized(lockA) {
synchronized(lockB) { ... }
}
// 线程 2
synchronized(lockB) {
synchronized(lockA) { ... } // 循环等待
}预防：统一锁顺序（始终先锁 A 再锁 B）；使用 tryLock(timeout) 替代 lock()。
活锁与饥饿
| 现象 | 说明 |
|---|---|
| 死锁 | 进程永久阻塞，无法推进 |
| 活锁 | 进程不断改变状态但无法推进（互相”礼让”） |
| 饥饿 | 进程长期得不到资源（低优先级持续被抢占） |