在Java中的無死鎖同步如何實現

這篇文章主要介紹“在Java中的無死鎖同步如何實現”的相關知識，小編通過實際案例向大家展示操作過程，操作方法簡單快捷，實用性強，希望這篇“在Java中的無死鎖同步如何實現”文章能幫助大家解決問題。

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

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

一、死鎖機制

讓我們回顧一下死鎖是如何工作的。考慮以下兩種方法：

java：

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

這些方法被有意設計為產生死鎖。讓我們詳細考慮這是如何發生的。

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

表格1

假設有兩個并行線程，一個執行increment()，另一個執行decrement()。每個線程的步驟將按正常順序執行，但是，如果我們將兩個線程放在一起考慮，一個線程的步驟將與另一個線程的步驟隨機交錯。隨機性來自系統線程調度程序強加的不可預測的延遲。可能的交織模式或場景非常多（準確地說，有 252 種）并且可以分為兩組。第一組是其中一個線程足夠快以獲取兩個鎖（參見表 2）。顯然，這兩種方法中的第 1 步和第 2 步只有在相應的鎖空閑時才能通過，否則，執行線程將不得不等待它們的釋放。

表格2

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

表格3

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

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

• 至少有兩個線程，每個線程至少占用兩個鎖。

• 死鎖只發生在特定的線程時序組合中。

• 死鎖的發生取決于鎖定順序。

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

2. 粗粒度同步

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

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

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

1. 存在涉及兩個變量的交易。

2. 兩個變量都連接到第三個變量（傳遞性）。

因此，您首先以這樣一種方式對變量進行分組，即同一組中的任何兩個變量都具有事務性連接，而不同組中的任何兩個變量都沒有。

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

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

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

3. 鎖定圖

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

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

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

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

1. 對于代碼中的每個鎖，在圖表上放置一個相應的節點；在這個例子中，這些是lock1和lock2

2. 對于所有線程試圖在已經持有鎖 A 的情況下獲取鎖 B 的語句，畫一個從節點 A 到節點 B 的箭頭；在該示例中，將有“鎖1 - >鎖2”在increment()和lock2 -> lock1中decrement()。如果一個線程按順序使用多個鎖，則為每兩個連續的鎖繪制一個箭頭。

第 1 節中示例的最終圖表如下所示：

圖 3

它有一個閉環：  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()。

同樣，此圖立即表明我們的設計包含潛在的死鎖。但是，不僅如此。它還提示我們如何修復設計；我們只需要打破循環！例如，我們可以交換方法中的鎖transaction3()。相應的箭頭改變方向，圖 4-B 中的圖變為無循環，這保證了固定代碼的死鎖安全性。

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

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

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

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

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
}
}
}
}

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

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

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

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
}
}
}
}

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

假設我們有一個有 N 個變量的系統，所以有 N 個關聯的鎖，因此圖中有 N 個節點。如果沒有強制排序，鎖會以隨機順序被抓取

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

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

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

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

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

5. 演示項目

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

此接口有三種使用上述不同同步方法的實現：

• CoarseGrainedImpl使用粗粒度同步。

• FineGrainedImpl使用細粒度同步的基本版本。

• FineGrainedWithMappingImpl使用細粒度同步的內存高效版本。

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

所有項目文件都在這里。

6. 隱形鎖

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

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

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實例中實際上存在一個額外的隱藏鎖。調用鏈put()-updateVersion()并increment()-computeIfPresent()-updateVersion()以相反的順序獲取這兩個鎖，這會導致潛在的死鎖。

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

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
}):
}

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

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

關于“在Java中的無死鎖同步如何實現”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識，可以關注億速云行業資訊頻道，小編每天都會為大家更新不同的知識點。