银行家算法
基础概念
- 当前可用资源数
Available - 已分配到的资源数
Allocation - 尚需资源需求
Need = Max - Allocation
例题
| 进程 | 已分配到的资源Allocation | 尚需资源需求Need | 当前可用资源数Available |
|---|---|---|---|
| P0 | (1,1,1,0) | (0,3,3,1) | (0,3,2,2) |
| P1 | (0,2,3,1) | (0,3,4,2) | |
| P2 | (0,2,1,2) | (1,0,3,4) | |
| P3 | (0,3,1,0) | (0,3,2,0) | |
| P4 | (1,0,2,1) | (0,4,2,3) |
该状态是否安全
1. 画表格
| 进程\资源 | Work | Need | Allocation | Work+Allocation | Finish |
|---|---|---|---|---|---|
2. 写出 Work
第一个 Work 就是 Available。
| 进程\资源 | Work | Need | Allocation | Work+Allocation | Finish |
|---|---|---|---|---|---|
| 0,3,2,2 |
3. 挑选 Need
若 Need < Work，就可以。刚好P3 可以,Need 为 (0,3,2,0)。
| 进程\资源 | Work | Need | Allocation | Work+Allocation | Finish |
|---|---|---|---|---|---|
| P3 | 0,3,2,2 | 0,3,2,0 | 0,3,1,0 | 0,6,3,2 | T |
4. 写出下一个 Work
下一个 Work 就是上一个 Work+Allocation，所以就是 (0,6,3,2)。
| 进程\资源 | Work | Need | Allocation | Work+Allocation | Finish |
|---|---|---|---|---|---|
| P3 | 0,3,2,2 | 0,3,2,0 | 0,3,1,0 | 0,6,3,2 | T |
| 0,6,3,2 |
5. 挑选 Need
发现 P0 就可以，是 (0,3,3,1)。然后找到对应的 Allocation，最终计算出 Work+Allocation。
| 进程\资源 | Work | Need | Allocation | Work+Allocation | Finish |
|---|---|---|---|---|---|
| P3 | 0,3,2,2 | 0,3,2,0 | 0,3,1,0 | 0,6,3,2 | T |
| P0 | 0,6,3,2 | 0,3,3,1 | 1,1,1,0 | 1,7,4,2 | T |
6. 以此类推
| 进程\资源 | Work | Need | Allocation | Work+Allocation | Finish |
|---|---|---|---|---|---|
| P3 | 0,3,2,2 | 0,3,2,0 | 0,3,1,0 | 0,6,3,2 | T |
| P0 | 0,6,3,2 | 0,3,3,1 | 1,1,1,0 | 1,7,4,2 | T |
| P1 | 1,7,4,2 | 0,3,4,2 | 0,2,3,1 | 1,9,7,3 | T |
| P4 | 1,9,7,3 | 0,4,3,2 | 1,0,2,1 | 2,9,9,4 | T |
| P2 | 2,9,9,4 | 1,0,3,4 | 0,2,1,2 | 2,11,10,6 | T |
所以该状态安全。安全序列为 P3
如果 P0 提出资源请求 (0,0,0,1) 系统能否将资源分配给它
回到题干
| 进程 | 已分配到的资源Allocation | 尚需资源需求Need | 当前可用资源数Available |
|---|---|---|---|
| P0 | (1,1,1,0) | (0,3,3,1) | (0,3,2,2) |
| P1 | (0,2,3,1) | (0,3,4,2) | |
| P2 | (0,2,1,2) | (1,0,3,4) | |
| P3 | (0,3,1,0) | (0,3,2,0) | |
| P4 | (1,0,2,1) | (0,4,2,3) |
判断是否可以更新
此时判断 Request 是否都小于 Need 和 Available。
P0 时，Request = (0,0,0,1)，此时 Need = (0,3,3,1)，Available = (0,3,2,2)
由于：
Request < Need 且 Request < Available
所以可以更新。
开始更新
- 新的
Need' = Need - Request - 新的
Allocation' = Allocation + Request - 新的
Available' = Available - Request
更新后：
Need'= (0,3,3,0)Allocation'= (1,1,1,1)Avaliable'= (0,3,2,1)
| 进程 | 已分配到的资源Allocation | 尚需资源需求Need | 当前可用资源数Available |
|---|---|---|---|
| P0 | (1,1,1,1) | (0,3,3,0) | (0,3,2,1) |
| P1 | (0,2,3,1) | (0,3,4,2) | |
| P2 | (0,2,1,2) | (1,0,3,4) | |
| P3 | (0,3,1,0) | (0,3,2,0) | |
| P4 | (1,0,2,1) | (0,4,2,3) |
判断安全性
| 进程\资源 | Work | Need | Allocation | Work+Allocation | Finish |
|---|---|---|---|---|---|
| P3 | 0,3,2,1 | 0,3,2,0 | 0,3,1,0 | 0,6,3,1 | T |
| P0 | 0,6,3,1 | 0,3,3,0 | 1,1,1,1 | 1,7,4,2 | T |
| P1 | 1,7,4,2 | 0,3,4,2 | 0,2,3,1 | 1,9,7,3 | T |
| P4 | 1,9,7,3 | 0,4,2,3 | 1,0,2,1 | 2,9,9,4 | T |
| P2 | 2,9,9,4 | 1,0,3,4 | 0,2,1,2 | 2,11,10,6 | T |
所以该状态安全。
安全序列为 P3