java如何實現(xiàn)銀行家算法

本篇內(nèi)容主要講解“java如何實現(xiàn)銀行家算法”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學(xué)習(xí)“java如何實現(xiàn)銀行家算法”吧!

銀行家算法核心

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

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

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

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

import java.util.Arrays;public class BanksTest {  // 用于存儲預(yù)操作后的資源變化  static int[] new_Avaliable = null;  // 用于存儲預(yù)操作的完成度  static boolean[] new_finish = null;  // 用于保存最終的進程執(zhí)行順序,初始化為非法進程-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 };    // 每個進程運行還需資源量    int[][] need = new int[5][3];    // 每個進程已分配的資源量    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 };    // 獲取每個進程運行時還需的資源量    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;    // 查看最終的安全序列的值，看是否存在初始的非法進程，如果存在，則說明該案例不存在安全的進程執(zhí)行順序    for (; i < right.length; i++) {      if (right[i] == -1) {        break;      }    }    if (i < right.length) {      System.out.println("該案例不存在安全的進程執(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;    // 如果深度為進程的個數(shù)數(shù)說明已經(jīng)查找到頭了,說明上一深度的進程是安全節(jié)點。因為上一深度的進程滿足了當(dāng)前資源數(shù)大于或等于該進程運行所需的資源數(shù)，且為安全序列中最后一個節(jié)點。    if (deep == need.length) {      return true;    }    // 遍歷所有節(jié)點進程開始查找,直到找到安全校驗成功的的節(jié)點進程    for (int i = 0; i < need.length; i++) {      // 對于未被標(biāo)記的進行校驗，已被標(biāo)記的為已被列為安全節(jié)點所以無需再進行校驗      if (!finish[i]) {        // 判斷當(dāng)前的節(jié)點進程的剩余的資源量,是否滿足運行所需的資源量        for (j = 0; j < avaliable.length; j++) {          // 不滿足          if (need[i][j] > avaliable[j]) {            break;          }        }        // 不滿足則處理下一個節(jié)點進程        if (j < avaliable.length) {          continue;        } else {          // 滿足情況          // 復(fù)制會被修改的前提條件，已便于當(dāng)前進程校驗不成功時，可以恢復(fù)前提條件，開始下一個節(jié)點進程的校驗          new_Avaliable = Arrays.copyOf(avaliable, avaliable.length);          new_finish = Arrays.copyOf(finish, finish.length);          // 假設(shè)當(dāng)前節(jié)點進程是可以校驗成功的節(jié)點進程，修改該進程運行完畢后釋放之前分配的進程。          for (j = 0; j < new_Avaliable.length; j++) {            new_Avaliable[j] += allocation[i][j];          }          // 假設(shè)標(biāo)記當(dāng)前為校驗成功的安全節(jié)點進程，下一深度查找時會忽略此進程。          new_finish[i] = true;          // 增加深度          deep++;          // 以上假設(shè)為前提，進行下一深度的安全校驗判斷其他所剩余進程是否可以繼續(xù)運行，而不造成死鎖。          flog = deepCheck(new_Avaliable, allocation, need, new_finish, deep, right);          // 如果進行安全校驗后為真，說明當(dāng)前進程是我們要找的進程          if (flog) {            // 保存到最終進程執(zhí)行序列的數(shù)組中            right[--deep] = i;            break;          }        }      }    }    // 安全校驗成功    if (flog) {      return true;    } else {      // 安全校驗失敗      // 清楚之前的假設(shè)標(biāo)記      new_finish[right[--deep]] = false;      return false;    }  }}

到此，相信大家對“java如何實現(xiàn)銀行家算法”有了更深的了解，不妨來實際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進入相關(guān)頻道進行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！