一、Mutex鎖簡介

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

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

當配置了DEBUG_MUTEXES的時候，內核會對上面的規則進行檢查，防止用戶誤用mutex，產生各種問題。

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

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

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

二、數據結構

1、互斥量對象

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

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

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

【文章福利】小編推薦自己的Linux內核技術交流群:【865977150】整理了一些個人覺得比較好的學習書籍、視頻資料共享在群文件里面，有需要的可以自行添加哦！！！前100名進群領取，額外贈送一份價值699的內核資料包（含視頻教程、電子書、實戰項目及代碼)

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

2、等待任務對象

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

3、MCS鎖對象

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

三、外部接口

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

四、嘗試獲取鎖

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

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

五、獲取mutex鎖

mutex_lock代碼如下：

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

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

在配置了主動搶占式內核（CONFIG_PREEMPT_VOLUNTARY）的情況下，might_resched會調用_cond_resched函數來主動觸發一次搶占。

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

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

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

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

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

當調用不同的持鎖API的時候，當前線程可以處于各種不同的狀態。

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

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

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

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

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

B、進入阻塞狀態，觸發一次調度。由于目前執行上下文處于關閉搶占狀態，因此這里的調度使用了關閉搶占版本的schedule函數。

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

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

六、樂觀自旋

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

1、成功獲取osq鎖，進入mutex樂觀自旋狀態，當owner釋放mutex鎖后，該線程結束樂觀自旋，成功持有了mutex，返回true

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

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

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

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

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

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

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

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

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

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

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

七、釋放mutex鎖

mutex_unlock的代碼如下：

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

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

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

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

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

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

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

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

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

C、喚醒top waiter任務

八、結論

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

Mutex