學不會的銀行家演算法

這是我們期末的課程設計，沒有控制臺輸入資源，直接測驗的程式，邏輯應該沒什么問題

什么是死鎖？

死鎖是指兩個或者兩個以上的行程（執行緒）在執行的程序中，由于競爭資源而造成的阻塞問題，若無外力的作用下會無法繼續推進，此時系統稱之為死鎖狀態，

銀行家演算法：主要是避免死鎖

產生死鎖的的必要條件：

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