银行家算法
2025/11/4大约 22 分钟
银行家算法 (Banker's Algorithm)
1. 银行家算法概述
银行家算法是一种经典的死锁避免算法，由荷兰计算机科学家Edsger W. Dijkstra于1965年提出。该算法的名称来源于银行业务中的借贷策略：银行家在发放贷款时，必须确保即使所有借款人同时要求最大贷款额度，银行仍有能力满足这些请求而不会导致资金短缺。
在操作系统中，银行家算法用于在资源分配过程中避免系统进入死锁状态。它通过模拟资源分配，并在分配前检查是否会导致系统进入不安全状态，从而决定是否执行资源分配。
2. 银行家算法的基本原理
2.1 核心思想
银行家算法的核心思想是：在每次分配资源前，先检查系统的安全状态。只有当分配资源后系统仍然处于安全状态时，才进行实际的资源分配。
2.2 安全状态与不安全状态
- 安全状态：存在一个资源分配序列，使得所有进程都能顺利完成执行
- 不安全状态：不存在这样的分配序列，系统有可能发生死锁
- 注意：不安全状态并不等同于死锁状态，但死锁状态一定是不安全状态
2.3 关键假设
银行家算法基于以下假设：
- 进程数量固定
- 资源类型固定
- 进程预先声明最大资源需求
- 进程在执行过程中按序请求资源
- 进程一旦获得资源，必须在有限时间内释放
3. 银行家算法的数据结构
银行家算法使用以下关键数据结构来描述系统状态：
3.1 系统资源总量 (Total Resources)
表示系统中每种资源的总数量。通常用一维数组Total表示：
Total = [R1_total, R2_total, ..., Rm_total]其中，Ri_total表示第i种资源的总数量，m为资源类型的数量。
3.2 可用资源向量 (Available Resources)
表示系统中每种资源的当前可用数量。通常用一维数组Available表示：
Available = [R1_available, R2_available, ..., Rm_available]其中，Ri_available表示第i种资源的当前可用数量。
3.3 最大需求矩阵 (Maximum Need Matrix)
表示每个进程对每种资源的最大需求量。通常用二维数组Max表示：
Max = [
[P0_R1_max, P0_R2_max, ..., P0_Rm_max],
[P1_R1_max, P1_R2_max, ..., P1_Rm_max],
...,
[Pn_R1_max, Pn_R2_max, ..., Pn_Rm_max]
]其中，Pi_Rj_max表示进程i对资源j的最大需求量，n为进程数量。
3.4 分配矩阵 (Allocation Matrix)
表示当前已分配给每个进程的资源数量。通常用二维数组Allocation表示：
Allocation = [
[P0_R1_allocated, P0_R2_allocated, ..., P0_Rm_allocated],
[P1_R1_allocated, P1_R2_allocated, ..., P1_Rm_allocated],
...,
[Pn_R1_allocated, Pn_R2_allocated, ..., Pn_Rm_allocated]
]其中，Pi_Rj_allocated表示当前已分配给进程i的资源j的数量。
3.5 需求矩阵 (Need Matrix)
表示每个进程还需要的资源数量。通常用二维数组Need表示：
Need = [
[P0_R1_need, P0_R2_need, ..., P0_Rm_need],
[P1_R1_need, P1_R2_need, ..., P1_Rm_need],
...,
[Pn_R1_need, Pn_R2_need, ..., Pn_Rm_need]
]其中，Pi_Rj_need表示进程i还需要的资源j的数量。
3.6 需求矩阵与其他矩阵的关系
需求矩阵可以通过最大需求矩阵和分配矩阵计算得到：
Need[i][j] = Max[i][j] - Allocation[i][j]4. 银行家算法的实现
银行家算法主要包含两个部分：
- 安全性检查算法：检查系统是否处于安全状态
- 资源分配算法：根据安全性检查结果决定是否分配资源
4.1 安全性检查算法
安全性检查算法通过模拟资源分配，找出是否存在一个安全序列。算法步骤如下：
初始化：
- 创建工作向量
Work，初始化为Available - 创建完成标志数组
Finish，初始化为全false
- 创建工作向量
查找可执行进程：
- 寻找一个满足以下条件的进程i：
Finish[i] == false- 对于所有资源j，
Need[i][j] <= Work[j]
- 寻找一个满足以下条件的进程i：
执行进程：
- 如果找到这样的进程i，假设该进程获取所需资源并执行完成
- 更新
Work向量：Work[j] = Work[j] + Allocation[i][j]（进程完成后释放资源） - 设置
Finish[i] = true - 重复步骤2
检查结果：
- 如果所有进程的
Finish[i] == true，则系统处于安全状态 - 否则，系统处于不安全状态
- 如果所有进程的
4.2 资源分配算法
当进程请求资源时，资源分配算法决定是否满足该请求：
请求验证：
- 检查请求是否超过进程的最大需求：如果
Request[i][j] > Max[i][j]，则请求无效 - 检查请求是否超过可用资源：如果
Request[i][j] > Available[j]，则进程必须等待
- 检查请求是否超过进程的最大需求：如果
尝试分配：
- 假设将资源分配给进程：
Available[j] = Available[j] - Request[i][j]Allocation[i][j] = Allocation[i][j] + Request[i][j]Need[i][j] = Need[i][j] - Request[i][j]
- 假设将资源分配给进程：
安全性检查：
- 调用安全性检查算法检查分配后系统是否安全
- 如果安全，接受分配；否则，回滚分配，进程等待
5. 银行家算法的Java实现
下面是银行家算法的完整Java实现，包括安全性检查和资源分配功能：
import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;
public class BankersAlgorithm {
private int[][] max; // 最大需求矩阵
private int[][] allocation; // 当前分配矩阵
private int[][] need; // 需求矩阵
private int[] available; // 可用资源向量
private int numProcesses; // 进程数量
private int numResources; // 资源种类数量
/**
* 构造银行家算法实例
* @param max 最大需求矩阵
* @param allocation 当前分配矩阵
* @param available 可用资源向量
*/
public BankersAlgorithm(int[][] max, int[][] allocation, int[] available) {
this.max = max;
this.allocation = allocation;
this.available = available;
this.numProcesses = max.length;
this.numResources = available.length;
// 计算需求矩阵
this.need = new int[numProcesses][numResources];
for (int i = 0; i < numProcesses; i++) {
for (int j = 0; j < numResources; j++) {
need[i][j] = max[i][j] - allocation[i][j];
}
}
}
/**
* 检查系统是否处于安全状态
* @return 如果系统安全返回true，否则返回false
*/
public boolean isSafe() {
boolean[] finish = new boolean[numProcesses]; // 记录进程是否完成
int[] work = Arrays.copyOf(available, numResources); // 工作向量
List<Integer> safeSequence = new ArrayList<>(); // 安全序列
int count = 0;
while (count < numProcesses) {
boolean found = false;
for (int i = 0; i < numProcesses; i++) {
if (!finish[i]) {
int j;
// 检查当前进程的所有资源需求是否都小于等于可用资源
for (j = 0; j < numResources; j++) {
if (need[i][j] > work[j]) {
break; // 资源不足，跳出循环
}
}
// 如果所有资源需求都满足
if (j == numResources) {
// 假设分配资源给该进程，该进程执行完成后释放资源
for (int k = 0; k < numResources; k++) {
work[k] += allocation[i][k];
}
finish[i] = true;
safeSequence.add(i);
found = true;
count++;
}
}
}
// 如果一轮检查没有找到可执行的进程，则系统不安全
if (!found) {
System.out.println("系统处于不安全状态，不存在安全序列");
return false;
}
}
// 所有进程都可以完成，系统安全
System.out.println("系统处于安全状态，安全序列: " + safeSequence);
return true;
}
/**
* 尝试分配资源给指定进程
* @param processId 进程ID
* @param request 请求的资源向量
* @return 如果分配成功返回true，否则返回false
*/
public boolean requestResources(int processId, int[] request) {
// 检查进程ID是否有效
if (processId < 0 || processId >= numProcesses) {
System.out.println("错误：无效的进程ID");
return false;
}
// 检查请求向量长度是否有效
if (request.length != numResources) {
System.out.println("错误：请求向量长度不匹配");
return false;
}
System.out.println("进程 " + processId + " 请求资源: " + Arrays.toString(request));
// 检查请求是否超过进程的最大需求
for (int i = 0; i < numResources; i++) {
if (request[i] > need[processId][i]) {
System.out.println("错误：请求超过最大需求");
return false;
}
}
// 检查请求是否超过可用资源
for (int i = 0; i < numResources; i++) {
if (request[i] > available[i]) {
System.out.println("错误：资源不足，进程必须等待");
return false;
}
}
// 尝试分配资源 - 保存当前状态，用于回滚
int[] tempAvailable = Arrays.copyOf(available, numResources);
int[][] tempAllocation = new int[numProcesses][numResources];
int[][] tempNeed = new int[numProcesses][numResources];
for (int i = 0; i < numProcesses; i++) {
tempAllocation[i] = Arrays.copyOf(allocation[i], numResources);
tempNeed[i] = Arrays.copyOf(need[i], numResources);
}
// 执行资源分配
for (int i = 0; i < numResources; i++) {
available[i] -= request[i];
allocation[processId][i] += request[i];
need[processId][i] -= request[i];
}
// 检查分配后系统是否安全
if (isSafe()) {
System.out.println("资源分配成功");
return true; // 安全，允许分配
} else {
// 不安全，回滚分配
System.out.println("分配会导致系统不安全，回滚操作");
available = tempAvailable;
for (int i = 0; i < numProcesses; i++) {
allocation[i] = tempAllocation[i];
need[i] = tempNeed[i];
}
return false;
}
}
/**
* 释放进程占用的资源
* @param processId 进程ID
* @param release 释放的资源向量
* @return 如果释放成功返回true，否则返回false
*/
public boolean releaseResources(int processId, int[] release) {
// 检查进程ID是否有效
if (processId < 0 || processId >= numProcesses) {
System.out.println("错误：无效的进程ID");
return false;
}
// 检查释放向量长度是否有效
if (release.length != numResources) {
System.out.println("错误：释放向量长度不匹配");
return false;
}
// 检查释放数量是否超过已分配数量
for (int i = 0; i < numResources; i++) {
if (release[i] > allocation[processId][i]) {
System.out.println("错误：释放的资源数量超过已分配的数量");
return false;
}
}
// 执行资源释放
System.out.println("进程 " + processId + " 释放资源: " + Arrays.toString(release));
for (int i = 0; i < numResources; i++) {
allocation[processId][i] -= release[i];
need[processId][i] += release[i];
available[i] += release[i];
}
System.out.println("资源释放成功");
return true;
}
/**
* 显示当前系统状态
*/
public void displaySystemState() {
System.out.println("\n===== 当前系统状态 =====");
// 显示可用资源
System.out.println("可用资源: " + Arrays.toString(available));
// 显示进程资源状态
System.out.println("进程资源状态:");
System.out.println("进程\t最大需求\t已分配\t\t还需要");
for (int i = 0; i < numProcesses; i++) {
System.out.print("P" + i + "\t");
System.out.print(Arrays.toString(max[i]) + "\t");
System.out.print(Arrays.toString(allocation[i]) + "\t");
System.out.println(Arrays.toString(need[i]));
}
}
/**
* 示例运行程序
*/
public static void main(String[] args) {
// 示例数据 - 5个进程，3种资源
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已分配的资源
};
int[] available = {3, 3, 2}; // 可用资源
// 创建银行家算法实例
BankersAlgorithm banker = new BankersAlgorithm(max, allocation, available);
// 显示初始状态
banker.displaySystemState();
// 检查初始状态是否安全
System.out.println("\n检查初始状态安全性:");
banker.isSafe();
// 示例1: 进程1请求资源 [1, 0, 2]
System.out.println("\n示例1: 进程1请求资源 [1, 0, 2]");
int[] request1 = {1, 0, 2};
banker.requestResources(1, request1);
banker.displaySystemState();
// 示例2: 进程4请求资源 [3, 3, 0]
System.out.println("\n示例2: 进程4请求资源 [3, 3, 0]");
int[] request2 = {3, 3, 0};
banker.requestResources(4, request2);
banker.displaySystemState();
// 示例3: 进程0释放资源 [0, 1, 0]
System.out.println("\n示例3: 进程0释放资源 [0, 1, 0]");
int[] release1 = {0, 1, 0};
banker.releaseResources(0, release1);
banker.displaySystemState();
// 再次检查安全性
System.out.println("\n再次检查系统安全性:");
banker.isSafe();
}
}6. 银行家算法的模拟运行
6.1 初始状态
假设系统中有5个进程(P0-P4)和3种资源(R1-R3)，初始状态如下：
- 总资源：[10, 5, 7]
- 可用资源：[3, 3, 2]
- 最大需求矩阵：
P0: [7, 5, 3] P1: [3, 2, 2] P2: [9, 0, 2] P3: [2, 2, 2] P4: [4, 3, 3] - 分配矩阵：
P0: [0, 1, 0] P1: [2, 0, 0] P2: [3, 0, 2] P3: [2, 1, 1] P4: [0, 0, 2] - 需求矩阵（计算得到）：
P0: [7, 4, 3] P1: [1, 2, 2] P2: [6, 0, 0] P3: [0, 1, 1] P4: [4, 3, 1]
6.2 安全性检查过程
初始安全性检查过程：
初始化：Work = [3, 3, 2], Finish = [false, false, false, false, false]
第一轮检查：
- P1: Need = [1, 2, 2] ≤ Work = [3, 3, 2]，可以执行
- 执行P1：Work = [3+2, 3+0, 2+0] = [5, 3, 2]
- Finish[1] = true
第二轮检查：
- P3: Need = [0, 1, 1] ≤ Work = [5, 3, 2]，可以执行
- 执行P3：Work = [5+2, 3+1, 2+1] = [7, 4, 3]
- Finish[3] = true
第三轮检查：
- P4: Need = [4, 3, 1] ≤ Work = [7, 4, 3]，可以执行
- 执行P4：Work = [7+0, 4+0, 3+2] = [7, 4, 5]
- Finish[4] = true
第四轮检查：
- P0: Need = [7, 4, 3] ≤ Work = [7, 4, 5]，可以执行
- 执行P0：Work = [7+0, 4+1, 5+0] = [7, 5, 5]
- Finish[0] = true
第五轮检查：
- P2: Need = [6, 0, 0] ≤ Work = [7, 5, 5]，可以执行
- 执行P2：Work = [7+3, 5+0, 5+2] = [10, 5, 7]
- Finish[2] = true
结果：所有进程的Finish为true，系统安全，安全序列为[P1, P3, P4, P0, P2]
6.3 资源分配示例
示例1：进程1请求资源 [1, 0, 2]
验证请求：
- 请求不超过最大需求：[1, 0, 2] ≤ [3, 2, 2]，有效
- 请求不超过可用资源：[1, 0, 2] ≤ [3, 3, 2]，有效
尝试分配：
- Available变为：[3-1, 3-0, 2-2] = [2, 3, 0]
- Allocation[1]变为：[2+1, 0+0, 0+2] = [3, 0, 2]
- Need[1]变为：[1-1, 2-0, 2-2] = [0, 2, 0]
安全性检查：
- 初始Work = [2, 3, 0], Finish = [false, false, false, false, false]
- P1: Need = [0, 2, 0] ≤ Work，执行后Work = [5, 3, 2]
- P3: Need = [0, 1, 1] ≤ Work，执行后Work = [7, 4, 3]
- P0: Need = [7, 4, 3] ≤ Work，执行后Work = [7, 5, 3]
- P4: Need = [4, 3, 1] ≤ Work，执行后Work = [7, 5, 5]
- P2: Need = [6, 0, 0] ≤ Work，执行后Work = [10, 5, 7]
- 所有进程完成，系统安全
结论：允许分配
示例2：进程4请求资源 [3, 3, 0]
验证请求：
- 请求不超过最大需求：[3, 3, 0] ≤ [4, 3, 3]，有效
- 请求不超过可用资源：[3, 3, 0] ≤ [3, 3, 2]，有效
尝试分配：
- Available变为：[0, 0, 2]
- Allocation[4]变为：[3, 3, 2]
- Need[4]变为：[1, 0, 1]
安全性检查：
- 初始Work = [0, 0, 2], Finish = [false, false, false, false, false]
- 没有进程的Need ≤ Work，系统不安全
结论：拒绝分配，回滚操作
7. 银行家算法的优缺点
7.1 优点
有效避免死锁：通过在资源分配前检查安全性，可以有效避免死锁的发生
资源利用率较高：相比死锁预防策略，银行家算法允许更多的并发操作，提高了资源利用率
灵活的资源分配：只要系统保持安全状态，就可以动态分配资源
理论基础坚实：有严格的数学证明和理论基础
7.2 缺点
需要预先知道资源需求：进程必须预先声明最大资源需求，这在实际应用中可能难以实现
系统状态保持开销大：需要维护和更新多个数据结构，增加了系统开销
无法应对动态进程创建和销毁：假设进程数量固定，不适应动态变化的环境
可能导致进程饥饿：为了保持系统安全，某些进程可能长时间得不到所需资源
实现复杂度高：特别是在大型系统中，安全性检查的复杂度会增加
8. 银行家算法的实际应用场景
8.1 适用场景
资源分配系统：如操作系统的资源管理器、数据库管理系统等
分布式系统：需要协调多个节点资源分配的分布式系统
嵌入式系统：资源受限且对可靠性要求高的嵌入式系统
云资源调度：云平台中的虚拟机资源分配
高可靠性要求的实时系统：不允许发生死锁的关键任务系统
8.2 不适用场景
需要频繁创建和销毁进程的系统：如Web服务器、应用服务器等
资源需求动态变化的系统：无法预先确定资源需求的应用
对响应时间要求极高的系统：安全性检查会增加响应延迟
资源种类和数量非常多的大型系统：算法复杂度会导致性能问题
9. 银行家算法的扩展
9.1 分布式银行家算法
分布式银行家算法是传统银行家算法在分布式系统环境下的扩展，用于管理跨多个节点的资源分配，避免分布式死锁。在分布式系统中，资源分布在不同的节点上，进程可能在多个节点上执行，这使得资源分配和死锁避免变得更加复杂。
9.1.1 实现原理
分布式银行家算法主要有两种实现方式：
集中式协调：
- 设立一个中央协调器节点
- 所有资源分配请求必须通过中央协调器
- 中央协调器维护全局资源状态，执行安全性检查
分布式协调：
- 每个节点维护本地资源状态和全局资源的部分视图
- 节点间通过消息传递进行协调
- 采用分布式一致性协议确保全局状态一致
9.1.2 主要挑战及解决方案
全局状态信息获取
挑战：
- 分布式系统中的节点可能同时修改资源状态
- 网络延迟和分区可能导致状态不一致
- 节点故障可能丢失状态信息
解决方案：
- 采用两阶段提交协议(2PC)确保原子性更新
- 实现分布式快照算法捕获一致的系统状态
- 使用复制技术保持状态副本，提高可靠性
分布式死锁检测
挑战：
- 资源请求可能跨越多个节点，形成全局等待图
- 检测过程中的系统状态可能已经改变
- 假死锁问题（由于消息延迟导致的误判）
解决方案：
- 维护全局等待图，定期合并各节点的本地等待图
- 采用带时间戳的请求消息，按逻辑时钟顺序处理
- 使用路径推进算法检测循环等待
资源分配决策
挑战：
- 跨节点资源请求需要协调多个节点
- 部分节点故障可能影响全局决策
- 通信开销可能导致性能下降
解决方案：
- 实现分层决策，本地请求优先在本地处理
- 采用乐观分配策略，先尝试分配后验证安全性
- 使用缓存技术减少跨节点通信
9.1.3 分布式银行家算法Java实现示例
以下是一个简化的分布式银行家算法实现，使用集中式协调方式：
import java.io.Serializable;
import java.rmi.Remote;
import java.rmi.RemoteException;
import java.rmi.registry.LocateRegistry;
import java.rmi.registry.Registry;
import java.rmi.server.UnicastRemoteObject;
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.locks.ReentrantLock;
// 分布式资源请求接口
interface DistributedBanker extends Remote {
boolean requestResources(String clientId, int[] request) throws RemoteException;
void releaseResources(String clientId, int[] release) throws RemoteException;
boolean registerClient(String clientId, int[] maxNeed) throws RemoteException;
void unregisterClient(String clientId) throws RemoteException;
Map<String, Object> getSystemState() throws RemoteException;
}
// 资源分配信息
class ResourceAllocation implements Serializable {
private static final long serialVersionUID = 1L;
int[] maxNeed; // 最大需求
int[] allocation; // 当前分配
int[] need; // 还需要的资源
public ResourceAllocation(int[] maxNeed) {
this.maxNeed = Arrays.copyOf(maxNeed, maxNeed.length);
this.allocation = new int[maxNeed.length];
this.need = Arrays.copyOf(maxNeed, maxNeed.length);
}
}
// 中央协调器实现
class CentralizedBankerImpl implements DistributedBanker {
private final int[] totalResources; // 系统总资源
private final int[] availableResources; // 可用资源
private final Map<String, ResourceAllocation> clients; // 客户端资源分配信息
private final ReentrantLock lock = new ReentrantLock(); // 同步锁
private final int numResourceTypes; // 资源类型数量
public CentralizedBankerImpl(int[] totalResources) {
this.totalResources = Arrays.copyOf(totalResources, totalResources.length);
this.availableResources = Arrays.copyOf(totalResources, totalResources.length);
this.clients = new ConcurrentHashMap<>();
this.numResourceTypes = totalResources.length;
}
@Override
public boolean registerClient(String clientId, int[] maxNeed) throws RemoteException {
lock.lock();
try {
// 检查客户端是否已存在
if (clients.containsKey(clientId)) {
System.out.println("客户端 " + clientId + " 已注册");
return false;
}
// 检查最大需求是否合理
for (int i = 0; i < numResourceTypes; i++) {
if (maxNeed[i] < 0 || maxNeed[i] > totalResources[i]) {
System.out.println("客户端 " + clientId + " 的最大需求不合理");
return false;
}
}
// 注册客户端
clients.put(clientId, new ResourceAllocation(maxNeed));
System.out.println("客户端 " + clientId + " 注册成功，最大需求: " + Arrays.toString(maxNeed));
return true;
} finally {
lock.unlock();
}
}
@Override
public void unregisterClient(String clientId) throws RemoteException {
lock.lock();
try {
ResourceAllocation alloc = clients.remove(clientId);
if (alloc != null) {
// 释放客户端占用的所有资源
for (int i = 0; i < numResourceTypes; i++) {
availableResources[i] += alloc.allocation[i];
}
System.out.println("客户端 " + clientId + " 注销成功，释放资源: " + Arrays.toString(alloc.allocation));
}
} finally {
lock.unlock();
}
}
@Override
public boolean requestResources(String clientId, int[] request) throws RemoteException {
lock.lock();
try {
ResourceAllocation alloc = clients.get(clientId);
if (alloc == null) {
System.out.println("客户端 " + clientId + " 未注册");
return false;
}
// 检查请求是否有效
for (int i = 0; i < numResourceTypes; i++) {
if (request[i] < 0) {
System.out.println("无效的资源请求");
return false;
}
if (request[i] > alloc.need[i]) {
System.out.println("请求超过最大需求");
return false;
}
if (request[i] > availableResources[i]) {
System.out.println("资源不足，请求被拒绝");
return false;
}
}
// 尝试分配资源
int[] tempAvailable = Arrays.copyOf(availableResources, numResourceTypes);
int[] tempAllocation = Arrays.copyOf(alloc.allocation, numResourceTypes);
int[] tempNeed = Arrays.copyOf(alloc.need, numResourceTypes);
// 模拟分配
for (int i = 0; i < numResourceTypes; i++) {
tempAvailable[i] -= request[i];
tempAllocation[i] += request[i];
tempNeed[i] -= request[i];
}
// 执行安全性检查
if (isSafe(tempAvailable)) {
// 实际分配资源
for (int i = 0; i < numResourceTypes; i++) {
availableResources[i] -= request[i];
alloc.allocation[i] += request[i];
alloc.need[i] -= request[i];
}
System.out.println("客户端 " + clientId + " 资源请求成功: " + Arrays.toString(request));
return true;
} else {
System.out.println("资源分配会导致系统不安全，请求被拒绝");
return false;
}
} finally {
lock.unlock();
}
}
@Override
public void releaseResources(String clientId, int[] release) throws RemoteException {
lock.lock();
try {
ResourceAllocation alloc = clients.get(clientId);
if (alloc == null) {
System.out.println("客户端 " + clientId + " 未注册");
return;
}
// 检查释放是否有效
for (int i = 0; i < numResourceTypes; i++) {
if (release[i] < 0 || release[i] > alloc.allocation[i]) {
System.out.println("无效的资源释放请求");
return;
}
}
// 释放资源
for (int i = 0; i < numResourceTypes; i++) {
availableResources[i] += release[i];
alloc.allocation[i] -= release[i];
alloc.need[i] += release[i];
}
System.out.println("客户端 " + clientId + " 资源释放成功: " + Arrays.toString(release));
} finally {
lock.unlock();
}
}
// 安全性检查
private boolean isSafe(int[] available) {
// 创建临时副本用于安全检查
int[] work = Arrays.copyOf(available, numResourceTypes);
Map<String, Boolean> finish = new HashMap<>();
// 初始化finish标志
for (String clientId : clients.keySet()) {
finish.put(clientId, false);
}
int count = 0;
while (count < clients.size()) {
boolean found = false;
for (Map.Entry<String, ResourceAllocation> entry : clients.entrySet()) {
String clientId = entry.getKey();
ResourceAllocation alloc = entry.getValue();
if (!finish.get(clientId)) {
boolean canExecute = true;
// 检查是否所有资源需求都满足
for (int i = 0; i < numResourceTypes; i++) {
if (alloc.need[i] > work[i]) {
canExecute = false;
break;
}
}
if (canExecute) {
// 假设进程执行完成，释放资源
for (int i = 0; i < numResourceTypes; i++) {
work[i] += alloc.allocation[i];
}
finish.put(clientId, true);
found = true;
count++;
}
}
}
// 如果一轮没有找到可执行进程，则系统不安全
if (!found) {
return false;
}
}
// 所有进程都可以完成，系统安全
return true;
}
@Override
public Map<String, Object> getSystemState() throws RemoteException {
lock.lock();
try {
Map<String, Object> state = new HashMap<>();
state.put("totalResources", Arrays.copyOf(totalResources, numResourceTypes));
state.put("availableResources", Arrays.copyOf(availableResources, numResourceTypes));
Map<String, Map<String, int[]>> clientStates = new HashMap<>();
for (Map.Entry<String, ResourceAllocation> entry : clients.entrySet()) {
String clientId = entry.getKey();
ResourceAllocation alloc = entry.getValue();
Map<String, int[]> clientState = new HashMap<>();
clientState.put("maxNeed", Arrays.copyOf(alloc.maxNeed, numResourceTypes));
clientState.put("allocation", Arrays.copyOf(alloc.allocation, numResourceTypes));
clientState.put("need", Arrays.copyOf(alloc.need, numResourceTypes));
clientStates.put(clientId, clientState);
}
state.put("clients", clientStates);
return state;
} finally {
lock.unlock();
}
}
}
// 分布式客户端示例
class DistributedClient {
private final String clientId;
private final DistributedBanker banker;
private final int[] maxNeed;
public DistributedClient(String clientId, DistributedBanker banker, int[] maxNeed) {
this.clientId = clientId;
this.banker = banker;
this.maxNeed = maxNeed;
}
public void start() throws RemoteException {
// 注册客户端
banker.registerClient(clientId, maxNeed);
try {
// 模拟资源请求和释放
Random random = new Random();
for (int i = 0; i < 5; i++) {
// 生成随机请求
int[] request = new int[maxNeed.length];
for (int j = 0; j < maxNeed.length; j++) {
request[j] = random.nextInt(Math.min(3, maxNeed[j]));
}
System.out.println(clientId + " 请求资源: " + Arrays.toString(request));
boolean success = banker.requestResources(clientId, request);
System.out.println(clientId + " 请求结果: " + (success ? "成功" : "失败"));
// 模拟使用资源
try {
Thread.sleep(1000 + random.nextInt(2000));
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
// 释放部分资源
if (success) {
int[] release = Arrays.copyOf(request, request.length);
for (int j = 0; j < request.length; j++) {
release[j] = random.nextInt(request[j] + 1);
}
System.out.println(clientId + " 释放资源: " + Arrays.toString(release));
banker.releaseResources(clientId, release);
}
}
} finally {
// 注销客户端
banker.unregisterClient(clientId);
}
}
}
// 服务器启动类
public class DistributedBankerServer {
public static void main(String[] args) {
try {
// 初始化总资源
int[] totalResources = {10, 5, 7}; // 3种资源，分别有10、5、7个实例
// 创建银行家实现
CentralizedBankerImpl bankerImpl = new CentralizedBankerImpl(totalResources);
// 导出远程对象
DistributedBanker stub = (DistributedBanker) UnicastRemoteObject.exportObject(bankerImpl, 0);
// 注册到RMI注册表
Registry registry = LocateRegistry.createRegistry(1099);
registry.bind("DistributedBanker", stub);
System.out.println("分布式银行家服务已启动");
// 启动几个客户端进行测试
Thread client1 = new Thread(() -> {
try {
DistributedBanker clientStub = (DistributedBanker) LocateRegistry.getRegistry().lookup("DistributedBanker");
DistributedClient client = new DistributedClient("Client1", clientStub, new int[]{7, 5, 3});
client.start();
} catch (Exception e) {
e.printStackTrace();
}
});
Thread client2 = new Thread(() -> {
try {
DistributedBanker clientStub = (DistributedBanker) LocateRegistry.getRegistry().lookup("DistributedBanker");
DistributedClient client = new DistributedClient("Client2", clientStub, new int[]{3, 2, 2});
client.start();
} catch (Exception e) {
e.printStackTrace();
}
});
client1.start();
client2.start();
} catch (Exception e) {
System.err.println("服务器异常: " + e.getMessage());
e.printStackTrace();
}
}
}9.1.4 分布式银行家算法的优化策略
分层资源管理
- 本地资源优先在节点内分配
- 跨节点资源请求才提交给中央协调器
- 减少全局协调的频率
缓存与预取
- 缓存常用资源的分配状态
- 预测性预取可能需要的资源
- 减少实时协调的需求
异步处理
- 使用消息队列处理资源请求
- 实现非阻塞式的资源分配策略
- 提高系统吞吐量
弹性设计
- 实现节点故障检测和恢复机制
- 支持动态加入和离开节点
- 确保系统在部分节点故障时仍能正常工作
9.1.5 实际应用场景
分布式数据库系统：管理跨多个节点的数据锁和连接资源
云资源调度：在多个数据中心之间协调虚拟机和存储资源
网格计算：在分布式计算环境中分配计算资源和任务
容器编排平台：如Kubernetes中的资源调度和管理
分布式文件系统：管理跨多个存储节点的存储空间分配
9.2 层次化银行家算法
针对大规模系统，采用层次化的银行家算法可以降低复杂度：
按资源类型分层：不同类型的资源由不同层次的管理器管理
按优先级分层：高优先级进程可以获得更灵活的资源分配
9.3 动态银行家算法
针对传统银行家算法的局限性，提出了动态银行家算法，允许：
动态调整最大需求：在一定条件下允许进程调整其最大资源需求
预测性资源分配：基于进程的历史行为预测资源需求
10. 总结
银行家算法是一种理论上非常完善的死锁避免算法，它通过在资源分配前进行安全性检查，确保系统始终处于安全状态，从而避免死锁的发生。尽管在实际应用中存在一些局限性，如需要预先知道资源需求、系统开销较大等，但银行家算法仍然是理解死锁避免机制的重要工具，也是很多资源分配系统设计的理论基础。
在实际系统设计中，通常需要根据具体需求和约束，选择合适的死锁处理策略，或者结合多种策略来获得更好的性能和可靠性。银行家算法的思想和原则，如资源预分配、安全性检查等，对于设计可靠的并发系统仍然具有重要的指导意义。