欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

学不会的银行家算法

程序员文章站 2022-04-14 14:05:11
这是我们期末的课程设计,没有控制台输入资源,直接测试的程序,逻辑应该没什么问题什么是死锁?死锁是指两个或者两个以上的进程(线程)在执行的过程中,由于竞争资源而造成的阻塞问题,若无外力的作用下会无法继续推进,此时系统称之为死锁状态。银行家算法:主要是避免死锁产生死锁的的必要条件:互斥条件:一个资源只能被一个进程占用,如果一个进程请求当前资源,资源被占用的时候,这....

     这是我们期末的课程设计,没有控制台输入资源,直接测试的程序,逻辑应该没什么问题

什么是死锁?

      死锁是指两个或者两个以上的进程(线程)在执行的过程中,由于竞争资源而造成的阻塞问题,若无外力的作用下会无法继续推进,此时系统称之为死锁状态。
学不会的银行家算法

银行家算法:主要是避免死锁

产生死锁的的必要条件:

  1. 互斥条件:一个资源只能被一个进程占用,如果一个进程请求当前资源,资源被占用的时候,这个进程只能等待资源被释放。
  2. 请求和保持条件:进程已经占用了一个资源,然后去请求新的资源但是资源被占用,此时请求的这个进程保持不释放原本所占有的资源。
  3. 不剥夺条件:进程在已占有的资源不可以强行剥夺资源,只能等待进程使用完然后释放。
  4. 环路等待:n个进程之间进行资源的环路等待。

逻辑图

学不会的银行家算法

示例

学不会的银行家算法
根据演算安全性序列为:B D E A C

计算的过程与思路

思路

  1. 首先拿到available与之各个进程之间的need依次作比较,找到满足的进程,分配给当前进程资源执行进程然后释放进程所占有的资源。available[j] = application[i][j]+need[i][j]。
  2. 进行预分配处理,实质是看给当前进程分配资源执行完以后,其他的进程都能得到执行。如果可以就能继续向下找。
  3. 重复上面的步骤依次记录执行的顺序。

过程

这里我就不写预分配的过程
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

相关标签: 算法 java