死鎖其實(shí)在信號量時已經(jīng)提到過，當(dāng)一個進(jìn)程想要申請資源A，擁有資源B，而另一個進(jìn)程想申請資源B，但是擁有資源A，那么就會產(chǎn)生死鎖。
信號量本身就是個資源，有一定數(shù)量。資源分為很多很多，如內(nèi)存空間，CPU周期，I/O設(shè)備等，每個資源有一定數(shù)量的資源實(shí)例。
資源和信號量一樣，有等待隊(duì)列，當(dāng)一個進(jìn)程想要申請資源，但需要其他進(jìn)程釋放此資源，則進(jìn)入該資源的等待隊(duì)列。
死鎖的必要條件：
1、互斥。即資源不能被多個進(jìn)程所占有。這點(diǎn)其實(shí)除了只讀文件，其他基本都滿足。
2、占有并等待：A進(jìn)程占有一些資源，還需要的一些資源被其他進(jìn)程占有，所以處在等待狀態(tài)。
3、非搶占：資源不能被中途搶占。
4、循環(huán)等待：｛P0，P1,P2....｝進(jìn)程隊(duì)列，P0等待P1占用的資源，類似。
只要4個條件滿足，則說明必定死鎖。
資源分配圖：為了清晰的看是否有死鎖。P->R實(shí)線 申請；R->P實(shí)線 分配；P->R虛線 需求。
當(dāng)每個資源類型只有一個實(shí)例，則有環(huán)等價于死鎖。
當(dāng)存在資源類型有多個實(shí)例，則死鎖必有環(huán)，有環(huán)不一定死鎖。
死鎖處理：
1.1 死鎖預(yù)防。通過不滿足四個必要條件之一。
（1）互斥：很難不滿足。
（2）占有并等待：第一，可要求進(jìn)程創(chuàng)建就要申請好全部的資源；或第二，進(jìn)程申請資源時要釋放占有的資源。
但是第一種情況會發(fā)生饑餓。因?yàn)槿绻粋€進(jìn)程需要很多很多進(jìn)程，這些資源幾乎不會同時有，則這個進(jìn)程永遠(yuǎn)不會執(zhí)行。
（3）非搶占：如果A進(jìn)程想要申請資源a，但是a被B進(jìn)程占有，且B進(jìn)程在等待資源b，則A進(jìn)程可以搶占B進(jìn)程的資源a執(zhí)行。等到B進(jìn)程得到原本
擁有的資源a和申請的b，則執(zhí)行。 搶占和被搶占
（4）循環(huán)等待：規(guī)定資源被申請的順序，每個進(jìn)程申請資源的順序被規(guī)定了。如果需要Rj（j<i）則需要先釋放Ri。
1.2 死鎖避免。前面討論的預(yù)防死鎖的解決方案中包括限制資源的申請，但是這對資源的利用率來說下降太多了。
所以引出了死鎖避免：要求事先得到進(jìn)程申請資源和擁有的資源的信息 來判定是否值得等待。(想起了管程的條件變量選擇重啟進(jìn)程的解決方
法就是得知進(jìn)程的最大需求)
最簡單的方法是事先告訴每個進(jìn)程對于每個資源類型的最大需求。從而使得循環(huán)等待不成立。
（1）安全狀態(tài):能確定一個進(jìn)程序列<p1,p2...>，按照這種順序執(zhí)行進(jìn)程就不會死鎖（一個結(jié)束一個開始）。使得當(dāng)Pi申請資源時，申請的資
源一定要小于剩余可用資源+pi隊(duì)列前面的進(jìn)程所占有的資源，則稱為安全的。因?yàn)槟阆耄琍i最多就等的長一點(diǎn)時間，但是最終還是能行的。
安全則不會死鎖。不安全不一定會死鎖。
只有資源分配后能安全狀態(tài)，才允許申請。
（2）資源分配圖算法：適用于每個資源類型只有一個實(shí)例。
分配邊釋放就變成需求邊。
2、允許進(jìn)入死鎖，但可以檢測并恢復(fù)。
3、忽略死鎖。
銀行家算法： 銀行有一些資源，一個客戶一會要一點(diǎn)資源，一會要一點(diǎn)資源，銀行耐著性子分配。 預(yù)先知道Max，Allocation，Available
在新進(jìn)程進(jìn)入時，必須說明需要資源類型的種類和數(shù)量，但是不能超過系統(tǒng)總資源。
n為進(jìn)程個數(shù)，m為資源類型種類，available為長度為m的向量，表示每種資源擁有多少的資源。
Max是n*m的矩陣，Max[i]表示特定進(jìn)程需要的每個資源的最大需求。
Allocation是n*m的矩陣，Allocation[i]表示特定進(jìn)程已經(jīng)分配的每個資源的數(shù)量。
Need是n*m的矩陣，Need[i]是特定進(jìn)程需要的剩余資源。
兩個向量比較，只有每個分量都大，才大。
安全性算法：
設(shè)work是長度m的向量，finish是長度n的向量
work=available;
for(int i=0;i<n;i++)
finish[i]=false;
for(int i=0;i<n;i++) O(n)
{
if(finish[i]==false&&Need[i]<work) O(m) //如果進(jìn)程i的最大剩余需求小于系統(tǒng)剩余的資源量
{
work=work+allocation[i]; O(m) //執(zhí)行完后釋放，則系統(tǒng)剩余資源變多
finish[i]=true; //進(jìn)程i執(zhí)行結(jié)束
}
else break;
}
for(int i=0;i<n;i++)
{
if(finish[i]==false) return false;
}
return true; |
資源請求算法：
Request[i]是進(jìn)程i的請求向量。
if Request[i]<Need[i] 說明能申請
if Request[i]<Available 說明能分配
if能分配
｛
Available-=Request[i]; //系統(tǒng)剩余減少
Allocation[i]+=Request[i]; //已分配增多
Need[i]-=Request[i]; //剩余需求減少
｝
分配完執(zhí)行安全性算法，即看看是不是安全。
系統(tǒng)不采用預(yù)防或避免提前去除死鎖時，可以
1、有一個算法可以檢索死鎖的發(fā)生。
2、有一個算法可以讓死鎖恢復(fù)。
當(dāng)資源類型只有一個資源實(shí)例時，可以用等待圖（只有進(jìn)程）解決。當(dāng)有環(huán)時，則死鎖。
當(dāng)資源類型可以有多個實(shí)例時，則可以用銀行家算法解決。
有一個好辦法解決死鎖，就是當(dāng)CPU使用率低于多少多少時，才調(diào)用死鎖檢測，再去除死鎖。
恢復(fù)死鎖可以：
1、隨便終止一個進(jìn)程打破循環(huán)等待。
當(dāng)選擇進(jìn)程的終止時，需要考慮很多方面，就像CPU調(diào)度里的優(yōu)先隊(duì)列法，可以以不同方面考慮優(yōu)先。可以以進(jìn)程執(zhí)行時間、進(jìn)程還需資源多少、進(jìn)程是交互的還是批處理的。
2、搶占死鎖進(jìn)程資源。
搶占要搶占誰的又是個問題。自己選唄~而被搶占資源的進(jìn)程必須回滾到不會發(fā)生死鎖的時刻。而且不能一直欺負(fù)一個進(jìn)程，這樣該進(jìn)程會發(fā)生饑餓。