摘要：雖然本文是一篇介紹死鎖及其解決方式的文章，但是對于多線程程序中的非死鎖問題我們也應該有所了解，這樣才能寫出正確且高效的多線程程序。

死鎖是多線程編程或者說是并發編程中的一個經典問題，也是我們在實際工作中很可能會碰到的問題。相信大部分讀者對“死鎖”這個詞都是略有耳聞的，但從我對后端開發崗位的面試情況來看很多同學往往對死鎖都還沒有系統的了解。雖然“死鎖”聽起來很高深，但是實際上已經被研究得比較透徹，大部分的解決方法都非常成熟和清晰，所以大家完全不用擔心這篇文章的難度。

雖然本文是一篇介紹死鎖及其解決方式的文章，但是對于多線程程序中的非死鎖問題我們也應該有所了解，這樣才能寫出正確且高效的多線程程序。多線程程序中的非死鎖問題主要分為兩類：

違反原子性問題

一些語句在底層會被分為多個底層指令運行，所以在多個線程之間這些指令就可能會存在穿插，這樣程序的行為就可能會與預期不符造成bug。

違反執行順序問題

一些程序語句可能會因為子線程立即啟動早于父線程中的后續代碼，或者是多個線程并發執行等情況，造成程序運行順序和期望不符導致產生bug。

這兩大非死鎖多線程問題及其解決方案在之前的文章《多線程中那些看不到的陷阱》里都有詳細的介紹，感興趣的讀者可以了解一下。

接下來就讓我們開始消滅死鎖吧！

死鎖，顧名思義就是導致線程卡死的鎖沖突，例如下面的這種情況：

可以看出，上面的兩個線程已經互相卡死了，線程t1在等待線程t2釋放鎖B，而線程t2在等待線程t1釋放鎖A。兩個線程互不相讓也就沒有一個線程可以繼續往下執行了。這種情況下就發生了死鎖。

上面的情況只是死鎖的一個例子，我們可以用更精確的方式描述死鎖出現的條件：

互斥。資源被競爭性地訪問，這里的資源可以理解為鎖；

持有并等待。線程持有已經分配給他們的資源，同時等待其他的資源；

不搶占。線程已經獲取到的資源不會被其他線程強制搶占；

環路等待。線程之間存在資源的環形依賴鏈，每個線程都依賴于鏈條中的下一個線程釋放必要的資源，而鏈條的末尾又依賴了鏈條頭部的線程，進入了一個循環等待的狀態。

上面這四個都是死鎖出現的必要條件，如果其中任何一個條件不滿足都不會出現死鎖。雖然這四個條件的定義看起來非常的理論和官方，但是在實際的編程實踐中，我們正是在死鎖的這四個必要條件基礎上構建出解決方案的。所以這里不妨思考一下這四個條件各自的含義，想一想如果去掉其中的一個條件死鎖是否還能發生，或者為什么不能發生。

了解了死鎖的概念和四個必要條件之后，我們下面就正式開始解決死鎖問題了。對于死鎖問題，我們最希望能夠達到的當然是完全不發生死鎖問題，也就是在死鎖發生之前就阻止它。

那么想要阻止死鎖的發生，我們自然是要讓死鎖無法成立，最直接的方法當然是破壞掉死鎖出現的必要條件。只要有任何一個必要條件無法成立，那么死鎖也就沒辦法發生了。

實踐中最有效也是最常用的一種死鎖阻止技術就是鎖排序，通過對加鎖的操作進行排序我們就能夠破壞環路等待條件。例如當我們需要獲取數組中某一個位置對應的鎖來修改這個位置上保存的值時，如果需要同時獲取多個位置對應的鎖，那么我們就可以按位置在數組中的排列先后順序統一從前往后加鎖。

試想一下如果程序中所有需要加鎖的代碼都按照一個統一的固定順序加鎖，那么我們就可以想象鎖被放在了一條不斷向前延伸的直線上，而因為加鎖的順序一定是沿著這條線向下走的，所以每條線程都只能向前加鎖，而不能再回頭獲取已經在后面的鎖了。這樣一來，線程只會向前單向等待鎖釋放，自然也就無法形成一個環路了。

其實大部分死鎖解決方法不止可以用于多線程編程領域，還可以擴展到更多的并發場景下。比如在數據庫操作中，如果我們要對某幾行數據執行更新操作，那么就會獲取這幾行數據所對應的鎖，我們同樣可以通過對數據庫更新語句進行排序來阻止在數據庫層面發生的死鎖。

但是這種方案也存在它的缺點，比如在大型系統當中，不同模塊直接解耦和隔離得非常徹底，不同模塊的研發同學之間都不清楚具體的實現細節，在這樣的情況下就很難做到整個系統層面的全局鎖排序了。在這種情況下，我們可以對方案進行擴充，例如Linux在內存映射代碼就使用了一種鎖分組排序的方式來解決這個問題。鎖分組排序首先按模塊將鎖分為了不同的組，每個組之間定義了嚴格的加鎖順序，然后再在組內對具體的鎖按規則進行排序，這樣就保證了全局的加鎖順序一致。在Linux的對應的源碼頂部，我們可以看到有非常詳盡的注釋定義了明確的鎖排序規則。

這種解決方案如果規模過大的話即使可以實現也會非常的脆弱，只要有一個加鎖操作沒有遵守鎖排序規則就有可能會引發死鎖。不過在像微服務之類解耦比較充分的場景下，只要架構拆分合理，任務模塊盡可能小且不會將加鎖范圍擴大到模塊之外，那么鎖排序將是一種非常實用和便捷的死鎖阻止技術。

想要破壞持有并等待條件，我們可以一次性原子性地獲取所有需要的鎖，比如通過一個專門的全局鎖作為加鎖令牌控制加鎖操作，只有獲取了這個鎖才能對其他鎖執行加鎖操作。這樣對于一個線程來說就相當于一次性獲取到了所有需要的鎖，且除非等待加鎖令牌否則在獲取其他鎖的過程中不會發生鎖等待。

這樣的解決方案雖然簡單粗暴，但這種簡單粗暴也帶來了一些問題：

這種實現會降低系統的并發性，因為所有需要獲取鎖的線程都要去競爭同一個加鎖令牌鎖；

并且因為要在程序的一開始就獲取所有需要的鎖，這就導致了線程持有鎖的時間超出了實際需要，很多鎖資源被長時間的持有所浪費，而其他線程只能等待之前的線程執行結束后統一釋放所有鎖；

另一方面，現代程序設計理念要求我們提高程序的封裝性，不同模塊之間的細節要互相隱藏，這就使得在一個統一的位置一次性獲取所有鎖變得不再可能。

如果一個線程已經獲取到了一些鎖，那么在這個線程釋放鎖之前這些鎖是不會被強制搶占的。但是為了防止死鎖的發生，我們可以選擇讓線程在獲取后續的鎖失敗時主動放棄自己已經持有的鎖并在之后重試整個任務，這樣其他等待這些鎖的線程就可以繼續執行了。

同樣的，這個方案也會有自己的缺陷：

雖然這種方式可以避免死鎖，但是如果幾個互相存在競爭的線程不斷地放棄、重試、放棄，那么就會導致活鎖問題（livelock）。在這種情況下，雖然線程沒有因為鎖沖突被卡死，但是仍然會被阻塞相當長的時間甚至一直處于重試當中。

這個問題的一種解決方式是給任務重試添加一個隨機的延遲時間，這樣就能大大降低任務沖突的概率了。在一些接口請求框架中也使用了這種技巧來分散服務高峰期的請求重試操作，防止服務陷入阻塞、崩潰、阻塞的惡性循環。

還是因為程序的封裝性，在一個模塊中難以釋放其他模塊中已經獲取到的鎖。

雖然每一個方案都有自己的缺陷，但是在適合它們的場景下，它們都能發揮出巨大的作用。

在之前的文章中，我們已經了解了一種與鎖完全不同的同步方式CAS。通過CAS提供的原子性支持，我們可以實現各種無鎖數據結構，不僅避免了互斥鎖所帶來的開銷和復雜性，也由此避開了我們一直在討論的死鎖問題。

AtomicInteger類中就大量使用了CAS操作來實現并發安全，例如incrementAndGet()方法就是用Unsafe類中基于CAS的原子累加方法getAndAddInt來實現的。下面是Unsafe類的getAndAddInt方法實現：

/**
 * 增加指定字段值并返回原值
 * 
 * @param obj           目標對象
 * @param valueOffset   目標字段的內存偏移量
 * @param increment     增加值
 * @return  字段原值
 */
public final int getAndAddInt(Object obj, long valueOffset, int increment) {
    // 保存字段原值的變量
    int oldValue;
    do {
        // 獲取字段原值
        oldValue = this.getIntVolatile(obj, valueOffset);

        // obj和valueOffset唯一指定了目標字段所對應的內存區域
        // while條件中不斷調用CAS方法來對目標字段值進行增加，并保證字段的值沒有被其他線程修改
        // 如果在修改過程中其他線程修改了這個字段的值，那么CAS操作失敗，循環語句會重試操作
    } while(!this.compareAndSwapInt(obj, valueOffset, oldValue, oldValue + increment));

    // 返回字段的原值
    return oldValue;
}

上面代碼中的compareAndSwapInt方法就是我們說的CAS操作（Compare And Swap），我們可以看到，CAS在每次執行時不一定會成功。如果執行CAS操作時目標字段的值已經被別的線程修改了，那么這次CAS操作就會失敗，循環語句將會在CAS操作失敗的情況下不斷重試同樣的操作。這種不斷重試的方式就被稱為自旋，在jvm當中對互斥鎖的等待也會通過少量的自旋操作來進行優化。

不過如果一個變量同時被多個線程以CAS方式修改，那么就有可能導致出現活鎖，多個線程將會一直不斷重試CAS操作。所以CAS操作的成本和數據競爭的激烈程度密切相關，在一些競爭非常激烈的情況下，CAS操作的成本甚至會超過互斥鎖。

除了累加整型值這樣的簡單場景之外，還有更多更復雜的無鎖(lock-free)數據結構，例如java.util.concurrent包中的ConcurrentLinkedDeque雙端隊列類就是一個無鎖的并發安全鏈表實現，有興趣的讀者可以了解一下。

這種方法同樣可以用在數據庫操作上，當我們執行update語句時可以在where子句中添加上一些字段的舊值作為條件，比如update t_xxxx set value = , version = version + 1 where id = xxx and version = 10，這樣我們就可以通過update語句返回的影響行數是不是0來判斷更新操作有沒有成功了，這是不是和CAS很相似？

有時，我們并不需要完全阻止死鎖的發生，而是可以通過其他的手段來控制死鎖的影響。就像如果新的治療手段可以使癌癥病人繼續活七八十年，那么癌癥也就沒有那么可怕了。

還有一種解決死鎖的方法就是讓死鎖發生，之后再解決它，就像電腦死機以后直接重啟一樣。使用這種方法我們可以這么做：如果多個線程出現了死鎖的情況，那么我們就殺死足夠多的線程使系統恢復到可運行狀態。在我們常用的關系型數據庫中使用的就是這種方法，數據庫會周期性地使用探測器創建資源圖，然后檢查其中是否存在循環。如果探測到了循環（死鎖），那么數據庫就會根據估算的執行成本高低殺死可以解決死鎖問題的盡可能成本最小的線程。

數據庫在被外部應用調用的過程中是沒辦法獲知外部應用的邏輯細節的，所以自然也就沒辦法用之前說的種種方法來解決死鎖問題，只能通過事后檢測并恢復來對死鎖問題做最低限度的保障。但是我們可以在我們的應用程序中應用更多的解決方案，從更上層解決死鎖問題。

在這篇文章中，我們從死鎖的概念出發，首先介紹了死鎖是什么和死鎖發生的四個必要條件。然后通過破壞任意一個必要條件產生了四種不同的阻止死鎖的解決方案，最后介紹了另外一種死鎖解決方法——在死鎖發生后再探測并恢復系統運行。相信大家可以在不同的場景中都能找到適合該場景的解決方案，但是鎖本質上是容易引入問題的，所以如果不是確有必要，最好不要貿然用鎖來進行處理。