一、Mutex鎖簡介

在linux內(nèi)核中，互斥量（mutex，即mutual exclusion）是一種保證串行化的睡眠鎖機制。和spinlock的語義類似，都是允許一個執(zhí)行線索進入臨界區(qū)，不同的是當(dāng)無法獲得鎖的時候，spinlock原地自旋，而mutex則是選擇掛起當(dāng)前線程，進入阻塞狀態(tài)。正因為如此，mutex無法在中斷上下文使用。和mutex更類似的機制（無法獲得鎖時都會阻塞）是binary semaphores，當(dāng)然，mutex有更嚴格的使用規(guī)則。

• 1、只有mutex的owner可以才可以釋放鎖
• 2、不可以多次釋放同一把鎖
• 3、不允許重復(fù)獲取同一把鎖，否則會死鎖
• 4、必須使用mutex初始化API來完成鎖的初始化，不能使用類似memset或者memcp之類的函數(shù)進行mutex初始化
• 5、不可以多次重復(fù)對mutex鎖進行初始化
• 6、線程退出后必須釋放自己持有的所有mutex鎖

當(dāng)配置了DEBUG_MUTEXES的時候，內(nèi)核會對上面的規(guī)則進行檢查，防止用戶誤用mutex，產(chǎn)生各種問題。

下面是一個簡單的mutex工作原理圖：

傳統(tǒng)的mutex只需要一個狀態(tài)標(biāo)記和一個等待隊列就OK了，等待隊列中是一個個阻塞的線程，thread owner當(dāng)前持有mutex，當(dāng)它離開臨界區(qū)釋放鎖的時候，會喚醒等待隊列中第一個線程（top waiter），這時候top waiter會去競爭持鎖，如果成功，那么從等待隊列中摘下，成為owner。如果失敗，繼續(xù)保持阻塞狀態(tài)，等待owner釋放鎖的時候喚醒它。在owner task持鎖過程中，如果有新的任務(wù)來競爭mutex，那么就會進入阻塞狀態(tài)并插入等待隊列的尾部。

相對于傳統(tǒng)的mutex，linux內(nèi)核進行了一些樂觀自旋的優(yōu)化，也就是說當(dāng)線程持鎖失敗的時候，可以選擇在mutex狀態(tài)標(biāo)記上自旋，等待owner釋放鎖，也可以選擇進入阻塞狀態(tài)并掛入等待隊列。具體如何選擇是在自旋等待的時間開銷和進程上下文切換的開銷之間進行平衡。此外為了防止多個線程自旋帶來的性能問題，mutex的樂觀自旋機制還引入了MCS鎖，后面章節(jié)我們會詳細描述。

二、數(shù)據(jù)結(jié)構(gòu)

1、互斥量對象

互斥量對象用struct mutex來抽象，其成員描述如下：

大部分的成員都非常好理解，除了osq這個成員，其工作原理示意圖如下：

字如其名，Optimistic spin queue就是樂觀自旋隊列的意思，也就是形成一組處于自旋狀態(tài)的任務(wù)隊列。和等待隊列不一樣，這個隊列中的任務(wù)都是當(dāng)前正在執(zhí)行的任務(wù)。Osq并沒有直接將這些任務(wù)的task struct形成隊列結(jié)構(gòu)，而是把per-CPU的mcs lock對象串聯(lián)形成隊列。Mcs lock中有cpu number，通過這些cpu number可以定位到指定cpu上的current thread，也就定位到了自旋的任務(wù)。

【文章福利】小編推薦自己的Linux內(nèi)核技術(shù)交流群:【865977150】整理了一些個人覺得比較好的學(xué)習(xí)書籍、視頻資料共享在群文件里面，有需要的可以自行添加哦?。。∏?00名進群領(lǐng)取，額外贈送一份價值699的內(nèi)核資料包（含視頻教程、電子書、實戰(zhàn)項目及代碼)

雖然都是自旋，但是自旋方式并不一樣。Osq隊列中的頭部節(jié)點是持有osq鎖的，只有該任務(wù)處于對mutex的owner進行樂觀自旋的狀態(tài)（我們稱之mutex樂觀自旋）。Osq隊列中的其他節(jié)點都是自旋在自己的mcs lock上（我們稱之mcs樂觀自旋）。當(dāng)頭部的mcs lock釋放掉后（結(jié)束mutex樂觀自旋，持有了mutex鎖），它會將mcs lock傳遞給下一個節(jié)點，從而讓spinner隊列上的任務(wù)一個個的按順序進入mutex的樂觀自旋，從而避免了cache-line bouncing帶來的性能開銷。

2、等待任務(wù)對象

由于是sleep lock，我們需要把等待的任務(wù)掛入隊列。在內(nèi)核中，Struct mutex_waiter用來抽象等待mutex的任務(wù)，其成員描述如下：

3、MCS鎖對象

在linux內(nèi)核中，我們對睡眠鎖（例如mutex、rwsem）進行了樂觀自旋的優(yōu)化，這涉及到MCS lock，struct optimistic_spin_node用來抽象樂觀自旋的MCS lock，其成員描述如下：

三、外部接口

Mutex模塊的外部接口API如下：

四、嘗試獲取鎖

和mutex_lock不一樣，mutex_trylock只是嘗試獲取鎖，如果成功，那么自然是好的，直接返回true，如果失敗，也不會阻塞，只是返回false就可以了。代碼主邏輯在__mutex_trylock_or_owner函數(shù)中，如下：

1. 對于mutex的owner成員，它是一個原子變量，我們采用了大量的原子操作來訪問或者更新它。然而判斷持鎖需要一連串的操作，我們并沒有采用同步機制（例如自旋鎖）來保護這一段的對owner成員操作，因此，我們這些操作放到一個for循環(huán)中，在操作的結(jié)尾處會判斷是否有其他線程插入修改了owner成員，如果中間有其他線程插入，那么就需要重新來過。
2. 如果task非空（task變量保存了owner中去掉flag部分的任務(wù)指針），并且也不等于current thread，那么說明mutex鎖被其他線程持有，還沒有釋放鎖（也有可能在是否鎖的時候，把鎖直接轉(zhuǎn)交給了其他線程），因此直接break跳出循環(huán)，持鎖失敗。
3. 如果task等于current thread，而且設(shè)置了MUTEX_FLAG_PICKUP的標(biāo)記，那么說明持鎖線程已經(jīng)把該mutex鎖轉(zhuǎn)交給了本線程，等待本線程來拾取。如果沒有MUTEX_FLAG_PICKUP標(biāo)記，那么也是直接break跳出循環(huán)，遞歸持鎖失敗。
4. 有兩種情況會走到這里的時候，一種情況是task為空，說明該mutex鎖處于unlocked狀態(tài)。另外一種情況是task非空，等于current thread，并且mutex發(fā)生了handoff，該鎖被轉(zhuǎn)交給當(dāng)前試圖持鎖的線程。無論哪種情況，都可以去執(zhí)行持鎖操作了。
5. 調(diào)用atomic_long_cmpxchg_acquire嘗試獲取鎖，如果成功獲取了鎖（沒有其他線程插入修改owner這個原子變量），返回NULL。如果owner發(fā)生了變化，說明中間有其他線程插入，那么重新來過。

五、獲取mutex鎖

mutex_lock代碼如下：

這里的might_sleep說明調(diào)用mutex_lock函數(shù)有可能會因為未能獲取到mutex鎖而進入阻塞狀態(tài)。在原子上下文中（中斷上下文、軟中斷上下文、持有自旋鎖、禁止搶占等），我們不能調(diào)用可以引起阻塞的函數(shù)，因此在might_sleep函數(shù)中嵌入了這個檢查，當(dāng)原子上下文中調(diào)用mutex_lock函數(shù)的時候，內(nèi)核會打印出內(nèi)核棧的信息，從而定位這個異常。

當(dāng)然，這個功能是在設(shè)置CONFIG_DEBUG_ATOMIC_SLEEP選項的情況下才生效的，如果沒有設(shè)置這個選項，might_sleep函數(shù)退化為might_resched函數(shù)。在配置了搶占式內(nèi)核（CONFIG_PREEMPT）或者非搶占式內(nèi)核（CONFIG_PREEMPT_NONE）的情況下，might_resched是空函數(shù)。

在配置了主動搶占式內(nèi)核（CONFIG_PREEMPT_VOLUNTARY）的情況下，might_resched會調(diào)用_cond_resched函數(shù)來主動觸發(fā)一次搶占。

主動搶占式內(nèi)核通過在might_sleep函數(shù)中增加了潛在的調(diào)度點實現(xiàn)了比非搶占式內(nèi)核更好的延遲特性，同時確保搶占帶來的進程切換開銷低于搶占式內(nèi)核。

Mutex是一種睡眠鎖，如果未能獲取鎖，那么當(dāng)前線程會阻塞。不過也許我們試圖獲取的mutex還處于空閑狀態(tài)，因此通過__mutex_trylock_fast來嘗試獲取mutex（mutex_lock的快速路徑）：

atomic_long_try_cmpxchg_acquire函數(shù)有三個參數(shù)，從左到右分別是value指針，old指針和new。該函數(shù)會對比*value和*old指針中的數(shù)值，如果相等執(zhí)行賦值*value=new同時返回true。如果不相等，不執(zhí)行賦值操作，直接返回false。

如果lock->owner的值等于0（即不僅task struct地址等于0，所有的flag也要等于0），那么將當(dāng)前線程的task struct的指針賦值給lock->owner，表示該mutex鎖已經(jīng)被當(dāng)前線程持有。如果lock->owner的值不等于0，表示該mutex鎖已經(jīng)被其他線程持有或者鎖正在傳遞給top waiter線程，當(dāng)前線程需要阻塞等待。需要特別說明的是上面描述的操作（比較和賦值）都是原子操作，不能有任何指令插入其中。

在未能獲取mutex鎖的情況下，我們需要調(diào)用__mutex_lock_slowpath函數(shù)進入慢速路徑。由于會進入睡眠，因此這里需要明確當(dāng)前線程需要處于的阻塞狀態(tài)，主要有三種狀態(tài)：D狀態(tài)、S狀態(tài)和KILLABLE。

當(dāng)調(diào)用不同的持鎖API的時候，當(dāng)前線程可以處于各種不同的狀態(tài)。

對于mutex_lock（大部分場景）當(dāng)前線程會進入D狀態(tài)。主要的代碼邏輯在__mutex_lock_common函數(shù)中，我們分段解讀（省略wait/wound和調(diào)試部分的代碼）：

__mutex_trylock用來再次嘗試獲取鎖，mutex_optimistic_spin則是mutex樂觀自旋（Optimistic spinning）部分的代碼。這兩個操作只要有其一能成功獲取mutex鎖，那么就直接返回了。由于沒有進入阻塞狀態(tài)，因此這個路徑也叫做中速路徑。

__mutex_trylock在上一節(jié)已經(jīng)講解了，不再贅述。樂觀自旋的思路是因為mutex鎖可能是被其他CPU上正在執(zhí)行中的線程持有，如果臨界區(qū)比較短，那么有可能該mutex鎖很快就被釋放。這時候，與其進行一次上下文切換，還不如自旋等待，畢竟上下文切換的開銷也是不小的。樂觀自旋機制底層使用的是MCS鎖，具體的細節(jié)我們會在其他文檔中描述。

慢速路徑的代碼如下（省略部分代碼）：

A、所謂慢速路徑其實就是阻塞當(dāng)前線程，這里將current task掛入mutex的等待隊列的尾部。這樣的操作讓所有等待mutex的任務(wù)按照時間的先后順序排列起來，當(dāng)mutex被釋放的時候，會首先喚醒隊首的任務(wù)，即最先等待的任務(wù)最先被喚醒。此外，在向空隊列插入第一個任務(wù)的時候，會給mutex flag設(shè)置上MUTEX_FLAG_WAITERS標(biāo)記，表示已經(jīng)有任務(wù)在等待這個mutex鎖了。

B、進入阻塞狀態(tài)，觸發(fā)一次調(diào)度。由于目前執(zhí)行上下文處于關(guān)閉搶占狀態(tài)，因此這里的調(diào)度使用了關(guān)閉搶占版本的schedule函數(shù)。

C、該任務(wù)被喚醒之后，如果是等待隊列中的第一個任務(wù)，即top waiter，那么需要給該mutex設(shè)置MUTEX_FLAG_HANDOFF，這樣即便本次喚醒后無法獲取到mutex（有些在該mutex上樂觀自旋的任務(wù)可能會搶先獲得鎖），那么下一次owner釋放鎖的時候，看到這個handoff標(biāo)記也會進行鎖的交接，不再是大家搶來搶去。通過這個機制，我們可以防止spinner隊列中的任務(wù)搶占CPU資源，餓死waiter隊列中的任務(wù)。

D、如果獲取到mutex，那么就退出循環(huán)，否則繼續(xù)進入阻塞狀態(tài)等待。如果是隊列中的第一個waiter，那么如果__mutex_trylock失敗，那么就進入樂觀自旋過程，這樣會有更大的機會成功獲取mutex鎖。

六、樂觀自旋

Mutex樂觀自旋的代碼位于mutex_optimistic_spin函數(shù)中，進入樂觀自旋函數(shù)的線程可能有下面幾個結(jié)果：

1、成功獲取osq鎖，進入mutex樂觀自旋狀態(tài)，當(dāng)owner釋放mutex鎖后，該線程結(jié)束樂觀自旋，成功持有了mutex，返回true

2、未能獲取osq鎖，在自己的MCS鎖上樂觀自旋。一旦成功持鎖，同步驟1

3、在MCS鎖或者mcs鎖樂觀自旋的時候，由于各種原因（例如owner進入阻塞狀態(tài)）而無法繼續(xù)樂觀自旋，那么mutex_optimistic_spin函數(shù)返回false，告知調(diào)用者樂觀自旋失敗，進入等待隊列。

我們分兩段來解析。首先來看第一段：

調(diào)用mutex_optimistic_spin函數(shù)的場景有兩個，一個是waiter等于NULL，這是發(fā)生在mutex_lock的早期，這時候試圖持鎖的線程還沒有掛入等待隊列，因此waiter等于NULL。另外一個場景是持鎖未果，掛入等待隊列，然后被喚醒之后的樂觀自旋。這時候試圖持鎖的線程已經(jīng)掛入等待隊列，因此waiter非空。在這種場景下，剛喚醒的top waiter線程會給與優(yōu)待，因此不需要持有osq鎖就可以長驅(qū)直入，進入樂觀自旋。

A、當(dāng)waiter為空時，因為是正常路徑的持鎖請求，所以在樂觀自旋之前需要持有osq鎖，只有獲得了osq鎖，當(dāng)前線程才能進入mutex樂觀自旋的過程。否則只能是在自己的MCS鎖上自旋等待。

B、是否樂觀自旋等待mutex可以從兩個視角思考：一方面，如果本cpu已經(jīng)設(shè)置了need resched標(biāo)記，那說明有其他任務(wù)想要搶占當(dāng)前試圖持鎖的任務(wù)。那么current task何必樂觀自旋呢，趕緊的去sleep為其他任務(wù)讓路吧。另外一方面需要從owner的行為來判斷。如果owner正在其他cpu歡暢運行，那么可以考慮進入樂觀自旋過程。

C、在基于共享內(nèi)存的多核計算系統(tǒng)中，mutex的實現(xiàn)是通過一個共享變量（owner成員）和一個隊列來完成復(fù)雜的控制的。如果有多個cpu上的線程同時樂觀自旋在這個共享變量上，那么就會出現(xiàn)緩存踩踏現(xiàn)象。為了解決這個問題，我們控制不能讓太多的線程進入mutex樂觀自旋狀態(tài)（輪詢owner成員），只有那些獲取了osq鎖的線程才能進入。未能持osq鎖的線程會進入mcs鎖的樂觀自旋過程，等待osq鎖的owner（當(dāng)前在mutex樂觀自旋）釋放osq鎖。關(guān)于osq鎖的細節(jié)我們在其他文章中描述。

完成了持osq鎖之后（或者是被喚醒的top waiter線程，它會掠過osq持鎖過程），我們就可以進入mutex樂觀自旋了，代碼如下：

A、首先還是調(diào)用__mutex_trylock_or_owner試圖獲取mutex鎖，如果返回的owner非空（需要注意的是：這里的owner變量不包括mutex flag部分），那么說明mutex鎖還在owner task手中。如果owner是空指針，說明原來持有鎖的owner已經(jīng)釋放鎖，同時這也就說明當(dāng)前線程持鎖成功，因此退出樂觀自旋的循環(huán)。需要注意的是在退出mutex樂觀自旋后會釋放osq鎖，從而會讓spinner隊列中的下一個mcs鎖自旋的任務(wù)進入mutex樂觀自旋狀態(tài)。

B、如果__mutex_trylock_or_owner返回了非空owner，說明當(dāng)前線程獲取鎖失敗，那么可以進入mutex樂觀自旋了。所謂自旋不是自旋在spinlock上，而是不斷的循環(huán)檢測鎖的owner task是否發(fā)生變化以及owner task的運行狀態(tài)。如果owner阻塞了或者當(dāng)前cpu有resched的需求（可能喚醒更高級任務(wù)），那么就停止自旋，返回false，走入fail_unlock流程。

C、如果mutex鎖的owner task發(fā)生變化（例如變成NULL）則mutex_spin_on_owner函數(shù)返回true，則說明可以跳轉(zhuǎn)到for循環(huán)處再次嘗試獲取鎖并進行樂觀自旋。

七、釋放mutex鎖

mutex_unlock的代碼如下：

如果一個線程獲取了某個mutex鎖之后，沒有任何其他的線程試圖進入臨界區(qū)，那么這時候mutex的owner成員就是該線程的task struct地址，并且所有的mutex flag都是clear的。在這種情況下，將mutex的owner成員清零即可，不需要額外的操作，我們稱之解鎖快速路徑（__mutex_unlock_fast）。

當(dāng)然，如果有其他線程在競爭該mutex鎖，那么情況會更復(fù)雜一些，這時候我們進入慢速路徑（_mutex_unlock_slowpath），慢速路徑的邏輯分成兩段：一段是釋放mutex鎖，另外一段是喚醒top waiter線程。我們首先一起看第一段的代碼，如下:

A、如果mutex flag中設(shè)定了handoff標(biāo)記，那么說明owner在釋放鎖的時候要主動的把鎖的owner傳遞給top waiter，不能讓后來插入的樂觀自旋的線程餓死top waiter。因此這時候我們還不能放鎖，需要在__mutex_handoff函數(shù)中釋放鎖給top waiter。

B、將owner的task struct地址部分清掉，這也就是意味著owner task放棄了持鎖。這時候，如果有樂觀自旋的任務(wù)在輪詢mutex owner，那么它會立刻感知到鎖被釋放，因此可以立刻獲取mutex鎖。在這樣的情況下，即便后面喚醒了top waiter，但為時已晚。

C、如果等待隊列中有任務(wù)阻塞在這個mutex中，那么退出循環(huán)，執(zhí)行慢速路徑中的第二段喚醒邏輯，否則直接返回，無需喚醒其他線程。

D、在操作owner的過程中，如果有其他線程對owner進行的修改（沒有同步機制保證多線程對owner的并發(fā)操作），那么重新設(shè)定owner，再次進行檢測。

第二段喚醒top waiter的代碼如下：

A、代碼執(zhí)行至此，需要喚醒top waiter，或者處理將鎖轉(zhuǎn)交top waiter的邏輯，無論哪種情況，都需要從等待隊列中找到top waiter。找到后將其加入wake queue。

B、如果有任務(wù)（一般是top waiter，參考其喚醒后的代碼邏輯）請求handoff mutex，那么調(diào)用__mutex_handoff函數(shù)可以直接將owner設(shè)置為top waiter任務(wù)，然后該任務(wù)在醒來之后直接pickup即可。這相當(dāng)與給了top waiter一些特權(quán)，防止由于不斷的插入樂觀自旋的任務(wù)而導(dǎo)致無法獲取CPU資源。

C、喚醒top waiter任務(wù)

八、結(jié)論

本文簡單的介紹了linux內(nèi)核中的mutex同步機制，在移動環(huán)境中，mutex鎖的性能表現(xiàn)不盡如人意，無論是吞吐量還是延遲。在重載的場景下，我們經(jīng)常會遇到Ux線程阻塞在mutex而引起的手機卡頓問題，如何在手機平臺上優(yōu)化mutex鎖的性能是我們OPPO內(nèi)核團隊一直在做的事情，也歡迎熱愛技術(shù)的你積極參與。

Mutex