Mutex 內核同步機制詳解

一、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，也就定位到了自旋的任務。

雖然都是自旋，但是自旋方式並不一樣。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 函數中，如下：

A、對於 mutex 的 owner 成員，它是一個原子變量，我們採用了大量的原子操作來訪問或者更新它。然而判斷持鎖需要一連串的操作，我們並沒有採用同步機制（例如自旋鎖）來保護這一段的對 owner 成員操作，因此，我們這些操作放到一個 for 循環中，在操作的結尾處會判斷是否有其他線程插入修改了 owner 成員，如果中間有其他線程插入，那麼就需要重新來過。

B、如果 task 非空（task 變量保存了 owner 中去掉 flag 部分的任務指針），並且也不等於 current thread，那麼說明 mutex 鎖被其他線程持有，還沒有釋放鎖（也有可能在是否鎖的時候，把鎖直接轉交給了其他線程），因此直接 break 跳出循環，持鎖失敗。

C、如果 task 等於 current thread，而且設置了 MUTEX_FLAG_PICKUP 的標記，那麼說明持鎖線程已經把該 mutex 鎖轉交給了本線程，等待本線程來拾取。如果沒有 MUTEX_FLAG_PICKUP 標記，那麼也是直接 break 跳出循環，遞歸持鎖失敗。

D、有兩種情況會走到這裏的時候，一種情況是 task 爲空，說明該 mutex 鎖處於 unlocked 狀態。另外一種情況是 task 非空，等於 current thread，並且 mutex 發生了 handoff，該鎖被轉交給當前試圖持鎖的線程。無論哪種情況，都可以去執行持鎖操作了。

E、調用 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 內核團隊一直在做的事情，也歡迎熱愛技術的你積極參與。

參考文獻：

1、內核源代碼

2、linux-5.10.61\Documentation\scheduler*

3、https://zhuanlan.zhihu.com/p/364130923

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/ftb6fYP26ZBNS-_CNkFyTg