• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

学不会的银行家算法

互联网 diligentman 1周前 (11-21) 4次浏览

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

什么是死锁?

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

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

产生死锁的的必要条件:

  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

学不会的银行家算法


喜欢 (0)