银行家算法【学习算法】

前言

2023-8-14 18:18:01

以下内容源自《【学习算法】》
仅供学习交流使用

版权

禁止其他平台发布时删除以下此话
本文首次发布于CSDN平台
作者是CSDN@日星月云
博客主页是https://blog.csdn.net/qq_51625007
禁止其他平台发布时删除以上此话

推荐

第三章 处理机调度和死锁【操作系统】：7.避免死锁

银行家算法

7.避免死锁

7.1 系统安全状态

在死锁避免方法中，把系统的状态分为安全状态和不安全状态。当系统处于安全状态时，可避免发生死锁。反之，当系统处于不安全状态时，则可能进入到死锁状态。

1安全状态

在该方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，才可将资源分配给进程，否则，令进程等待。

2由安全状态向不安全状态的转换

如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。

在建立了系统安全状态的概念后便可知道避免死锁的基本思想，就是确保系统始终处于安全状态。一个系统开始是处于安全状态的，当有进程请求一个可用资源时，系统需对该进程的请求进行计算，若将资源分配给进程后系统仍处于安全状态，才将该资源分配给进程。

7.2 利用银行家算法避免死锁

1银行家算法中的数据结构

为了实现银行家算法，在系统中必须设置这样四个数据结构，分别用来描述系统中可利用的资源、所有进程对资源的最大需求、系统中的资源分配，以及所有进程还需要多少资源的情况。

(1) 可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Available[j]=K，则表示系统中现有Rj类资源K个。

(2) 最大需求矩阵Max。这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K，则表示进程i需要Rj类资源的最大数目为K。

(3) 分配矩阵Allocation。这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K，则表示进程i当前已分得Rj类资源的数目为K。

(4) 需求矩阵Need。这也是一个n×m矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K，则表示进程i还需要Rj类资源K个方能完成其任务。

上述三个矩阵间存在下述关系：

Need[i,j]=Max[i,j]-Allocation[i,j]

2银行家算法

设Requesti是进程Pi的请求向量，如果Requesti[j]=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：

(1) 如果Requesti[j]≤Need[i,j]，便转向步骤(2)；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。

(2) 如果Requesti[j]≤Available[j]，便转向步骤(3)；否则，表示尚无足够资源，Pi须等待。

(3) 系统试探着把资源分配给进程Pi，并修改数据结构中的数值。

(4) 系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。

3安全性算法

系统所执行的安全性算法可描述如下：

(1) 设置两个向量：①工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work=Available；②Finish：它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish[i]=false；当有足够资源分配给进程时，再令Finish[i]=true。

(2) 从进程集合中找到一个能满足下述条件的进程：

①Finish[i]=false;

②Need[i,j]≤Work[j];

若找到，执行步骤(3)，否则，执行步骤(4)。

(3) 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：

Work[j] = Work[j] + Allocation[i,j];

Finish[i] = true;

go to step 2;

(4) 如果所有进程的Finish[i]=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。

Java算法实现

代码

package os.chapter3._3_6_1;import java.util.Arrays;public class BankerAlgorithm {private final int[][] max; // 最大需求矩阵private final int[][] allocation; // 已分配矩阵private final int[][] need; // 剩余需求矩阵private final int[] available; // 可用资源向量private final int processNum; // 进程数量private final int resourceNum; // 资源数量public BankerAlgorithm(int[][] max, int[][] allocation, int[] available) {this.max = max;this.allocation = allocation;this.need = new int[max.length][max[0].length];this.available = available;this.processNum = max.length;this.resourceNum = max[0].length;initNeed();}public void initNeed(){for (int i = 0; i < processNum; i++) {for (int j = 0; j < resourceNum; j++) {this.need[i][j] = max[i][j] - allocation[i][j];}}}// 银行家算法public void bankerAlgorithm(int[] request,int p) {System.out.println("==========================================");System.out.println("检查初始时的安全性");//初始时刻的安全性int[] safeSequence = safetyCheck();if (safeSequence==null){System.out.println("初始时系统不安全");}else{// 输出安全序列System.out.println("Safe Sequence:");for (int i : safeSequence) {System.out.print("P" + i + " ");}System.out.println();}System.out.println("==========================================");System.out.println("检查是否满足条件1");for(int j=0;j<resourceNum;j++){if(request[j]>need[p][j]){System.out.println("P"+p+"所需要的资源已超过它所宣布的最大值");return;}}System.out.println("检查是否满足条件2");for(int j=0;j<resourceNum;j++){if(request[j]>available[j]){System.out.println("尚无足够资源，P"+p+"必须等待");return;}}System.out.println("==========================================");//试探分配System.out.println("开始试探分配");System.out.println("P"+p+":"+Arrays.toString(request));for(int j=0;j<resourceNum;j++){available[j]=available[j]-request[j];allocation[p][j]=allocation[p][j]+request[j];need[p][j]=need[p][j]-request[j];}System.out.println("开始安全检查");int[] s = safetyCheck();if (s!=null) {System.out.println("可以分配"+"P"+p+":"+Arrays.toString(request));} else {System.out.println("不能分配"+"P"+p+":"+Arrays.toString(request));}System.out.println("==========================================");}// 安全性检查算法public int[] safetyCheck() {int[] work; // 工作向量work = Arrays.copyOf(available, available.length);boolean[] finish = new boolean[processNum]; // 进程是否完成执行的标志int[] safeSequence = new int[processNum]; // 安全序列int count = 0; // 记录已完成的进程数量// 初始化完成标志数组for (int i = 0; i < processNum; i++) {finish[i] = false;}// 寻找可执行的进程直到全部进程执行完毕或者找不到可执行的进程while (count < processNum) {boolean found = false;// 遍历所有进程，查找满足资源需求的进程for (int i = 0; i < processNum; i++) {if (!finish[i] && checkResources(i,work)) {for (int j = 0; j < resourceNum; j++) {work[j] += allocation[i][j];}finish[i] = true;safeSequence[count] = i;count++;found = true;}}// 如果没有找到满足资源需求的进程，则认为系统不安全if (!found) {return null;}}return safeSequence;}// 检查进程的资源需求是否小于等于可用资源private boolean checkResources(int process,int[] work) {for (int i = 0; i < resourceNum; i++) {if (need[process][i] > work[i]) {return false;}}return true;}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};BankerAlgorithm banker = new BankerAlgorithm(max, allocation, available);int[] request1={1,0,2};banker.bankerAlgorithm(request1,1);int[] request4={3,3,0};banker.bankerAlgorithm(request4,4);int[] request0={0,2,0};banker.bankerAlgorithm(request0,0);}
}

结果

==========================================
检查初始时的安全性
Safe Sequence:
P1 P3 P4 P0 P2 
==========================================
检查是否满足条件1
检查是否满足条件2
==========================================
开始试探分配
P1:[1, 0, 2]
开始安全检查
可以分配P1:[1, 0, 2]
==========================================
==========================================
检查初始时的安全性
Safe Sequence:
P1 P3 P4 P0 P2 
==========================================
检查是否满足条件1
检查是否满足条件2
尚无足够资源，P4必须等待
==========================================
检查初始时的安全性
Safe Sequence:
P1 P3 P4 P0 P2 
==========================================
检查是否满足条件1
检查是否满足条件2
==========================================
开始试探分配
P0:[0, 2, 0]
开始安全检查
不能分配P0:[0, 2, 0]
==========================================Process finished with exit code 0

最后

2023-8-14 18:20:16

我们都有光明的未来

祝大家考研上岸
祝大家工作顺利
祝大家得偿所愿
祝大家如愿以偿
点赞收藏关注哦