Java模拟實作銀行家算法

Java模拟實作銀行家算法

​ 在上一文中我們詳細的讨論了銀行家算法，包含其資料結構、算法步驟和安全性算法，在本文中，我們使用Java語言來實作銀行家算法，并以上一文中的題目來進行驗證。

​ 關于銀行家算法的具體細節，請參看​​上篇博文​​。

​ 首先，我們給出銀行家算法的執行流程圖：

​ 下面我們就步入正題，一起來看下銀行家算法的實作吧：

​ 首先就是資料結構的定義，分别為可利用的資源、所有程序對資源的最大需求、系統中的資源配置設定、以及所有程序仍需要的資源情況。

//可利用資源變量
private List<Integer> available = new ArrayList<>();

//最大資源需求矩陣
private List<List<Integer>> max = new ArrayList<>();

//資源配置設定矩陣
private List<List<Integer>> allocation = new ArrayList<>();

//仍需資源需求矩陣
private List<List<Integer>> need = new ArrayList<>();
      

​ 對于Requesti，我們使用如下結構來定義：

@Data
public class RequestSource {

//請求資源的程序編号
private int id;

//請求的資源清單
private List<Integer> source;
}
      

​ 然後我們來看下銀行家算法的主體代碼：

//銀行家算法
public void bankerAlgorithm(RequestSource request) throws Exception {
//請求資源程序的編号
int id = request.getId();
//判斷請求資源是否超過程序所聲明的最大需求數
for (int i = 0; i < available.size(); i++) {
if (request.getSource().get(i) > need.get(id).get(i)) {
throw new Exception("程序P" + id + "請求資源超過其申明的最大值，發生異常");
    }
  }
//判斷OS目前是否可以滿足程序此次的資源請求
for (int i = 0; i < available.size(); i++) {
if (request.getSource().get(i) > available.get(i)) {
throw new Exception("目前OS尚無足夠的資源滿足程序P" + id + "請求資源，發生異常");
    }
  }
//進行資源的試探配置設定
resourceAllocation(request);
//進行安全性檢查
if (!securityCheck()) {
rollbackAllocation(request);
System.out.println("程序P" + id + "申請資源" + request.getSource() + "不可配置設定！");
  } else {
System.out.println("程序P" + id + "申請資源" + request.getSource() + "配置設定成功！");
  }
}

//資源配置設定，直接配置設定，如果安全性檢查不通過，進行資源復原釋放
private void resourceAllocation(RequestSource request) {
//請求資源程序的編号
int id = request.getId();
List<Integer> requestSource = request.getSource();
//目前程序已經配置設定的資源
List<Integer> currentAllocation = allocation.get(id);
//目前程序仍需的資源
List<Integer> currentNeed = need.get(id);

//修改可利用資源數量、已配置設定資源、仍需求資源
//注：因為在前面已經判斷過request<=need和available,是以資源不會變成負,不需要處理異常
for (int i = 0; i < available.size(); i++) {
available.set(i, available.get(i) - requestSource.get(i));
currentAllocation.set(i, currentAllocation.get(i) + requestSource.get(i));
currentNeed.set(i, currentNeed.get(i) - requestSource.get(i));
  }
//更新總的配置設定矩陣
allocation.set(id, currentAllocation);
//更新總的需求矩陣
need.set(id, currentNeed);
}

//安全性檢查算法
private boolean securityCheck() {
//步驟1：初始化臨時變量work和
List<Integer> work = new ArrayList<>();
work.addAll(available);
int processCount = max.size();
List<Boolean> finish = new ArrayList<>();
for (int i = 0; i < processCount; i++) {
finish.add(false);
  }
//i表示已執行多少個程序，id表示可執行的程序号，j表示資源的類型
int i, j, id;
//在步驟1中是否找到一個能滿足條件的程序，即是否有程序可以執行完畢，釋放資源
boolean flag;
//步驟1：從程序集合中找到滿足條件的程序
for (i = 0; i < processCount; i++) {
flag = false;
for (id = 0; id < processCount; id++) {
//finish為true表示可以獲得所需資源，順利執行完畢
if (finish.get(id)) {
continue;
      }
List<Integer> currentNeed = need.get(id);
//j表示資源的類型
for (j = 0; j < work.size(); j++) {
if (currentNeed.get(j) > work.get(j)) {
break;
        }
      }
//目前程序id所需的資源可以得到滿足，轉而執行步驟2
if (j == work.size()) {
//步驟2
List<Integer> currentAllocation = allocation.get(id);
for (j = 0; j < work.size(); j++) {
//程序可以順利完成，釋放資源
work.set(j, work.get(j) + currentAllocation.get(j));

        }
//更改标志位
finish.set(id, true);
flag = true;
//跳出循環，執行步驟1
System.out.println("此程序執行完畢：P" + id);
break;
      }
    }
//上接break
//判斷是否程序配置設定資源，掃描程序集合一遍，如未配置設定資源，則表示沒有程序可以繼續執行，
//立刻跳出循環，轉而執行步驟3
if (!flag) {
break;
    }
  }

//步驟3：判斷是否所有程序的finish标志位是否全為true
for (id = 0; id < processCount; id++) {
//如果有一個為false，則處于不安全狀态
if (!finish.get(id)) {
return false;
    }
  }
return true;
}

//安全性檢查不通過，復原剛才配置設定的資源
private void rollbackAllocation(RequestSource request) {
//請求資源程序的編号
int id = request.getId();
List<Integer> requestSource = request.getSource();
//目前程序已經配置設定的資源
List<Integer> currentAllocation = allocation.get(id);
//目前程序仍需的資源
List<Integer> currentNeed = need.get(id);

//修改可利用資源數量、已配置設定資源、仍需求資源
//注：因為在前面已經判斷過request<=need和available,是以資源不會變成負,不需要處理異常
for (int i = 0; i < available.size(); i++) {
available.set(i, available.get(i) + requestSource.get(i));
currentAllocation.set(i, currentAllocation.get(i) - requestSource.get(i));
currentNeed.set(i, currentNeed.get(i) + requestSource.get(i));
  }
//更新總的配置設定矩陣
allocation.set(id, currentAllocation);
//更新總的需求矩陣
need.set(id, currentNeed);
}
      

​ 為了友善的展示系統的資源配置設定情況，需要寫一個print函數：

private void printResourceAllocationPic() {
for (int i = 0; i < max.size(); i++) {
System.out.println(max.get(i) + " " + allocation.get(i) + " " + need.get(i));
  }
System.out.println("目前可用資源：" + available);
}
      

​ 最後我們使用上一篇中的例子來進行驗證，題目修改後如下:

例題：假定系統中有五個程序{P0, P1, P2, P3, P4}和三類資源{A, B, C}，各種資源的對應數量為10、5、7，在T0時刻的資源配置設定圖如下圖所示。

​ (1)請檢查T0時刻的安全性。

​ (2)程序P1送出請求向量Request1(1, 0, 2)，為保證系統安全，系統能否将資源配置設定給它？

​ (3)程序P4送出請求向量Request4(3, 3, 0)，為保證系統安全，系統能否将資源配置設定給它？

​ (4)程序P0送出請求向量Request0(0, 2, 0)，為保證系統安全，系統能否将資源配置設定給它？

測試代碼如下：

@Test
public void bankTest() throws Exception {
Integer[][] maxArray = {{7, 5, 3}, {3, 2, 2}, {9, 0, 2}, {2, 2, 2}, {4, 3, 3}};
for (Integer[] tmpArray : maxArray) {
max.add(Arrays.asList(tmpArray));
  }
Integer[][] allocationArray = {{0, 1, 0}, {2, 0, 0}, {3, 0, 2}, {2, 1, 1}, {0, 0, 2}};
for (Integer[] tmpArray : allocationArray) {
allocation.add(Arrays.asList(tmpArray));
  }
Integer[][] needArray = {{7, 4, 3}, {1, 2, 2}, {6, 0, 0}, {0, 1, 1}, {4, 3, 1}};
for (Integer[] tmpArray : needArray) {
need.add(Arrays.asList(tmpArray));
  }
Integer[] availableArray = {3, 3, 2};
available = Arrays.asList(availableArray);

//第一問
System.out.println("第一問？");
//printResourceAllocationPic();
System.out.println("系統安全性檢查結果為：" + securityCheck());
// printResourceAllocationPic();

System.out.println();
System.out.println("第二問？");
//第二問
//建構程序request對象
RequestSource request = new RequestSource();
request.setId(1);
List<Integer> requestSource = new ArrayList<Integer>() {{
add(1);
add(0);
add(2);
  }};
request.setSource(requestSource);
System.out.println("申請資源前的資源配置設定情況：");
printResourceAllocationPic();
bankerAlgorithm(request);
System.out.println("銀行家算法執行後的資源配置設定情況：");
printResourceAllocationPic();

//第三問
System.out.println();
System.out.println("第三問？");
try {
request.setId(4);
Integer[] requestArray = {3, 3, 0};
requestSource = Arrays.asList(requestArray);
request.setSource(requestSource);
System.out.println("申請資源前的資源配置設定情況：");
printResourceAllocationPic();
bankerAlgorithm(request);
printResourceAllocationPic();
  } catch (Exception e) {
System.out.println("無法申請資源，異常原因為：" + e.getMessage());
  }

//第四問
System.out.println();
System.out.println("第四問？");
request.setId(0);
Integer[] requestArray = {0, 2, 0};
requestSource = Arrays.asList(requestArray);
request.setSource(requestSource);
System.out.println("申請資源前的資源配置設定情況：");
printResourceAllocationPic();
bankerAlgorithm(request);
System.out.println("銀行家算法執行後的資源配置設定情況：");
printResourceAllocationPic();
}
      

執行結果如下圖所示：

​ 從圖中可以看到，安全序列為{P1,P3,P0,P2,P4}，是以T0時刻OS處于安全狀态。

​ 從圖中可以看到，資源配置設定後，OS中還存在安全序列為{P1,P3,P0,P2,P4}，是以通過了安全性檢查，是以可以進行資源配置設定，配置設定後的資源如圖中下方紅框所示。

​ 因為此時系統中的Available=(2, 3, 0)，是以無法滿足Request4(3, 3, 0)。

​ 由上圖可知，資源試探配置設定給程序P0後，無法滿足任何程序，是以不存在安全序列，故復原資源。

總結

​ 本文中使用Java語言模拟實作銀行家算法，上面所有所有代碼放到一個類中即可實作（不包含RequestSource，需單獨一個檔案）。算法有較強的擴充性，資源種類可變，程序數可變，有想法的同學可考慮使用Java多線程來模拟死鎖問題，并使用銀行家算法來避免死鎖。這一定會非常有趣。

​ 又到了分隔線以下，本文到此就結束了，本文内容全部都是由部落客自己進行整理并結合自身的了解進行總結，如果有什麼錯誤，還請批評指正。