学不会的银行家算法
程序员文章站
2022-04-14 14:05:11
这是我们期末的课程设计,没有控制台输入资源,直接测试的程序,逻辑应该没什么问题什么是死锁?死锁是指两个或者两个以上的进程(线程)在执行的过程中,由于竞争资源而造成的阻塞问题,若无外力的作用下会无法继续推进,此时系统称之为死锁状态。银行家算法:主要是避免死锁产生死锁的的必要条件:互斥条件:一个资源只能被一个进程占用,如果一个进程请求当前资源,资源被占用的时候,这....
这是我们期末的课程设计,没有控制台输入资源,直接测试的程序,逻辑应该没什么问题
什么是死锁?
死锁是指两个或者两个以上的进程(线程)在执行的过程中,由于竞争资源而造成的阻塞问题,若无外力的作用下会无法继续推进,此时系统称之为死锁状态。
银行家算法:主要是避免死锁
产生死锁的的必要条件:
- 互斥条件:一个资源只能被一个进程占用,如果一个进程请求当前资源,资源被占用的时候,这个进程只能等待资源被释放。
- 请求和保持条件:进程已经占用了一个资源,然后去请求新的资源但是资源被占用,此时请求的这个进程保持不释放原本所占有的资源。
- 不剥夺条件:进程在已占有的资源不可以强行剥夺资源,只能等待进程使用完然后释放。
- 环路等待:n个进程之间进行资源的环路等待。
逻辑图
示例
根据演算安全性序列为:B D E A C
计算的过程与思路
思路
- 首先拿到available与之各个进程之间的need依次作比较,找到满足的进程,分配给当前进程资源执行进程然后释放进程所占有的资源。available[j] = application[i][j]+need[i][j]。
- 进行预分配处理,实质是看给当前进程分配资源执行完以后,其他的进程都能得到执行。如果可以就能继续向下找。
- 重复上面的步骤依次记录执行的顺序。
过程
这里我就不写预分配的过程
1.比较need与available的值下面就不写这个过程了每次都需要作比较,分配给B执行B释放B所占有的资源available 5 3 2
2.分配给D执行D释放D所占有的资源available 7 4 3
3.分配给E执行E释放E所占有的资源available 7 4 5
4.分配给A执行A释放A所占有的资源available 7 5 5
5.分配给C执行C释放C所占有的资源available 10 5 7
这是整个的计算过程
下面贴出代码
代码
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class blanker {
/**
* 找到安全序列
* @param application 进程占用资源数
* @param need 进程需求资源数
* @param available
* @return
*/
public List<Integer> security(int[][] application,int[][] need,int[] available){
List<Integer> list = new ArrayList<>();
int count = 0;
//表示进程执行完成
boolean[] flag = new boolean[application.length];
while(true){
//无限循环
for (int i = 0; i < application.length; i++) {
//表示哪个进程
if (judge(need,available,i) && !flag[i]){
//表示当前进程可以申请到资源,进行预分配
int[][] applications = application;
int[] availables = new int[available.length];
for (int k = 0; k < available.length; k++) {
//进行预分配
availables[k] = available[k]+application[i][k];
flag[i] = true;
}
//复制当前数组
boolean[] flags = Arrays.copyOf(flag,flag.length);
boolean b = preDistribution(applications, need, availables,flags);
//预分配成功
if (b){
for (int k = 0; k < available.length; k++) {
available[k] = available[k] + application[i][k];
}
//表示预分配成功
list.add(i);
}
count++;
}
}
if (count >= application.length){
//表示分配失败
break;
}
}
if (list.size() == application.length) {
return list;
}
return new ArrayList<>();
}
/**
* 预分配处理
* @param application 每个进程所占用的对应资源的数目
* @param need 每个进程所需要的对应资源的数目
* @param available 可以使用的资源数目
* @return
*/
public static boolean preDistribution(int[][] application,int[][] need,int[] available,boolean[] flag){
//执行的次数
int k = 0;
while (true){
for (int i = 0; i < need.length; i++) {
if (judge(need,available,i) && !flag[i]){
//表示申请到资源
for (int j = 0; j < need[0].length; j++) {
//释放当前用所占用的资源
available[j] = application[i][j] + available[j];
}
//表示当前进程已经执行完成
flag[i] = true;
}
}
k++;
//每次for循环完判断是否标志
if (judgeFlag(flag)){
return true;
}
//表示执行次数超过进程数 不能预分配
if (k > application.length){
return false;
}
}
}
/**
* 判断预分配是否完成
* @param flag
* @return
*/
public static boolean judgeFlag(boolean[] flag){
for (int i = 0; i < flag.length; i++) {
if (!flag[i]){
return false;
}
}
return true;
}
/**
* 判断当前进程的能否申请到资源
* @param need
* @param available
* @param i
* @return
*/
public static boolean judge(int[][] need, int[] available,int i){
for (int j = 0; j < need[i].length; j++) {
if(need[i][j] > available[j]){
return false;
}
}
return true;
}
public static void main(String[] args) {
int[][] application = new int[][]{{0, 1, 0}, {2, 0, 0}, {3, 0, 2}, {2, 1, 1}, {0, 0, 2}};
int[][] need = new int[][]{{7, 4, 3}, {1, 2, 2}, {6, 0, 0}, {0, 1, 1}, {4, 3, 1}};
int[] available = new int[]{3,3,2};
blanker blanker = new blanker();
List<Integer> security = blanker.security(application, need, available);
char[] progress = new char[]{'A','B','C','D','E'};
for (Integer lists : security){
System.out.print(progress[lists]+" ");
}
}
}
执行结果
final
本文地址:https://blog.csdn.net/weixin_44048140/article/details/109831336