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

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

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

違反原子性問題

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

違反執(zhí)行順序問題

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

這種實現(xiàn)會降低系統(tǒng)的并發(fā)性，因為所有需要獲取鎖的線程都要去競爭同一個加鎖令牌鎖；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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