银行家算法是一个避免死锁的著名算法，是由艾兹格.迪杰斯特拉设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。
一、背景介绍
在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。
安全序列：指一个进程序列{p1,......,pn}是安全的，即对于每一个进程pi（1<= i<=n）,它以后尚需要的资源量不超过系统当前剩余资源量与所有进程pj(j<i)当前占有资源量之和。
安全状态一定是没有死锁发生的。
不安全状态:不存在一个安全序列，不安全状态一定导致死锁。
二、相关数据结构
银行家算法中的数据结构
- 设系统中有m种不同资源, n个进程
- Available向量: 系统中尚未分配的每种资源的总量
- Available[j]: 尚未分配的资源j的数量
- Max矩阵: 各个进程对每种资源的最大需求量(进程事先声明)
- Max[i, j]（Claim[i,j]): 进程i 对资源j 的最大需求量
- Allocation矩阵: 当前资源分配状况
- Allocation[i, j]: 进程i获得的资源j的数量
- Need矩阵: 每个进程还需要的资源的数量
- Need[i, j]: 进程i尚需的资源j的数量
各数据结构之间的关系
- Resource[j] = Available[j] + (Allocation[1, j] + Allocation[2, j] + … + Allocation[n, j])
- Max[i, j] <= Resource[j]
- Allocation[i, j] <= Max[i, j]
- Allocation[i, j] + Need[i, j] =Max[i, j]
安全性算法
1. 设Work和Finish 分别是长度为m 和n 的向量，按如下方式进行初始化:
Work = Available
Finish [i] = false ( i =1,2, …, n)
2. 查找这样的i使其满足:(a) Finish [i] = false (b) Need i <=Work
3. 如果没有这样的 i 存在，那么就转到第4步.
4. Work = Work + Allocation i Finish[i] = True 返回到第2步.
5. 如果对所有的i，Finish [i] == True ，那么系统处于安全状态
例题讲解1
R1,R2,R3的数量分别为(9,3,6); Available(1,1,2)
问：1.该时刻是否为安全状态
2.进程A请求资源Request(1,0,1)，能够分配吗？为什么？
解题步骤如下：（注：！！！圆圈序号表示做题方法，答案中不必出现。）
1.画出如下表格
①首先将available中的数字填在首行work中
②available（1,1,2）分别和A、B、C、D中的need相比较，倘若小于，则从上往下依次选择。例如B（1,0,2）小于则将B填入第一行，其后need、Allocation依次填入
③接着计算work+allocation的值与R1R2R3（9,3,6）相比较，小于则为true
④将上一行中的work+allocation的值填入下一行work中，接着重复②之后的操作。
⑤直到填完最后一个进程，finish都为true则此时产生了一个安全序列。
2.①将requestA和needA和Available相比较，若小于二者则可继续判断，否则不够分配。
RequestA(1,0,1)<=Need(2,2,2)
RequestA(1,0,1)<=Available(1,1,2)
②修改A的allocation和need，allocation+requestA ， need-requestA 并将值填入其中。
假定满足进程A的要求，为它分配所申请的资源，并且修改AllocaitonA 和 NeedA，得到： 
此时：Available＝(0,1,1)：不能分配给任何进程；因此不能分配此次请求。
③此时available-requsetA得到（0,1,1）此时，更新A的状态，重复第一问判断是否存在安全状态。通过比较我们发现available（0,1,1）小于任何一个进程的Need故无法进行分配
例题讲解2
设系统在T0时刻系统状态如下：剩余资源向量为: A=(2, 3, 3)
问：① T0时刻是否为安全状态？若是，请给出安全序列。
② 在T0时刻若进程P2请求资源（0，3，4），是否能实施资源分配？为什么？
③ 在②的基础上，若进程P4请求资源（2，0，1），是否能实施资源分配？为什么？
解析：与题1不同的是，题2并未给出一个系统的表，因此需要在草稿本上列出表格的大概状态。最大资源需求（Max）已分配资源数量（allocation）剩余资源向量（available）
need = max - allocation,其余步骤参考题1 即可
答案：1. 是，安全序列：p4, p5, p1, p2, p3
2.因为 R（0,3,4）> A （2,3,3,）所以不能分配。
3.因为R(2,0,1)<=N4(2, 0,1)且 < A(2,3,3)假设可以满足，则N4=(0, 0, 0), A= (0,3,2)，在此基础上，是安全的，因此可以实施分配。安全序列为：p4,p5,p1,p2,p3
三、参考示例代码
import java.util.Arrays; class BankersAlgorithm { private int[][] max; // 最大需求矩阵 private int[][] allocation; // 已分配资源矩阵 private int[][] need; // 剩余需求矩阵 private int[] available; // 可用资源向量 private int[][] request; // 请求资源矩阵 public BankersAlgorithm(int[][] max, int[][] allocation, int[] available) { this.max = max; this.allocation = allocation; this.available = available; int numOfProcesses = max.length; int numOfResources = available.length; this.need = new int[numOfProcesses][numOfResources]; this.request = new int[numOfProcesses][numOfResources]; // 计算剩余需求矩阵 for (int i = 0; i < numOfProcesses; i++) { for (int j = 0; j < numOfResources; j++) { need[i][j] = max[i][j] - allocation[i][j]; } } } public void requestResources(int pid, int[] request) { System.out.println("进程 " + pid + " 请求资源: " + Arrays.toString(request)); boolean safe = checkSafety(pid, request); if (safe) { System.out.println("请求通过，为进程 " + pid + " 分配资源 " + Arrays.toString(request)); allocateResources(pid, request); } else { System.out.println("请求被拒绝，进程 " + pid + " 等待..."); } } private boolean checkSafety(int pid, int[] request) { int numOfProcesses = max.length; int numOfResources = available.length; int[] work = Arrays.copyOf(available, numOfResources); boolean[] finish = new boolean[numOfProcesses]; // 设置该进程的请求资源情况 for (int i = 0; i < numOfResources; i++) { allocation[pid][i] += request[i]; need[pid][i] -= request[i]; work[i] -= request[i]; } int count = 0; // 用于统计已分配资源的进程数 boolean hasFinished = true; // 标识是否存在符合条件的进程 while (count < numOfProcesses && hasFinished) { hasFinished = false; for (int i = 0; i < numOfProcesses; i++) { if (!finish[i] && checkNeedLessOrEqual(work, need[i])) { // 分配资源给进程 for (int j = 0; j < numOfResources; j++) { work[j] += allocation[i][j]; } finish[i] = true; count++; hasFinished = true; } } } // 恢复该进程的请求资源情况 for (int i = 0; i < numOfResources; i++) { allocation[pid][i] -= request[i]; need[pid][i] += request[i]; work[i] += request[i]; } return count == numOfProcesses; } private boolean checkNeedLessOrEqual(int[] work, int[] need) { for (int i = 0; i < work.length; i++) { if (work[i] < need[i]) { return false; } } return true; } private void allocateResources(int pid, int[] request) { int numOfResources = available.length; for (int i = 0; i < numOfResources; i++) { available[i] -= request[i]; allocation[pid][i] += request[i]; need[pid][i] -= request[i]; } } } public class TestBanker { public static void main(String[] args) { int[][] max = { {7, 5, 3}, {3, 2, 2}, {9, 0, 2}, {2, 2, 2}, {4, 3, 3} }; int[][] allocation = { {0, 1, 0}, {2, 0, 0}, {3, 0, 2}, {2, 1, 1}, {0, 0, 2} }; int[] available = {3, 3, 2}; // 继续编写您想要的代码逻辑 } }
