鍍金池/ 教程/ Java/ 避免死鎖
Slipped Conditions
阻塞隊(duì)列
無阻塞算法
嵌套管程鎖死
Java 并發(fā)性和多線程介紹
死鎖
線程安全及不可變性
并發(fā)編程模型
Java 中的讀/寫鎖
剖析同步器
競態(tài)條件與臨界區(qū)
多線程的優(yōu)點(diǎn)
CAS
線程通信
如何創(chuàng)建并運(yùn)行 java 線程
阿姆達(dá)爾定律
避免死鎖
信號量
多線程的代價(jià)
饑餓和公平
線程池
重入鎖死
Java 中的鎖
Java 內(nèi)存模型
線程安全與共享資源
Java 同步塊

避免死鎖

在有些情況下死鎖是可以避免的。本文將展示三種用于避免死鎖的技術(shù)：

  1. 加鎖順序
  2. 加鎖時(shí)限
  3. 死鎖檢測

加鎖順序

當(dāng)多個(gè)線程需要相同的一些鎖，但是按照不同的順序加鎖，死鎖就很容易發(fā)生。

如果能確保所有的線程都是按照相同的順序獲得鎖，那么死鎖就不會發(fā)生?？聪旅孢@個(gè)例子：

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

如果一個(gè)線程（比如線程 3）需要一些鎖，那么它必須按照確定的順序獲取鎖。它只有獲得了從順序上排在前面的鎖之后，才能獲取后面的鎖。

例如，線程 2 和線程 3 只有在獲取了鎖 A 之后才能嘗試獲取鎖 C(譯者注：獲取鎖 A 是獲取鎖 C 的必要條件)。因?yàn)榫€程 1 已經(jīng)擁有了鎖 A，所以線程 2 和 3 需要一直等到鎖 A 被釋放。然后在它們嘗試對 B 或 C 加鎖之前，必須成功地對 A 加了鎖。

按照順序加鎖是一種有效的死鎖預(yù)防機(jī)制。但是，這種方式需要你事先知道所有可能會用到的鎖(譯者注：并對這些鎖做適當(dāng)?shù)呐判?/em>)，但總有些時(shí)候是無法預(yù)知的。

加鎖時(shí)限

另外一個(gè)可以避免死鎖的方法是在嘗試獲取鎖的時(shí)候加一個(gè)超時(shí)時(shí)間，這也就意味著在嘗試獲取鎖的過程中若超過了這個(gè)時(shí)限該線程則放棄對該鎖請求。若一個(gè)線程沒有在給定的時(shí)限內(nèi)成功獲得所有需要的鎖，則會進(jìn)行回退并釋放所有已經(jīng)獲得的鎖，然后等待一段隨機(jī)的時(shí)間再重試。這段隨機(jī)的等待時(shí)間讓其它線程有機(jī)會嘗試獲取相同的這些鎖，并且讓該應(yīng)用在沒有獲得鎖的時(shí)候可以繼續(xù)運(yùn)行(譯者注：加鎖超時(shí)后可以先繼續(xù)運(yùn)行干點(diǎn)其它事情，再回頭來重復(fù)之前加鎖的邏輯)。

以下是一個(gè)例子，展示了兩個(gè)線程以不同的順序嘗試獲取相同的兩個(gè)鎖，在發(fā)生超時(shí)后回退并重試的場景：

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 毫秒進(jìn)行重試加鎖，因此它可以先成功地獲取到兩個(gè)鎖。這時(shí)，線程 1 嘗試獲取鎖 A 并且處于等待狀態(tài)。當(dāng)線程 2 結(jié)束時(shí)，線程 1 也可以順利的獲得這兩個(gè)鎖（除非線程 2 或者其它線程在線程 1 成功獲得兩個(gè)鎖之前又獲得其中的一些鎖）。

需要注意的是，由于存在鎖的超時(shí)，所以我們不能認(rèn)為這種場景就一定是出現(xiàn)了死鎖。也可能是因?yàn)楂@得了鎖的線程（導(dǎo)致其它線程超時(shí)）需要很長的時(shí)間去完成它的任務(wù)。

此外，如果有非常多的線程同一時(shí)間去競爭同一批資源，就算有超時(shí)和回退機(jī)制，還是可能會導(dǎo)致這些線程重復(fù)地嘗試但卻始終得不到鎖。如果只有兩個(gè)線程，并且重試的超時(shí)時(shí)間設(shè)定為 0 到 500 毫秒之間，這種現(xiàn)象可能不會發(fā)生，但是如果是 10 個(gè)或 20 個(gè)線程情況就不同了。因?yàn)檫@些線程等待相等的重試時(shí)間的概率就高的多（或者非常接近以至于會出現(xiàn)問題）。

(譯者注：超時(shí)和重試機(jī)制是為了避免在同一時(shí)間出現(xiàn)的競爭，但是當(dāng)線程很多時(shí)，其中兩個(gè)或多個(gè)線程的超時(shí)時(shí)間一樣或者接近的可能性就會很大，因此就算出現(xiàn)競爭而導(dǎo)致超時(shí)后，由于超時(shí)時(shí)間一樣，它們又會同時(shí)開始重試，導(dǎo)致新一輪的競爭，帶來了新的問題。)

這種機(jī)制存在一個(gè)問題，在 Java 中不能對 synchronized 同步塊設(shè)置超時(shí)時(shí)間。你需要?jiǎng)?chuàng)建一個(gè)自定義鎖，或使用 Java5 中 java.util.concurrent 包下的工具。寫一個(gè)自定義鎖類不復(fù)雜，但超出了本文的內(nèi)容。后續(xù)的 Java 并發(fā)系列會涵蓋自定義鎖的內(nèi)容。

死鎖檢測

死鎖檢測是一個(gè)更好的死鎖預(yù)防機(jī)制，它主要是針對那些不可能實(shí)現(xiàn)按序加鎖并且鎖超時(shí)也不可行的場景。

每當(dāng)一個(gè)線程獲得了鎖，會在線程和鎖相關(guān)的數(shù)據(jù)結(jié)構(gòu)中（map、graph 等等）將其記下。除此之外，每當(dāng)有線程請求鎖，也需要記錄在這個(gè)數(shù)據(jù)結(jié)構(gòu)中。

當(dāng)一個(gè)線程請求鎖失敗時(shí)，這個(gè)線程可以遍歷鎖的關(guān)系圖看看是否有死鎖發(fā)生。例如，線程 A 請求鎖 7，但是鎖 7 這個(gè)時(shí)候被線程 B 持有，這時(shí)線程 A 就可以檢查一下線程 B 是否已經(jīng)請求了線程 A 當(dāng)前所持有的鎖。如果線程 B 確實(shí)有這樣的請求，那么就是發(fā)生了死鎖（線程 A 擁有鎖 1，請求鎖 7；線程 B 擁有鎖 7，請求鎖 1）。

當(dāng)然，死鎖一般要比兩個(gè)線程互相持有對方的鎖這種情況要復(fù)雜的多。線程 A 等待線程 B，線程 B 等待線程 C，線程 C 等待線程 D，線程 D 又在等待線程 A。線程 A 為了檢測死鎖，它需要遞進(jìn)地檢測所有被 B 請求的鎖。從線程 B 所請求的鎖開始，線程 A 找到了線程 C，然后又找到了線程 D，發(fā)現(xiàn)線程 D 請求的鎖被線程 A 自己持有著。這是它就知道發(fā)生了死鎖。

下面是一幅關(guān)于四個(gè)線程（A,B,C 和 D）之間鎖占有和請求的關(guān)系圖。像這樣的數(shù)據(jù)結(jié)構(gòu)就可以被用來檢測死鎖。

http://wiki.jikexueyuan.com/project/java-concurrent/images/17.png" alt="" />

那么當(dāng)檢測出死鎖時(shí)，這些線程該做些什么呢？

一個(gè)可行的做法是釋放所有鎖，回退，并且等待一段隨機(jī)的時(shí)間后重試。這個(gè)和簡單的加鎖超時(shí)類似，不一樣的是只有死鎖已經(jīng)發(fā)生了才回退，而不會是因?yàn)榧渔i的請求超時(shí)了。雖然有回退和等待，但是如果有大量的線程競爭同一批鎖，它們還是會重復(fù)地死鎖（編者注：原因同超時(shí)類似，不能從根本上減輕競爭）。

一個(gè)更好的方案是給這些線程設(shè)置優(yōu)先級，讓一個(gè)（或幾個(gè)）線程回退，剩下的線程就像沒發(fā)生死鎖一樣繼續(xù)保持著它們需要的鎖。如果賦予這些線程的優(yōu)先級是固定不變的，同一批線程總是會擁有更高的優(yōu)先級。為避免這個(gè)問題，可以在死鎖發(fā)生的時(shí)候設(shè)置隨機(jī)的優(yōu)先級。