银行家算法（Banker’s Algorithm）是由艾兹格·迪杰斯特拉（Edsger Dijkstra）于1965年提出的一种经典死锁避免算法。该算法最初为银行系统设计，用于判断在分配贷款时系统是否仍处于安全状态。在操作系统中，它被广泛应用于多进程环境下的资源分配管理，确保系统永远不会进入死锁状态。
算法核心思想
银行家算法的核心思想是：在分配资源之前，先预判分配后系统是否仍处于安全状态。只有当系统处于安全状态时，才会真正分配资源给进程。
算法维护以下四类关键数据结构：
| 数据结构 | 含义 | 维度 |
|---|---|---|
| Available | 每种资源的可用数量 | 长度为 m 的向量 |
| Max | 每个进程对每种资源的最大需求 | n × m 矩阵 |
| Allocation | 每个进程已分配的资源数量 | n × m 矩阵 |
| Need | 每个进程还需要的资源数量 | n × m 矩阵 |
其中 Need[i][j] = Max[i][j] - Allocation[i][j]，表示进程 i 对资源 j 的剩余需求。
安全状态判定算法
安全状态判定是银行家算法的核心。算法通过模拟资源分配，寻找是否存在一个安全序列，使得所有进程都能顺利完成。
算法步骤
- 初始化工作向量
Work = Available，完成向量Finish = [false, ..., false] - 寻找满足以下条件的进程 Pi：
Finish[i] == falseNeed[i] <= Work（逐分量比较）- 若找到这样的进程，假设其顺利执行完毕并释放资源：
Work = Work + Allocation[i]，标记Finish[i] = true - 重复步骤2-3，直到无法找到满足条件的进程
- 若所有进程的
Finish均为true，则系统处于安全状态；否则为不安全状态
资源请求处理流程
当进程 Pi 发出资源请求 Request 时，系统按以下步骤处理：
- 合法性检查：若
Request > Need[i]，拒绝请求（请求超出声明的最大需求） - 可用性检查：若
Request > Available，进程必须等待（资源不足） - 试分配：临时分配资源，更新各数据结构
- 安全性检查：运行安全状态判定算法
- 决策：若安全则正式分配；否则撤销试分配，进程等待
完整Java实现
以下提供可直接运行的完整Java实现，包含核心算法类与测试用例：
import java.util.Arrays;
/**
* 银行家算法实现 —— 死锁避免与资源安全序列检测
*
* 本类实现了完整的银行家算法，包括：
* 1. 系统初始化与数据结构维护
* 2. 安全状态判定算法
* 3. 资源请求处理流程
* 4. 安全序列输出
*/
public class BankersAlgorithm {
// 进程数量
private final int n;
// 资源种类数量
private final int m;
// 可用资源向量 Available[j] = 资源j的可用数量
private final int[] available;
// 最大需求矩阵 Max[i][j] = 进程i对资源j的最大需求
private final int[][] max;
// 已分配矩阵 Allocation[i][j] = 进程i已分配的资源j数量
private final int[][] allocation;
// 需求矩阵 Need[i][j] = 进程i还需要资源j的数量
private final int[][] need;
/**
* 构造函数：初始化银行家算法数据结构
*
* @param available 系统初始可用资源向量
* @param max 各进程对资源的最大需求矩阵
* @param allocation 各进程已分配资源矩阵
*/
public BankersAlgorithm(int[] available, int[][] max, int[][] allocation) {
this.n = max.length; // 进程数
this.m = available.length; // 资源种类数
this.available = Arrays.copyOf(available, m);
this.max = deepCopy(max);
this.allocation = deepCopy(allocation);
this.need = new int[n][m];
// 计算需求矩阵：Need = Max - Allocation
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
need[i][j] = max[i][j] - allocation[i][j];
}
}
}
/**
* 安全状态判定算法
*
* 核心逻辑：模拟所有进程按某种顺序执行完毕，检查是否存在安全序列。
* 若存在，则系统处于安全状态，不会发生死锁。
*
* @return 安全序列（进程索引数组）；若系统不安全则返回null
*/
public int[] findSafeSequence() {
// Work向量：当前可用资源（可动态增加，因为进程完成后会释放资源）
int[] work = Arrays.copyOf(available, m);
// Finish向量：标记进程是否已完成
boolean[] finish = new boolean[n];
// 存储找到的安全序列
int[] safeSequence = new int[n];
int count = 0;
while (count < n) {
boolean found = false;
// 遍历所有进程，寻找可以完成的进程
for (int i = 0; i < n; i++) {
if (!finish[i] && canExecute(i, work)) {
// 进程i可以执行：分配其所需资源，执行完毕后释放所有资源
for (int j = 0; j < m; j++) {
work[j] += allocation[i][j];
}
finish[i] = true;
safeSequence[count++] = i;
found = true;
}
}
// 若一轮遍历后未找到可执行的进程，说明不存在安全序列
if (!found) {
return null;
}
}
return safeSequence;
}
/**
* 判断进程是否能以当前Work向量执行完毕
*
* @param processIndex 进程索引
* @param work 当前可用资源向量
* @return true if Need[processIndex] <= Work (逐分量比较)
*/
private boolean canExecute(int processIndex, int[] work) {
for (int j = 0; j < m; j++) {
if (need[processIndex][j] > work[j]) {
return false; // 任一资源不足则无法执行
}
}
return true;
}
/**
* 处理进程的资源请求
*
* 完整流程：合法性检查 -> 可用性检查 -> 试分配 -> 安全性检查 -> 决策
*
* @param processIndex 请求资源的进程索引
* @param request 请求的资源向量
* @return 请求结果描述字符串
*/
public String requestResource(int processIndex, int[] request) {
// 步骤1：合法性检查 —— 请求不能超过进程声明的最大需求
for (int j = 0; j < m; j++) {
if (request[j] > need[processIndex][j]) {
return String.format(
"拒绝：进程P%d请求资源%d超过其最大需求%d",
processIndex, request[j], need[processIndex][j]
);
}
}
// 步骤2：可用性检查 —— 请求不能超过当前可用资源
for (int j = 0; j < m; j++) {
if (request[j] > available[j]) {
return String.format(
"等待：进程P%d请求资源%d超过当前可用%d",
processIndex, request[j], available[j]
);
}
}
// 步骤3：试分配 —— 临时修改数据结构
for (int j = 0; j < m; j++) {
available[j] -= request[j];
allocation[processIndex][j] += request[j];
need[processIndex][j] -= request[j];
}
// 步骤4：安全性检查
int[] safeSequence = findSafeSequence();
if (safeSequence != null) {
// 安全：正式确认分配
return String.format(
"批准：进程P%d的资源请求已分配。安全序列：%s",
processIndex, Arrays.toString(safeSequence)
);
} else {
// 不安全：撤销试分配，恢复原始状态
for (int j = 0; j < m; j++) {
available[j] += request[j];
allocation[processIndex][j] -= request[j];
need[processIndex][j] += request[j];
}
return String.format(
"拒绝：进程P%d的资源请求会导致系统进入不安全状态",
processIndex
);
}
}
/**
* 打印当前系统状态
*/
public void printState() {
System.out.println("\n========== 当前系统状态 ==========");
System.out.println("可用资源 Available: " + Arrays.toString(available));
System.out.println("\n进程 | Max | Allocation | Need ");
System.out.println("-----|----------|------------|----------");
for (int i = 0; i < n; i++) {
System.out.printf("P%-3d | %-8s | %-10s | %s%n",
i, Arrays.toString(max[i]),
Arrays.toString(allocation[i]),
Arrays.toString(need[i]));
}
}
/**
* 深度拷贝二维数组
*/
private static int[][] deepCopy(int[][] original) {
int[][] copy = new int[original.length][];
for (int i = 0; i < original.length; i++) {
copy[i] = Arrays.copyOf(original[i], original[i].length);
}
return copy;
}
/**
* 主函数：演示银行家算法的完整工作流程
*/
public static void main(String[] args) {
// ========== 测试案例 ==========
// 系统有3种资源，初始总量分别为：A=10, B=5, C=7
// 5个进程 P0~P4
int[] available = {3, 3, 2}; // 初始可用资源
int[][] max = {
{7, 5, 3}, // P0
{3, 2, 2}, // P1
{9, 0, 2}, // P2
{2, 2, 2}, // P3
{4, 3, 3} // P4
};
int[][] allocation = {
{0, 1, 0}, // P0
{2, 0, 0}, // P1
{3, 0, 2}, // P2
{2, 1, 1}, // P3
{0, 0, 2} // P4
};
BankersAlgorithm banker = new BankersAlgorithm(available, max, allocation);
banker.printState();
// 检查初始状态是否安全
int[] safeSeq = banker.findSafeSequence();
System.out.println("\n初始状态安全序列: " + Arrays.toString(safeSeq));
// 模拟P1请求资源 (1, 0, 2)
System.out.println("\n>>> P1 请求资源 [1, 0, 2]");
System.out.println(banker.requestResource(1, new int[]{1, 0, 2}));
banker.printState();
// 验证安全序列
safeSeq = banker.findSafeSequence();
System.out.println("当前安全序列: " + Arrays.toString(safeSeq));
// 模拟P4请求资源 (3, 3, 0) —— 应被拒绝（超过可用）
System.out.println("\n>>> P4 请求资源 [3, 3, 0]");
System.out.println(banker.requestResource(4, new int[]{3, 3, 0}));
// 模拟P0请求资源 (0, 2, 0) —— 应被拒绝（会导致不安全状态）
System.out.println("\n>>> P0 请求资源 [0, 2, 0]");
System.out.println(banker.requestResource(0, new int[]{0, 2, 0}));
banker.printState();
}
}
执行结果与分析
运行上述代码，你将看到类似以下的输出：
========== 当前系统状态 ==========
可用资源 Available: [3, 3, 2]
进程 | Max | Allocation | Need
-----|----------|------------|----------
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]
初始状态安全序列: [1, 3, 4, 0, 2]
>>> P1 请求资源 [1, 0, 2]
批准：进程P1的资源请求已分配。安全序列：[3, 4, 0, 2, 1]
...
>>> P0 请求资源 [0, 2, 0]
拒绝：进程P0的资源请求会导致系统进入不安全状态
从输出中可以观察到几个关键点：
- 初始状态是安全的，安全序列为
[1, 3, 4, 0, 2]。这意味着按此顺序执行，每个进程都能获得所需资源并顺利完成。 - P1请求
[1, 0, 2]被批准，因为试分配后系统仍然存在安全序列。 - P0请求
[0, 2, 0]被拒绝，因为该分配会导致剩余可用资源无法满足任何进程的剩余需求，系统进入不安全状态。
算法复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 初始化 | O(n × m) | O(n × m) |
| 安全状态判定 | O(n² × m) | O(n + m) |
| 资源请求处理 | O(n² × m) | O(n + m) |
其中 n 为进程数量，m 为资源种类数量。安全状态判定的时间复杂度为 O(n² × m)，因为在最坏情况下需要遍历所有进程 n 次，每次遍历检查 m 个资源维度。
算法优缺点
优点：
– 保证系统永远不会进入死锁状态，是一种预防性策略
– 无需进程在执行前声明所有资源需求（只需声明最大需求）
– 算法逻辑清晰，易于理解和实现
缺点：
– 要求进程必须事先声明每种资源的最大需求量，实际中往往难以精确预估
– 进程数量必须固定，不支持动态创建和销毁进程
– 算法时间复杂度为 O(n² × m)，进程和资源种类较多时开销较大
– 过于保守，可能拒绝一些实际上不会导致死锁的资源请求
总结
银行家算法是操作系统课程中的经典算法，它通过预先判断资源分配的安全性来避免死锁的发生。本文提供的Java实现涵盖了算法的核心逻辑，包括安全状态判定和资源请求处理两大模块。理解这一算法的关键在于把握”安全序列”的概念——只要存在至少一个安全序列，系统就不会死锁。
掌握银行家算法不仅能加深对死锁避免机制的理解，也为学习更复杂的资源调度算法（如等待图检测、资源排序法等）奠定了坚实基础。
