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