银行家算法-分析与编码
银行家算法
Banker\’s Algorithm是一个避免Deadlock的算法，是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计。
算法背景
在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。
银行家在客户申请的贷款数量不超过之前声明的最大值时，都应尽量满足更多客户的需要。
可以看到关键字：
- 资金不能无限借需要声明最大资金量。
- 客户借满了以后，需要及时归还（通常这点不太容易做到…）。
- 算法的目的是尽量满足跟多客户的需求（没有侧重，没有VIP，通常来说这点也不太容易做到，毕竟商业追求利益最大化…）。
当然，我们不去考虑太多其他策略，单就算法而论。
类比操作系统：
- 银行的资金相当于OS中的资源（CPU，内存，线程etc.）；
- 银行的用户相当于OS中的进程；
由于该算法在避免死锁的方法中，所施加的限制条件较弱，有可能（敲黑板!）获得令人满意的系统性能。
算法内容
基本思想：分配资源之前，先判断分配后系统是否是安全的；若是，才分配；否则，回滚分配；
由此可见，算法的核心应该是判断系统是否安全。
先看百科对系统安全的定义：安全序列是指一个进程序列{P1，…，Pn}是安全的，即对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和。（反正我是没看明白…）
所谓安全通俗来说就是：分给进程A以后，我要先看一下：现有的空闲资源加上其他进程归还的资源后，不会让任何一个进程永远处于等待状态。
下面看一下整个流程：
数据结构
- 数组
int[] mAvailable：表示系统当前空闲资源； - 二维数组
int[][] mAllocated：各进程当前已经持有的资源数； - 二维数组
int[][] mNeed：各进程还需要的资源数;
算法主流程
- 如果进程
i请求资源j大于进程i还需要的资源数mNeed[i][j]，则出错；否则继续下一步。 - 如果进程
i请求资源j大于当前该资源的空闲数mAvailable[i][j]，则申请失败进程等待；否则继续下一步。 - 先执行分配，再检查系统安全性，若安全则分配生效；否则，回滚分配。
检查系统安全性
- 先检查当前触发安全性检查的进程i是否已经完成分配，若已完成则假设其迅速归还；否则不做处理继续下一步。
- 从所有进程中找到未完成且当前资源可以为其完成分配的进程，再假设已完成分配且其归还所有资源；重复此步骤，直到再也找不到满足条件的进程。
- 检查所有进程的状态，如果存在未标记Over的进程，则系统不安全，否则系统安全。
注：
上面说的完成分配，理解成分配给进程其初始宣称的所有资源的最大数量。
Talk is Cheap，Show you the Code：
申请资源部分
/**
* 进程申请资源
*
* @param i 进程编号
* @param j 资源编号
* @param x 资源数量
* @return 0：申请成功，-1：错误，1：资源不足，2：不安全分配
*/
public int apply(int i, int j, int x) {
if (x > mNeed[i][j]) {
Main.d(i + "进程请求资源数" + j + "（数量：" + x + "），大于初始宣称数" + mNeed[i][j] + "，拒绝分配!");
return -1;
}
// 如果请求数量超过了当前系统空闲资源，需要先等待
if (x > mAvailable[j]) {
Main.d(i + "进程请求资源数" + j + "（数量：" + x + "），大于资源空闲数" + mAvailable[j] + "，需要等待");
return 1;
}
// 否则，先分配给进程
mAvailable[j] -= x;
mAllocated[i][j] += x;
mNeed[i][j] -= x;
// 分配后测试系统安全性
if (!checkSafe(i)) {
// 如果系统不安全，则撤回分配
mAvailable[j] += x;
mAllocated[i][j] -= x;
mNeed[i][j] += x;
Main.d(i + "进程请求资源" + j + "（数量：" + x + "），分配后导致系统不安全，需要等待...");
return 2;
}
Main.d(i + "进程请求资源" + j + "（数量：" + x + "），分配成功！");
// 分配后如果系统安全，则分配成立
return 0;
}
安全性检查部分
/**
* 测试系统是否安全
*
* @param k 触发检查的进程编号
* @return 系统在分配k进程资源后是否处于安全状态
*/
public boolean checkSafe(int k) {
int[] work = new int[mAvailable.length];
System.arraycopy(mAvailable, 0, work, 0, mAvailable.length);
// 当前触发检查的进程是k，需要看一下进程在此次分配后是否可以结束，如果可以，需要退还名下资源
returnResIfFinished(work, k);
// 初始化各进程的完成状态
boolean[] finish = new boolean[mAllocated.length];
boolean isOk;
for (int i = 0; i < mAllocated.length; i++) {
isOk = true;
for (int j = 0; j < mAvailable.length; j++) {
if (mNeed[i][j] > 0) {
isOk = false;
break;
}
}
finish[i] = isOk;
}
for (int i = 0; i < finish.length; i++) {
if (finish[i]) {
continue;
}
// 在未完成的进程中，找到一个可以分配资源的进程
isOk = true;
for (int j = 0; j < work.length; j++) {
if (mNeed[i][j] > work[j]) {
isOk = false;
break;
}
}
if (!isOk) {
continue;
}
// 如果可以，就假设把资源分配给了它，且假设它运行完成了并退还了资源
finish[i] = true;
for (int j = 0; j < work.length; j++) {
work[j] += mAllocated[i][j];
}
// 类似topo排序，空闲资源有退还，重新扫描
i = 0;
}
// 最后检查，是否所有的进程最后都可以安全结束
for (boolean ans : finish) {
if (!ans) {
return false;
}
}
return true;
}
最后，附上测试DEMO：
笔者注：除去注释后核心类SystemInfo代码约100行，相对来说理解起来不算太困难。
完整DEMO
public class Main {
public static void main(String[] args) throws Exception {
SystemInfo system = new SystemInfo(3, 1, 2);
system.init(new int[][]{{2, 1, 0}, {3, 0, 2}, {1, 1, 1}, {2, 1, 2}, {3, 1, 0}, {3, 1, 2}});
request(system, 0, 0, 2);
request(system, 0, 1, 1);
request(system, 1, 0, 1);
request(system, 1, 0, 2);
request(system, 1, 2, 1);
request(system, 1, 2, 1);
request(system, 2, 0, 1);
request(system, 2, 1, 1);
request(system, 2, 2, 1);
request(system, 3, 0, 1);
request(system, 3, 0, 1);
request(system, 3, 1, 1);
request(system, 3, 2, 2);
request(system, 4, 0, 1);
request(system, 4, 0, 2);
request(system, 4, 1, 1);
request(system, 5, 0, 3);
request(system, 5, 1, 1);
request(system, 5, 2, 1);
request(system, 5, 2, 1);
}
private static void request(SystemInfo sys, int i, int j, int x) {
new Thread(new Runnable() {
@Override
public void run() {
// 申请系统资源，如果失败就等待300~600ms后重试
while (0 != sys.apply(i, j, x)) {
try {
Thread.sleep((long) (Math.random() * 300 + 300));
} catch (InterruptedException ignore) {
}
}
// 模拟资源使用 500~1000 ms
try {
Thread.sleep((long) (Math.random() * 500 + 500));
} catch (InterruptedException ignore) {
}
sys.returnResIfFinished(i);
}
}).start();
}
public static void d(Object info) {
System.out.println(info);
}
}
class SystemInfo {
// 系统可用资源
private int[] mAvailable;
// 各进程当前已经持有的资源数
private int[][] mAllocated;
// 各进程还需要的资源数
private int[][] mNeed;
/**
* 初始化
*
* @param res 系统资源
*/
public SystemInfo(int... res) {
mAvailable = new int[res.length];
System.arraycopy(res, 0, mAvailable, 0, res.length);
}
/**
* 初始化，各进程宣称对各种资源的最大需求
*
* @param max 最大需求量
*/
public void init(int[][] max) {
assert null != max;
assert max.length > 0;
assert max[0].length == mAvailable.length;
mAllocated = new int[max.length][mAvailable.length];
mNeed = new int[max.length][mAvailable.length];
for (int i = 0; i < max.length; i++) {
System.arraycopy(max[i], 0, mNeed[i], 0, mAvailable.length);
// TODO 这个时候应该评估一下，把所有资源都给某一个进程，是否能满足需求，若不能则申请失败
}
}
/**
* 进程申请资源
*
* @param i 进程编号
* @param j 资源编号
* @param x 资源数量
* @return 0：申请成功，-1：错误，1：资源不足，2：不安全分配
*/
public synchronized int apply(int i, int j, int x) {
if (x > mNeed[i][j]) {
Main.d(i + "进程请求资源数" + j + "（数量：" + x + "），大于初始宣称数" + mNeed[i][j] + "，拒绝分配!");
return -1;
}
// 如果请求数量超过了当前系统空闲资源，需要先等待
if (x > mAvailable[j]) {
Main.d(i + "进程请求资源数" + j + "（数量：" + x + "），大于资源空闲数" + mAvailable[j] + "，需要等待");
return 1;
}
// 否则，先分配给进程
mAvailable[j] -= x;
mAllocated[i][j] += x;
mNeed[i][j] -= x;
// 分配后测试系统安全性
if (!checkSafe(i)) {
// 如果系统不安全，则撤回分配
mAvailable[j] += x;
mAllocated[i][j] -= x;
mNeed[i][j] += x;
Main.d(i + "进程请求资源" + j + "（数量：" + x + "），分配后导致系统不安全，需要等待...");
return 2;
}
Main.d(i + "进程请求资源" + j + "（数量：" + x + "），分配成功！");
// 分配后如果系统安全，则分配成立
return 0;
}
/**
* 测试系统是否安全
*
* @param k 触发检查的进程编号
* @return 系统在分配k进程资源后是否处于安全状态
*/
public boolean checkSafe(int k) {
int[] work = new int[mAvailable.length];
System.arraycopy(mAvailable, 0, work, 0, mAvailable.length);
// 当前触发检查的进程是k，需要看一下进程在此次分配后是否可以结束，如果可以，需要退还名下资源
returnResIfFinished(work, k);
// 初始化各进程的完成状态
boolean[] finish = new boolean[mAllocated.length];
boolean isOk;
for (int i = 0; i < mAllocated.length; i++) {
isOk = true;
for (int j = 0; j < mAvailable.length; j++) {
if (mNeed[i][j] > 0) {
isOk = false;
break;
}
}
finish[i] = isOk;
}
for (int i = 0; i < finish.length; i++) {
if (finish[i]) {
continue;
}
// 在未完成的进程中，找到一个可以分配资源的进程
isOk = true;
for (int j = 0; j < work.length; j++) {
if (mNeed[i][j] > work[j]) {
isOk = false;
break;
}
}
if (!isOk) {
continue;
}
// 如果可以，就假设把资源分配给了它，且假设它运行完成了并退还了资源
finish[i] = true;
for (int j = 0; j < work.length; j++) {
work[j] += mAllocated[i][j];
}
// 类似topo排序，空闲资源有退还，重新扫描
i = 0;
}
// 最后检查，是否所有的进程最后都可以安全结束
for (boolean ans : finish) {
if (!ans) {
return false;
}
}
return true;
}
/**
* 检查进程资源是否申请完毕，如果完毕则立即归还资源
*
* @param res 资源池
* @param k 进程编号
*/
private void returnResIfFinished(int[] res, int k) {
boolean isOk = true;
for (int i = 0; i < res.length; i++) {
if (mNeed[k][i] > 0) {
isOk = false;
break;
}
}
// 退还进程名下资源
if (isOk) {
for (int i = 0; i < res.length; i++) {
res[i] += mAllocated[k][i];
}
}
}
/**
* 【测试用】
* 用于外部各进程自己检查是否资源申请完毕，申请完毕则假设立即归还
*
* @param k 进程编号
*/
public synchronized void returnResIfFinished(int k) {
returnResIfFinished(mAvailable, k);
}
}
以上。
2020.02.03
湖南.永州
版权声明：本文为chavin原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。