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

加鎖順序
加鎖時限
死鎖檢測

加鎖順序

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

如果能確保所有的線程都是按照相同的順序獲得鎖，那么死鎖就不會發(fā)生。看下面這個例子：

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已經(jīng)擁有了鎖A，所以線程2和3需要一直等到鎖A被釋放。然后在它們嘗試對B或C加鎖之前，必須成功地對A加了鎖。

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

加鎖時限

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

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

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并且處于等待狀態(tài)。當線程2結(jié)束時，線程1也可以順利的獲得這兩個鎖（除非線程2或者其它線程在線程1成功獲得兩個鎖之前又獲得其中的一些鎖）。

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

此外，如果有非常多的線程同一時間去競爭同一批資源，就算有超時和回退機制，還是可能會導致這些線程重復地嘗試但卻始終得不到鎖。如果只有兩個線程，并且重試的超時時間設定為0到500毫秒之間，這種現(xiàn)象可能不會發(fā)生，但是如果是10個或20個線程情況就不同了。因為這些線程等待相等的重試時間的概率就高的多（或者非常接近以至于會出現(xiàn)問題）。
(譯者注：超時和重試機制是為了避免在同一時間出現(xiàn)的競爭，但是當線程很多時，其中兩個或多個線程的超時時間一樣或者接近的可能性就會很大，因此就算出現(xiàn)競爭而導致超時后，由于超時時間一樣，它們又會同時開始重試，導致新一輪的競爭，帶來了新的問題。)

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

死鎖檢測

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

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

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

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

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



那么當檢測出死鎖時，這些線程該做些什么呢？

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

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

java并發(fā)（十一）避免死鎖