admin 管理员组文章数量: 887017
在学操作系统的时候，了解到死锁问题，今天在学习并发编程时，也遇到了死锁，在了解了死锁的原因后，遇到一个经典的算法——银行家算法，这是一种避免死锁的算法。在学习完后，我决定总结一下银行家算法的核心思想。
什么是死锁？
死锁是指在计算机系统中，多个进程或线程因竞争资源或互相等待而陷入的一种永久阻塞的状态。具体来说，死锁发生在以下四个条件同时满足的情况下：
-
互斥条件：某些资源在同一时间只能被一个进程使用。如果其他进程请求该资源，则必须等待。
-
占有且等待条件：一个进程已经持有至少一个资源，但又请求新的资源，而新的资源正被其他进程持有，因此进程必须等待。
-
不剥夺条件：资源不能被强行从一个进程中剥夺，必须由持有它的进程主动释放。
-
循环等待条件：存在一个进程链，使得每个进程都在等待链中的下一个进程所持有的资源，形成一个环形等待链。
银行家算法
计算机科学家艾兹赫尔·戴克斯特拉（Edsger Dijkstra）于1965年提出了银行家算法（Banker's Algorithm）。该算法模拟银行家在向客户贷款时的决策过程，确保系统在资源分配过程中始终处于安全状态。
先看安全状态
到底什么是安全呢？先看一个情景：
系统共有12台磁带机，然后有3个进程，P1，P2，P3
| 进程 | 最大需求 | 已分配 | 可用 |
| P1 | 10 | 5 | |
| P2 | 4 | 2 | |
| P3 | 9 | 2 |
问题：操作系统该怎么分配呢？
除了已分配的5+2+2=9，还剩12-9=3，这3个磁带机如果给P1，完了，彻底完了，现在P1占有5+3=8台，操作系统一台不剩了，但是，P1，P2，P3，还在向操作系统申请，但是刚刚已经分配完了，这样3个进程都一直申请，由于无法结束，谁也无法释放资源，所以进入死锁状态了，这个锅得是操作系统来背，我们可以理所当然的想到，操作系统剩下的3台，应给P2两台，P2需要4台，已经有两台了，再来2台就能结束，并还操作系统4台，这样操作系统就有1+4=5台了，接下来给P1，P1顺利结束，然后给P3，P3顺利结束。问题就在分配上，通过分配就能避免死锁问题。
安全状态
安全状态是指系统能够按某种顺序为每一个进程分配资源，使得每个进程都能够顺利完成其工作并释放资源。换句话说，在安全状态下，系统总能找到一个进程序列，使得每个进程在其需求的资源得到满足后，都能顺利执行并释放资源，从而使其他进程也能获得资源并完成任务。
不安全状态
不安全状态是指系统当前无法保证一定能找到一个进程序列，使得所有进程都能够顺利完成其工作。不安全状态不一定会导致死锁，但存在进入死锁的风险。如果系统处于不安全状态，并不意味着系统已经死锁，只是说在某些资源分配情况下，系统可能会进入死锁状态。
再看银行家算法
这里大概明白银行家算法怎么来的了，就是通过算法，保证资源分配是安全的，从而避免死锁。
基本概念
-
资源类型和实例：系统中有多种资源类型，每种资源类型有若干实例。例如，资源类型R1有10个实例，资源类型R2有5个实例等。
-
进程：系统中有若干进程，每个进程需要一定数量的资源来完成其任务。
-
分配矩阵（Allocation）：当前已经分配给各个进程的资源数量。
-
需求矩阵（Need）：每个进程还需要的资源数量，等于其最大需求减去已分配的资源。
-
可用矩阵（Available）：统当前可用的各类资源数量。
工作原理
-
安全性检查：
系统计算当前状态是否安全，即是否存在一种进程执行顺序，使得每个进程都能顺利完成并释放其占用的资源。 -
资源请求处理：
当进程请求资源时，系统假设分配这些资源，并再次进行安全性检查。如果分配资源后系统仍然处于安全状态，则分配资源；否则，拒绝该请求，进程继续等待。
具体步骤
-
初始化：
- 创建并初始化分配矩阵、需求矩阵和可用矩阵。
-
资源请求：
- 进程发出资源请求。
-
试探性分配：
- 假设将请求的资源分配给进程，更新分配矩阵、需求矩阵和可用矩阵。
-
安全性检查：
- 检查假设分配后系统是否处于安全状态。如果是，正式分配资源；否则，恢复状态，拒绝请求。
示例
假设系统有三种资源类型：A、B、C，它们的实例数分别为10、5、7。系统有五个进程：P0, P1, P2, P3, P4。给出分配矩阵、最大需求矩阵和可用矩阵如下：
-
分配矩阵（Allocation）：
A B C 0 1 0 2 0 0 3 0 2 2 1 1 0 0 2 -
最大需求矩阵（Max）：
A B C 7 5 3 3 2 2 9 0 2 2 2 2 4 3 3 -
可用矩阵（Available）：
A B C 3 3 2
理解上的注意点
在开始我提到了并发编程，这里指的是线程死锁，那银行家算法解决的是进程死锁还是线程死锁呢？
银行家算法主要用于解决进程死锁问题，而不是特定的线程死锁问题。虽然进程和线程在许多方面有相似之处，特别是在资源分配和同步方面，但是银行家算法是设计用来在操作系统的层面上管理资源分配，从而避免进程之间的死锁。
在多线程编程中，线程死锁也是一个重要问题，但通常解决线程死锁的方法更多是依赖于锁机制的设计和使用，如避免嵌套锁定、使用超时锁定机制或设计无锁算法等。银行家算法的思想也可以在多线程环境中应用，但其主要用途还是在进程资源分配和调度中，确保系统不会因为资源分配不当而进入死锁状态。
手动实现（模拟）
这是编程实现，有兴趣的朋友可以试试
import java.util.Scanner;
public class BankersAlgorithm {
private int numberOfProcesses;
private int numberOfResources;
private int[] available;
private int[][] maximum;
private int[][] allocation;
private int[][] need;
public BankersAlgorithm(int numberOfProcesses, int numberOfResources) {
this.numberOfProcesses = numberOfProcesses;
this.numberOfResources = numberOfResources;
available = new int[numberOfResources];
maximum = new int[numberOfProcesses][numberOfResources];
allocation = new int[numberOfProcesses][numberOfResources];
need = new int[numberOfProcesses][numberOfResources];
}
public void input() {
Scanner scanner = new Scanner(System.in);
System.out.println("输入可用资源：");
for (int i = 0; i < numberOfResources; i++) {
available[i] = scanner.nextInt();
}
System.out.println("输入最大需求矩阵：");
for (int i = 0; i < numberOfProcesses; i++) {
for (int j = 0; j < numberOfResources; j++) {
maximum[i][j] = scanner.nextInt();
}
}
System.out.println("输入分配矩阵：");
for (int i = 0; i < numberOfProcesses; i++) {
for (int j = 0; j < numberOfResources; j++) {
allocation[i][j] = scanner.nextInt();
}
}
calculateNeed();
}
private void calculateNeed() {
for (int i = 0; i < numberOfProcesses; i++) {
for (int j = 0; j < numberOfResources; j++) {
need[i][j] = maximum[i][j] - allocation[i][j];
}
}
}
public boolean isSafe() {
boolean[] finish = new boolean[numberOfProcesses];
int[] work = available.clone();
while (true) {
boolean found = false;
for (int i = 0; i < numberOfProcesses; i++) {
if (!finish[i]) {
boolean canAllocate = true;
for (int j = 0; j < numberOfResources; j++) {
if (need[i][j] > work[j]) {
canAllocate = false;
break;
}
}
if (canAllocate) {
for (int j = 0; j < numberOfResources; j++) {
work[j] += allocation[i][j];
}
finish[i] = true;
found = true;
}
}
}
if (!found) {
break;
}
}
for (boolean b : finish) {
if (!b) {
return false;
}
}
return true;
}
public boolean requestResources(int process, int[] request) {
for (int i = 0; i < numberOfResources; i++) {
if (request[i] > need[process][i]) {
System.out.println("请求的资源超过需要的资源。");
return false;
}
if (request[i] > available[i]) {
System.out.println("请求的资源超过可用的资源。");
return false;
}
}
for (int i = 0; i < numberOfResources; i++) {
available[i] -= request[i];
allocation[process][i] += request[i];
need[process][i] -= request[i];
}
if (!isSafe()) {
for (int i = 0; i < numberOfResources; i++) {
available[i] += request[i];
allocation[process][i] -= request[i];
need[process][i] += request[i];
}
System.out.println("系统进入不安全状态，资源请求被拒绝。");
return false;
}
return true;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("输入进程数量和资源种类数量：");
int numberOfProcesses = scanner.nextInt();
int numberOfResources = scanner.nextInt();
BankersAlgorithm ba = new BankersAlgorithm(numberOfProcesses, numberOfResources);
ba.input();
if (ba.isSafe()) {
System.out.println("系统处于安全状态。");
} else {
System.out.println("系统处于不安全状态。");
}
System.out.println("输入请求的进程编号和资源请求向量：");
int process = scanner.nextInt();
int[] request = new int[numberOfResources];
for (int i = 0; i < numberOfResources; i++) {
request[i] = scanner.nextInt();
}
if (ba.requestResources(process, request)) {
System.out.println("资源请求成功。");
} else {
System.out.println("资源请求失败。");
}
}
}版权声明：本文标题：一文搞懂银行家算法 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1727378071h1111126.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论