Appearance
银行家算法
考情分析
银行家算法是 408 大题的常考内容，需要完整手算安全序列。属于 🔥🔥🔥 高频核心。
死锁预防是"一刀切"地破坏必要条件，代价高。银行家算法更聪明——每次分配资源前先模拟一下，如果分完之后系统还能找到一条让所有进程都完成的路径，就批准；否则就让进程等着。
核心思想
银行家算法的思想来源于银行贷款：银行在发放贷款前要判断是否会导致资金无法回收。类比到操作系统：在分配资源前判断是否会导致死锁。
核心：每次分配资源前，先假设分配，然后用安全性算法检查是否仍处于安全状态。
数据结构
设系统有 n 个进程，m 种资源：
| 数据结构 | 维度 | 含义 |
|---|---|---|
| Available | 1×m | 各类资源的可用数量 |
| Max | n×m | 每个进程对各类资源的最大需求 |
| Allocation | n×m | 每个进程已分配的各类资源数量 |
| Need | n×m | 每个进程还需要的各类资源数量 |
关键关系：Need[i] = Max[i] - Allocation[i]
安全性算法
用于判断当前状态是否安全（是否存在安全序列）：
1. 初始化:
Work = Available // 工作向量，表示系统可提供的资源
Finish[i] = false // 所有进程标记为未完成
2. 查找一个满足条件的进程 P_i:
Finish[i] == false 且 Need[i] <= Work
3. 如果找到:
Work = Work + Allocation[i] // 模拟回收该进程的资源
Finish[i] = true
回到步骤 2
4. 如果所有 Finish[i] == true:
系统处于安全状态，找到的顺序就是安全序列
否则: 不安全完整算例
设有 3 种资源 A、B、C，总量为 (10, 5, 7)，5 个进程：
| 进程 | Max(A,B,C) | Allocation(A,B,C) | Need(A,B,C) |
|---|---|---|---|
| P0 | 7, 5, 3 | 0, 1, 0 | 7, 4, 3 |
| P1 | 3, 2, 2 | 2, 0, 0 | 1, 2, 2 |
| P2 | 9, 0, 2 | 3, 0, 2 | 6, 0, 0 |
| P3 | 2, 2, 2 | 2, 1, 1 | 0, 1, 1 |
| P4 | 4, 3, 3 | 0, 0, 2 | 4, 3, 1 |
Available = (10-7, 5-2, 7-5) = (3, 3, 2)
安全性检查
| 步骤 | Work(A,B,C) | 选择进程 | Need ≤ Work? | 执行后 Work |
|---|---|---|---|---|
| 1 | 3, 3, 2 | P1 | (1,2,2)≤(3,3,2) ✓ | 3+2, 3+0, 2+0 = 5, 3, 2 |
| 2 | 5, 3, 2 | P3 | (0,1,1)≤(5,3,2) ✓ | 5+2, 3+1, 2+1 = 7, 4, 3 |
| 3 | 7, 4, 3 | P4 | (4,3,1)≤(7,4,3) ✓ | 7+0, 4+0, 3+2 = 7, 4, 5 |
| 4 | 7, 4, 5 | P0 | (7,4,3)≤(7,4,5) ✓ | 7+0, 4+1, 5+0 = 7, 5, 5 |
| 5 | 7, 5, 5 | P2 | (6,0,0)≤(7,5,5) ✓ | 10, 5, 7 |
安全序列：P1 → P3 → P4 → P0 → P2（安全序列不唯一）
资源请求处理
假设 P1 请求 Request = (1, 0, 2)：
- 检查 Request ≤ Need[P1]：(1,0,2) ≤ (1,2,2) ✓
- 检查 Request ≤ Available：(1,0,2) ≤ (3,3,2) ✓
- 试探分配：
- Available = (3,3,2) - (1,0,2) = (2, 3, 0)
- Allocation[P1] = (2,0,0) + (1,0,2) = (3, 0, 2)
- Need[P1] = (1,2,2) - (1,0,2) = (0, 2, 0)
- 执行安全性算法检查新状态是否安全
如果安全 → 正式分配；如果不安全 → 撤销试探分配，进程等待。
交互可视化
算法的局限性
| 局限 | 说明 |
|---|---|
| 需要预知 Max | 进程必须事先声明最大资源需求 |
| 效率低 | 每次分配都要执行安全性检查 |
| 进程数固定 | 不适合进程数动态变化的系统 |
易错
银行家算法计算中最常见的错误：
- 进程完成后释放的资源是 Allocation（已持有的），不是 Need（还需要的）。即
，不是 - 安全序列不唯一，但不安全状态是确定的——只要找不到任何安全序列就是不安全
- "不安全状态"≠"死锁"：不安全状态只是可能死锁，不是一定
考研高频考点
- 🔥🔥🔥 手算安全序列（给定 Max/Allocation/Available，逐步计算 Work）
- 🔥🔥🔥 处理资源请求的三步检查（Request≤Need, Request≤Available, 安全性检查）
- 🔥🔥 Need = Max - Allocation
- 🔥🔥 安全序列不唯一
- 🔥 银行家算法属于死锁避免（不是预防也不是检测）
银行家算法是"事前预防"，但如果觉得这个检查开销太大、愿意冒一点风险呢？下一篇看死锁检测与解除——先让死锁发生，再处理。