避免死鎖的一個著名演算法

Ⅰ 死鎖的預防

理解了死鎖的原因，尤其是產生死鎖的四個必要條件，就可以最大可能地避免、預防和解除死鎖。只要打破四個必要條件之一就能有效預防死鎖的發生：打破互斥條件：改造獨占性資源為虛擬資源，大部分資源已無法改造。打破不可搶占條件：當一進程佔有一獨占性資源後又申請一獨占性資源而無法滿足，則退出原佔有的資源。打破佔有且申請條件：採用資源預先分配策略，即進程運行前申請全部資源，滿足則運行，不然就等待，這樣就不會佔有且申請。打破循環等待條件：實現資源有序分配策略，對所有設備實現分類編號，所有進程只能採用按序號遞增的形式申請資源。
所以，在系統設計、進程調度等方面注意如何不讓這四個必要條件成立，如何確定資源的合理分配演算法，避免進程永久占據系統資源。此外，也要防止進程在處於等待狀態的情況下佔用資源,在系統運行過程中，對進程發出的每一個系統能夠滿足的資源申請進行動態檢查，並根據檢查結果決定是否分配資源，若分配後系統可能發生死鎖，則不予分配，否則予以分配。因此，對資源的分配要給予合理的規劃。
下面幾種方法可用以避免重裝死鎖的發生：
①允許目的節點將不完整的報文遞交給目的端系統；
②一個不能完整重裝的報文能被檢測出來，並要求發送該報文的源端系統重新傳送；
③為每個節點配備一個後備緩沖空間，用以暫存不完整的報文。
①、②兩種方法不能很滿意地解決重裝死鎖，因為它們使端系統中的協議復雜化了。一般的設計中，網路層應該對端系統透明，也即端系統不該考慮諸如報文拆、裝之類的事。③方法雖然不涉及端系統,但使每個節點增加了開銷。 這種演算法資源按某種規則系統中的所有資源統一編號（例如列印機為1、磁帶機為2、磁碟為3、等等），申請時必須以上升的次序。系統要求申請進程：
1、對它所必須使用的而且屬於同一類的所有資源，必須一次申請完；
2、在申請不同類資源時，必須按各類設備的編號依次申請。例如：進程PA，使用資源的順序是R1，R2； 進程PB，使用資源的順序是R2，R1；若採用動態分配有可能形成環路條件，造成死鎖。
採用有序資源分配法：R1的編號為1，R2的編號為2；
PA：申請次序應是：R1，R2
PB：申請次序應是：R1，R2
這樣就破壞了環路條件，避免了死鎖的發生 避免死鎖演算法中最有代表性的演算法是Dijkstra E.W 於1968年提出的銀行家演算法：
銀行家演算法是避免死鎖的一種重要方法，防止死鎖的機構只能確保上述四個條件之一不出現，則系統就不會發生死鎖。通過這個演算法可以用來解決生活中的實際問題，如銀行貸款等。
程序實現思路銀行家演算法顧名思義是來源於銀行的借貸業務，一定數量的本金要應多個客戶的借貸周轉，為了防止銀行家資金無法周轉而倒閉，對每一筆貸款，必須考察其是否能限期歸還。在操作系統中研究資源分配策略時也有類似問題，系統中有限的資源要供多個進程使用，必須保證得到的資源的進程能在有限的時間內歸還資源，以供其他進程使用資源。如果資源分配不得到就會發生進程循環等待資源，則進程都無法繼續執行下去的死鎖現象。
把一個進程需要和已佔有資源的情況記錄在進程式控制制中，假定進程式控制制塊PCB其中「狀態」有就緒態、等待態和完成態。當進程在處於等待態時，表示系統不能滿足該進程當前的資源申請。「資源需求總量」表示進程在整個執行過程中總共要申請的資源量。顯然，每個進程的資源需求總量不能超過系統擁有的資源總數， 銀行演算法進行資源分配可以避免死鎖。

Ⅱ 怎麼解決死鎖現象

產生死鎖的原因：一是系統提供的資源數量有限，不能滿足每個進程的使用；二是多道程序運行時，進程推進順序不合理。

產生死鎖的必要條件是：1、互斥條件；2、不可剝奪條件（不可搶占）；3、部分分配；4、循環等待。

根據產生死鎖的四個必要條件，只要使其中之一不能成立，死鎖就不會出現。為此，可以採取下列三種預防措施：
1、採用資源靜態分配策略，破壞"部分分配"條件；
2、允許進程剝奪使用其他進程佔有的資源，從而破壞"不可剝奪"條件；
3、採用資源有序分配法，破壞"環路"條件。

死鎖的避免不嚴格地限制死鎖的必要條件的存在，而是系統在系統運行過程中小心地避免死鎖的最終發生。最著名的死鎖避免演算法是銀行家演算法。死鎖避免演算法需要很大的系統開銷。

解決死鎖的另一條途徑是死鎖檢測方法，這種方法對資源的分配不加限制，即允許死鎖的發生。但系統定時地運行一個"死鎖檢測"程序，判斷系統是否已發生死鎖，若檢測到死鎖發生則設法加以解除。

解除死鎖常常採用下面兩種方法：1、資源剝奪法；2、撤消進程法

Ⅲ 通過破壞死鎖的必要條件預防死鎖，什麼條件一般不允許破壞

產生死鎖的原因：（1）競爭系統資源
（2）進程的推進順序不當
產生死鎖的必要條件：
互斥條件：進程要求對所分配的資源進行排它性控制，即在一段時間內某資源僅為一進程所佔用。
請求和保持條件：當進程因請求資源而阻塞時，對已獲得的資源保持不放。
不剝奪條件：進程已獲得的資源在未使用完之前，不能剝奪，只能在使用完時由自己釋放。
環路等待條件：在發生死鎖時，必然存在一個進程--資源的環形鏈。
解決死鎖的基本方法：
預防死鎖：
資源一次性分配：（破壞請求和保持條件）
可剝奪資源：即當某進程新的資源未滿足時，釋放已佔有的資源（破壞不可剝奪條件）
資源有序分配法：系統給每類資源賦予一個編號，每一個進程按編號遞增的順序請求資源，釋放則相反（破壞環路等待條件）
避免死鎖:
預防死鎖的幾種策略，會嚴重地損害系統性能。因此在避免死鎖時，要施加較弱的限制，從而獲得
較滿意的系統性能。由於在避免死鎖的策略中，允許進程動態地申請資源。因而，系統在進行資源分配之前預先計算資源分配的安全性。若此次分配不會導致系統進入不安全狀態，則將資源分配給進程；否則，進程等待。其中最具有代表性的避免死鎖演算法是銀行家演算法。
檢測死鎖
首先為每個進程和每個資源指定一個唯一的號碼；
然後建立資源分配表和進程等待表

Ⅳ 避免死鎖的方法有哪些

1、避免給一個鎖嵌套上鎖，在持有一個鎖的時候，不要再給這個鎖上鎖。如果使用多個鎖，使用std::lock。

2、在持有鎖時，不要調用別人提供的函數，因為你不清楚別人的代碼怎麼實現的，不知道它是不是在使用鎖。

3、給多個鎖上鎖時，固定順序。如果在給多個所上鎖，並且無法使用std::lock，最好的做法就是在每一個線程中，都按照同樣的順序。

4、分層次來使用鎖，把程序分成幾個層次。區分每個層次中使用的鎖，當一個線程已經持有更低層次的鎖時，不允許使用高層次的鎖。可以在程序運行時給不同的鎖加上層次號，記錄每個線程持有的鎖。

(4)避免死鎖的一個著名演算法擴展閱讀：

解決方法

在系統中已經出現死鎖後，應該及時檢測到死鎖的發生，並採取適當的措施來解除死鎖。

死鎖預防。

這是一種較簡單和直觀的事先預防的方法。方法是通過設置某些限制條件，去破壞產生死鎖的四個必要條件中的一個或者幾個，來預防發生死鎖。預防死鎖是一種較易實現的方法，已被廣泛使用。但是由於所施加的限制條件往往太嚴格，可能會導致系統資源利用率和系統吞吐量降低。

死鎖避免。

系統對進程發出的每一個系統能夠滿足的資源申請進行動態檢查，並根據檢查結果決定是否分配資源；如果分配後系統可能發生死鎖，則不予分配，否則予以分配。這是一種保證系統不進入死鎖狀態的動態策略。

死鎖檢測和解除。

先檢測：這種方法並不須事先採取任何限制性措施，也不必檢查系統是否已經進入不安全區，此方法允許系統在運行過程中發生死鎖。但可通過系統所設置的檢測機構，及時地檢測出死鎖的發生，並精確地確定與死鎖有關的進程和資源。檢測方法包括定時檢測、效率低時檢測、進程等待時檢測等。

然後解除死鎖：採取適當措施，從系統中將已發生的死鎖清除掉。

這是與檢測死鎖相配套的一種措施。當檢測到系統中已發生死鎖時，須將進程從死鎖狀態中解脫出來。常用的實施方法是撤銷或掛起一些進程，以便回收一些資源，再將這些資源分配給已處於阻塞狀態的進程，使之轉為就緒狀態，以繼續運行。死鎖的檢測和解除措施，有可能使系統獲得較好的資源利用率和吞吐量，但在實現上難度也最大。

Ⅳ 有沒有人懂操作系統的銀行家演算法，最好有一道例題可以講

銀行家演算法是一種最有代表性的避免死鎖的演算法。在避免死鎖方法中允許進程動態地申請資源，但系 銀行家演算法統在進行資源分配之前，應先計算此次分配資源的安全性，若分配不會導致系統進入不安全狀態，則分配，否則等待。為實現銀行家演算法，系統必須設置若干數據結構。
要解釋銀行家演算法，必須先解釋操作系統安全狀態和不安全狀態。
安全序列是指一個進程序列{P1，…，Pn}是安全的，即對於每一個進程Pi(1≤i≤n），它以後尚需要的資源量不超過系統當前剩餘資源量與所有進程Pj (j < i )當前佔有資源量之和。
我們可以把操作系統看作是銀行家，操作系統管理的資源相當於銀行家管理的資金，進程向操作系統請求分配資源相當於用戶向銀行家貸款。
為保證資金的安全，銀行家規定：
(1) 當一個顧客對資金的最大需求量不超過銀行家現有的資金時就可接納該顧客；
(2) 顧客可以分期貸款，但貸款的總數不能超過最大需求量；
(3) 當銀行家現有的資金不能滿足顧客尚需的貸款數額時，對顧客的貸款可推遲支付，但總能使顧客在有限的時間里得到貸款；
(4) 當顧客得到所需的全部資金後，一定能在有限的時間里歸還所有的資金.
操作系統按照銀行家制定的規則為進程分配資源，當進程首次申請資源時，要測試該進程對資源的最大需求量，如果系統現存的資源可以滿足它的最大需求量則按當前的申請量分配資源，否則就推遲分配。當進程在執行中繼續申請資源時，先測試該進程本次申請的資源數是否超過了該資源所剩餘的總量。若超過則拒絕分配資源，若能滿足則按當前的申請量分配資源，否則也要推遲分配。
銀行家演算法
在避免死鎖的方法中，所施加的限制條件較弱，有可能獲得令人滿意的系統性能。在該方法中把系統的狀態分為安全狀態和不安全狀態，只要能使系統始終都處於安全狀態，便可以避免發生死鎖。
銀行家演算法的基本思想是分配資源之前，判斷系統是否是安全的；若是，才分配。它是最具有代表性的避免死鎖的演算法。
設進程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("輸入的進程號不存在，重新輸入!\n");
gotoenter;
}
err:
{
printf("請輸入進程");
printf("%d",i);
printf("申請的資源數\n");
printf("類別:ABC\n");
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("類資源的資源量!申請不合理，出錯!請重新選擇!\n");
gotoerr;
}
else
{
if(Request[j]>AVAILABLE[j])
{
printf("進程");
printf("%d",i);
printf("申請的資源數大於系統可用");
printf("%d",j);
printf("類資源的資源量!申請不合理，出錯!請重新選擇!\n");
gotoerr;
}
}
}
}
changdata(i);
if(chkerr())
{
rstordata(i);
showdata();
}
else
showdata();
printf("\n");
printf("按'y'或'Y'鍵繼續,否則退出\n");
flag=getch();
if(flag=='y'||flag=='Y')
{
gotoenter;
}
else
{
exit(0);
}
}
/*顯示數組*/
voidshowdata()
{
inti,j;
printf("系統可用資源向量:\n");
printf("***Available***\n");
printf("資源類別:ABC\n");
printf("資源數目:");
for(j=0;j<N;j++)
{
printf("%d",AVAILABLE[j]);
}
printf("\n");
printf("\n");
printf("各進程還需要的資源量:\n");
printf("******Need******\n");
printf("資源類別:ABC\n");
for(i=0;i<M;i++)
{
printf("");
printf("%d",i);
printf("號進程:");
for(j=0;j<N;j++)
{
printf("%d",NEED[i][j]);
}
printf("\n");
}
printf("\n");
printf("各進程已經得到的資源量:\n");
printf("***Allocation***\n");
printf("資源類別:ABC\n");
for(i=0;i<M;i++)
{
printf("");
printf("%d",i);
printf("號進程:");
/*printf(":\n");*/
for(j=0;j<N;j++)
{
printf("%d",ALLOCATION[i][j]);
}
printf("\n");
}
printf("\n");
}
/*系統對進程請求響應，資源向量改變*/
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("系統不安全!!!本次資源申請不成功!!!\n");
return1;
}
printf("\n");
printf("經安全性檢查，系統安全，本次分配成功。\n");
printf("\n");
printf("本次安全序列：");
for(i=0;i<M;i++)//列印安全系統的進程調用順序
{
printf("進程");
printf("%d",temp[i]);
if(i<M-1)
printf("->");
}
printf("\n");
return0;
}

Ⅵ java怎麼避免多線程的死鎖 復制粘貼黨請勿回答，謝謝

都有人問過這問題了，為什麼不能復制粘貼？
產生死鎖的原因：一是系統提供的資源數量有限，不能滿足每個進程的使用；二是多道程序運行時，進程推進順序不合理。

產生死鎖的必要條件是：1、互斥條件；2、不可剝奪條件（不可搶占）；3、部分分配；4、循環等待。

根據產生死鎖的四個必要條件，只要使其中之一不能成立，死鎖就不會出現。為此，可以採取下列三種預防措施： 
1、採用資源靜態分配策略，破壞"部分分配"條件； 
2、允許進程剝奪使用其他進程佔有的資源，從而破壞"不可剝奪"條件； 
3、採用資源有序分配法，破壞"環路"條件。

死鎖的避免不嚴格地限制死鎖的必要條件的存在，而是系統在系統運行過程中小心地避免死鎖的最終發生。最著名的死鎖避免演算法是銀行家演算法。死鎖避免演算法需要很大的系統開銷。

解決死鎖的另一條途徑是死鎖檢測方法，這種方法對資源的分配不加限制，即允許死鎖的發生。但系統定時地運行一個"死鎖檢測"程序，判斷系統是否已發生死鎖，若檢測到死鎖發生則設法加以解除。

解除死鎖常常採用下面兩種方法：1、資源剝奪法；2、撤消進程法

Ⅶ 什麼是進程同步和死鎖

進程同步：我們把非同步環境下的一組並發進程因直接制約而互相發送消息而進行互相合作、互相等待，使得各進程按一定的速度執行的過程稱為進程間的同步。具有同步關系的一組並發進程稱為合作進程，合作進程間互相發送的信號稱為消息或事件。
如果我們對一個消息或事件賦以唯一的消息名，則我們可用過程wait
(消息名)表示進程等待合作進程發來的消息，而用過程signal
(消息名)
表示向合作進程發送消息。
進程死鎖：如果多個進程同時佔有對方需要的資源而同時請求對方的資源，而它們在得到請求之前不會釋放所佔有的資源，那麼就會導致死鎖的發生，也就是進程不能實現同步。

Ⅷ 死鎖怎麼解決

處理死鎖的思路如下：

預防死鎖：破壞四個必要條件中的一個或多個來預防死鎖。

避免死鎖：在資源動態分配的過程中，用某種方式防止系統進入不安全的狀態。

檢測死鎖：運行時產生死鎖，及時發現思索，將程序解脫出來。

解除死鎖：發生死鎖後，撤銷進程，回收資源，分配給正在阻塞狀態的進程。

預防死鎖的辦法：

破壞請求和保持條件：

1、一次性的申請所有資源。之後不在申請資源，如果不滿足資源條件則得不到資源分配。

2、只獲得初期資源運行，之後將運行完的資源釋放，請求新的資源。

破壞不可搶占條件：當一個進程獲得某種不可搶占資源，提出新的資源申請，若不能滿足，則釋放所有資源，以後需要，再次重新申請。

破壞循環等待條件：對資源進行排號，按照序號遞增的順序請求資源。若進程獲得序號高的資源想要獲取序號低的資源，就需要先釋放序號高的資源。

(8)避免死鎖的一個著名演算法擴展閱讀

形成死鎖的四個必要條件：

（1） 互斥條件：一個資源每次只能被一個進程使用。

（2） 請求與保持條件：一個進程因請求資源而阻塞時，對已獲得的資源保持不放。

（3） 不剝奪條件:進程已獲得的資源，在末使用完之前，不能強行剝奪。

（4） 循環等待條件:若干進程之間形成一種頭尾相接的循環等待資源關系。

如果一組進程中每一個進程都在等待僅由該組進程中的其他進程才能引發的事件，那麼該組進程是死鎖的。

舉例來說：有兩個進程A和B,A持有資源a等待b資源，B持有資源b等待a資源，兩個進程都在等待另一個資源的同時不釋放資源，就形成死鎖。

Ⅸ 產生進程死鎖的原因是什麼如何接觸死鎖

原因：

1、競爭不可搶占性資源

p1已經打開F1，想去打開F2，p2已經打開F2，想去打開F1，但是F1和F2都是不可搶占的，這是發生死鎖。

2、競爭可消耗資源引起死鎖

進程間通信，如果順序不當，會產生死鎖，比如p1發消息m1給p2，p1接收p3的消息m3，p2接收p1的m1，發m2給p3，p3，以此類推，如果進程之間是先發信息的那麼可以完成通信，但是如果是先接收信息就會產生死鎖。

3、進程推進順序不當

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

接觸：必備條件

1、互斥性：線程對資源的佔有是排他性的，一個資源只能被一個線程佔有，直到釋放。

2、請求和保持條件：一個線程對請求被佔有資源發生阻塞時，對已經獲得的資源不釋放。

3、不剝奪：一個線程在釋放資源之前，其他的線程無法剝奪佔用。

4、循環等待：發生死鎖時，線程進入死循環，永久阻塞。

(9)避免死鎖的一個著名演算法擴展閱讀

死鎖的檢測

1、每個進程、每個資源制定唯一編號。

2、設定一張資源分配表，記錄各進程與佔用資源之間的關系。

3、設置一張進程等待表，記錄各進程與要申請資源之間的關系。

死鎖的解除

1、搶占資源，從一個或多個進程中搶占足夠數量的資源，分配給死鎖進程，以解除死鎖狀態。

2、終止（或撤銷）進程，終止（或撤銷）系統中的一個或多個死鎖進程，直至打破循環環路，使系統從死鎖狀態解脫出來。

Ⅹ 避免死鎖的一個著名的演算法是

銀行家演算法