銀行家算法學習筆記

一.概念引入

        銀行家算法（ banker's algorithm ）由 Dijkstra于1965提出，關鍵是将死鎖的問題示範為一個銀行家貸款的模型，由于能用于銀行系統的現金貸款而出名。一個銀行家向一群客戶發放信用卡，每個客戶有不同的信用額度。每個客戶可以提出信用額度内的任意額度的請求，直到額度用完後再一次性還款。銀行家承諾每個客戶最終都能獲得自己需要的額度。所謂“最終”，是說銀行家可以先挂起某個額度請求較大的客戶的請求，優先滿足小額度的請求，等小額度的請求還款後，再處理挂起的請求。這樣，資金能夠永遠流通。是以銀行家算法其核心是：保證銀行家系統的資源數至少不小于一個客戶的所需要的資源數。

        銀行家算法是一種最有代表性的避免死鎖的算法。在避免死鎖方法中允許程序動态地申請資源，但銀行家算法在系統在進行資源配置設定之前(并不是真的不配置設定，這樣就沒法做了，隻不過是試探性配置設定，不滿足的話再恢複)，應先計算此次配置設定資源的安全性，若配置設定不會導緻系統進入不安全狀态，則配置設定，否則等待。為實作銀行家算法，系統必須設定若幹資料結構。要解釋銀行家算法，必須先解釋作業系統安全狀态和不安全狀态。安全序列是指存在一個程序式列{P1，…，Pn}是安全的，不會死鎖(至少兩個線程占有某資源A，但是都不滿足，剩餘的資源A配置設定給誰仍然無法滿足)，安全狀态如果存在一個由系統中所有程序構成的安全序列P1，…，Pn，則系統處于安全狀态，安全狀态一定是沒有死鎖發生；不安全狀态不存在一個安全序列，不安全狀态不一定導緻死鎖。

        本算法在理論上是出色的，能非常有效地避免死鎖，但從某種意義上說，它缺乏實用價值，因為很少有程序能夠在運作前就知道其所需資源的最大值，且程序數也不是固定的，往往在不斷地變化（如新使用者登入或退出），況且原來可用的資源也可能突然間變成不可用（如列印機、錄音帶機可能被損壞）。

二.算法原理

        銀行家算法的基本思想是配置設定資源之前，判斷系統是否是安全的；若是，才配置設定。每配置設定一次資源就測試一次是否安全，不是資源全部就位後才測試，注意了解checkError函數的循環順序。

        我們可以把作業系統看作是銀行家，作業系統管理的資源相當于銀行家管理的資金，程序向作業系統請求配置設定資源相當于使用者向銀行家貸款。

為保證資金的安全，銀行家規定：

1. 當一個顧客對資金的最大需求量不超過銀行家現有的資金時就可接納該顧客(試探性配置設定)
2. 顧客可以分期貸款，但貸款的總數不能超過最大需求量(可能一次并不能滿足所需要的全部資源)
3. 當銀行家現有的資金不能滿足顧客尚需的貸款數額時，對顧客的貸款可推遲支付，但總能使顧客在有限的時間裡得到貸款(不存在死鎖)
4. 當顧客得到所需的全部資金後，一定能在有限的時間裡歸還所有的資金(運作後釋放)

        作業系統按照銀行家制定的規則為程序配置設定資源，當程序首次申請資源時，要測試該程序對資源的最大需求量，如果系統現存的資源可以滿足它的最大需求量則按目前的申請量配置設定資源，否則就推遲配置設定。當程序在執行中繼續申請資源時，先測試該程序本次申請的資源數是否超過了該資源所剩餘的總量。若超過則拒絕配置設定資源，若能存在安全狀态，則按目前的申請量配置設定資源，否則也要推遲配置設定。

三.算法的Java實作

1: import java.util.Arrays;      

2: import javax.swing.JOptionPane;      

3:      

4: public class Banker {      

5:      

6:   /*      

7:    * 資源向量必須全部設定成static，因為可能      

8:    * 同一個線程多次輸入才滿足條件      

9:    */      

10:   //每個線程需要的資源數      

11:   static int max[][] = { { 7, 5, 3 }, { 3, 2, 2 }, { 9, 0, 2 },      

12:     { 2, 2, 2 }, { 4, 3, 3 } };      

13:   //系統可用資源數      

14:   static int avaliable[] = {10,5,7};      

15:   //已經配置設定資源      

16:   static int allocation[][] = { { 0, 0, 0 }, { 0, 0, 0 }, { 0, 0, 0 },      

17:     { 0, 0, 0 }, { 0, 0, 0 } };      

18:   //每個程序還需要的資源數,初試一個資源也沒配置設定；實際上應該等于max-avaliable      

19:   static int need[][] = Arrays.copyOf(max,max.length);      

20:   //每次申請的資源數      

21:   static int request[] = { 0, 0, 0 };      

22:   //NUM個線程，N種資源      

23:   static final int NUM = 5, N = 3;      

24:   static Function function = new Function();      

25:      

26:   public static void main(String[] args) {      

27:     JOptionPane jpane = new JOptionPane();      

28:      

29:     //是否進行模拟标志，沒有布爾，因為從JOpotionpane輸入      

30:     int flag = 1;      

31:      

32:     while(1==flag) {      

33:       /*      

34:        * 用與判斷線程号是否合法      

35:        * 需要放在while内部，防止下次繼續模拟時i還是上次輸入的      

36:        */      

37:       int i = -1;      

38:       while(i<0||i>=NUM) {      

39:         String str = jpane.showInputDialog("輸入申請資源的線程号(0到4)：");      

40:         i = Integer.parseInt(str);      

41:         if(i<0||i>=NUM) {      

42:           JOptionPane.showMessageDialog(jpane, "輸入的線程号不合法！！！");      

43:         }      

44:       }      

45:       //資源輸入有效性标志      

46:       boolean tag = true;      

47:       for(int j=0; j<N; j++) {      

48:         String str = jpane.showInputDialog("輸入線程"+i+"所申請的資源"+j+"數目：");      

49:         request[j] = Integer.parseInt(str);      

50:         //有效性檢查      

51:         if(request[j]>need[i][j]) {      

52:           JOptionPane.showMessageDialog(jpane, "輸入的資源數大于需要資源數！！！");      

53:           tag = false;      

54:           break;      

55:         }else {      

56:           if(request[j]>avaliable[j]) {      

57:             JOptionPane.showMessageDialog(jpane, "輸入的資源數大于可用資源數！！！");      

58:             tag = false;      

59:             break;      

60:           }      

61:         }      

62:       }      

63:       //是否存在安全序列      

64:       boolean vis = true;      

65:       if(tag) {      

66:         function.allocateK(i);      

67:         vis = function.checkError(i);      

68:         if(false==vis) {      

69:           //上面調用了allocateK，是以不僅需要釋放，還需要恢複      

70:           function.freeKAndRestore(i);      

71:         }else {      

72:           //測試是否全部資源到位      

73:           boolean f = function.checkRun(i);      

74:           if(true==f) {      

75:             JOptionPane.showMessageDialog(jpane      

76:                 ,"程序"+i+"全部資源到位！！！"+"\n"+"即将釋放所占用資源");      

77:             function.freeKNotRestore(i);      

78:           }      

79:         }      

80:       }else {      

81:         //實際上沒必要清空，因為該數組是輸入的，隻為了展示一種良好習慣      

82:         Arrays.fill(request,0);      

83:       }      

84:       String str = JOptionPane.showInputDialog("是否繼續模拟(1表示是，0退出)？");      

85:       flag = Integer.parseInt(str);      

86:     }      

87:   }      

88: }      

89:      

90: class Function {      

91:   /*      

92:    * 實際上完全是靜态的，沒必要新new一個Banker      

93:    */      

94:   Banker banker = new Banker();      

95:   //為線程k配置設定資源      

96:   public void allocateK(int k) {      

97:     for(int i=0; i<banker.N; i++) {      

98:       banker.avaliable[i] -= banker.request[i];      

99:       banker.need[k][i] -= banker.request[i];      

100:       banker.allocation[k][i] += banker.request[i];      

101:     }      

102:   }      

103:   public boolean checkError(int i) {      

104:     int work = 0;      

105:     //存儲所有線程是否安全      

106:     boolean[] finish = new boolean[banker.NUM];      

107:     Arrays.fill(finish,false);      

108:     //存儲一個安全序列      

109:     int temp[] = new int[banker.NUM];      

110:     Arrays.fill(temp,0);      

111:     //temp數組下标      

112:     int t = 0;      

113:      

114:     //線程号參數是i      

115:     for(int j=0; j<banker.N; j++) {      

116:       work = banker.avaliable[j];      

117:       int k = i;      

118:      

119:       while(k<banker.NUM) {      

120:         if(finish[k]==false&&work>=banker.need[k][j]) {      

121:           /*      

122:            *  注意不是max數組，因為此時線程k      

123:            *  所需資源不一定完全就位      

124:            *  加的是allocation，因為進行此項檢查前先試探性地      

125:            *  配置設定給線程k資源了      

126:            */      

127:           //滿足該線程，回收該項資源，看是否滿足其它線程      

128:           work += banker.allocation[k][j];      

129:           finish[k] = true;      

130:           temp[t++] = k;      

131:           k = 0;      

132:      

133:         }else {      

134:           k++;      

135:         }      

136:       }      

137:       //和while平級      

138:       for(int p=0; p<banker.NUM; p++) {      

139:         if(finish[p]==false) {      

140:           return false;      

141:         }      

142:       }      

143:     }      

144:     return true;      

145:   }      

146:   //釋放線程k所占用資源并恢複      

147:   public void freeKAndRestore(int k) {      

148:     for(int i=0; i<banker.N; i++) {      

149:       banker.avaliable[i] += banker.request[i];      

150:       banker.need[k][i] += banker.request[i];      

151:       banker.allocation[k][i] -= banker.request[i];      

152:     }      

153:   }      

154:   //僅僅釋放線程k所占用資源，僅在某線程全部得到資源運作後才調用      

155:   public void freeKNotRestore(int k) {      

156:     for(int i=0; i<banker.N; i++) {      

157:       banker.avaliable[i] = banker.avaliable[i] + banker.allocation[k][i];      

158:     }      

159:   }      

160:   //三種資源是否全部到位      

161:   public boolean checkRun(int k) {      

162:     int n = 0;      

163:     for(int i=0; i<banker.N; i++) {      

164:       if (banker.need[k][i] == 0)      

165:         n++;      

166:     }      

167:     if (n == 3)      

168:       return true;      

169:     else      

170:       return false;      

171:   }      

172: }      

​