前言
2023-8-14 18:18:01
以下内容源自《【学习算法】》
仅供学习交流使用
版权
禁止其他平台发布时删除以下此话
本文首次发布于CSDN平台
作者是CSDN@日星月云
博客主页是https://blog.csdn.net/qq_51625007
禁止其他平台发布时删除以上此话
推荐
银行家算法
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
我们都有光明的未来
祝大家考研上岸
祝大家工作顺利
祝大家得偿所愿
祝大家如愿以偿
点赞收藏关注哦
