銀行家算法（Java）

系統安全狀態

安全狀態

指系統能按某種進程推進順序（P1，P2，... ，Pn）未每個進程Pi分配器所需資源，直至滿足每個進程對資源的最大需求，使每個進程都可以順利的完成，此時成（P1，P2，...，Pn）為安全序列，沒找到安全序列則說明系統處于不安全狀態

只要系統處于安全狀態就不會發生死鎖，系統處于不安全狀態就有可能會發生死鎖

舉例：

假定系統中有三個進程P1、P2、P3，共有12臺磁帶機。進程P1總共需要10 臺磁帶機，P2和P3 分別需要 4，9。假定在T0時刻，進程P1、P2、P3 分別已獲得 5、2、2臺磁帶機，則還有三臺尚未分配

那么T0 時刻系統是安全的，因為還有一個安全序列（P2，P1，P3）【先將兩臺磁帶機分配給P2，P2執行完后釋放所有磁帶機，還剩下5臺，然后全部分配給P1，執行完釋放，再分配給P3】，所以我們稱T0時刻系統是安全的

如果此時P3想再請求一個磁帶機，這時需要考慮如果分配給P3一個磁帶機后是否還能處于安全狀態，如果不處于安全狀態則不會分配給P3。（分配后已分配為 5、2、3，剩余2，如果全部分配給P2執行完釋放也智能剩余4臺磁帶機，而P1還需要5臺，P2還需要6臺，顯然不能完成執行）所以此時系統并不會將磁帶機分配給P3，因為這會讓系統處于不安全狀態。

銀行家算法

系統資源分配規則

• 每一個新進程進入系統時，他必須先聲明在運行過程中可能需要請求的每種資源類型的最大單元數目，其數目不超過系統所擁有的資源總量
• 進程請求一組資源時，系統必須首先確定受否有足夠的資源分配給該進程
• 如果有足夠的資源分配，還需要計算將這些資源分配后是否會使系統處于不安全狀態
• 只有當系統不會處于安全狀態的時候才會將資源分配給進程，否則讓進程等待

數據結構

• 系統可利用資源向量 Available。這時一個含有m個元素的數組，每個元素表示一類可利用的資源數目。初始值為 系統 的所有資源總量
• 最大需求矩陣 Max。這是一個 n * m 的矩陣，它定義了系統中 n 個進程中每一個進程對 m 類資源的最大需求（對應上表最大需求，只不過這里有 m 類資源，上表只描述一種）
• 分配矩陣 Allocation。這是一個 n * m 的矩陣，它定義了系統中 n 個進程中每一個進程對 m 類資源的當前分配量（對應上表已分配，只不過這里有 m 類資源，上表只描述一種）
• 需求矩陣 Need。這是一個 n * m 的矩陣，用以表示 n 個進程中每個進程對 m 類資源完成程序運行還需要的 數量（就是一個需求量 Need滿足如后定義 Need = Max - Allocation ），這個矩陣方便計算

銀行家算法

用 Request_i 表示進程 i 的請求資源向量，Request_i[j] = K 表示 進程 i 想要請求獲取 第 i 類資源 K 個

public  boolean  isRequest(int[] Request_i, int i) throws InterruptedException {
    for(int j = 0; j < Request_i.length; j++)
        if(Request_i[j] > Need[i][j])
            throw new RuntimeException("請求資源數量超過最大需求資源數量");
    for(int j = 0; j < Request_i.length; j++)
        if(Request_i[j] > Available[j]) {
            synchronized(BankerAlgorithm.class) {
                BankerAlgorithm.class.wait();
                return false;
            }
        }
    // 嘗試分配資源
    for(int j = 0; j < Request_i.length; j++) {
        Available[j] -= Request_i[j];
        Allocation[i][j] += Request_i[j];
        Need[i][j] -= Request_i[j];
    }
    // 執行安全分析算法，如果安全則正是將資源分配給進程 Pi，以完成本次分配，否則本次的試探分配作廢，恢復原來資源分配狀態，讓進程 Pi 等待
    if(isSafety()){
        System.out.println("安全：可用分配");
        return true;
    }
    else{
        for(int j = 0; j < Request_i.length; j++) {
            Available[j] += Request_i[j];
            Allocation[i][j] -= Request_i[j];
            Need[i][j] += Request_i[j];
        }
        synchronized(BankerAlgorithm.class) {
            BankerAlgorithm.class.wait();
            return false;
        }
    }
}

安全性算法

先預定義向量 Work 和 布爾數組 Finish

Work表示可提供給進程據徐運行所需的各類資源數目 在執行算法之前初始化 Work = Available

當進程 Pi 滿足系統資源分配時令 Finish[i] = true

public boolean isSafety(){
    int[] Work = new int[Available.length];
    boolean[] Finish = new boolean[Need.length];
    for(int i = 0; i < Available.length; i++){
        Work[i] = Available[i];
    }
    int unFinished = Finish.length;	// 定義未完成的數量
    int preUnFinished = -1;	// 定義完成一次計算之后
    while(unFinished != 0 && unFinished != preUnFinished){
        preUnFinished = unFinished;
        TASK: for(int i = 0; i < Finish.length; i++){
            /*
                 * 如果該進程未完成，判斷是不是所有的 Work[j] >= Need[i][j]
                 * 如果滿足則假設執行完該進程，所以我們可用直接讓 Work[j] += Need[i][j],
                 * 并標注已完成 Finish[i] = true;
                 * 未完成數量減1 unFinished--
                 */
            if(!Finish[i]){
                for(int j = 0; j < Need[i].length; j++ ){
                    if(Work[j] < Need[i][j]){
                        //有一項不滿足則直接跳過循環（因為已經不可能完成該進程）
                        continue TASK;
                    }
                }
                // 如果全部慢則則完成上述
                for(int j = 0; j < Allocation[i].length; j++)
                    Work[j] += Allocation[i][j];
                Finish[i] = true;
                System.out.println(i);
                unFinished--;
            }
        }
        System.out.println("Work: " + Arrays.toString(Work));
        System.out.println("Finished: " + Arrays.toString(Finish));
        System.out.println("unFinished:" + unFinished);
        System.out.println("preUnFinished:" + preUnFinished);
        /*
         * 如果發現程序執行完一周之后并沒有減少 unFinished 那么表明找不到安全序列了
         */
    }
    if(unFinished == 0){
        return true;
    }
    else
        return false;
}