一、什麼是死鎖
多線程以及多程序改善了系統資源的使用率并提高了系統 的處理能力。然而，并發執行也帶來了新的問題——死鎖。
死鎖是指兩個或兩個以上的程序（線程）在運作過程中因争奪資源而造成的一種僵局（Deadly-Embrace) ) ，若無外力作用，這些程序（線程）都将無法向前推進。
下面我們通過一些執行個體來說明死鎖現象。
先看生活中的一個執行個體，2個人一起吃飯但是隻有一雙筷子，2人輪流吃（同時擁有2隻筷子才能吃）。某一個時候，一個拿了左筷子，一人拿了右筷子，2個人都同時占用一個資源，等待另一個資源，這個時候甲在等待乙吃完并釋放它占有的筷子，同理，乙也在等待甲吃完并釋放它占有的筷子，這樣就陷入了一個死循環，誰也無法繼續吃飯。。。
在計算機系統中也存在類似的情況。例如，某計算機系統中隻有一台列印機和一台輸入裝置，程序P1正占用輸入裝置，同時又提出使用列印機的請求，但此時列印機正被程序P2 所占用，而P2在未釋放列印機之前，又提出請求使用正被P1占用着的輸入裝置。這樣兩個程序互相無休止地等待下去，均無法繼續執行，此時兩個程序陷入死鎖狀态。
關于死鎖的一些結論：
- 參與死鎖的程序數至少為兩個
- 參與死鎖的所有程序均等待資源
- 參與死鎖的程序至少有兩個已經占有資源
- 死鎖程序是系統中目前程序集合的一個子集
- 死鎖會浪費大量系統資源，甚至導緻系統崩潰。
二、死鎖與饑餓
饑餓（Starvation）指一個程序一直得不到資源。
死鎖和饑餓都是由于程序競争資源而引起的。饑餓一般不占有資源，死鎖程序一定占有資源。
三、資源的類型
3.1 可重用資源和消耗性資源
3.1.1 可重用資源（永久性資源）
可被多個程序多次使用，如所有硬體。
- 隻能配置設定給一個程序使用，不允許多個程序共享。
- 程序在對可重用資源的使用時，須按照請求資源、使用資源、釋放資源這樣的順序。
- 系統中每一類可重用資源中的單元數目是相對固定的，程序在運作期間，既不能建立，也不能删除。
3.1.2 消耗性資源（臨時性資源）
又稱臨時性資源，是由程序在運作期間動态的建立和消耗的。
- 消耗性資源在程序運作期間是可以不斷變化的，有時可能為0。
- 程序在運作過程中，可以不斷地創造可消耗性資源的單元，将它們放入該資源類的緩沖區中，以增加該資源類的單元數目。
- 程序在運作過程中，可以請求若幹個可消耗性資源單元，用于程序自己消耗，不再将它們傳回給該資源類中。
可消耗資源通常是由生産者程序建立，由消費者程序消耗。最典型的可消耗資源是用于程序間通信的消息。
3.2 可搶占資源和不可搶占資源
3.2.1 可搶占資源
可搶占資源指某程序在獲得這類資源後，該資源可以再被其他程序或系統搶占。對于這類資源是不會引起死鎖的。
CPU 和主存均屬于可搶占性資源。
3.2.2 不可搶占資源
一旦系統把某資源配置設定給該程序後，就不能将它強行收回，隻能在程序用完後自行釋放。
錄音帶機、列印機等屬于不可搶占性資源。
四、死鎖産生的原因
- 競争不可搶占資源引起死鎖
- 通常系統中擁有的不可搶占資源，其數量不足以滿足多個程序運作的需要，使得程序在運作過程中，會因争奪資源而陷入僵局，如錄音帶機、列印機等。隻有對不可搶占資源的競争 才可能産生死鎖，對可搶占資源的競争是不會引起死鎖的。
- 競争可消耗資源引起死鎖
- 程序推進順序不當引起死鎖
- 程序在運作過程中，請求和釋放資源的順序不當，也同樣會導緻死鎖。例如，并發程序 P1、P2分别保持了資源R1、R2，而程序P1申請資源R2，程序P2申請資源R1時，兩者都會因為所需資源被占用而阻塞。
- 信号量使用不當也會造成死鎖。程序間彼此互相等待對方發來的消息，結果也會使得這 些程序間無法繼續向前推進。例如，程序A等待程序B發的消息，程序B又在等待程序A 發的消息，可以看出程序A和B不是因為競争同一資源，而是在等待對方的資源導緻死鎖。
4.1 競争不可搶占資源引起死鎖
如：共享檔案時引起死鎖
系統中擁有兩個程序P1和P2，它們都準備寫兩個檔案F1和F2。而這兩者都屬于可重用和不可搶占性資源。如果程序P1在打開F1的同時，P2程序打開F2檔案，當P1想打開F2時由于F2已結被占用而阻塞，當P2想打開1時由于F1已結被占用而阻塞，此時就會無線等待下去，形成死鎖。
4.2 競争可消耗資源引起死鎖
如：程序通信時引起死鎖
系統中擁有三個程序P1、P2和P3，m1、m2、m3是3可消耗資源。程序P1一方面産生消息m1，将其發送給P2，另一方面要從P3接收消息m3。而程序P2一方面産生消息m2，将其發送給P3，另一方面要從P1接收消息m1。類似的，程序P3一方面産生消息m3，将其發送給P1，另一方面要從P2接收消息m2。
如果三個程序都先發送自己産生的消息後接收别人發來的消息，則可以順利的運作下去不會産生死鎖，但要是三個程序都先接收别人的消息而不産生消息則會永遠等待下去，産生死鎖。
4.3 程序推進順序不當引起死鎖
上圖中，如果按曲線1的順序推進，兩個程序可順利完成；如果按曲線2的順序推進，兩個程序可順利完成；如果按曲線3的順序推進，兩個程序可順利完成；如果按曲線4的順序推進，兩個程序将進入不安全區D中，此時P1保持了資源R1，P2保持了資源R2，系統處于不安全狀态，如果繼續向前推進，則可能産生死鎖。
五、産生死鎖的四個必要條件
5.1 互斥條件：
程序要求對所配置設定的資源（如列印機）進行排他性控制，即在一段時間内某資源僅為一個程序所占有。此時若有其他程序請求該資源，則請求程序隻能等待。
5.2 不可剝奪條件:
程序所獲得的資源在未使用完畢之前，不能被其他程序強行奪走，即隻能由獲得該資源的程序自己來釋放（隻能是主動釋放)。
5.3 請求與保持條件：
程序已經保持了至少一個資源，但又提出了新的資源請求，而該資源已被其他程序占有，此時請求程序被阻塞，但對自己已獲得的資源保持不放。
5.4 循環等待條件:
存在一種程序資源的循環等待鍊，鍊中每一個程序已獲得的資源同時被 鍊中下一個程序所請求。即存在一個處于等待狀态的程序集合{Pl, P2, …, pn}，其中Pi等 待的資源被P(i+1)占有（i=0, 1, …, n-1)，Pn等待的資源被P0占有，如圖2-15所示。
直覺上看，循環等待條件似乎和死鎖的定義一樣，其實不然。按死鎖定義構成等待環所 要求的條件更嚴，它要求Pi等待的資源必須由P(i+1)來滿足，而循環等待條件則無此限制。 例如，系統中有兩台輸出裝置，P0占有一台，PK占有另一台，且K不屬于集合{0, 1, …, n}。
Pn等待一台輸出裝置，它可以從P0獲得，也可能從PK獲得。是以，雖然Pn、P0和其他 一些程序形成了循環等待圈，但PK不在圈内，若PK釋放了輸出裝置，則可打破循環等待, 如圖2-16所示。是以循環等待隻是死鎖的必要條件。
資源配置設定圖含圈而系統又不一定有死鎖的原因是同類資源數大于1。但若系統中每類資 源都隻有一個資源，則資源配置設定圖含圈就變成了系統出現死鎖的充分必要條件。
以上這四個條件是死鎖的必要條件，隻要系統發生死鎖，這些條件必然成立，而隻要上述條件之一不滿足，就不會發生死鎖。
産生死鎖的一個例子:
/**
* 一個簡單的死鎖類
* 當DeadLock類的對象flag==1時（td1），先鎖定o1,睡眠500毫秒
* 而td1在睡眠的時候另一個flag==0的對象（td2）線程啟動，先鎖定o2,睡眠500毫秒
* td1睡眠結束後需要鎖定o2才能繼續執行，而此時o2已被td2鎖定；
* td2睡眠結束後需要鎖定o1才能繼續執行，而此時o1已被td1鎖定；
* td1、td2互相等待，都需要得到對方鎖定的資源才能繼續執行，進而死鎖。
*/
public class DeadLock implements Runnable {
public int flag = 1;
//靜态對象是類的所有對象共享的
private static Object o1 = new Object(), o2 = new Object();
@Override
public void run() {
System.out.println("flag=" + flag);
if (flag == 1) {
synchronized (o1) {
try {
Thread.sleep(500);
} catch (Exception e) {
e.printStackTrace();
}
synchronized (o2) {
System.out.println("1");
}
}
}
if (flag == 0) {
synchronized (o2) {
try {
Thread.sleep(500);
} catch (Exception e) {
e.printStackTrace();
}
synchronized (o1) {
System.out.println("0");
}
}
}
}
public static void main(String[] args) {
DeadLock td1 = new DeadLock();
DeadLock td2 = new DeadLock();
td1.flag = 1;
td2.flag = 0;
//td1,td2都處于可執行狀态，但JVM線程排程先執行哪個線程是不确定的。
//td2的run()可能在td1的run()之前運作
new Thread(td1).start();
new Thread(td2).start();
}
} 六、處理死鎖的方法
- 預防死鎖：通過設定某些限制條件，去破壞産生死鎖的四個必要條件中的一個或幾個條件，來防止死鎖的發生。
- 避免死鎖：在資源的動态配置設定過程中，用某種方法去防止系統進入不安全狀态，進而避免死鎖的發生。
- 檢測死鎖：允許系統在運作過程中發生死鎖，但可設定檢測機構及時檢測死鎖的發生，并采取适當措施加以清除。
- 解除死鎖：當檢測出死鎖後，便采取适當措施将程序從死鎖狀态中解脫出來。
6.1 預防死鎖
1.破壞“互斥”條件:
破壞“互斥”條件，就是在系統裡取消互斥。若資源不被一個程序獨占使用，那麼死鎖是肯定不會發生的。但一般來說在所列的四個條件中，“互斥”條件是無法破壞的。是以，在死鎖預防裡主要是破壞其他幾個必要條件，而不去涉及破壞“互斥”條件。
注意：互斥條件不能被破壞，否則會造成結果的不可再現性。
2.破壞“占有并等待”條件:
破壞“占有并等待”條件，就是在系統中不允許程序在已獲得某種資源的情況下，申請其他資源。即要想出一個辦法，阻止程序在持有資源的同時申請其他資源。
方法一：建立程序時，要求它申請所需的全部資源，系統或滿足其所有要求，或什麼也不給它。這是所謂的 “ 一次性配置設定”方案。
方法二：要求每個程序提出新的資源申請前，釋放它所占有的資源。這樣，一個程序在需要資源S時，須先把它先前占有的資源R釋放掉，然後才能提出對S的申請，即使它可能很快又要用到資源R。
3.破壞“不可搶占”條件：
破壞“不可搶占”條件就是允許對資源實行搶奪。
方法一：如果占有某些資源的一個程序進行進一步資源請求被拒絕，則該程序必須釋放它最初占有的資源，如果有必要，可再次請求這些資源和另外的資源。
方法二：如果一個程序請求目前被另一個程序占有的一個資源，則作業系統可以搶占另一個程序，要求它釋放資源。隻有在任意兩個程序的優先級都不相同的條件下，方法二才能預防死鎖。
4.破壞“循環等待”條件：
破壞“循環等待”條件的一種方法，是将系統中的所有資源統一編号，程序可在任何時刻提出資源申請，但所有申請必須按照資源的編号順序（升序）提出。這樣做就能保證系統不出現死鎖。
6.2 避免死鎖
了解了死鎖的原因，尤其是産生死鎖的四個必要條件，就可以最大可能地避免、預防和解除死鎖。是以，在系統設計、程序排程等方面注意如何讓這四個必要條件不成立，如何确定資源的合理配置設定算法，避免程序永久占據系統資源。此外，也要防止程序在處于等待狀态的情況下占用資源。是以，對資源的配置設定要給予合理的規劃。
預防死鎖和避免死鎖的差別：
預防死鎖是設法至少破壞産生死鎖的四個必要條件之一,嚴格的防止死鎖的出現,而避免死鎖則不那麼嚴格的限制産生死鎖的必要條件的存在,因為即使死鎖的必要條件存在,也不一定發生死鎖。避免死鎖是在系統運作過程中注意避免死鎖的最終發生。
6.2.1 常用避免死鎖的方法
6.2.1.1 有序資源配置設定法
這種算法資源按某種規則系統中的所有資源統一編号（例如列印機為1、錄音帶機為2、磁盤為3、等等），申請時必須以上升的次序。系統要求申請程序：
1、對它所必須使用的而且屬于同一類的所有資源，必須一次申請完；
2、在申請不同類資源時，必須按各類裝置的編号依次申請。例如：程序PA，使用資源的順序是R1，R2； 程序PB，使用資源的順序是R2，R1；若采用動态配置設定有可能形成環路條件，造成死鎖。
采用有序資源配置設定法：R1的編号為1，R2的編号為2；
PA：申請次序應是：R1，R2
PB：申請次序應是：R1，R2
這樣就破壞了環路條件，避免了死鎖的發生。
6.2.1.2 銀行家算法
詳見銀行家算法.
6.2.2 常用避免死鎖的技術
- 加鎖順序（線程按照一定的順序加鎖）
- 加鎖時限（線程嘗試擷取鎖的時候加上一定的時限，超過時限則放棄對該鎖的請求，并釋放自己占有的鎖）
- 死鎖檢測
6.2.2.1 加鎖順序
當多個線程需要相同的一些鎖，但是按照不同的順序加鎖，死鎖就很容易發生。
如果能確定所有的線程都是按照相同的順序獲得鎖，那麼死鎖就不會發生。看下面這個例子：
Thread 1:
lock A
lock B
Thread 2:
wait for A
lock C (when A locked)
Thread 3:
wait for A
wait for B
wait for C 如果一個線程（比如線程3）需要一些鎖，那麼它必須按照确定的順序擷取鎖。它隻有獲得了從順序上排在前面的鎖之後，才能擷取後面的鎖。
例如，線程2和線程3隻有在擷取了鎖A之後才能嘗試擷取鎖C(譯者注：擷取鎖A是擷取鎖C的必要條件)。因為線程1已經擁有了鎖A，是以線程2和3需要一直等到鎖A被釋放。然後在它們嘗試對B或C加鎖之前，必須成功地對A加了鎖。
按照順序加鎖是一種有效的死鎖預防機制。但是，這種方式需要你事先知道所有可能會用到的鎖(譯者注：并對這些鎖做适當的排序)，但總有些時候是無法預知的。
6.2.2.2 加鎖時限
另外一個可以避免死鎖的方法是在嘗試擷取鎖的時候加一個逾時時間，這也就意味着在嘗試擷取鎖的過程中若超過了這個時限該線程則放棄對該鎖請求。若一個線程沒有在給定的時限内成功獲得所有需要的鎖，則會進行回退并釋放所有已經獲得的鎖，然後等待一段随機的時間再重試。這段随機的等待時間讓其它線程有機會嘗試擷取相同的這些鎖，并且讓該應用在沒有獲得鎖的時候可以繼續運作(譯者注：加鎖逾時後可以先繼續運作幹點其它事情，再回頭來重複之前加鎖的邏輯)。
以下是一個例子，展示了兩個線程以不同的順序嘗試擷取相同的兩個鎖，在發生逾時後回退并重試的場景：
Thread 1 locks A
Thread 2 locks B
Thread 1 attempts to lock B but is blocked
Thread 2 attempts to lock A but is blocked
Thread 1’s lock attempt on B times out
Thread 1 backs up and releases A as well
Thread 1 waits randomly (e.g. 257 millis) before retrying.
Thread 2’s lock attempt on A times out
Thread 2 backs up and releases B as well
Thread 2 waits randomly (e.g. 43 millis) before retrying. 在上面的例子中，線程2比線程1早200毫秒進行重試加鎖，是以它可以先成功地擷取到兩個鎖。這時，線程1嘗試擷取鎖A并且處于等待狀态。當線程2結束時，線程1也可以順利的獲得這兩個鎖（除非線程2或者其它線程線上程1成功獲得兩個鎖之前又獲得其中的一些鎖）。
需要注意的是，由于存在鎖的逾時，是以我們不能認為這種場景就一定是出現了死鎖。也可能是因為獲得了鎖的線程（導緻其它線程逾時）需要很長的時間去完成它的任務。
此外，如果有非常多的線程同一時間去競争同一批資源，就算有逾時和回退機制，還是可能會導緻這些線程重複地嘗試但卻始終得不到鎖。如果隻有兩個線程，并且重試的逾時時間設定為0到500毫秒之間，這種現象可能不會發生，但是如果是10個或20個線程情況就不同了。因為這些線程等待相等的重試時間的機率就高的多（或者非常接近以至于會出現問題）。
(譯者注：逾時和重試機制是為了避免在同一時間出現的競争，但是當線程很多時，其中兩個或多個線程的逾時時間一樣或者接近的可能性就會很大，是以就算出現競争而導緻逾時後，由于逾時時間一樣，它們又會同時開始重試，導緻新一輪的競争，帶來了新的問題。)
這種機制存在一個問題，在Java中不能對synchronized同步塊設定逾時時間。你需要建立一個自定義鎖，或使用Java5中java.util.concurrent包下的工具。寫一個自定義鎖類不複雜，但超出了本文的内容。後續的Java并發系列會涵蓋自定義鎖的内容。
6.2.2.3 死鎖檢測
死鎖檢測是一個更好的死鎖預防機制，它主要是針對那些不可能實作按序加鎖并且鎖逾時也不可行的場景。
每當一個線程獲得了鎖，會線上程和鎖相關的資料結構中（map、graph等等）将其記下。除此之外，每當有線程請求鎖，也需要記錄在這個資料結構中。
當一個線程請求鎖失敗時，這個線程可以周遊鎖的關系圖看看是否有死鎖發生。例如，線程A請求鎖7，但是鎖7這個時候被線程B持有，這時線程A就可以檢查一下線程B是否已經請求了線程A目前所持有的鎖。如果線程B确實有這樣的請求，那麼就是發生了死鎖（線程A擁有鎖1，請求鎖7；線程B擁有鎖7，請求鎖1）。
當然，死鎖一般要比兩個線程互相持有對方的鎖這種情況要複雜的多。線程A等待線程B，線程B等待線程C，線程C等待線程D，線程D又在等待線程A。線程A為了檢測死鎖，它需要遞進地檢測所有被B請求的鎖。從線程B所請求的鎖開始，線程A找到了線程C，然後又找到了線程D，發現線程D請求的鎖被線程A自己持有着。這是它就知道發生了死鎖。
下面是一幅關于四個線程（A,B,C和D）之間鎖占有和請求的關系圖。像這樣的資料結構就可以被用來檢測死鎖。
6.3 檢測死鎖
一般來說，由于作業系統有并發，共享以及随機性等特點，通過預防和避免的手段達到排除死鎖的目的是很困難的。這需要較大的系統開銷，而且不能充分利用資源。為此，一種簡便的方法是系統為程序配置設定資源時，不采取任何限制性措施，但是提供了檢測和解脫死鎖的手段：能發現死鎖并從死鎖狀态中恢複出來。是以，在實際的作業系統中往往采用死鎖的檢測與恢複方法來排除死鎖。
死鎖檢測與恢複是指系統設有專門的機構，當死鎖發生時，該機構能夠檢測到死鎖發生的位置和原因，并能通過外力破壞死鎖發生的必要條件，進而使得并發程序從死鎖狀态中恢複出來。
這時程序P1占有資源R1而申請資源R2，程序P2占有資源R2而申請資源R1，按循環等待條件，程序和資源形成了環路，是以系統是死鎖狀态。程序P1，P2是參與死鎖的程序。
下面我們再來看一看死鎖檢測算法。算法使用的資料結構是如下這些：
占有矩陣A：n*m階，其中n表示并發程序的個數，m表示系統的各類資源的個數，這個矩陣記錄了每一個程序目前占有各個資源類中資源的個數。
申請矩陣R：n*m階，其中n表示并發程序的個數，m表示系統的各類資源的個數，這個矩陣記錄了每一個程序目前要完成工作需要申請的各個資源類中資源的個數。
空閑向量T：記錄目前m個資源類中空閑資源的個數。
完成向量F：布爾型向量值為真（true）或假（false），記錄目前n個并發程序能否進行完。為真即能進行完，為假則不能進行完。
臨時向量W：開始時W：=T。
算法步驟：
（1）W：=T，
對于所有的i=1，2，…，n，
如果A[i]=0，則F[i]：=true；否則，F[i]：=false
（2）找滿足下面條件的下标i：
F[i]：=false并且R[i]〈=W
如果不存在滿足上面的條件i，則轉到步驟（4）。
（3）W：=W+A[i]
F[i]：=true
轉到步驟（2）
（4）如果存在i，F[i]：=false，則系統處于死鎖狀态，且Pi程序參與了死鎖。什麼時候進行死鎖的檢測取決于死鎖發生的頻率。如果死鎖發生的頻率高，那麼死鎖檢測的頻率也要相應提高，這樣一方面可以提高系統資源的使用率，一方面可以避免更多的程序卷入死鎖。如果程序申請資源不能滿足就立刻進行檢測，那麼每當死鎖形成時即能被發現，這和死鎖避免的算法相近，隻是系統的開銷較大。為了減小死鎖檢測帶來的系統開銷，一般采取每隔一段時間進行一次死鎖檢測，或者在CPU的使用率降低到某一數值時，進行死鎖的檢測。
6.4 解除死鎖
一旦檢測出死鎖，就應立即釆取相應的措施，以解除死鎖。
死鎖解除的主要方法有：
1) 資源剝奪法。挂起某些死鎖程序，并搶占它的資源，将這些資源配置設定給其他的死鎖程序。但應防止被挂起的程序長時間得不到資源，而處于資源匮乏的狀态。
2) 撤銷程序法。強制撤銷部分、甚至全部死鎖程序并剝奪這些程序的資源。撤銷的原則可以按程序優先級和撤銷程序代價的高低進行。