一、Mutex鎖簡(jiǎn)介

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

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

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

下面是一個(gè)簡(jiǎn)單的mutex工作原理圖：

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

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

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

1、互斥量對(duì)象

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

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

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

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

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

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

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

3、MCS鎖對(duì)象

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

三、外部接口

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

四、嘗試獲取鎖

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

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

五、獲取mutex鎖

mutex_lock代碼如下：

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

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

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

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

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

atomic_long_try_cmpxchg_acquire函數(shù)有三個(gè)參數(shù)，從左到右分別是value指針，old指針和new。該函數(shù)會(huì)對(duì)比*value和*old指針中的數(shù)值，如果相等執(zhí)行賦值*value=new同時(shí)返回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ù)進(jìn)入慢速路徑。由于會(huì)進(jìn)入睡眠，因此這里需要明確當(dāng)前線程需要處于的阻塞狀態(tài)，主要有三種狀態(tài)：D狀態(tài)、S狀態(tài)和KILLABLE。

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

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

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

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

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

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

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

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

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

六、樂觀自旋

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

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

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

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

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

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

A、當(dāng)waiter為空時(shí)，因?yàn)槭钦Ｂ窂降某宙i請(qǐng)求，所以在樂觀自旋之前需要持有osq鎖，只有獲得了osq鎖，當(dāng)前線程才能進(jìn)入mutex樂觀自旋的過程。否則只能是在自己的MCS鎖上自旋等待。

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

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

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

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

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

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

七、釋放mutex鎖

mutex_unlock的代碼如下：

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

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

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

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

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

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

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

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

B、如果有任務(wù)（一般是top waiter，參考其喚醒后的代碼邏輯）請(qǐng)求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é)論

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

Mutex