银行家算法分析
参考资料
概述
持有并等待条件导致的死锁
在多进程或多线程并发访问资源的场景下，死锁（Deadlock）是一种让人头疼的问题：几个任务相互等待，谁也拿不到继续执行的机会。银行家算法（Banker’s Algorithm）就是荷兰计算机科学家 Dijkstra 提出的一套“贷款”式资源分配方案，保证系统不陷入死锁。
为什么需要银行家算法
想象一家银行有一笔总资金，多个客户（进程）可能随时来申请贷款（资源）。如果不加以控制，一旦所有客户都拿走部分贷款，却留下一些客户的需求得不到满足，就可能让银行陷入“钱不够分”又“谁也不肯还款”的窘境。操作系统中的资源（内存块、I/O 通道、锁等）同理：若乱放行，很可能出现死锁，各进程互相等待而永远卡住。
在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。
银行家算法的核心思想是：
在满足安全条件的前提下才分配资源，永远确保系统处于“安全状态”——即总能找到一种方式，让所有进程依次完成。
算法流程
算法需要管理的“账本”
银行家算法维护四张表/向量，仿佛银行的“账本”：
- Available（可用资源向量）
系统当前还剩余多少个各类资源可以分配。
- Max（最大需求矩阵）
每个进程一生中最多可能向系统请求多少该类资源，事先必须申报。
- Allocation（已分配矩阵）
系统已发给每个进程多少资源。
- Need（需求矩阵）
每个进程还“差”多少资源才算满足最大需求，它等于
只有在
Request ≤ Need且Request ≤ Available的条件下，才会尝试分配。更重要的是，真正分配前还要做一次“安全性检查”（Safety Check）。
什么是“安全状态”？
“安全状态”意味着：即便所有进程都提出最坏请求，系统依然能保证按某种顺序让它们一个个拿到资源、干完活再归还。
要检测这一点，算法会模拟一个“假设执行”过程：
- 复制一份可用资源
Work = Available，并标记所有进程Finish[i] = false。 - 找到一个
Finish[i]==false且其Need[i] ≤ Work的进程（说明它现在提出最大需求也能满足）。 - 假设让它拿到所需资源并执行完毕：把它手里原本的
Allocation[i]全部“还给”Work (Work += Allocation[i])，并把Finish[i]=true。 - 重复第 2、3 步，直到没有可满足的进程为止。
- 如果最后所有
Finish[i]都变成了true，说明系统处于安全状态；否则，不安全。
分配资源前的“试探”与回滚
当某个进程 Request[i] 时，银行家算法按照以下步骤执行：
合法性检查
- 若
Request[i][j] > Need[i][j]——进程请求超过申报最大值，直接报错； - 若
Request[i][j] > Available[j]——当前可用资源不足，让进程等待。
试探性分配
Available := Available - Request[i]
Allocation[i] := Allocation[i] + Request[i]
Need[i] := Need[i] - Request[i]安全性检测
- 如果“假设执行”后仍处于安全状态，就真正批准这笔分配；
- 否则回退到分配前的状态，让进程继续等待。
这样，系统永远不会进入一个“一旦分配就死锁”的局面。
一步步示例演示
假设有 5 个进程
Available = [3, 3, 2] // 还空闲的 A、B、C 实例数
Max =
P0: [7, 5, 3]
P1: [3, 2, 2]
P2: [9, 0, 2]
P3: [2, 2, 2]
P4: [4, 3, 3]
Allocation =
P0: [0, 1, 0]
P1: [2, 0, 0]
P2: [3, 0, 2]
P3: [2, 1, 1]
P4: [0, 0, 2]
Need = Max − Allocation =
P0: [7,4,3]
P1: [1,2,2]
P2: [6,0,0]
P3: [0,1,1]
P4: [4,3,1]安全性检查示例
Work = [3,3,2]- 找到
（Need [1,2,2]≤ Work）→ “假设”它执行并还资源 →
Work = [3,3,2] + Alloc[P1]=[2,0,0] = [5,3,2]
Finish[P1] = true- 再找
（Need [0,1,1]≤[5,3,2]），放行并还：
Work = [5,3,2] + [2,1,1] = [7,4,3]
Finish[P3] = true- 然后
, , 依次被发现、安全、放行……最终所有 Finish[]都是true，说明系统安全。
进程发请求示例
若 [1,0,2]：
Request≤Need&& ≤Available（[3,3,2]），合法；- 暂时分配后
Available’=[2,3,0]，Alloc[1]=[3,0,2]，Need[1]=[0,2,0]； - 再用安全性检查，仍找得一条完成序列 → 批准；
反之，若分配后安全性检查失败，就拒绝这次请求并回滚，保证系统永不死锁。
代码实现
C++ 版本
#include <vector>
#include <iostream>
using namespace std;
// 安全性检查
bool isSafe(vector<int> Available,
vector<vector<int>>& Max,
vector<vector<int>>& Alloc) {
int n = Max.size(), m = Available.size();
vector<int> Work = Available;
vector<bool> Finish(n, false);
// 计算 Need
vector<vector<int>> Need(n, vector<int>(m));
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
Need[i][j] = Max[i][j] - Alloc[i][j];
// 模拟放行
for (int k = 0; k < n; ++k) {
bool found = false;
for (int i = 0; i < n; ++i) {
if (!Finish[i]) {
bool ok = true;
for (int j = 0; j < m; ++j)
if (Need[i][j] > Work[j]) { ok = false; break; }
if (ok) {
for (int j = 0; j < m; ++j) Work[j] += Alloc[i][j];
Finish[i] = true;
found = true;
}
}
}
if (!found) break;
}
// 全能放行才安全
for (bool f : Finish) if (!f) return false;
return true;
}
// 请求资源接口
bool requestResource(int pid, vector<int> Request,
vector<int>& Available,
vector<vector<int>>& Max,
vector<vector<int>>& Alloc) {
int m = Available.size();
// 合法性检查
for (int j = 0; j < m; ++j)
if (Request[j] > Max[pid][j] - Alloc[pid][j]
|| Request[j] > Available[j]) return false;
// 试探性分配
for (int j = 0; j < m; ++j) {
Available[j] -= Request[j];
Alloc[pid][j] += Request[j];
}
// 安全检测：通过就保留，否则回滚
if (isSafe(Available, Max, Alloc)) return true;
for (int j = 0; j < m; ++j) {
Available[j] += Request[j];
Alloc[pid][j] -= Request[j];
}
return false;
}
int main(){
vector<int> Available{3,3,2};
vector<vector<int>> Max{
{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}
};
vector<vector<int>> Alloc{
{0,1,0},{2,0,0},{3,0,2},{2,1,1},{0,0,2}
};
cout << "初始安全? " << (isSafe(Available, Max, Alloc) ? "是\n" : "否\n");
vector<int> req{1,0,2};
cout << "P1 请求 [1,0,2]: "
<< (requestResource(1, req, Available, Max, Alloc) ? "批准\n":"拒绝\n");
}Python 版本
def is_safe(available, max_d, alloc):
n, m = len(max_d), len(available)
work = available[:]
finish = [False]*n
need = [[max_d[i][j]-alloc[i][j] for j in range(m)]
for i in range(n)]
while True:
found = False
for i in range(n):
if not finish[i] and all(need[i][j] <= work[j] for j in range(m)):
for j in range(m):
work[j] += alloc[i][j]
finish[i] = True
found = True
if not found: break
return all(finish)
def request_resource(pid, req, available, max_d, alloc):
m = len(available)
# 合法性检查
for j in range(m):
if req[j] > max_d[pid][j]-alloc[pid][j] or req[j] > available[j]:
return False
# 试探分配
for j in range(m):
available[j] -= req[j]
alloc[pid][j] += req[j]
if is_safe(available, max_d, alloc):
return True
# 回滚
for j in range(m):
available[j] += req[j]
alloc[pid][j] -= req[j]
return False
if __name__ == "__main__":
avail = [3,3,2]
max_d = [[7,5,3],[3,2,2],[9,0,2],[2,2,2],[4,3,3]]
alloc = [[0,1,0],[2,0,0],[3,0,2],[2,1,1],[0,0,2]]
print("初始安全?", is_safe(avail, max_d, alloc))
print("P1 请求 [1,0,2]:",
"批准" if request_resource(1, [1,0,2], avail, max_d, alloc) else "拒绝")Go 版本
package main
import "fmt"
_// BankersAlgorithm 结构体定义了银行家算法所需的数据结构_
_// available: 可用资源向量_
_// max: 最大需求矩阵_
_// allocation: 分配矩阵_
_// need: 需求矩阵_
type BankersAlgorithm struct {
**available** []int
**max** [][]int
**allocation** [][]int
**need** [][]int
}
_// NewBankersAlgorithm 初始化银行家算法_
_// 参数:_
_// - available: 系统可用资源向量_
_// - max: 进程最大需求矩阵_
_// - allocation: 当前分配矩阵_
_// 返回: 初始化后的银行家算法实例_
func NewBankersAlgorithm(available []int, max [][]int, allocation [][]int) *BankersAlgorithm {
_// 创建新的银行家算法实例_
ba := &BankersAlgorithm{
**available**: make([]int, len(available)),
**max**: make([][]int, len(max)),
**allocation**: make([][]int, len(allocation)),
**need**: make([][]int, len(max)),
}
_// 复制可用资源向量_
copy(ba.available, available)
_// 复制最大需求矩阵_
for i := range max {
ba.max[i] = make([]int, len(max[i]))
copy(ba.max[i], max[i])
}
_// 复制分配矩阵_
for i := range allocation {
ba.allocation[i] = make([]int, len(allocation[i]))
copy(ba.allocation[i], allocation[i])
}
_// 计算需求矩阵 need = max - allocation_
for i := range max {
ba.need[i] = make([]int, len(max[i]))
for j := range max[i] {
ba.need[i][j] = max[i][j] - allocation[i][j]
}
}
return ba
}
_// RequestResources 处理进程的资源请求_
_// 参数:_
_// - processID: 请求资源的进程ID_
_// - request: 请求的资源向量_
_// 返回: 请求是否成功_
func (ba *BankersAlgorithm) RequestResources(processID int, request []int) bool {
_// 检查请求是否超过最大需求_
for i := range request {
if request[i] > ba.need[processID][i] {
fmt.Printf("进程 %d 请求的资源超过最大需求\n", processID)
return false
}
}
_// 检查系统是否有足够的可用资源_
for i := range request {
if request[i] > ba.available[i] {
fmt.Printf("资源不足，进程 %d 需等待\n", processID)
return false
}
}
_// 试探性分配资源_
for i := range request {
ba.available[i] -= request[i]
ba.allocation[processID][i] += request[i]
ba.need[processID][i] -= request[i]
}
_// 检查分配后系统是否安全_
if !ba.isSafe() {
fmt.Println("分配后系统处于不安全状态，撤销分配")
_// 撤销分配，恢复原状态_
for i := range request {
ba.available[i] += request[i]
ba.allocation[processID][i] -= request[i]
ba.need[processID][i] += request[i]
}
return false
}
fmt.Println("资源分配成功，系统处于安全状态")
return true
}
_// isSafe 检查系统是否处于安全状态_
_// 返回: 系统是否安全_
func (ba *BankersAlgorithm) isSafe() bool {
_// 初始化工作向量和完成向量_
work := make([]int, len(ba.available))
copy(work, ba.available)
finish := make([]bool, len(ba.max))
_// 寻找可以完成的进程_
for {
found := false
for i := range ba.max {
if !finish[i] && ba.canFinish(work, ba.need[i]) {
_// 进程i可以完成，释放其资源_
for j := range work {
work[j] += ba.allocation[i][j]
}
finish[i] = true
found = true
}
}
if !found {
break
}
}
_// 检查是否所有进程都能完成_
for _, f := range finish {
if !f {
return false
}
}
return true
}
_// canFinish 检查进程是否能够完成_
_// 参数:_
_// - work: 当前可用资源向量_
_// - need: 进程需求向量_
_// 返回: 进程是否可以完成_
func (ba *BankersAlgorithm) canFinish(work []int, need []int) bool {
for i := range work {
if need[i] > work[i] {
return false
}
}
return true
}
func main() {
_// 初始化系统资源数据_
available := []int{3, 3, 2} _// 可用资源向量_
max := [][]int{ _// 最大需求矩阵_
{7, 5, 3},
{3, 2, 2},
{9, 0, 2},
{2, 2, 2},
{4, 3, 3},
}
allocation := [][]int{ _// 当前分配矩阵_
{0, 1, 0},
{2, 0, 0},
{3, 0, 2},
{2, 1, 1},
{0, 0, 2},
}
_// 创建银行家算法实例_
ba := NewBankersAlgorithm(available, max, allocation)
_// 模拟进程1请求资源_
processID := 1
request := []int{0, 2, 0}
_// 处理资源请求_
if ba.RequestResources(processID, request) {
fmt.Println("资源分配成功")
} else {
fmt.Println("资源分配失败")
}
}算法效率与适用场景
- 时间复杂度：每次请求都要调用一次安全性检查，最坏
（ 是进程数， 是资源种类数）。 - 优点：只要需求申报准确，能彻底避免死锁；逻辑清晰，易于理解与实现。
- 缺点：
- 计算量较大，不适合大量进程和资源同时在线的场景；
- 要求进程提前申报最大需求，有时难以预估；
- 如果申报过高就浪费资源，过低又可能限制并发度。
典型应用：
嵌入式实时系统、小型操作系统、数据库连接池管理等场景——进程/线程数目不多、资源类型有限、死锁成本高，正好适合使用银行家算法来保证系统健康运行。
总结
银行家算法用“银行发放贷款”这一比喻，把死锁避免转化为“安全性检查 + 试探性分配 + 回滚”三步走。理解它的核心，就是：
- 维护 Available/Max/Allocation/Need 这四张“账本”；
- 安全性检测：模拟最坏情况看系统是否还能让所有进程“还清”资源；
- 只在安全状态下正式分配，否则拒绝并回滚。
这样的设计保证了系统永不进入死锁，但也带来了计算开销和使用局限。在实际工程中，我们要根据并发规模与实时性要求，权衡是否使用这一经典算法。希望本文的通俗讲解和示例代码，能让你对银行家算法有清晰而深入的理解。
