死锁
medium操作系统死锁银行家算法资源分配
什么是死锁
死锁（Deadlock）是指两个或多个进程互相等待对方持有的资源，导致所有相关进程都无法继续执行的状态。
用一个比喻：两个人在狭窄的走廊中面对面走来，每个人都坚持让对方先让路，结果谁也过不去。
进程 A: 进程 B:
持有 资源 1 持有 资源 2
请求 资源 2 → 等待 B 释放 请求 资源 1 → 等待 A 释放
│ │
└──── 互相等待，永远阻塞 ────────┘
死锁的四个必要条件
死锁的发生必须同时满足以下四个条件（由 Coffman 提出）：
| 条件 | 含义 | 类比 |
|---|---|---|
| 互斥 | 资源一次只能被一个进程占用 | 一把锁只能一个人拿 |
| 持有并等待 | 进程持有资源的同时请求新资源 | 拿着 A 等着要 B |
| 不可抢占 | 已分配的资源不能被强制回收 | 不能从别人手里抢 |
| 循环等待 | 存在进程的环形等待链 | A 等 B，B 等 A |
打破任意一个条件，死锁就不会发生。
死锁的处理策略
1. 预防死锁（Prevention）
通过设计协议，破坏四个必要条件中的至少一个：
| 破坏的条件 | 方法 | 缺点 |
|---|---|---|
| 互斥 | 使用不需要互斥的资源（如只读文件） | 很多资源本质上需要互斥 |
| 持有并等待 | 一次性请求所有资源 | 资源利用率低 |
| 不可抢占 | 允许抢占资源（请求不到就释放已有的） | 实现复杂，可能导致饥饿 |
| 循环等待 | 资源排序法：给所有资源编号，进程必须按编号递增的顺序请求 | 需要预知所有资源 |
资源排序法是实践中最常用的预防策略：
资源编号: R1=1, R2=2, R3=3
规则: 只能按编号从小到大请求资源
进程 A: lock(R1) → lock(R2) ✅
进程 B: lock(R1) → lock(R2) ✅ ← 不会循环等待
反例:
进程 A: lock(R1) → lock(R2)
进程 B: lock(R2) → lock(R1) ❌ ← 违反排序规则
2. 避免死锁（Avoidance）
允许前三个条件存在，在每次资源分配前动态判断是否会导致死锁。
银行家算法（Banker's Algorithm）
类似银行贷款：银行在批准贷款前，会检查剩余资金是否足以满足至少一个客户的完整需求。如果是，则系统处于安全状态。
示例: 3 类资源 (A=10, B=5, C=7)，5 个进程
已分配 最大需求 仍需要
A B C A B C A B C
P0 0 1 0 7 5 3 7 4 3
P1 2 0 0 3 2 2 1 2 2
P2 3 0 2 9 0 2 6 0 0
P3 2 1 1 2 2 2 0 1 1
P4 0 0 2 4 3 3 4 3 1
当前可用: A=3, B=3, C=2
安全序列检查:
1. P1 仍需 (1,2,2) ≤ 可用 (3,3,2) → 执行 P1 → 可用变为 (5,3,2)
2. P3 仍需 (0,1,1) ≤ 可用 (5,3,2) → 执行 P3 → 可用变为 (7,4,3)
3. P4 仍需 (4,3,1) ≤ 可用 (7,4,3) → 执行 P4 → ...
4. ...
找到安全序列 <P1, P3, P4, P2, P0> → 安全状态 ✅
3. 检测死锁 + 恢复（Detection & Recovery）
不预防也不避免，让死锁发生后再检测并恢复。
检测方法：构建资源分配图（RAG），检测是否存在环路。
恢复方法：
- 终止进程：杀掉参与死锁的部分或全部进程
- 资源抢占：强制回收某个进程的资源，让其回滚
- 回滚：将进程回退到某个安全状态的检查点
4. 鸵鸟策略（忽略）
如果死锁发生的概率极低，处理死锁的代价大于重启系统，可以选择不处理。大多数通用操作系统（包括 Linux、Windows）对用户态死锁采用此策略——死锁了就重启程序。
生产高频题
死锁的四个必要条件是什么？
互斥、持有并等待、不可抢占、循环等待。四个条件必须同时满足才会死锁。
如何预防死锁？
最实用的方法是资源排序法（破坏循环等待条件）：给所有锁/资源一个全局编号，规定所有线程必须按编号从小到大的顺序获取锁。
银行家算法的基本思想？
每次分配资源前，检查分配后系统是否仍处于安全状态（即是否存在一个安全序列，使得所有进程都能按顺序完成）。如果安全则分配，否则拒绝，让进程等待。