銀行家算法避免死鎖的研究與實現(xiàn)

1、銀行家算法避免死鎖的研究與實現(xiàn)學(xué)號：姓名：專業(yè)：1 死鎖11.1 什么是死鎖11.2 產(chǎn)生死鎖的原因11.2.1 競爭系統(tǒng)資源11.2.2 進(jìn)程的推進(jìn)不當(dāng)21.3 產(chǎn)生死鎖的必要條件21.4 解決死鎖的基本方法21.4.1 預(yù)防死鎖21.4.2 避免死鎖31.4.3 死鎖檢測31.4.4 死鎖的恢復(fù)42 銀行家算法42.1 關(guān)于銀行家算法43 程序?qū)崿F(xiàn)73.1 程序說明73.2 程序源代碼73.3 程序測試1.1(R2),兩進(jìn)程共享這兩臺設(shè)備。1；1；1死鎖1.1 什么是死鎖在多道程序設(shè)計環(huán)境下，多個進(jìn)程可能競爭一定數(shù)量的資源。一個進(jìn)程申請資源，如果資源不可用，那么進(jìn)入等待狀態(tài)。如果所申請的資

2、源被其他等待進(jìn)程占有，那么該等待進(jìn)程有可能無法改變狀態(tài)，這種情況稱為死鎖(deadlock)。設(shè)系統(tǒng)有一臺打印機(R1),一臺讀卡機用信號量S1表示R1是否可用，初值為用信號量S2表示R2是否可用，初值為第 8頁這兩個進(jìn)程在并發(fā)執(zhí)行過程中，可能會發(fā)生如下的情況。即P1占用R1,P2占用R2,同時P1和P2又分別申請R2和R1的資源。于是造成了死鎖。1.2 產(chǎn)生死鎖的原因1.2.1 競爭系統(tǒng)資源如循環(huán)圖所示：系統(tǒng)中只有一臺打印機R1和一臺讀卡機R2,可供進(jìn)程P1和P2共享。R1、R2已經(jīng)分別分配給P1、P2使用，當(dāng)P1、P2在不釋放資源R1、R2而又同時分別申請R2、R1(如圖)，形成環(huán)路，這樣

3、會產(chǎn)生死鎖。1.2.2 進(jìn)程的推進(jìn)不當(dāng)如前面的例子可知他只是可能發(fā)生死鎖，也就是說進(jìn)程的推進(jìn)不同會導(dǎo)致不同的結(jié)果。1.3 產(chǎn)生死鎖的必要條件互斥條件進(jìn)程要求對所分配的資源進(jìn)行排它性控制，即在一段時間內(nèi)某資源僅升-進(jìn)程所占用。1占有并等待條件當(dāng)進(jìn)程因請求資源而阻塞時，對已獲得的資源保持不放。非搶占條件進(jìn)程已獲得的資源在未使用完之前，不能剝奪，只能在使用完時由自己釋放。循環(huán)等待條件在發(fā)生死鎖時，必然存在一個進(jìn)程-資源的環(huán)形鏈。1.4 解決死鎖的基本方法1.4.1 預(yù)防死鎖前面我們降到了死鎖的必要條件，那么只要一個條件不滿足的話，就不會發(fā)生死鎖了。所以我們可以從必要條件的角度來預(yù)防死鎖。a.互斥條件

4、對于非共享資源，必須有互斥條件。而共享資源是不會涉及死鎖。所以通常不能通過否定互斥條件來預(yù)防死鎖：有些資源本身是非共享的。b.占有并等待為了確保該條件不在系統(tǒng)內(nèi)出現(xiàn)，必須保證：當(dāng)一個進(jìn)程申請一個資源時，它不能占有其他資源。資源一次性分配可以解決這個問題。實現(xiàn)這一分配有兩種協(xié)議1 .每個進(jìn)程在執(zhí)行前申請并獲得所有資源。2 .允許進(jìn)程在沒有資源時才可申請資源。兩種協(xié)議的缺點：1 .資源利用率不高2 .可能發(fā)生饑餓（磁帶用到一半被搶了）C.非搶占允許當(dāng)前進(jìn)程被其他進(jìn)程搶過去。缺點：可能發(fā)生饑餓（磁帶用到一般被搶了）d.循環(huán)等待條件確保此條件不成立的方法就是對所有資源類型進(jìn)行完全排序，且要求每個進(jìn)程按

5、遞增順序來申請資源。實現(xiàn)方法：資源有序分配法遵循兩種協(xié)議：A.每個進(jìn)程只按遞增順序申請資源。（第一次可以申請多個，但之后申請編號必須比前面大）編號B.進(jìn)程申請編號比擁有資源編號小時必須先釋放大編號資源。資源名稱磁帶機打印機繪圖儀讀卡機卡片穿孔機這樣進(jìn)程如果需要磁帶機和繪圖機，那進(jìn)程必須先申請磁帶機，再申請繪圖機。如果再想申請打印機，則必須先釋放繪圖機。1.4.2避免死鎖通過前面介紹想必大家也看到了在預(yù)防死鎖的過程中會嚴(yán)重系統(tǒng)性能。因此在避免死鎖中我們不得不施加較弱的限制，從而獲得比較滿意的性能。由于在避免死鎖的策略中，允許進(jìn)程動態(tài)地申請資源。因而，系統(tǒng)在進(jìn)行資源分配之前預(yù)先計算資源分配的安全性

6、。若此次分配不會導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)，則將資源分配給進(jìn)程；否則，進(jìn)程等待。最具代表性的避免死鎖的算法是銀行家算法。一般來說，由于操作系統(tǒng)有并發(fā)，共享以及隨機性等特點，通過預(yù)防和避免的手段達(dá)到排除死鎖的目的是很困難的。這需要較大的系統(tǒng)開銷，而且不能充分利用資源。為此，一種簡便的方法是系統(tǒng)為進(jìn)程分配資源時，不采取任何限制性措施，但是提供了檢測和解脫死鎖的手段：能發(fā)現(xiàn)死鎖并從死鎖狀態(tài)中恢復(fù)出來。因此，在實際的操作系統(tǒng)中往往采用死鎖的檢測與恢復(fù)方法來排除死鎖。死鎖檢測與恢復(fù)是指系統(tǒng)設(shè)有專門的機構(gòu)，當(dāng)死鎖發(fā)生時，該機構(gòu)能夠檢測到死鎖發(fā)生的位置和原因，并能通過外力破壞死鎖發(fā)生的必要條件，從而使得并發(fā)進(jìn)程

7、從死鎖狀態(tài)中恢復(fù)出來。1 .一個用來檢查系統(tǒng)狀態(tài)從而確定是否出現(xiàn)了死鎖算法。即死鎖檢測2 .一個用來從死鎖狀態(tài)中恢復(fù)的算法。即恢復(fù)算法1.4.3死鎖檢測首先可以通過畫分配圖來判斷是否發(fā)生了死鎖。但如何用算法來判斷呢？死鎖檢測算法。算法使用的數(shù)據(jù)結(jié)構(gòu)是如下這些：占有矩陣A:n*m階，其中n表示并發(fā)進(jìn)程的個數(shù)，m表示系統(tǒng)的各類資源的個數(shù)，這個矩陣記錄了每一個進(jìn)程當(dāng)前占有各個資源類中資源的個數(shù)。申請矩陣R:n*m階，其中n表示并發(fā)進(jìn)程的個數(shù)，m表示系統(tǒng)的各類資源的個數(shù)，這個矩陣記錄了每一個進(jìn)程當(dāng)前要完成工作需要申請的各個資源類中資源的個數(shù)?？臻e向量T:記錄當(dāng)前m個資源類中空閑資源的個數(shù)。完成向量F:

8、布爾型向量值為真(true)或假(false)，記錄當(dāng)前n個并發(fā)進(jìn)程能否進(jìn)行完。為真即能進(jìn)行完，為假則不能進(jìn)行完。臨時向量W開始時W=T。算法步驟：(1)W=T,對于所有的i=1,2,.,n,如果Ai=0,貝UFi:=true;否貝U,Fi:=false(2)找滿足下面條件的下標(biāo)i:Fi:=false并且Ri=W如果不存在滿足上面的條件i,則轉(zhuǎn)到步驟(4)。(3)W=W+AiFi:=true轉(zhuǎn)到步驟(2)(4)如果存在i,Fi:=false,則系統(tǒng)處于死鎖狀態(tài)，且Pi進(jìn)程參與了死鎖。什麼時候進(jìn)行死鎖的檢測取決于死鎖發(fā)生的頻率。如果死鎖發(fā)生的頻率高，那麼死鎖檢測的頻率也要相應(yīng)提高，這樣一方面可以

9、提高系統(tǒng)資源的利用率，一方面可以避免更多的進(jìn)程卷入死鎖。如果進(jìn)程申請資源不能滿足就立刻進(jìn)行檢測，那麼每當(dāng)死鎖形成時即能被發(fā)現(xiàn)，這和死鎖避免的算法相近，只是系統(tǒng)的開銷較大。為了減小死鎖檢測帶來的系統(tǒng)開銷，一般采取每隔一段時間進(jìn)行一次死鎖檢測，或者在CPU的利用率降低到某一數(shù)值時，進(jìn)行死鎖的檢測。1.4.4死鎖的恢復(fù)一旦在死鎖檢測時發(fā)現(xiàn)了死鎖，就要消除死鎖，使系統(tǒng)從死鎖狀態(tài)中恢復(fù)過來。(1)最簡單，最常用的方法就是進(jìn)行系統(tǒng)的重新啟動，不過這種方法代價很大，它意味著在這之前所有的進(jìn)程已經(jīng)完成的計算工作都將付之東流，包括參與死鎖的那些進(jìn)程，以及未參與死鎖的進(jìn)程。(2)撤消進(jìn)程，剝奪資源。終止參與死鎖的

10、進(jìn)程，收回它們占有的資源，從而解除死鎖。這時又分兩種情況：一次性撤消參與死鎖的全部進(jìn)程，剝奪全部資源；或者逐步撤消參與死鎖的進(jìn)程，逐步收回死鎖進(jìn)程占有的資源。一般來說，選擇逐步撤消的進(jìn)程時要按照一定的原則進(jìn)行，目的是撤消那些代價最小的進(jìn)程，比如按進(jìn)程的優(yōu)先級確定進(jìn)程的代價；考慮進(jìn)程運行時的代價和與此進(jìn)程相關(guān)的外部作業(yè)的代價等因素。此外，還有進(jìn)程回退策略，即讓參與死鎖的進(jìn)程回退到?jīng)]有發(fā)生死鎖前某一點處，并由此點處繼續(xù)執(zhí)行，以求再次執(zhí)行時不再發(fā)生死鎖。雖然這是個較理想的辦法，但是操作起來系統(tǒng)開銷極大，要有堆棧這樣的機構(gòu)記錄進(jìn)程的每一步變化，以便今后的回退，有時這是無法做到的。2銀行家算法2.1 關(guān)

11、于銀行家算法銀行家算法(Banker'sAlgorithm)是一個避免死鎖(Deadlock)的著名算法，是由艾茲格迪杰在1965年為T.H.E系統(tǒng)設(shè)計的一種避免死鎖產(chǎn)生的算法。它以銀行借貸系統(tǒng)的斯特拉分配策略為基礎(chǔ)，判斷并保證系統(tǒng)的安全運行。2.2 安全序列講銀行家算法之前，我們首先引入安全序列的定義：所謂系統(tǒng)是安全的，是指系統(tǒng)中的所有進(jìn)程能夠按照某一種次序分配資源，并且依次地運行完畢，這種進(jìn)程序列P1,P2,.,Pn就是安全序列。如果存在這樣一個安全序列，則系統(tǒng)是安全的；如果系統(tǒng)不存在這樣一個安全序列，則系統(tǒng)是不安全的。安全序列P1,P2,.,Pn是這樣組成的：若對于每一個進(jìn)程Pi

12、,它需要的附加資源可以被系統(tǒng)中當(dāng)前可用資源加上所有進(jìn)程Pj當(dāng)前占有資源之和所滿足，則P1,P2,.,Pn為一個安全序列，這時系統(tǒng)處于安全狀態(tài)，不會進(jìn)入死鎖狀態(tài)。雖然存在安全序列時一定不會有死鎖發(fā)生，但是系統(tǒng)進(jìn)入不安全狀態(tài)(四個死鎖的必要條件同時發(fā)生)也未必會產(chǎn)生死鎖。當(dāng)然，產(chǎn)生死鎖后，系統(tǒng)一定處于不安全狀態(tài)。2.3 算法原理我們可以把操作系統(tǒng)看作是銀行家，操作系統(tǒng)管理的資源相當(dāng)于銀行家管理的資金，進(jìn)程向操作系統(tǒng)請求分配資源相當(dāng)于用戶向銀行家貸款。為保證資金的安全，銀行家規(guī)定：(1)當(dāng)一個顧客對資金的最大需求量不超過銀行家現(xiàn)有的資金時就可接納該顧客；(2)顧客可以分期貸款，但貸款的總數(shù)不能超過最

13、大需求量；(3)當(dāng)銀行家現(xiàn)有的資金不能滿足顧客尚需的貸款數(shù)額時，對顧客的貸款可推遲支付，但總能使顧客在有限的時間里得到貸款；(4)當(dāng)顧客得到所需的全部資金后，一定能在有限的時間里歸還所有的資金操作系統(tǒng)按照銀行家制定的規(guī)則為進(jìn)程分配資源，當(dāng)進(jìn)程首次申請資源時，要測試該進(jìn)程對資源的最大需求量，如果系統(tǒng)現(xiàn)存的資源可以滿足它的最大需求量則按當(dāng)前的申請量分配資源，否則就推遲分配。當(dāng)進(jìn)程在執(zhí)行中繼續(xù)申請資源時，先測試該進(jìn)程本次申請的資源數(shù)是否超過了該資源所剩余的總量。若超過則拒絕分配資源，若能滿足則按當(dāng)前的申請量分配資源，否則也要推遲分配。2.4 銀行家算法設(shè)進(jìn)程i提出t#求Requests,則銀行家算法

14、按如下規(guī)則進(jìn)行判斷。(1)如果Requests<Needi,j,則轉(zhuǎn)向(2),否則認(rèn)為出錯。(2)如果Requests<Availablej,則轉(zhuǎn)向(3);否則表示尚無足夠資源，Pi需等待。(3)假設(shè)進(jìn)程i的申請已獲批準(zhǔn)，于是修改系統(tǒng)狀態(tài)：Availablej=Availablej-RequestiAllocationi,j=Allocationi,j+RequestjNeedi,j=Needi,j-Requestj(4)系統(tǒng)執(zhí)行安全性檢查，如安全，則分配成立；否則試探險性分配作廢，系統(tǒng)恢復(fù)原狀，進(jìn)程等待。算法流程圖2.5 安全性檢查算法(1)設(shè)置兩個工作向量Work=AVAILA

15、BLE;FINISH(2)從進(jìn)程集合中找到一個滿足下述條件的進(jìn)程，F(xiàn)INISH=false;NEED<=Work;如找到，執(zhí)行(3);否則，執(zhí)行(4)(3)設(shè)進(jìn)程獲得資源，可順利執(zhí)行，直至完成，從而釋放資源。Work=Work+ALLOCATION;Finish=true;GOTO2(4)如所有的進(jìn)程Finish=true,則表示安全；否則系統(tǒng)不安全。3程序?qū)崿F(xiàn)3.1 程序說明操作系統(tǒng)：windows764位開發(fā)工具：MyEcplise|開發(fā)語百：java|Jdk版本：1.7相關(guān)字段和方法：IntMAX進(jìn)程所需最大資源數(shù)IntAVAILABLE口系統(tǒng)初始資源IntNEED每進(jìn)程需的資源I

16、ntM進(jìn)程數(shù)IntN資源數(shù)showdate():顯示進(jìn)程及資源分配情況方法chkerr(ints):安全查檢方法3.2 程序源代碼packagetest;importjavax.swing.JOptionPane;publicclassTest2/每個進(jìn)程所需要的最大資源數(shù)publicstaticintMAX叩=6,5,3,3,2,1,9,0,2,2,2,2,4,3,3;/系統(tǒng)擁有的初始資源數(shù)publicstaticintAVAILABLE口=9,6,8;/系統(tǒng)已給每個進(jìn)程分配的資源數(shù)publicstaticintALLOCATION口口=0,0,0,0,0,0,0,0,0,0,0,0,0,0

17、,0;/每個進(jìn)程還需要的資源數(shù)publicstaticintNEED川=6,5,3,3,2,1,9,0,2,2,2,2,4,3,3;/每次申請的資源數(shù)publicstaticintRequest=0,0,0;/進(jìn)程數(shù)與資源數(shù)publicstaticintM=5,N=3;intFALSE=0;intTRUE=1;publicstaticvoidmain(Stringargs)inti=0,j=0;intflag=1;Test2bank=newTest2();bank.showdata();while(flag=1)i=-1;while(i<0|i>=M)Stringstr=JOpti

18、onPane.showInputDialog("請輸入需申請資源的進(jìn)程號(從0到"+(M-1)+"，否則重輸入!)");i=Integer.parseInt(str);if(i<0|i>=M)System.out.println("輸入的進(jìn)程號不存在，重新輸入!n");System.out.print("請輸入進(jìn)程"+i+"申請的資源數(shù)n");for(j=0;j<N;j+)Stringstr=JOptionPane.showInputDialog("資源"+

19、j+":");Requestj=Integer.parseInt(str);if(Requestj>NEEDij)System.out.print("進(jìn)程"+i+"申請的資源數(shù)大于進(jìn)程"+i+"還需要"+j+"類資源的資源量!申請不合理，出錯!請重新選擇!n");flag=0;break;elseif(Requestj>AVAILABLEj)System.out.print("進(jìn)程"+i+"申請的資源數(shù)大于系統(tǒng)可用"+j+"類資源的資

20、源量!申請不合理，出錯!請重新選擇!n");flag=0;break;if(flag=1)bank.changdata(i);intchkerr=bank.chkerr(i);if(chkerr=1)bank.rstordata(i);bank.showdata();elsebank.showdata();intcheck=bank.check0(i);if(check=1)System.out.print("進(jìn)程"+i+"已經(jīng)完成，系統(tǒng)將其所占用資源釋放n");bank.free(i);elsebank.showdata();System.o

21、ut.println("n");Stringstr=JOptionPane.showInputDialog("是否繼續(xù)銀行家算法演示,按'1'鍵繼續(xù),按'0'鍵退出演示");flag=Integer.parseInt(str);publicvoidshowdata()inti,j;for (j = 0; j < N; j+) System.out.print("System.out.println();System.out.println("nfor (i = 0; i < M; i+) S

22、ystem.out.print("for (j = 0; j < N; j+) System.out.print("系統(tǒng)可用的資源數(shù)為:n");資源"+j+":"+AVAILABLEj+"");各進(jìn)程還需要的資源量:");進(jìn)程"+i+":");System.out.print("資源"+j+":"+NEEDij+"");System.out.print("n");System.out.pri

23、nt("n各進(jìn)程已經(jīng)得到的資源量:n");for(i=0;i<M;i+)System.out.print("進(jìn)程");System.out.print(i);for(j=0;j<N;j+)System.out.print("資源"+j+":"+ALLOCATIONij+"");System.out.print("n");/分配資源，并重新更新各種狀態(tài)第 9頁publicvoidchangdata(intk)intj;for(j=0;j<N;j+)AVAILA

24、BLEj=AVAILABLEj-Requestj;ALLOCATIONkj=ALLOCATIONkj+Requestj;NEEDkj=NEEDkj-Requestj;/回收資源，并重新更新各種狀態(tài)publicvoidrstordata(intk)intj;for(j=0;j<N;j+)AVAILABLEj=AVAILABLEj+Requestj;ALLOCATIONkj=ALLOCATIONkj-Requestj;NEEDkj=NEEDkj+Requestj;/釋放資源publicvoidfree(intk)for(intj=0;j<N;j+)AVAILABLEj=AVAILABL

25、Ej+ALLOCATIONkj;System.out.print("釋放"+k+"號進(jìn)程的"+j+"資源!n");publicintcheck0(intk)intj,n=0;for(j=0;j<N;j+)if(NEEDkj=0)n+;if(n=3)return1;elsereturn0;/檢查安全性函數(shù)publicintchkerr(ints)intWORK;intFINISH=newintM,temp=newintM;/保存臨時的安全進(jìn)程序列inti,j,k=0;for(i=0;i<M;i+)FINISHi=FALSE;

26、for(j=0;j<N;j+)WORK=AVAILABLEj;/第j個資源可用數(shù)i=s;/判斷第i個進(jìn)程是否滿足條件while(i<M)if(FINISHi=FALSE&&NEEDij<=WORK)WORK=WORK+ALLOCATIONij;FINISHi=TRUE;tempk=i;k+;i=0;elsei+;for(i=0;i<M;i+)!n");if(FINISHi=FALSE)System.out.print("n系統(tǒng)不安全!本次資源申請不成功return1;System.out.print("n經(jīng)安全性檢查，系統(tǒng)安全，本次分配成功。n");System.out.print("本次安全序列：");for(i=0;i<M-1;i+)System.out.print("進(jìn)程"+tempi+"->");System.out.print("