银行家算法（Banker’s Algorithm）是一个避免死锁（Deadlock）的著名算法，是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死結產生的演算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。
背景
在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。
银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。
什么是死锁
在操作系统中，存在许多进程，死锁是指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。
在一篇博客中作者很形象地对死锁做了比喻：
你和妈妈陷入了僵局...
你: "妈妈, 你不开电视让我看动画片, 我就不吃饭, 哼!"
妈妈: "气死我了, 如果你不吃饭, 我就不给你开电视看动画片!"
结果是: 饭也没吃成，动画片也没看成（挨顿打是另话）
产生死锁的条件
-
互斥条件：指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源，则请求者只能等待，直至占有资源的进程用毕释放。
-
请求和保持条件：指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。
-
不剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。
-
环路等待条件：指在发生死锁时，必然存在一个进程——资源的环形链，即进程集合{P0，P1，P2，···，Pn}中的P0正在等待一个P1占用的资源；P1正在等待P2占用的资源，……，Pn正在等待已被P0占用的资源。
银行家算法与死锁关系
我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。
为保证资金的安全，银行家规定：
-
当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客；
-
顾客可以分期贷款，但贷款的总数不能超过最大需求量；
- 当银行家现有的资金不能满足顾客尚需的贷款数额时，对顾客的贷款可推迟支付，但总能使顾客在有限的时间里得到贷款；
- 当顾客得到所需的全部资金后，一定能在有限的时间里归还所有的资金.
操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。若超过则拒绝分配资源，若能满足则按当前的申请量分配资源，否则也要推迟分配。
简言之，银行家算法实际上是对资源进行拟分配，计算分配后系统是否安全，安全则执行分配，不安全则拒绝分配（可以理解为银行对贷款客户的偿还能力评估）。
系统的安全状态
如果所有过程有可能完成执行（终止），则一个状态被认为是安全的。由于系统无法知道什么时候一个过程将终止，或者之后它需要多少资源，系统假定所有进程将最终试图获取其声明的最大资源并在不久之后终止。在大多数情况下，这是一个合理的假设，因为系统不是特别关注每个进程运行了多久（至少不是从避免死锁的角度）。此外，如果一个进程终止前没有获取其它能获取的最多的资源，它只是让系统更容易处理。
基于这一假设，该算法通过尝试寻找允许每个进程获得的最大资源并结束（把资源返还给系统）的进程请求的一个理想集合，来决定一个状态是否是安全的。不存在这个集合的状态都是不安全的。
安全状态举例
假定系统中有五个进程{P0、P1、P2、P3、P4}和三种类型资源{A、B、C}，每一种资源的数量分别为10、5、7。各进程的最大需求、T0时刻资源分配情况如下所示。
不安全状态举例
代码实现
伪代码实现
- P - 进程的集合
-
Mp - 进程p的最大的请求数目
- Cp - 进程p当前被分配的资源
- A - 当前可用的资源
// 摘自维基百科
while (P != ∅) {
found = FALSE;
foreach (p ∈ P) {
if (Mp − Cp ≤ A) {
/* p可以獲得他所需的資源。假設他得到資源後執行；執行終止，並釋放所擁有的資源。*/
A = A + Cp ;
P = P − {p};
found = TRUE;
}
}
if (! found) return FAIL;
}
return OK;
Java实现
package com.achan.util;
import com.achan.banker.bean.Resources;
import java.util.Map;
/**
* @author Achan
* @date 2020/5/9
*/
public final class ShowDataUtil {
private ShowDataUtil() {}
public static String mapToString(Map<?, ?> map) {
StringBuilder builder = new StringBuilder().append("{");
for (Map.Entry<?, ?> entry : map.entrySet()) {
builder.append(entry.getKey().toString()).append("=").append(entry.getValue().toString()).append(", ");
}
builder.append("}");
return builder.toString();
}
public static String simpleResources(Map<String, Resources> resourcesMap) {
StringBuilder stringBuilder = new StringBuilder();
resourcesMap.forEach((s, resources) -> {
stringBuilder.append(s).append(":").append(resources.getValue()).append(" ");
});
return stringBuilder.toString();
}
}
package com.achan.banker.bean;
/**
* 系统资源/银行存款
*/
public class Resources {
/**
* 类型，源代码中的name
*/
private String type;
/**
* 值
*/
private Integer value;
public String getType() {
return type;
}
public Integer getValue() {
return value;
}
public Resources setValue(Integer value) {
this.value = value;
return this;
}
public Resources setType(String type) {
this.type = type;
return this;
}
@Override
public String toString() {
return "Resources{" +
"type='" + type + '\'' +
", value=" + value +
'}';
}
}
package com.achan.banker.bean;
import java.util.Map;
/**
* 表示该类为一个Progress
* @author Achan
*/
public interface Progress {
/**
* 获取进程id
* @return 进程id
*/
String getId();
/**
* 申请所需所有资源
*
* @return 是否成功
*/
default boolean applySystemResource() {
// 获取银行实例
return Banker.tryAllocationResources(this, this.getNeedResources());
}
/**
* 申请部分资源
* @param resources 申请的资源
* @return 申请
*/
default boolean applySystemResource(Map<String, Resources> resources) {
return Banker.tryAllocationResources(this, resources);
}
/**
* 运行
* @return 是否运行成功
*/
default boolean run() {
return applySystemResource();
}
/**
* 进程是否完成
* @return ignore
*/
default boolean isFinished() {
return false;
}
/**
* 进程运行完成调用
*/
void finished();
/**
* 释放进程资源
* @param resourcesMap 系统资源
*/
default void freeResources(Map<String, Resources> resourcesMap) {
this.getAllocationResources().forEach((key, value) -> {
resourcesMap.get(key).setValue(resourcesMap.get(key).getValue() + value.getValue());
value.setValue(0);
});
this.getNeedResources().forEach((key, value) -> value.setValue(0));
}
/**
* 获取进程运行所需资源
* @return 进程所需资源
*/
Map<String, Resources> getNeedResources();
default int getNeedResourcesSum() {
int needResourcesSum = 0;
Map<String, Resources> progressNeedResources = this.getNeedResources();
for (Resources resources : progressNeedResources.values()) {
needResourcesSum += resources.getValue();
}
return needResourcesSum;
}
/**
* 获取进程所需最大资源
* @return 进程所需最大资源
*/
Map<String, Resources> getMaxResources();
/**
* 获取进程已分配资源
* @return 进程已分配资源
*/
Map<String, Resources> getAllocationResources();
}
package com.achan.banker.bean.progress;
import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import com.achan.banker.Main;
import com.achan.banker.bean.Progress;
import com.achan.banker.bean.Resources;
import com.achan.util.ShowDataUtil;
/**
* 进程类/消费者/银行客户
* @author Achan
*/
public class ProgressImp implements Progress {
/**
* 进程运行所需最大资源
*/
private final Map<String, Resources> maxResources;
/**
* 进程已分配资源
*/
private final Map<String, Resources> allocationResources;
/**
* 进程目前仍需要的资源（虽然可以用max-allocation计算出来，在这里直接声明，用空间换时间）
*/
private final Map<String, Resources> needResources;
/**
* 进程结束标识
*/
protected Boolean finished = false;
private String name;
public ProgressImp(String name, Collection<Resources> maxResources, Collection<Resources> allocationResources) {
setName(name);
this.maxResources = new HashMap<>(maxResources.size());
maxResources.forEach(r -> {
if (this.maxResources.containsKey(r.getType())) {
// 如果包含该key，合并之
this.maxResources.put(r.getType(),
r.setValue(this.maxResources.get(r.getType()).getValue() + r.getValue()));
} else {
this.maxResources.put(r.getType(), r);
}
});
this.allocationResources = new HashMap<>(this.maxResources.size());
allocationResources.forEach(r -> {
if (this.maxResources.containsKey(r.getType())) {
if (this.allocationResources.containsKey(r.getType())) {
// 如果包含该key，合并之
this.allocationResources.put(r.getType(),
r.setValue(this.allocationResources.get(r.getType()).getValue() + r.getValue()));
} else {
this.allocationResources.put(r.getType(), r);
}
// 如果已分配的资源大于最大需求资源，回收多余资源
if (this.allocationResources.get(r.getType()).getValue() > this.maxResources.get(r.getType())
.getValue()) {
this.allocationResources.put(r.getType(), this.allocationResources.get(r.getType())
.setValue(this.maxResources.get(r.getType()).getValue()));
}
} // 运行不需要该资源，舍去
});
this.needResources = new HashMap<>(this.maxResources.size());
maxResources.forEach(r -> {
this.needResources.put(r.getType(),
new Resources().setType(r.getType())
.setValue(r.getValue() - (this.allocationResources.get(r.getType()) == null ? 0
: this.allocationResources.get(r.getType()).getValue())));
});
}
@Override
public String getId() {
return name;
}
@Override
public boolean isFinished() {
return finished;
}
@Override
public void finished() {
this.finished = true;
}
@Override
public Map<String, Resources> getNeedResources() {
return needResources;
}
@Override
public Map<String, Resources> getMaxResources() {
return maxResources;
}
@Override
public Map<String, Resources> getAllocationResources() {
return allocationResources;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
@Override
public String toString() {
return "ProgressImp{" +
"maxResources=" + ShowDataUtil.mapToString(maxResources) +
", allocationResources=" + ShowDataUtil.mapToString(allocationResources) +
", needResources=" + ShowDataUtil.mapToString(needResources) +
", finished=" + finished +
", name='" + name + '\'' +
'}';
}
}
package com.achan.banker.bean;
import com.achan.banker.bean.progress.ProgressImp;
import com.achan.util.ShowDataUtil;
import java.util.*;
/**
* 银行家/操作系统
* 简单单例模式
* Banker
*
* @author Achan
*/
public class Banker {
/**
* 系统最多资源种类
*/
public final static int SYSTEM_MAX_RESOURCES_COUNT = 26;
/**
* 系统当前可用资源
*/
private static HashMap<String, Resources> systemCurrentResources;
private static Banker BANKER;
/**
* 系统中的所有进程
*/
private static LinkedList<Progress> progresses;
private Banker(List<String> resourceTypes, List<Integer> resourceValues) {
int min = Math.min(resourceTypes.size(), resourceValues.size());
min = Math.min(SYSTEM_MAX_RESOURCES_COUNT, min);
// 初始化资源空间，直接指定空间大小
systemCurrentResources = new HashMap<>(min);
progresses = new LinkedList<>();
for (int i = 0; i < min; i++) {
// 忽略掉重复命名
if (!systemCurrentResources.containsKey(resourceTypes.get(i))) {
systemCurrentResources.put(resourceTypes.get(i),
new Resources().setType(resourceTypes.get(i)).setValue(resourceValues.get(i)));
}
}
}
/**
* 获取银行实例，如果银行实例未初始化，先初始化后获取
*
* @param resourceTypes 资源类型
* @param resourceValues 资源可用值
* @return 返回当前银行实例
*/
public static Banker initBanker(List<String> resourceTypes, List<Integer> resourceValues) {
if (BANKER == null) {
// 当参数为null时忽略
if (resourceTypes == null || resourceValues == null) {
return null;
}
BANKER = new Banker(resourceTypes, resourceValues);
}
return BANKER;
}
/**
* 获取当前银行实例
*
* @return 当前银行实例，未初始化时返回null
*/
public static Banker getCurrentBanker() {
return BANKER;
}
/**
* 获取指定类型的资源，只读
*
* @param resourceType 资源类型
* @return 所获取的资源，不存在为null
*/
public static Resources getResources(String resourceType) {
return systemCurrentResources.get(resourceType);
}
/**
* 向指定进程分配指定资源
*
* @param progress 申请资源的进程
* @param applyResources 申请的资源数目
* @return 是否分配成功
*/
public static boolean tryAllocationResources(Progress progress, Map<String, Resources> applyResources) {
Progress progressBak = deepCloneProgress(progress);
Map<String, Resources> tempResources = deepCloneSystemResources();
for (Map.Entry<String, Resources> entry : applyResources.entrySet()) {
// 系统当前该类型资源
final Resources systemResources = tempResources.get(entry.getKey());
int requestValue = entry.getValue().getValue();
int needMaxValue = progress.getNeedResources().get(entry.getKey()).getValue();
// 请求大于需要
if (requestValue > needMaxValue) {
requestValue = needMaxValue;
entry.getValue().setValue(needMaxValue);
}
if (systemResources.getValue() < requestValue) {
// 系统当前资源小于请求资源
return false;
} else {
// 资源分配
tempResources.get(entry.getKey()).setValue(systemResources.getValue() - requestValue);
needMaxValue = needMaxValue - requestValue;
progress.getNeedResources().get(entry.getKey()).setValue(needMaxValue);
progress.getAllocationResources().get(entry.getKey())
.setValue(progress.getAllocationResources().get(entry.getKey()).getValue() + requestValue);
}
}
// 安全性检查
if (systemIsSafe(tempResources) != null) {
// 存在安全序列，释放进程资源
if (progress.getNeedResourcesSum() == 0) {
progress.freeResources(systemCurrentResources);
progress.finished();
} else {
for (Map.Entry<String, Resources> entry : applyResources.entrySet()) {
final Resources systemResources = systemCurrentResources.get(entry.getKey());
systemResources.setValue(systemResources.getValue() - entry.getValue().getValue());
}
}
return true;
} else {
// 不成功，向系统返回已分配的资源
progress.getNeedResources().putAll(progressBak.getNeedResources());
progress.getAllocationResources().putAll(progressBak.getAllocationResources());
return false;
}
}
/**
* 使用所提供的资源进行模拟系统安全性检查
*
* @param tempResources 现有资源
* @return 如果安全，返回进程运行集合，不安全返回null
*/
public static Collection<Progress> systemIsSafe(Map<String, Resources> tempResources) {
List<Progress> result = new ArrayList<>(progresses.size());
// 克隆一个进程池
List<Progress> tempProgressList = deepCloneSystemProgresses();
// 释放所有已完成进程
for (Progress p : tempProgressList) {
if (p.getNeedResourcesSum() == 0) {
p.freeResources(tempResources);
p.finished();
result.add(p);
}
}
// TODO 这里最好使用动态规划进行优化
for (int i = 0; i < tempProgressList.size(); i++) {
Progress p = tempProgressList.get(i);
if (p.isFinished()) {
continue;
}
boolean canRun = true;
Map<String, Resources> progressNeedResources = p.getNeedResources();
// 判断是否可以运行
for (Map.Entry<String, Resources> entry : progressNeedResources.entrySet()) {
canRun = canRun && (tempResources.get(entry.getKey()).getValue() >= entry.getValue().getValue());
}
if (canRun) {
// 释放系统资源
p.freeResources(tempResources);
p.finished();
result.add(p);
// 重新判断，因为本次循环已经结束，i会自增
i = -1;
}
}
if (result.size() != progresses.size()) {
return null;
} else {
return result;
}
}
/**
* 系统安全性检查，当前系统是否安全，如果想模拟检查，请使用isSafe(tempResources: Map<String, Resources>)
*
* @return 如果安全，返回进程运行集合，不安全返回null
*/
public static Collection<Progress> systemIsSafe() {
return systemIsSafe(deepCloneSystemResources());
}
/**
* 向系统添加新进程
*
* @param progress 新进程
* @return 是否添加成功
*/
public static boolean putNewProgress(Progress progress) {
if (progress == null) {
return false;
}
// 进程当前已分配资源小于系统当前可用资源初始化成功
boolean isOk = true;
for (Map.Entry<String, Resources> entry : progress.getAllocationResources().entrySet()) {
isOk = isOk && entry.getValue().getValue() < systemCurrentResources.get(entry.getKey()).getValue();
}
if (isOk) {
progresses.push(progress);
for (Map.Entry<String, Resources> entry : progress.getAllocationResources().entrySet()) {
systemCurrentResources.get(entry.getKey()).setValue(
systemCurrentResources.get(entry.getKey()).getValue() - entry.getValue().getValue());
}
}
return isOk;
}
/**
* @return 获取当前系统资源备份
*/
private static Map<String, Resources> deepCloneSystemResources() {
HashMap<String, Resources> result = new HashMap<>(systemCurrentResources.size());
for (Map.Entry<String, Resources> entry : systemCurrentResources.entrySet()) {
result.put(entry.getKey(), new Resources()
.setType(entry.getKey())
.setValue(entry.getValue().getValue()));
}
return result;
}
private static List<Progress> deepCloneSystemProgresses() {
ArrayList<Progress> result = new ArrayList<>(progresses.size());
progresses.forEach(progress -> result.add(deepCloneProgress(progress)));
return result;
}
private static Progress deepCloneProgress(Progress progress) {
List<Resources> tempAllocationResources = new LinkedList<>();
progress.getAllocationResources().values().forEach(resources ->
tempAllocationResources.add(new Resources()
.setType(resources.getType()).setValue(resources.getValue())));
return new ProgressImp(progress.getId(), progress.getMaxResources().values(), tempAllocationResources);
}
public static void showData() {
System.out.println("当前系统可用资源：" + ShowDataUtil.simpleResources(systemCurrentResources));
System.out.println("当前系统进程：");
System.out.println("进程名\tMax\tAllocation\tNeed");
progresses.forEach(p -> System.out.println(p.getId() + "\t"
+ ShowDataUtil.simpleResources(p.getMaxResources()) + "\t"
+ ShowDataUtil.simpleResources(p.getAllocationResources()) + "\t"
+ ShowDataUtil.simpleResources(p.getNeedResources())));
}
public static List<Progress> getProgresses() {
return progresses;
}
}
package com.achan.banker;
import com.achan.banker.bean.Banker;
import com.achan.banker.bean.Progress;
import com.achan.banker.bean.Resources;
import com.achan.banker.bean.progress.ProgressImp;
import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;
/**
* @author Achan
* @date 2020/5/8
*/
public class Main {
static Scanner scanner = new Scanner(System.in);
public static void main(String[] args) {
initSystem();
Banker.showData();
Collection<Progress> safeProgress = Banker.systemIsSafe();
System.out.println("系统是否进程安全？" + (safeProgress != null));
if (safeProgress != null) {
System.out.println("安全序列：");
safeProgress.forEach(progress -> System.out.print(progress.getId() + "\t"));
System.out.println();
}
while (true) {
System.out.println("*************************************************************");
System.out.println();
System.out.println();
System.out.println("\t-------------------银行家算法演示------------------");
System.out.println(" R(r):请求分配 \n");
System.out.println(" E(e):退出 \n");
System.out.println("\t---------------------------------------------------");
System.out.print("输入您的选择：");
String input = scanner.next();
switch (input) {
case "r":
case "R":
if (applyResources()) {
System.out.println("允许分配");
safeProgress = Banker.systemIsSafe();
if (safeProgress != null) {
System.out.println("安全序列：");
safeProgress.forEach(progress -> System.out.print(progress.getId() + "\t"));
System.out.println();
}
} else {
System.out.println("不允许分配");
}
Banker.showData();
break;
case "e":
case "E":
scanner.close();
System.exit(0);
default:
System.out.println("请输入正确选择");
break;
}
}
}
public static boolean applyResources() {
List<Progress> progresses = Banker.getProgresses();
Progress progress;
while (true) {
System.out.print("输入申请分配资源的进程位置（0-" + (progresses.size() - 1) + "）：");
int number = scanner.nextInt();
if (number >= progresses.size()) {
System.out.println("输入错误请重新输入");
} else {
progress = progresses.get(number);
break;
}
}
System.out.println("当前所选进程：" + progress.toString());
System.out.print("输入申请各项资源的值（一行，用空格分开）：");
scanner.nextLine();
String[] input = scanner.nextLine().split(" ");
// 需要申请的资源
Map<String, Resources> applyResources = new HashMap<>(progress.getMaxResources().size());
AtomicInteger i = new AtomicInteger();
progress.getMaxResources().forEach((s, resources) -> {
int value;
// 规避非法输入
try {
value = Integer.parseInt(input[i.getAndIncrement()]);
} catch (Exception e) {
value = 0;
}
Resources r = new Resources().setType(s).setValue(value);
applyResources.put(s, r);
});
return progress.applySystemResource(applyResources);
}
public static void initSystem() {
/*
* 样例输入（安全）：
* 3
* 10 5 7
* 5
* 7 0 5 1 3 0
* 3 2 2 0 2 0
* 9 3 0 0 2 2
* 2 2 2 1 2 1
* 4 0 3 0 3 2
*
*/
System.out.print("输入资源数目：");
int resourcesCount = scanner.nextInt();
List<String> resourceNames = new ArrayList<>(resourcesCount);
List<Integer> resourceValues = new ArrayList<>(resourcesCount);
for (int i = 0; i < Math.min(resourcesCount, Banker.SYSTEM_MAX_RESOURCES_COUNT); i++) {
String resourceName = Character.toString('A' + i);
System.out.print("输入资源" + resourceName + "系统最大值（整数）：");
resourceNames.add(resourceName);
resourceValues.add(scanner.nextInt());
}
Banker.initBanker(resourceNames, resourceValues);
System.out.print("输入系统进程数量：");
int progressCount = scanner.nextInt();
for (int i = 0; i < progressCount; i++) {
List<Resources> maxResources = new ArrayList<>(resourcesCount);
List<Resources> allocationResources = new ArrayList<>(resourcesCount);
for (String name : resourceNames) {
System.out.printf("请输入Progress-%d资源%s的最大需求量及当前分配量（空格隔开）：", i, name);
maxResources.add(new Resources().setType(name).setValue(scanner.nextInt()));
allocationResources.add(new Resources().setType(name).setValue(scanner.nextInt()));
}
if (!Banker.putNewProgress(new ProgressImp("Progress-" + i, maxResources, allocationResources))) {
i--;
}
}
}
}
友情链接
我的个人博客
我的公众号AchanYao后援团
如果觉得本文对你有用的话可以点赞+关注
