銀行家算法核心

成都創(chuàng)新互聯(lián)專注骨干網(wǎng)絡(luò)服務(wù)器租用十年，服務(wù)更有保障！服務(wù)器租用，德陽機(jī)房托管 成都服務(wù)器租用，成都服務(wù)器托管，骨干網(wǎng)絡(luò)帶寬，享受低延遲，高速訪問。靈活、實(shí)現(xiàn)低成本的共享或公網(wǎng)數(shù)據(jù)中心高速帶寬的專屬高性能服務(wù)器。

先尋找滿足系統(tǒng)當(dāng)前剩余的資源量（avaliable ）>=進(jìn)程運(yùn)行所需的資源數(shù)的進(jìn)程（need），再假設(shè)這個(gè)進(jìn)程安全校驗(yàn)是成功的，當(dāng)這個(gè)進(jìn)程運(yùn)行完畢后，釋放資源后，現(xiàn)在系統(tǒng)當(dāng)前剩余的資源(avaliable)=avaliable+該線程之前已分配的資源（allocation） ，將該節(jié)點(diǎn)進(jìn)程設(shè)為處理時(shí)忽略進(jìn)程，再以上條件為前提進(jìn)行安全校驗(yàn)。
安全校驗(yàn)：一個(gè)進(jìn)程獲得資源后，運(yùn)行完畢，釋放之前分配的資源，其他的線程可以繼續(xù)運(yùn)行，而不會(huì)造成死鎖。
這樣就會(huì)產(chǎn)生回溯。

滿足條件：是否存在一個(gè)進(jìn)程運(yùn)行所需的資源數(shù)<=當(dāng)前系統(tǒng)剩余的資源數(shù)。

查找操作：先判斷回溯的步長（層數(shù)）是否等于節(jié)點(diǎn)的個(gè)數(shù)，如果等于說明已經(jīng)找到了正確路徑，返回真給上一層，如果不滿足，則看一下此層是否存在滿足條件的節(jié)點(diǎn)，如果存在，這一該節(jié)點(diǎn)為回溯點(diǎn)開始查找操作。如果都不存在，說明上一層的回溯點(diǎn)不是我們要找的節(jié)點(diǎn)，返回假給上一層，并回溯回到上一層節(jié)點(diǎn)，將忽略標(biāo)記清楚，換另一個(gè)滿足條件的節(jié)點(diǎn)繼續(xù)在進(jìn)行查找操作。

先以一個(gè)滿足條件的節(jié)點(diǎn)進(jìn)行忽略標(biāo)記（下一次查找時(shí)可忽略此節(jié)點(diǎn)），回溯的步長加一，再進(jìn)行查找操作（下一層）。

import java.util.Arrays;

public class BanksTest {
  // 用于存儲(chǔ)預(yù)操作后的資源變化
  static int[] new_Avaliable = null;
  // 用于存儲(chǔ)預(yù)操作的完成度
  static boolean[] new_finish = null;
  // 用于保存最終的進(jìn)程執(zhí)行順序,初始化為非法進(jìn)程-1
  static int right[] = { -1, -1, -1, -1, -1 };

  public static void main(String[] args) {
    // 大需求量
    int[][] max = { { 7, 5, 3 }, { 3, 2, 2 }, { 9, 0, 2 }, { 2, 2, 2 }, { 4, 3, 3 } };
    // 當(dāng)前系統(tǒng)可用資源量
    int[] avaliable = { 3, 3, 2 };
    // 每個(gè)進(jìn)程運(yùn)行還需資源量
    int[][] need = new int[5][3];
    // 每個(gè)進(jìn)程已分配的資源量
    int[][] allocation = { { 0, 1, 0 }, { 2, 0, 0 }, { 3, 0, 2 }, { 2, 1, 1 }, { 0, 0, 2 } };
    // 用于第一深度預(yù)判的初始化
    boolean finish[] = { false, false, false, false, false };
    // 獲取每個(gè)進(jìn)程運(yùn)行時(shí)還需的資源量
    for (int i = 0; i < max.length; i++) {
      for (int j = 0; j < max[i].length; j++) {
        need[i][j] = max[i][j] - allocation [i][j];
      }
    }
    // 創(chuàng)建遞歸深度
    int deep = 0;
    // 調(diào)用回溯遞歸算法
    deepCheck(avaliable, allocation, need, finish, deep, right);
    int i = 0;
    // 查看最終的安全序列的值，看是否存在初始的非法進(jìn)程，如果存在，則說明該案例不存在安全的進(jìn)程執(zhí)行順序
    for (; i < right.length; i++) {
      if (right[i] == -1) {
        break;
      }
    }
    if (i < right.length) {
      System.out.println("該案例不存在安全的進(jìn)程執(zhí)行順序");
      return;
    }
    // 打印安全的執(zhí)行順序
    for (int j = 0; j < right.length; j++) {
      System.out.println(right[j]);

    }

  }

  // 完全遞歸回溯查找安全順序
  public static boolean deepCheck(int[] avaliable, int[][] allocation, int[][] need, boolean finish[], int deep,
      int right[]) {
    int j = 0;
    boolean flog = false;
    // 如果深度為進(jìn)程的個(gè)數(shù)數(shù)說明已經(jīng)查找到頭了,說明上一深度的進(jìn)程是安全節(jié)點(diǎn)。因?yàn)樯弦簧疃鹊倪M(jìn)程滿足了當(dāng)前資源數(shù)大于或等于該進(jìn)程運(yùn)行所需的資源數(shù)，且為安全序列中最后一個(gè)節(jié)點(diǎn)。
    if (deep == need.length) {
      return true;
    }
    // 遍歷所有節(jié)點(diǎn)進(jìn)程開始查找,直到找到安全校驗(yàn)成功的的節(jié)點(diǎn)進(jìn)程
    for (int i = 0; i < need.length; i++) {
      // 對于未被標(biāo)記的進(jìn)行校驗(yàn)，已被標(biāo)記的為已被列為安全節(jié)點(diǎn)所以無需再進(jìn)行校驗(yàn)
      if (!finish[i]) {
        // 判斷當(dāng)前的節(jié)點(diǎn)進(jìn)程的剩余的資源量,是否滿足運(yùn)行所需的資源量
        for (j = 0; j < avaliable.length; j++) {
          // 不滿足
          if (need[i][j] > avaliable[j]) {
            break;
          }
        }
        // 不滿足則處理下一個(gè)節(jié)點(diǎn)進(jìn)程
        if (j < avaliable.length) {
          continue;
        } else {
          // 滿足情況
          // 復(fù)制會(huì)被修改的前提條件，已便于當(dāng)前進(jìn)程校驗(yàn)不成功時(shí)，可以恢復(fù)前提條件，開始下一個(gè)節(jié)點(diǎn)進(jìn)程的校驗(yàn)
          new_Avaliable = Arrays.copyOf(avaliable, avaliable.length);
          new_finish = Arrays.copyOf(finish, finish.length);
          // 假設(shè)當(dāng)前節(jié)點(diǎn)進(jìn)程是可以校驗(yàn)成功的節(jié)點(diǎn)進(jìn)程，修改該進(jìn)程運(yùn)行完畢后釋放之前分配的進(jìn)程。
          for (j = 0; j < new_Avaliable.length; j++) {
            new_Avaliable[j] += allocation[i][j];
          }
          // 假設(shè)標(biāo)記當(dāng)前為校驗(yàn)成功的安全節(jié)點(diǎn)進(jìn)程，下一深度查找時(shí)會(huì)忽略此進(jìn)程。
          new_finish[i] = true;
          // 增加深度
          deep++;
          // 以上假設(shè)為前提，進(jìn)行下一深度的安全校驗(yàn)判斷其他所剩余進(jìn)程是否可以繼續(xù)運(yùn)行，而不造成死鎖。
          flog = deepCheck(new_Avaliable, allocation, need, new_finish, deep, right);
          // 如果進(jìn)行安全校驗(yàn)后為真，說明當(dāng)前進(jìn)程是我們要找的進(jìn)程
          if (flog) {
            // 保存到最終進(jìn)程執(zhí)行序列的數(shù)組中
            right[--deep] = i;
            break;
          }

        }

      }

    }
    // 安全校驗(yàn)成功
    if (flog) {
      return true;
    } else {
      // 安全校驗(yàn)失敗
      // 清楚之前的假設(shè)標(biāo)記
      new_finish[right[--deep]] = false;
      return false;
    }

  }
}

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)建站www.cdcxhl.com，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

分享題目：使用java實(shí)現(xiàn)銀行家算法-創(chuàng)新互聯(lián)
URL標(biāo)題：http://weahome.cn/article/dpehip.html