在Java中的無死鎖同步實現(xiàn)方法分享！內(nèi)容解析！干貨分享！

線程同步是克服多線程程序中競爭條件的好工具。但是，它也有陰暗面。死鎖：難以發(fā)現(xiàn)、重現(xiàn)和修復的嚴重錯誤。防止它們發(fā)生的唯一可靠方法是正確設計您的代碼，這是本文的主題。我們將看看死鎖的起源，考慮一種發(fā)現(xiàn)現(xiàn)有代碼中潛在死鎖的方法，并提出設計無死鎖同步的實用方法。這些概念將通過一個簡單的演示項目進行說明。

假設讀者已經(jīng)熟悉多線程編程，并且對 Java 中的線程同步原語有很好的理解。在接下來的部分中，我們不會區(qū)分同步語句和鎖 API，使用術(shù)語“鎖”來表示這兩種類型的可重入鎖，在示例中更喜歡前者。

一、死鎖機制

讓我們回顧一下死鎖是如何工作的?？紤]以下兩種方法：

java：

void increment ({
synchronized(lock1) {
synchronized(lock2){
variablel ++;
}
}
}
void decrement ({
synchronized(lock2){
synchronized(lock1) {
variable--;
}
}}

這些方法被有意設計為產(chǎn)生死鎖。讓我們詳細考慮這是如何發(fā)生的。

increment() 和 decrement()基本上由以下5個步驟：

表格1

假設有兩個并行線程，一個執(zhí)行increment()，另一個執(zhí)行decrement()。每個線程的步驟將按正常順序執(zhí)行，但是，如果我們將兩個線程放在一起考慮，一個線程的步驟將與另一個線程的步驟隨機交錯。隨機性來自系統(tǒng)線程調(diào)度程序強加的不可預測的延遲?？赡艿慕豢椖Ｊ交驁鼍胺浅６啵蚀_地說，有 252 種）并且可以分為兩組。第一組是其中一個線程足夠快以獲取兩個鎖（參見表 2）。顯然，這兩種方法中的第 1 步和第 2 步只有在相應的鎖空閑時才能通過，否則，執(zhí)行線程將不得不等待它們的釋放。

表格2

在第二組中，兩個線程都成功獲取了鎖。結(jié)果見表3：該組中的所有案例均成功完成。

表格3

該組中的所有情況都會導致第一個線程等待第二個線程擁有的鎖，而第二個線程等待第一個線程擁有的鎖，因此兩個線程都無法進一步進行：

圖1

這是具有所有典型屬性的經(jīng)典死鎖情況。讓我們概述重要的：

• 至少有兩個線程，每個線程至少占用兩個鎖。
• 死鎖只發(fā)生在特定的線程時序組合中。
• 死鎖的發(fā)生取決于鎖定順序。

第二個屬性意味著死鎖不能隨意重現(xiàn)。此外，它們的再現(xiàn)性取決于操作系統(tǒng)、CPU 頻率、CPU 負載和其他因素。后者意味著軟件測試的概念不適用于死鎖，因為相同的代碼可能在一個系統(tǒng)上完美運行而在另一個系統(tǒng)上失敗。因此，交付正確應用程序的唯一方法是通過設計消除死鎖。這種設計有兩種基本方法，現(xiàn)在讓我們從更簡單的方法開始。

2. 粗粒度同步

從上面列表中的第一個屬性可以看出，如果我們的應用程序中的任何線程都不允許同時持有多個鎖，則不會發(fā)生死鎖。好的，這聽起來像是一個計劃，但是我們應該使用多少鎖以及將它們放在哪里？

最簡單和最直接的答案是用一個鎖保護所有事務。例如，為了保護一個復雜的數(shù)據(jù)對象，您可以將其所有公共方法聲明為同步的。這種方法用于?java.util.Hashtable?. 簡單的代價是由于缺乏并發(fā)而導致的性能損失，因為所有方法都是相互阻塞的。

幸運的是，在許多情況下，粗粒度同步可以以較少限制的方式執(zhí)行，從而允許一些并發(fā)和更好的性能。為了解釋它，我們應該引入一個事務連接變量的概念。假設如果滿足兩個條件中的任何一個，則兩個變量在事務上連接：

1. 存在涉及兩個變量的交易。
2. 兩個變量都連接到第三個變量（傳遞性）。

因此，您首先以這樣一種方式對變量進行分組，即同一組中的任何兩個變量都具有事務性連接，而不同組中的任何兩個變量都沒有。然后通過單獨的專用鎖保護每個組：

圖2

上面的解釋對于“transaction”和“involves”這兩個術(shù)語的確切含義來說有點短，但如果要準確地解釋，那么解釋的篇文章就太長了，所以這篇文章只有留給讀者直覺和經(jīng)驗。

 這種高級粗粒度同步的一個很好的現(xiàn)實例子是?java.util.concurrent.ConcurrentHashMap?. 在這個對象內(nèi)部，有許多相同的數(shù)據(jù)結(jié)構(gòu)（“桶（buckets）”），每個?桶?都由自己的鎖保護。事務被分派到由鍵的哈希碼確定的存儲桶。因此，具有不同密鑰的事務大多會進入不同的存儲桶，這使得它們可以并發(fā)執(zhí)行而不會犧牲線程安全性，由于存儲桶的事務獨立性，這是可能的。

但是，某些解決方案需要比粗粒度同步可以實現(xiàn)的更高級別的并發(fā)性。稍后，我們將考慮如何處理這個問題，但首先，我們需要介紹一種分析同步方案的有效方法。

3. 鎖定圖

假設您需要確定給定的代碼是否包含潛在的死鎖。讓我們稱這種任務為“同步分析”或“死鎖分析”。你會如何處理這個問題？ 

最有可能的是，您會嘗試對線程爭用鎖的所有可能場景進行排序，試圖找出是否存在不良場景。在第 1 節(jié)中，我們采用了如此簡單的方法，結(jié)果發(fā)現(xiàn)場景太多了。即使在最簡單的情況下，也有 252 個，因此徹底檢查它們是不可能的。在實踐中，您可能最終只會考慮幾個場景，并希望您沒有遺漏一些重要的東西。換句話說，公平的死鎖分析無法通過幼稚的方法完成，我們需要一種專門的、更有效的方法。

此方法包括構(gòu)建鎖定圖并檢查它是否存在循環(huán)依賴關系。鎖定圖是顯示鎖和線程在這些鎖上的交互的圖形。此類圖中的每個閉環(huán)都表示可能存在死鎖，并且沒有閉環(huán)保證了代碼的死鎖安全性。

這是繪制鎖定圖的秘訣。它以第 1 節(jié)中的代碼為例：

1. 對于代碼中的每個鎖，在圖表上放置一個相應的節(jié)點；在這個例子中，這些是?lock1?和?lock2?
2. 對于所有線程試圖在已經(jīng)持有鎖 A 的情況下獲取鎖 B 的語句，畫一個從節(jié)點 A 到節(jié)點 B 的箭頭；在該示例中，將有“鎖1 - >鎖2”在?increment()?和?lock2 -> lock1?中?decrement()?。如果一個線程按順序使用多個鎖，則為每兩個連續(xù)的鎖繪制一個箭頭。

第 1 節(jié)中示例的最終圖表如下所示：

圖 3

它有一個閉環(huán)： ? lock1 -> lock2 -> lock1?，它立即告訴我們代碼包含潛在的死鎖。

讓我們再做一個練習。思考以下代碼：

java：

void transaction1 (int amount){
synchronized(lock1) {
synchronized(lock2) {
// do something}
}
void transaction2(int amount){
synchronized(lock2) {
synchronized(lock3) {
// do something}
}
void transaction3(int amount){
synchronized(lock3) {
synchronized(lock1) {
// do zomething}
}

讓我們看看這段代碼是否是死鎖安全的。有3把鎖：?lock1，lock2，lock3?和3條鎖定路徑：?lock1 -> lock2?在?transaction1()?，?lock2 -> lock3?在?transaction2()?，?lock3 -> lock1?在?transaction3()?。

結(jié)果圖如圖 4-A 所示：

圖 4

同樣，此圖立即表明我們的設計包含潛在的死鎖。但是，不僅如此。它還提示我們?nèi)绾涡迯驮O計；我們只需要打破循環(huán)！例如，我們可以交換方法中的鎖?transaction3()?。相應的箭頭改變方向，圖 4-B 中的圖變?yōu)闊o循環(huán)，這保證了固定代碼的死鎖安全性。

現(xiàn)在我們已經(jīng)熟悉了圖表的神奇之處，我們準備繼續(xù)使用更復雜但更有效的方法來設計無死鎖同步。

4. 帶鎖排序的細粒度同步

這一次，我們走的是讓同步盡可能細粒度的路線，希望得到最大可能的事務并發(fā)度作為回報。這種設計基于兩個原則。

第一個原則是禁止任何變量同時參與多個交易。為了實現(xiàn)這一點，我們將每個變量與一個唯一的鎖相關聯(lián)，并通過獲取與相關變量關聯(lián)的所有鎖來啟動每個事務。以下代碼說明了這一點：

java：

void transaction(Item i1，Item i2, Item i3,double amount){
synchronized(i1.lock) {
synchronized(i2.lock){
synchronized(i3.lock) {
// do actual transaction on the items
}
}
}
}

一旦獲得鎖，其他事務就不能訪問這些變量，因此它們不會被并發(fā)修改。這意味著系統(tǒng)中的所有事務都是一致的。同時，允許在不相交變量集上的事務并發(fā)運行。因此，我們獲得了一個高度并發(fā)但線程安全的系統(tǒng)。

但是，這樣的設計會立即導致死鎖的可能性，因為現(xiàn)在我們處理多個線程和每個線程的多個鎖。

然后，第二個設計原則開始發(fā)揮作用，它指出必須以規(guī)范的順序獲取鎖以防止死鎖。這意味著我們將每個鎖與一個唯一的常量索引相關聯(lián)，并始終按照它們的索引定義的順序獲取鎖。將這個原理應用到上面的代碼中，我們得到了細粒度設計的完整說明：

java：

void transaction(Item i1，Item i2，Item i3，double… amounts) {
// Our plan is to use item IDs as canonical indices for locks
Item[] order = {i1, i2, i3} ;
Arrays.sort(order，(a, b) -> Long. compare(a.id,b.id)) ;
synchronized(order [o].lock){
synchronized(order[1].lock){
synchronized(order[2].lock) {
// do actual transaction on the items
}
}
}
}

但是，確定規(guī)范排序確實可以防止死鎖嗎？我們能證明嗎？答案是肯定的，我們可以使用鎖定圖來完成。

假設我們有一個有 N 個變量的系統(tǒng)，所以有 N 個關聯(lián)的鎖，因此圖中有 N 個節(jié)點。如果沒有強制排序，鎖會以隨機順序被抓取，所以在圖中，會有兩個方向的隨機箭頭，并且肯定會存在表示死鎖的閉環(huán)：

圖 5

如果我們強制執(zhí)行鎖排序，從高到低索引的鎖路徑將被排除，所以唯一剩下的箭頭將是那些從左到右的箭頭：

圖 6

無論我們多么努力，我們都不會在這個圖上找到一個閉環(huán)，因為只有當箭頭在兩個方向上時才可能存在閉環(huán)，但事實并非如此。而且，沒有閉環(huán)意味著沒有死鎖。證明是完整的。

好吧，通過使用細粒度鎖和鎖排序，我們可以構(gòu)建一個高并發(fā)、線程安全和無死鎖的系統(tǒng)。但是，提高并發(fā)性是否需要付出代價？讓我們考慮一下。

首先，在低并發(fā)的情況下，與粗粒度的方法相比，存在一定的速度損失。每個鎖捕獲是一個相當昂貴的操作，但細粒度設計假設鎖捕獲至少是兩倍。但是，隨著并發(fā)請求數(shù)量的增加，由于使用了多個 CPU 內(nèi)核，細粒度設計很快就會變得更好。

其次，由于大量的鎖對象，存在內(nèi)存開銷。幸運的是，這很容易解決。如果受保護的變量是對象，我們可以擺脫單獨的鎖對象，并將變量本身用作自己的鎖。否則，例如，如果變量是原始數(shù)組元素，我們可能只需要有限數(shù)量的額外對象。為此，我們定義了從變量 ID 到中等大小的鎖數(shù)組的映射。在這種情況下，鎖必須按它們的實際索引排序，而不是按變量 ID。

最后但并非最不重要的是代碼的復雜性。雖然粗粒度的設計可以通過聲明一些方法同步來完成，細粒度的方法需要編寫相當數(shù)量的相當長的代碼，有時我們甚至可能需要弄亂業(yè)務邏輯。這樣的代碼需要仔細編寫并且更難維護。不幸的是，這個困難無法解決，但結(jié)果值得麻煩，這將在下面演示。

5. 演示項目

要了解提議的設計模式在實際代碼中的外觀，讓我們看一下簡單的演示項目。該項目的目標是構(gòu)建一個模擬銀行一些基本功能的庫。為簡潔起見，它使用一組固定的賬戶，僅實現(xiàn)四種操作：查詢余額、存款、取款和賬戶間資金轉(zhuǎn)移。為了使任務更有趣，要求賬戶余額不能為負，也不能超過某個值。違反這些規(guī)則的交易應該被拒絕。庫 API 在接口MockBank 中定義。

此接口有三種使用上述不同同步方法的實現(xiàn)：

• CoarseGrainedImpl使用粗粒度同步。
• FineGrainedImpl使用細粒度同步的基本版本。
• FineGrainedWithMappingImpl使用細粒度同步的內(nèi)存高效版本。

還有一個對實現(xiàn)的性能和正確性的測試，MockBankCrashTest。每個源文件在類注釋中包含算法的詳細描述。多次測試運行未顯示線程安全違規(guī)或死鎖。在多核系統(tǒng)上，細粒度設計的性能是粗粒度設計的幾倍，正如預期的那樣。

所有項目文件都在這里。

6. 隱形鎖

到目前為止，所提出的設計模式似乎可以自動解決任何同步問題。雖然這并非完全不真實，但存在一些您應該注意的問題。

上述部分中的注意事項雖然本身是正確和有效的，但并未考慮環(huán)境。通常，這是一個錯誤，因為我們的代碼不可避免地要與操作系統(tǒng)和庫進行交互，其中可能存在隱藏的鎖，這些鎖可能會干擾我們的同步代碼，從而導致意外死鎖。讓我們看一個例子?？紤]以下代碼：

java:

private Hashtable<String，Long> db = new Hashtable<>();
private long version;
public void put (String key,long value) {
updateversion (key);
db. put (key,value) ;
}
public long increment (String key){
db.computeIfPresent (key,(k, v)->{
updateversion(k);
return v+1 ;
}):
}
private synchronized void updateversion (String key){
db.put (key+".version", versiontl++);
}

這么一看，這段代碼應該是無死鎖的，因為?updateVersion()?. 但是，這種印象是錯誤的，因為Hashtable實例中實際上存在一個額外的隱藏鎖。調(diào)用鏈?put()-updateVersion()?并?increment()-computeIfPresent()-updateVersion()?以相反的順序獲取這兩個鎖，這會導致潛在的死鎖。

一位有經(jīng)驗的讀者可能會在這里正確地爭辯說，上面的代碼相當蹩腳，并且是故意設計來導致死鎖的。然后，這里是更簡潔的示例，我們嘗試在映射中原子地交換兩個值：

java:

private final Map<Integer，String> map = new ConcurrentHashMap<>();
map.put (1，"1");
map. put (2,“2");}
public void swapalues(Integer key1，Integer key2) {
map.compute(key1，(k1，v1) ->{
return map. put (key2, v1); 
// returns v2
}):
}

這一次，根本沒有鎖，代碼看起來完全合法，但是，我們再次遇到了潛在的死鎖。原因是在內(nèi)部設計?ConcurrentHashMap?，這已在第 2 節(jié)中概述 。以相反的順序調(diào)用?swapValues(1,2)?和?swapValues(2,1)?獲取相應桶的鎖，這意味著代碼可能會死鎖。這就是文檔  ?ConcurrentHashMap.compute()?強烈不鼓勵嘗試從回調(diào)中更改地圖的原因。不幸的是，在許多情況下，文檔中缺少此類警告。

如上例所示，對隱藏鎖的干擾最有可能發(fā)生在回調(diào)方法中。因此，建議保持回調(diào)簡短、簡單且不調(diào)用同步方法。如果這是不可能的，您應該始終牢記執(zhí)行回調(diào)的線程可能持有一個或多個隱藏鎖，并相應地計劃同步。

結(jié)論

在本文中，我們探討了多線程編程中的死鎖問題。我們發(fā)現(xiàn)如果按照一定的設計模式編寫同步代碼，可以完全避免死鎖。我們還研究了此類設計為何以及如何工作，其適用性的限制是什么，以及如何有效地發(fā)現(xiàn)和修復現(xiàn)有代碼中的潛在死鎖。預計所提供的材料為設計完美的無死鎖同步提供了足夠的實用指南。

所有源文件都可以作為zip 存檔從 Github 下載。