避免死鎖

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

<a href="http://ifeve.com/deadlock-prevention/#ordering">加鎖順序</a>

<a href="http://ifeve.com/deadlock-prevention/#timeout">加鎖時限</a>

<a href="http://ifeve.com/deadlock-prevention/#detection">死鎖檢測</a>

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

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

如果一個線程（比如線程3）需要一些鎖，那麼它必須按照确定的順序擷取鎖。它隻有獲得了從順序上排在前面的鎖之後，才能擷取後面的鎖。

例如，線程2和線程3隻有在擷取了鎖a之後才能嘗試擷取鎖c(譯者注：擷取鎖a是擷取鎖c的必要條件)。因為線程1已經擁有了鎖a，是以線程2和3需要一直等到鎖a被釋放。然後在它們嘗試對b或c加鎖之前，必須成功地對a加了鎖。

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

另外一個可以避免死鎖的方法是在嘗試擷取鎖的時候加一個逾時時間，這也就意味着在嘗試擷取鎖的過程中若超過了這個時限該線程則放棄對該鎖請求。若一

個線程沒有在給定的時限内成功獲得所有需要的鎖，則會進行回退并釋放所有已經獲得的鎖，然後等待一段随機的時間再重試。這段随機的等待時間讓其它線程有機

會嘗試擷取相同的這些鎖，并且讓該應用在沒有獲得鎖的時候可以繼續運作(譯者注：加鎖逾時後可以先繼續運作幹點其它事情，再回頭來重複之前加鎖的邏輯)。

以下是一個例子，展示了兩個線程以不同的順序嘗試擷取相同的兩個鎖，在發生逾時後回退并重試的場景：

在上面的例子中，線程2比線程1早200毫秒進行重試加鎖，是以它可以先成功地擷取到兩個鎖。這時，線程1嘗試擷取鎖a并且處于等待狀态。當線程2結束時，線程1也可以順利的獲得這兩個鎖（除非線程2或者其它線程線上程1成功獲得兩個鎖之前又獲得其中的一些鎖）。

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

此外，如果有非常多的線程同一時間去競争同一批資源，就算有逾時和回退機制，還是可能會導緻這些線程重複地嘗試但卻始終得不到鎖。如果隻有兩個線

程，并且重試的逾時時間設定為0到500毫秒之間，這種現象可能不會發生，但是如果是10個或20個線程情況就不同了。因為這些線程等待相等的重試時間的

機率就高的多（或者非常接近以至于會出現問題）。

(譯者注：逾時和重試機制是為了避免在同一時間出現的競争，但是當線程很多時，其中兩個或多個線程的逾時時間一樣或者接近的可能性就會很大，是以就算出現競争而導緻逾時後，由于逾時時間一樣，它們又會同時開始重試，導緻新一輪的競争，帶來了新的問題。)

這種機制存在一個問題，在java中不能對synchronized同步塊設定逾時時間。你需要建立一個自定義鎖，或使用java5中

java.util.concurrent包下的工具。寫一個自定義鎖類不複雜，但超出了本文的内容。後續的java并發系列會涵蓋自定義鎖的内容。

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

每當一個線程獲得了鎖，會線上程和鎖相關的資料結構中（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）之間鎖占有和請求的關系圖。像這樣的資料結構就可以被用來檢測死鎖。

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

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

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