銀行家算法解決死鎖

1、銀行家算法解決死鎖問題1、 設(shè)系統(tǒng)中有3種類型的資源（A，B，C）和5個(gè)進(jìn)程P1、P2、P3、P4、P5，A資源的數(shù)量為17，B資源的數(shù)量為5，C資源的數(shù)量為20。在T0時(shí)刻系統(tǒng)狀態(tài)見下表（T0時(shí)刻系統(tǒng)狀態(tài)表）所示。系統(tǒng)采用銀行家算法實(shí)施死鎖避免策略。（12分）T0時(shí)刻系統(tǒng)狀態(tài)表最大資源需求量已分配資源數(shù)量A B CA B CP15 5 92 1 2P25 3 64 0 2P3 4 0 114 0 5P44 2 52 0 4P54 2 43 1 4T0時(shí)刻系統(tǒng)狀態(tài)表P2請(qǐng)求資源（0，3，4）（0，1，1）(1) T0時(shí)刻是否為安全狀態(tài)？若是，請(qǐng)給出安全序列。(2) 在T0時(shí)刻若進(jìn)程P2請(qǐng)求資源

2、（0，3，4），是否能實(shí)施資源分配？為什么？(3) 在（2）的基礎(chǔ)上，若進(jìn)程P4請(qǐng)求資源（2，0，1），是否能實(shí)施資源分配？為什么？(4) 在（3）的基礎(chǔ)上，若進(jìn)程P1請(qǐng)求資源（0，2，0），是否能實(shí)施資源分配？為什么？答：當(dāng)前的系統(tǒng)狀態(tài)描述為： /資源最大需求數(shù)量 max /已分配資源數(shù)量 alloc /還需資源數(shù)量 Need /資源總量 /系統(tǒng)可用資源向量（1）T0時(shí)刻是否為安全狀態(tài)？若是，請(qǐng)給出安全序列。在T0時(shí)刻，由于V（2，3，3）大于等于（C-A）中P5所在行的向量（1，1，0），因此V能滿足P5的運(yùn)行，在P5運(yùn)行后，系統(tǒng)的狀態(tài)為： 同樣的，在P5運(yùn)行后，V（5，4，7）也大于等于

3、C-A中P4所在的行（2，2，1），則能滿足P4的運(yùn)行。P4運(yùn)行后，系統(tǒng)的狀態(tài)為： 按照上述同樣的方法，P4運(yùn)行后，P3，P2，P1也能按順序運(yùn)行。（備注：考試時(shí)需要都寫出來）。因此，在T0時(shí)刻，存在安全序列：P5、P4、P3、P2、P1。T0時(shí)刻是安全的。-另外一解法（書中解法）-執(zhí)行序列選擇：首先選擇需求資源總數(shù)最少的優(yōu)先。WorkneedAllocWork_allocFinishA B CA B CA B CA B CTP52 3 31 1 03 1 45 4 7TP45 4 72 2 12 0 47 4 11TP37 4 110 0 64 0 511 4 16TP211 4 161 3

4、 44 0 215 4 18TP115 4 183 4 72 1 217 5 20TFinish 都為TRUE得到在T0時(shí)刻，安全序列：P5、P4、P3、P2、P1。-另外一解法（書中解法）-（2）在T0時(shí)刻若進(jìn)程P2請(qǐng)求資源（0，3，4），是否能實(shí)施資源分配？為什么？P2申請(qǐng)資源（0，3，4），但在C-A中，P2所在行向量是（1，3，4）。對(duì)于資源R1，P2的申請(qǐng)超過它所預(yù)定的需求。因此，該申請(qǐng)不給予分配。（3）在（2）的基礎(chǔ)上，若進(jìn)程P4請(qǐng)求資源（2，0，1），是否能實(shí)施資源分配？為什么？A）P4申請(qǐng)（2，0，1）不超過C-A中P4所在行的向量（2，2，1）。B）V（2，3，3）大于等于P

5、4的申請(qǐng)（2，0，1）C）對(duì)P4的申請(qǐng)（2，0，1）進(jìn)行預(yù)分配，預(yù)分配后，系統(tǒng)的狀態(tài)為： 可用資源V（0，3，2）大于等于C-A中P4所在的行（0，2，0），因此可以滿足P4的運(yùn)行。P4運(yùn)行后，系統(tǒng)的狀態(tài)為： 同樣的方法（考試時(shí)需要列出），可計(jì)算出存在安全序列：P4，P5，P3，P2，P1。因此，預(yù)分配后系統(tǒng)的狀態(tài)是安全狀態(tài)。對(duì)于，P4請(qǐng)求資源（2，0，1），給予分配，分配后的系統(tǒng)新狀態(tài)為： -另外一解法（書中解法）-A）P4申請(qǐng)（2，0，1）不超過C-A中P4所在行的向量（2，2，1）。B）V（2，3，3）大于等于P4的申請(qǐng)（2，0，1）C）對(duì)P4的申請(qǐng)（2，0，1）進(jìn)行預(yù)分配，預(yù)分配后，系

6、統(tǒng)的狀態(tài)為：MaxallocNeedavailableA B CA B CA B CA B CP15 5 92 1 23 4 70 3 2(2 3 3)P25 3 64 0 21 3 4P34 0 114 0 50 0 6P44 2 54 0 5(2 0 4)0 2 0(2 2 1)P54 2 43 1 41 1 0注意：（）內(nèi)的值為舊值安全性算法：WorkneedAllocWork_allocFinishA B CA B CA B CA B CP40 3 20 2 04 0 54 3 7TP54 3 71 1 03 1 47 4 11TP37 4 110 0 64 0 511 4 16TP2

7、11 4 161 3 44 0 215 4 18TP115 4 183 4 72 1 217 5 20TFinish 都為TRUE在P4申請(qǐng)資源（2，0，1），給予分配后，可以得到安全序列：P5、P4、P3、P2、P1。P4申請(qǐng)資源（2，0，1）后，系統(tǒng)狀態(tài)為：MaxallocNeedavailableA B CA B CA B CA B CP15 5 92 1 23 4 70 3 2P25 3 64 0 21 3 4P34 0 114 0 50 0 6P44 2 54 0 50 2 0P54 2 43 1 41 1 0-另外一解法（書中解法）-（4）在（3）的基礎(chǔ)上，若進(jìn)程P1請(qǐng)求資源（0，

8、2，0），是否能實(shí)施資源分配？為什么進(jìn)程P1請(qǐng)求資源（0，2，0）A）P1申請(qǐng)（0，2，0）不超過C-A中P1所在行的向量（3，4，7）。B）V（0，3，2）大于等于P1的申請(qǐng)（0，2，0）C）對(duì)P1的申請(qǐng)（0，2，0）進(jìn)行預(yù)分配，預(yù)分配后，系統(tǒng)的狀態(tài)為： V（0，2，1）不大于等于P1到P5任一進(jìn)程在C-A中的向量，因此系統(tǒng)進(jìn)行預(yù)分配后處于不安全狀態(tài)。對(duì)于P1申請(qǐng)資源（，），不給予分配。-另外一解法（書中解法）-進(jìn)程P1請(qǐng)求資源（0，2，0）A）P1申請(qǐng)（0，2，0）不超過C-A中P1所在行的向量（3，4，7）。B）V（0，3，2）大于等于P1的申請(qǐng)（0，2，0）C）對(duì)P1的申請(qǐng)（0，2，0

9、）進(jìn)行預(yù)分配，預(yù)分配后，系統(tǒng)的狀態(tài)為：MaxallocNeedavailableA B CA B CA B CA B CP15 5 92 3 2(2 1 2)3 2 7(3 4 7)0 1 2(0 3 2)P25 3 64 0 21 3 4P34 0 114 0 50 0 6P44 2 54 0 50 2 0P54 2 43 1 41 1 0注意：（）內(nèi)的值為舊值有效資源不能滿足所有進(jìn)程的Need值，因此對(duì)P1的申請(qǐng)進(jìn)行了分配后，系統(tǒng)處于不安全狀態(tài)。-另外一解法（書中解法）-一.概念引入銀行家算法（ banker's algorithm ）由 Dijkstra于1965提出，關(guān)鍵是將死

10、鎖的問題演示為一個(gè)銀行家貸款的模型，由于能用于銀行系統(tǒng)的現(xiàn)金貸款而出名。一個(gè)銀行家向一群客戶發(fā)放信用卡，每個(gè)客戶有不同的信用額度。每個(gè)客戶可以提出信用額度內(nèi)的任意額度的請(qǐng)求，直到額度用完后再一次性還款。銀行家承諾每個(gè)客戶最終都能獲得自己需要的額度。所謂“最終”，是說銀行家可以先掛起某個(gè)額度請(qǐng)求較大的客戶的請(qǐng)求，優(yōu)先滿足小額度的請(qǐng)求，等小額度的請(qǐng)求還款后，再處理掛起的請(qǐng)求。這樣，資金能夠永遠(yuǎn)流通。所以銀行家算法其核心是：保證銀行家系統(tǒng)的資源數(shù)至少不小于一個(gè)客戶的所需要的資源數(shù)。銀行家算法是一種最有代表性的避免死鎖的算法。在避免死鎖方法中允許進(jìn)程動(dòng)態(tài)地申請(qǐng)資源，但銀行家算法在系統(tǒng)在進(jìn)行資源分配之前

11、(并不是真的不分配，這樣就沒法做了，只不過是試探性分配，不滿足的話再恢復(fù))，應(yīng)先計(jì)算此次分配資源的安全性，若分配不會(huì)導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)，則分配，否則等待。為實(shí)現(xiàn)銀行家算法，系統(tǒng)必須設(shè)置若干數(shù)據(jù)結(jié)構(gòu)。要解釋銀行家算法，必須先解釋操作系統(tǒng)安全狀態(tài)和不安全狀態(tài)。安全序列是指存在一個(gè)進(jìn)程序列P1，Pn是安全的，不會(huì)死鎖(至少兩個(gè)線程占有某資源A，但是都不滿足，剩余的資源A分配給誰仍然無法滿足)，安全狀態(tài)如果存在一個(gè)由系統(tǒng)中所有進(jìn)程構(gòu)成的安全序列P1，Pn，則系統(tǒng)處于安全狀態(tài)，安全狀態(tài)一定是沒有死鎖發(fā)生；不安全狀態(tài)不存在一個(gè)安全序列，不安全狀態(tài)不一定導(dǎo)致死鎖。本算法在理論上是出色的，能非常有效地避免

12、死鎖，但從某種意義上說，它缺乏實(shí)用價(jià)值，因?yàn)楹苌儆羞M(jìn)程能夠在運(yùn)行前就知道其所需資源的最大值，且進(jìn)程數(shù)也不是固定的，往往在不斷地變化（如新用戶登錄或退出），況且原來可用的資源也可能突然間變成不可用（如打印機(jī)、磁帶機(jī)可能被損壞）。二.算法原理銀行家算法的基本思想是分配資源之前，判斷系統(tǒng)是否是安全的；若是，才分配。每分配一次資源就測(cè)試一次是否安全，不是資源全部就位后才測(cè)試，注意理解checkError函數(shù)的循環(huán)順序。我們可以把操作系統(tǒng)看作是銀行家，操作系統(tǒng)管理的資源相當(dāng)于銀行家管理的資金，進(jìn)程向操作系統(tǒng)請(qǐng)求分配資源相當(dāng)于用戶向銀行家貸款。 為保證資金的安全，銀行家規(guī)定：當(dāng)一個(gè)顧客對(duì)資金的最大需求量不

13、超過銀行家現(xiàn)有的資金時(shí)就可接納該顧客(試探性分配)顧客可以分期貸款，但貸款的總數(shù)不能超過最大需求量(可能一次并不能滿足所需要的全部資源)當(dāng)銀行家現(xiàn)有的資金不能滿足顧客尚需的貸款數(shù)額時(shí)，對(duì)顧客的貸款可推遲支付，但總能使顧客在有限的時(shí)間里得到貸款(不存在死鎖)當(dāng)顧客得到所需的全部資金后，一定能在有限的時(shí)間里歸還所有的資金(運(yùn)行后釋放)操作系統(tǒng)按照銀行家制定的規(guī)則為進(jìn)程分配資源，當(dāng)進(jìn)程首次申請(qǐng)資源時(shí)，要測(cè)試該進(jìn)程對(duì)資源的最大需求量，如果系統(tǒng)現(xiàn)存的資源可以滿足它的最大需求量則按當(dāng)前的申請(qǐng)量分配資源，否則就推遲分配。當(dāng)進(jìn)程在執(zhí)行中繼續(xù)申請(qǐng)資源時(shí)，先測(cè)試該進(jìn)程本次申請(qǐng)的資源數(shù)是否超過了該資源所剩余的總量。

14、若超過則拒絕分配資源，若能存在安全狀態(tài)，則按當(dāng)前的申請(qǐng)量分配資源，否則也要推遲分配。三.算法的Java實(shí)現(xiàn) 1: import java.util.Arrays; 2: import javax.swing.JOptionPane; 3: 4: public class Banker 5: 6: /* 7: * 資源向量必須全部設(shè)置成static，因?yàn)榭赡?8: * 同一個(gè)線程多次輸入才滿足條件 9: */ 10: /每個(gè)線程需要的資源數(shù) 11: static int max = 7, 5, 3 , 3, 2, 2 , 9, 0, 2 , 12: 2, 2, 2 , 4, 3, 3 ; 13:

15、 /系統(tǒng)可用資源數(shù) 14: static int avaliable = 10,5,7; 15: /已經(jīng)分配資源 16: static int allocation = 0, 0, 0 , 0, 0, 0 , 0, 0, 0 , 17: 0, 0, 0 , 0, 0, 0 ; 18: /每個(gè)進(jìn)程還需要的資源數(shù),初試一個(gè)資源也沒分配；實(shí)際上應(yīng)該等于max-avaliable 19: static int need = Arrays.copyOf(max,max.length); 20: /每次申請(qǐng)的資源數(shù) 21: static int request = 0, 0, 0 ; 22: /NUM個(gè)線

16、程，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: /是否進(jìn)行模擬標(biāo)志，沒有布爾，因?yàn)閺腏Opotionpane輸入 30: int flag = 1; 31: 32: while(1=flag) 33: /* 34: * 用與判斷線程號(hào)是否合法 35: * 需要放在while

17、內(nèi)部，防止下次繼續(xù)模擬時(shí)i還是上次輸入的 36: */ 37: int i = -1; 38: while(i<0|i>=NUM) 39: String str = jpane.showInputDialog("輸入申請(qǐng)資源的線程號(hào)(0到4)："); 40: i = Integer.parseInt(str); 41: if(i<0|i>=NUM) 42: JOptionPane.showMessageDialog(jpane, "輸入的線程號(hào)不合法！"); 43: 44: 45: /資源輸入有效性標(biāo)志 46: boolean t

18、ag = true; 47: for(int j=0; j<N; j+) 48: String str = jpane.showInputDialog("輸入線程"+i+"所申請(qǐng)的資源"+j+"數(shù)目："); 49: requestj = Integer.parseInt(str); 50: /有效性檢查 51: if(requestj>needij) 52: JOptionPane.showMessageDialog(jpane, "輸入的資源數(shù)大于需要資源數(shù)！"); 53: tag = false;

19、54: break; 55: else 56: if(requestj>avaliablej) 57: JOptionPane.showMessageDialog(jpane, "輸入的資源數(shù)大于可用資源數(shù)！"); 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: /上面調(diào)用了

20、allocateK，所以不僅需要釋放，還需要恢復(fù) 70: function.freeKAndRestore(i); 71: else 72: /測(cè)試是否全部資源到位 73: boolean f = function.checkRun(i); 74: if(true=f) 75: JOptionPane.showMessageDialog(jpane 76: ,"進(jìn)程"+i+"全部資源到位！"+"n"+"即將釋放所占用資源"); 77: function.freeKNotRestore(i); 78: 79: 80:

21、 else 81: /實(shí)際上沒必要清空，因?yàn)樵摂?shù)組是輸入的，只為了展示一種良好習(xí)慣 82: Arrays.fill(request,0); 83: 84: String str = JOptionPane.showInputDialog("是否繼續(xù)模擬(1表示是，0退出)？"); 85: flag = Integer.parseInt(str); 86: 87: 88: 89: 90: class Function 91: /* 92: * 實(shí)際上完全是靜態(tài)的，沒必要新new一個(gè)Banker 93: */ 94: Banker banker = new Banker();

22、95: /為線程k分配資源 96: public void allocateK(int k) 97: for(int i=0; i<banker.N; i+) 98: banker.avaliablei -= banker.requesti; 99: banker.needki -= banker.requesti;100: banker.allocationki += banker.requesti;101: 102: 103: public boolean checkError(int i) 104: int work = 0;105: /存儲(chǔ)所有線程是否安全106: boolean

23、 finish = new booleanbanker.NUM;107: Arrays.fill(finish,false);108: /存儲(chǔ)一個(gè)安全序列109: int temp = new intbanker.NUM;110: Arrays.fill(temp,0);111: /temp數(shù)組下標(biāo)112: int t = 0;113: 114: /線程號(hào)參數(shù)是i115: for(int j=0; j<banker.N; j+) 116: work = banker.avaliablej;117: int k = i;118: 119: while(k<banker.NUM) 120: if(finishk=false&&work>=banker.needkj) 121: /*122: * 注意不是max數(shù)組，因?yàn)榇藭r(shí)線程k123: * 所需資源不一定完全就位124: * 加的是allocation，因?yàn)檫M(jìn)行此項(xiàng)檢查前先試探性地125: * 分配給線程k資源了126: */127: /滿足該線程，回收該項(xiàng)資源，看是否滿足其它線程128: work += banker.allocationkj;129: finishk = true;130: tempt+ = k;131: k = 0