用銀行家演算法拒絕死鎖的例題

『壹』 避免死鎖-----銀行家演算法詳解

避免死鎖策略旨在預防系統進入不安全狀態，以防止死鎖的發生，相較於預防死鎖，其對資源分配的限制更寬松，旨在提升系統性能。

銀行家演算法由迪傑斯特拉為T.H.E系統設計，旨在避免在發放現金貸款時系統無法滿足所有客戶需要的情況。

演算法通過四大數據結構實現：可利用資源向量、最大需求矩陣、分配矩陣和需求矩陣。其中，可利用資源向量動態反映系統中每類資源的可用數量；最大需求矩陣定義每個進程對各類資源的最大需求；分配矩陣記錄已分配資源數量；需求矩陣表示進程尚需資源數量。

當新進程請求資源時，系統檢查資源分配後是否會導致不安全狀態。若資源充足且分配後系統仍安全，則進行分配；否則，進程等待。

安全性演算法是銀行家演算法的一部分，用於檢測資源分配後的系統狀態。該演算法創建工作向量和結束標志向量，從進程集合中選擇一個滿足條件的進程，分配所需資源並更新相關數據。若所有進程都可順利運行，則系統安全，否則，系統不安全。

通過一個例子，我們可以了解銀行家演算法的執行過程。在這個例子中，我們檢查了T0時刻的安全性，並模擬了進程P0請求資源的場景，分析了系統在不同狀態下的行為。

總結，銀行家演算法是一種經典的避免死鎖策略，通過限制相對寬松的資源分配，旨在提升系統性能。同時，安全性演算法確保了系統在資源分配後保持安全狀態。選擇何種死鎖處理方法應根據OS設計目的而定，沒有絕對的優劣之分。

『貳』 銀行家演算法的演算法實現

在避免死鎖的方法中，所施加的限制條件較弱，有可能獲得令人滿意的系統性能。在該方法中把系統的狀態分為安全狀態和不安全狀態，只要能使系統始終都處於安全狀態，便可以避免發生死鎖。
銀行家演算法的基本思想是分配資源之前，判斷系統是否是安全的；若是，才分配。它是最具有代表性的避免死鎖的演算法。
設進程cusneed提出請求REQUEST [i]，則銀行家演算法按如下規則進行判斷。
(1)如果REQUEST [cusneed] [i]<= NEED[cusneed][i]，則轉（2)；否則，出錯。
(2)如果REQUEST [cusneed] [i]<= AVAILABLE[i]，則轉（3)；否則，等待。
(3)系統試探分配資源，修改相關數據：
AVAILABLE[i]-=REQUEST[cusneed][i];
ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];
NEED[cusneed][i]-=REQUEST[cusneed][i];
(4)系統執行安全性檢查，如安全，則分配成立；否則試探險性分配作廢，系統恢復原狀，進程等待。 （1)設置兩個工作向量Work=AVAILABLE;FINISH
(2)從進程集合中找到一個滿足下述條件的進程，
FINISH==false;
NEED<=Work;
如找到，執行（3)；否則，執行（4)
(3)設進程獲得資源，可順利執行，直至完成，從而釋放資源。
Work=Work+ALLOCATION;
Finish=true;
GOTO 2
(4)如所有的進程Finish= true，則表示安全；否則系統不安全。
銀行家演算法流程圖
演算法（C語言實現） #include<STRING.H>#include<stdio.h>#include<stdlib.h>#include<CONIO.H>/*用到了getch()*/#defineM5/*進程數*/#defineN3/*資源數*/#defineFALSE0#defineTRUE1/*M個進程對N類資源最大資源需求量*/intMAX[M][N]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};/*系統可用資源數*/intAVAILABLE[N]={10,5,7};/*M個進程已分配到的N類數量*/intALLOCATION[M][N]={{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0}};/*M個進程已經得到N類資源的資源量*/intNEED[M][N]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};/*M個進程還需要N類資源的資源量*/intRequest[N]={0,0,0};voidmain(){inti=0,j=0;charflag;voidshowdata();voidchangdata(int);voidrstordata(int);intchkerr();showdata();enter:{printf(請輸入需申請資源的進程號（從0到);printf(%d,M-1);printf(）:);scanf(%d,&i);}if(i<0||i>=M){printf(輸入的進程號不存在，重新輸入! );gotoenter;}err:{printf(請輸入進程);printf(%d,i);printf(申請的資源數 );printf(類別:ABC );printf();for(j=0;j<N;j++){scanf(%d,&Request[j]);if(Request[j]>NEED[i][j]){printf(%d,i);printf(號進程);printf(申請的資源數>進程);printf(%d,i);printf(還需要);printf(%d,j);printf(類資源的資源量!申請不合理，出錯!請重新選擇! );gotoerr;}else{if(Request[j]>AVAILABLE[j]){printf(進程);printf(%d,i);printf(申請的資源數大於系統可用);printf(%d,j);printf(類資源的資源量!申請不合理，出錯!請重新選擇! );gotoerr;}}}}changdata(i);if(chkerr()){rstordata(i);showdata();}elseshowdata();printf( );printf(按'y'或'Y'鍵繼續,否則退出 );flag=getch();if(flag=='y'||flag=='Y'){gotoenter;}else{exit(0);}}/*顯示數組*/voidshowdata(){inti,j;printf(系統可用資源向量: );printf(***Available*** );printf(資源類別:ABC );printf(資源數目:);for(j=0;j<N;j++){printf(%d,AVAILABLE[j]);}printf( );printf( );printf(各進程還需要的資源量: );printf(******Need****** );printf(資源類別:ABC );for(i=0;i<M;i++){printf();printf(%d,i);printf(號進程:);for(j=0;j<N;j++){printf(%d,NEED[i][j]);}printf( );}printf( );printf(各進程已經得到的資源量: );printf(***Allocation*** );printf(資源類別:ABC );for(i=0;i<M;i++){printf();printf(%d,i);printf(號進程:);/*printf(: );*/for(j=0;j<N;j++){printf(%d,ALLOCATION[i][j]);}printf( );}printf( );}/*系統對進程請求響應，資源向量改變*/voidchangdata(intk){intj;for(j=0;j<N;j++){AVAILABLE[j]=AVAILABLE[j]-Request[j];ALLOCATION[k][j]=ALLOCATION[k][j]+Request[j];NEED[k][j]=NEED[k][j]-Request[j];}}/*資源向量改變*/voidrstordata(intk){intj;for(j=0;j<N;j++){AVAILABLE[j]=AVAILABLE[j]+Request[j];ALLOCATION[k][j]=ALLOCATION[k][j]-Request[j];NEED[k][j]=NEED[k][j]+Request[j];}}/*安全性檢查函數*/intchkerr()//在假定分配資源的情況下檢查系統的安全性{intWORK[N],FINISH[M],temp[M];//temp[]用來記錄進程安全執行的順序inti,j,m,k=0,count;for(i=0;i<M;i++)FINISH[i]=FALSE;for(j=0;j<N;j++)WORK[j]=AVAILABLE[j];//把可利用資源數賦給WORK[]for(i=0;i<M;i++){count=0;for(j=0;j<N;j++)if(FINISH[i]==FALSE&&NEED[i][j]<=WORK[j])count++;if(count==N)//當進程各類資源都滿足NEED<=WORK時{for(m=0;m<N;m++)WORK[m]=WORK[m]+ALLOCATION[i][m];FINISH[i]=TRUE;temp[k]=i;//記錄下滿足條件的進程k++;i=-1;}}for(i=0;i<M;i++)if(FINISH[i]==FALSE){printf(系統不安全!!!本次資源申請不成功!!! );return1;}printf( );printf(經安全性檢查，系統安全，本次分配成功。 );printf( );printf(本次安全序列：);for(i=0;i<M;i++)//列印安全系統的進程調用順序{printf(進程);printf(%d,temp[i]);if(i<M-1)printf(->);}printf( );return0;}

『叄』 銀行家演算法

銀行家演算法是一種預防死鎖的演算法。具體演算法步驟可以參考網路： 銀行家演算法

例子 ：某系統有A、B、C、D , 4類資源共5個進程（P0、P1、P2、P3、P4）共享，各進程對資源的需求和分配情況如下表所示。

輸入進程的數目:5
輸入資源的種類:4
輸入每個進程最多所需的各類資源數:
P0 : 0 0 1 2
P1 : 1 7 5 0
P2 : 2 3 5 6
P3 : 0 6 5 2
P4 : 0 6 5 6
輸入每個進程已經分配的各類資源數:
P0 : 0 0 1 2
P1 : 1 0 0 0
P2 : 1 3 5 4
P3 : 0 6 3 2
P4 : 0 0 1 4
請輸入各個資源現有的數目:
1 5 2 0
當前系統安全!
系統安全序列是:
P0->P2->P1->P3->P4
輸入要申請資源的進程號(0-4)：1
輸入進程所請求的各資源的數量:0 4 2 0
系統安全!
系統安全序列是:
P0->P2->P1->P3->P4
同意分配請求!

系統可用的資源數為 : 1 1 0 0
各進程還需要的資源量:
進程 P0 : 0 0 0 0
進程 P1 : 0 3 3 0
進程 P2 : 1 0 0 2
進程 P3 : 0 0 2 0
進程 P4 : 0 6 4 2

各進程已經得到的資源量:
進程 P0 : 0 0 1 2
進程 P1 : 1 4 2 0
進程 P2 : 1 3 5 4
進程 P3 : 0 6 3 2
進程 P4 : 0 0 1 4

是否再次請求分配？是請按Y/y，否請按N/n:
N

『肆』 操作系統(死鎖避免)----銀行家演算法解題

死鎖：是指兩個以上的進程都因要求對方已經佔有的資源，導致無法運行下去的現象，死鎖是系統的一種出錯狀態，不僅浪費大量的系統資源，甚至會導纖賀余致整個系統的崩潰，所以死鎖是盡量預防和避免的。

產生死鎖的四個條件：

死鎖的處理

銀行家演算法是死鎖避免的重要演算法。

銀行家算毀滾法：資源==錢；收回資源==收回貸款；收不回資源==不會放貸；

例題：假設系統中有三類互斥資源R1，R2，R3。可用資源分別是9,8,5.在T0時刻系統有P1，P2，P3，P4，P5五個進程，這些進程最大的需求和已分配的資源如下所示，如果按_執行，那麼系統的狀態是安全的。

解：第一步：根據可用資源，可以求得剩餘資源。

R1=9-(1+2+2+1+1)=2

R2=8-(2+1+1+2+1)=1

R3=5-(1+1+0+0+3)=0

第二拍納步：根據剩餘資源求得還需要的資源數。

公式：還需資源（Need）=最大需求（Max）-已分配資源（Allocation）。

第三部，根據剩餘資源數，求出安全序列。

根據剩餘資源可得，p2可以執行（條件：每個值都必須≦剩餘資源）

由此可見安全序列為P2-->p4-->p5-->p1-->p3。

其實安全序列不是唯一的，這是為什麼呢？

大家可以看出來，現有資源要大於需要資源的情況下是有多種選擇的，因此安全序列不唯一。

『伍』 怎樣用C語言描述操作系統里的死鎖演算法謝謝。

利用銀行家演算法避免死鎖 . 銀行家演算法 設Requesti是進程Pi的請求向量，如果Requesti〔j〕=K，表示進程Pi需要K個Rj類型的資源。當Pi發出資源請求後，系統按下述步驟進行檢查：� (1) 如果Requesti〔j〕≤Need〔i,j〕，便轉向步驟2；否則認為出錯，因為它所需要的資源數已超過它所宣布的最大值。 (2) 如果Requesti〔j〕≤Available〔j〕，便轉向步驟(3)；否則， 表示尚無足夠資源，Pi須等待。 (3) 系統試探虛清著把資源分配給進程Pi，並修改下面數據結構中的數值：� Available〔j〕∶=Available〔j〕-Requesti〔j〕;� Allocation〔i,j〕∶=Allocation〔i,j〕+Requesti〔j〕;� Need〔i,j〕∶=Need〔i,j〕-Requesti〔j〕;� (4) 系統執行安全性演算法，檢查此次資源分配後，系統是否處於安全狀態。若安全，才正式將資源分配給進程Pi，以完成本次分配；否則， 將本次的試探分配作廢，恢復原來的資源分配狀態，讓進程Pi等待。 (3) 系統試探著把資源分配給進程Pi，並修改下面數據結構中的數值：� Available〔j〕∶=Available〔j〕-Requesti〔j〕;� Allocation〔i,j〕∶=Allocation〔i,j〕+Requesti〔j〕;� Need〔i,j〕∶=Need〔i,j〕-Requesti〔j〕;� (4) 系統執行安全性演算法，檢冊散查此次資源分配後，系統是否處於安全狀態。若安全，才正式將資源分配給進程Pi，以完成本次分配；否則， 將本次的試探分配作廢，恢復原來的資源分配狀態，讓進程Pi等待。 (3) 系統試探著把資源分配給進程Pi，並修改下面數據結構中的數值：� Available〔j〕∶=Available〔j〕-Requesti〔j〕;� Allocation〔i,j〕∶=Allocation〔i,j〕+Requesti〔j〕;� Need〔i,j〕∶=Need〔差姿前i,j〕-Requesti〔j〕;� (4) 系統執行安全性演算法，檢查此次資源分配後，系統是否處於安全狀態。若安全，才正式將資源分配給進程Pi，以完成本次分配；否則， 將本次的試探分配作廢，恢復原來的資源分配狀態，讓進程Pi等待。

『陸』 什麼是死鎖，怎樣引入死鎖

1.死鎖：如果一組進程中的每一個進程都在等待僅由該組進程中的其它進程才能引發的事件，那麼該組進程是死鎖的。
2.產生死鎖的原因：
（1）競爭不可搶占性資源。
（2）競爭可消耗資源。
當系統中供多個進程共享的資源如列印機，公用隊列等，其數目不足以滿足諸進程的需要時，會引起諸進程對資源的競爭而產生死鎖。12

（3）進程推進順序不當。
進程在運行過程中，請求和釋放資源的順序不當，也同樣會導致產生進程死鎖。12

如果系統資源充足，進程的資源請求都能夠得到滿足，死鎖出現的可能性就很低，否則就會因爭奪有限的資源而陷入死鎖。其次，進程運行推進順序與速度不同，也可能產生死鎖。
一個線程也可引起死鎖。12

3.產生死鎖的四個必要條件：
（1） 互斥條件：一個資源每次只能被一個進程使用。
（2） 請求和保持條件：一個進程因請求資源而阻塞時，對已獲得的資源保持不放。
（3） 不可搶占條件:進程已獲得的資源，在末使用完之前，不能強行剝奪，只能在進程使用完時由自己釋放。
（4） 循環等待條件:若干進程之間形成一種頭尾相接的循環等待資源關系。
這四個條件是死鎖的必要條件，只要系統發生死鎖，這些條件必然成立，而只要上述條件之一不滿足，就不會發生死鎖。因此可以寫下如下的預防死鎖的方法。
4.避免死鎖的方法：
（1）破壞「互斥」條件:就是在系統里取消互斥。若資源不被一個進程獨占使用，那麼死鎖是肯定不會發生的。但一般「互斥」條件是無法破壞的。因此，在死鎖預防里主要是破壞其他三個必要條件，而不去涉及破壞「互斥」條件。
（2）破壞「請求和保持」條件:在系統中不允許進程在已獲得某種資源的情況下，申請其他資源。即要想出一個辦法，阻止進程在持有資源的同時申請其他資源。
方法一：所有進程在運行之前，必須一次性地申請在整個運行過程中所需的全部資源。這樣，該進程在整個運行期間，便不會再提出資源請求，從而破壞了「請求」條件。系統在分配資源時，只要有一種資源不能滿足進程的要求，即使其它所需的各資源都空閑也不分配給該進程，而讓該進程等待。由於該進程在等待期間未佔有任何資源，於是破壞了「保持」條件。
該方法優點：簡單、易行且安全。
缺點：a.資源被嚴重浪費，嚴重惡化了資源的利用率。
b.使進程經常會發生飢餓現象。12

方法二：要求每個進程提出新的資源申請前，釋放它所佔有的資源。這樣，一個進程在需要資源S時，須先把它先前佔有的資源R釋放掉，然後才能提出對S的申請，即使它可能很快又要用到資源R。
（3）破壞「不可搶占」條件：允許對資源實行搶奪。
方法一：如果佔有某些資源的一個進程進行進一步資源請求被拒絕，則該進程必須釋放它最初佔有的資源，如果有必要，可再次請求這些資源和另外的資源。
方法二：如果一個進程請求當前被另一個進程佔有的一個資源，則操作系統可以搶占另一個進程，要求它釋放資源。只有在任意兩個進程的優先順序都不相同的條件下，該方法才能預防死鎖。
（4）破壞「循環等待」條件：將系統中的所有資源統一編號，進程可在任何時刻提出資源申請，但所有申請必須按照資源的編號順序（升序）提出。這樣做就能保證系統不出現死鎖。
利用銀行家演算法避免死鎖：
銀行家演算法:
設進程i提出請求Request[j]，則銀行家演算法按如下規則進行判斷。
(1) 如果Request[j]≤Need[i,j]，則轉向（2），否則認為出錯，因為它所需要的資源數已超過它所宣布的最大值。
(2) 如果Request[j]≤Available[j]，則轉向（3）；否則表示尚無足夠資源，Pi需等待。
(3) 假設進程i的申請已獲批准，於是修改系統狀態：
Available[j]=Available[j]-Request[i]
Allocation[i,j]=Allocation[i,j]+Request[j]
Need[i,j]=Need[i,j]-Request[j]
(4)系統執行安全性檢查，如安全，則分配成立；否則試探險性分配作廢，系統恢復原狀，進程等待。
安全性演算法：
(1) 設置兩個工作向量Work=Available；Finish[i]=False
(2) 從進程集合中找到一個滿足下述條件的進程，
Finish [i]=False;

Need[i,j]≤Work[j];

如找到，執行(3)；否則，執行(4)123456

(3) 設進程獲得資源，可順利執行，直至完成，從而釋放資源。
Work[j]=Work[j]+Allocation[i,j];

Finish[i]=True;

Go to step 2;123456

(4) 如所有的進程Finish[i]=true，則表示安全；否則系統不安全。
5.死鎖的解除：
一旦檢測出死鎖，就應立即釆取相應的措施，以解除死鎖。死鎖解除的主要兩種方法：
1) 搶占資源。從一個或多個進程中搶占足夠數量的資源，分配給死鎖進程，以解除死鎖狀態。
2) 終止（或撤銷）進程。終止（或撤銷）系統中的一個或多個死鎖進程，直至打破循環環路，使系統從死鎖狀態解脫出來。
總結：
一般情況下,如果同一個線程先後兩次調用lock,在第二次調用時,由於鎖已經被佔用,該線程會掛起等待別的線程釋放鎖,然而鎖正是被自己佔用著的,該線程又被掛起而沒有機會釋放鎖,因此就永遠處於掛起等待狀態了,這叫做死鎖(Deadlock)。另⼀一種典型的死鎖情形是這樣:線程A獲得了鎖1,線程B獲得了鎖2,這時線程A調⽤用lock試圖獲得鎖2,結果是需要掛起等待線程B釋放鎖2,而這時線程B也調⽤用lock試圖獲得鎖1,結果是需要掛起等待線程A釋放鎖1,於是線程A和B都永遠處於掛起狀態了。12

注意：
寫程序時應該盡量避免同時獲得多個鎖,如果一定有必要這么做,則有一個原則:如果所有線程在需要多個鎖時都按相同的先後順序(常見的是按Mutex變數的地址順序)獲得鎖,則不會出現死鎖。比如一個程序中用到鎖1、鎖2、鎖3,它們所對應的Mutex變數的地址是鎖1<鎖2<鎖3,那麼所有線程在需要同時獲得2個或3個鎖時都應該按鎖1、鎖2、鎖3的順序獲得。如果要為所有的鎖確定一個先後順序比較困難,則應pthread_mutex_trylock調用代替pthread_mutex_lock 調用,以免死鎖。