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

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

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

違反原子性問題

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

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

一些程序語句可能會(huì)因?yàn)樽泳€程立即啟動(dòng)早于父線程中的后續(xù)代碼，或者是多個(gè)線程并發(fā)執(zhí)行等情況，造成程序運(yùn)行順序和期望不符導(dǎo)致產(chǎn)生bug。

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

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

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

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

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

互斥。資源被競(jìng)爭(zhēng)性地訪問，這里的資源可以理解為鎖；

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

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

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

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

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

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

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

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

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

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

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

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

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

這種實(shí)現(xiàn)會(huì)降低系統(tǒng)的并發(fā)性，因?yàn)樗行枰@取鎖的線程都要去競(jìng)爭(zhēng)同一個(gè)加鎖令牌鎖；

并且因?yàn)橐诔绦虻囊婚_始就獲取所有需要的鎖，這就導(dǎo)致了線程持有鎖的時(shí)間超出了實(shí)際需要，很多鎖資源被長(zhǎng)時(shí)間的持有所浪費(fèi)，而其他線程只能等待之前的線程執(zhí)行結(jié)束后統(tǒng)一釋放所有鎖；

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

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

同樣的，這個(gè)方案也會(huì)有自己的缺陷：

雖然這種方式可以避免死鎖，但是如果幾個(gè)互相存在競(jìng)爭(zhēng)的線程不斷地放棄、重試、放棄，那么就會(huì)導(dǎo)致活鎖問題（livelock）。在這種情況下，雖然線程沒有因?yàn)殒i沖突被卡死，但是仍然會(huì)被阻塞相當(dāng)長(zhǎng)的時(shí)間甚至一直處于重試當(dāng)中。

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

還是因?yàn)槌绦虻姆庋b性，在一個(gè)模塊中難以釋放其他模塊中已經(jīng)獲取到的鎖。

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

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

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

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

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

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

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

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

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

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

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

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

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