編者按：對于Linux系統編程來說，競爭和同步是繞不開的話題。之前分享過Java的對象鎖，有讀者說自己不做Java不太能理解，這次分享Linux中很基礎的同步機制：futex，內容包括基本接口定義和對于優先級反轉的處理，希望對大家的技術成長有幫助。

一、什么是futex？

futex是Fast Userspace muTEX的縮寫，該機制是由Rusty Russell、Hubertus Franke和Mathew Kirkwood在2.5.7版本的內核中引入，雖然名字中有互斥鎖（mutex）的含義，但實際它是一種用于用戶空間應用程序的通用同步工具（基于futex可以在userspace實現互斥鎖、讀寫鎖、condition variable等同步機制）。Futex組成包括：

內核空間的等待隊列

用戶空間層的32-bit futex word（所有平臺都是32bit，包括64位平臺）

在沒有競爭的場景下，鎖的獲取和釋放性能都非常高，不需要內核的參與，僅僅是通過用戶空間的原子操作來修改futex word的狀態即可。在有競爭的場景下，如果線程無法獲取futex鎖，那么把自己放入到 wait queue中（陷入內核，有系統調用的開銷），而在owner task釋放鎖的時候，如果檢測到有競爭（等待隊列中有阻塞任務），就會通過系統調用來喚醒等待隊列中的任務，使其恢復執行，繼續去持鎖。如果沒有競爭，那么也無需陷入內核。

二、Futex用戶和內核空間接口API是什么？

Futex接口函數的原型如下：

Futex系統調用的復雜性體現在其參數上，要理解futex需要充分理解其參數：

futex系統調用支持各種各樣的操作碼，如下：

1、FUTEX_WAIT：如果futex word中仍然保存著參數val給定的值，那么當前線程則進入睡眠，等待FUTEX_WAKE的操作喚醒它。

2、FUTEX_WAKE：最多喚醒val個等待在futex word上的線程。Val或者等于1（喚醒1個等待線程）或者等于INT_MAX（喚醒全部等待線程）

3、FUTEX_WAIT_BITSET：同FUTEX_WAIT，只不過多提供一個mask的參數

4、FUTEX_WAKE_BITSET：同FUTEX_WAKE，只不過多提供一個mask參數用來選擇喚醒哪一個waiter。

5、FUTEX_LOCK_PI：PI版本的FUTEX_WAIT

6、FUTEX_UNLOCK_PI：PI版本的FUTEX_WAKE

7、FUTEX_REQUEUE：這個操作包括喚醒和移動隊列兩個動作。喚醒val個等待在uaddr上的waiter，如果還有其他的waiter，那么將這些等待在uaddr的waiter轉移到uaddr2的等待隊列上去（最多轉移val2個waiter）

8、FUTEX_CMP_REQUEUE：同上，不過需要對比val3這個uaddr的期望值。

除了futex wait和wake這樣的基本操作，futex還有其他應用在復雜場景的操作碼，由于在手機場景沒有使用，本文不再介紹。

我們整理各個操作碼的參數如下：

三、對于normal futex，內核中如何組織等待隊列？

Futex相關的數據結構組織如下圖所示：

從邏輯上看，通過futex實現的互斥鎖和內核中的互斥鎖mutex是一樣的（通過futex實現的讀寫鎖的概念和內核的rwsem也是一樣，不再贅述），只不過futex互斥鎖是分裂開的：futex word和等待隊列是分別在用戶空間和內核空間，內核的mutex互斥鎖可以講把待隊列頭放置在mutex對象上，但是對于futex，我們沒有對應的內核鎖對象，因此我們就需要一個算法將futex word和其等待隊列映射起來。為了管理掛入等待隊列的futex阻塞任務，內核建立了一個hansh table如下：

在初始化的時候，內核會構建hashsize個futex hash bucket結構，每個bucket用來管理futex鏈表（hash key相同）。futex_hash_bucket數據結構定義如下：

每一個等待在futex word的task都有一個futex_q對象（后文稱之futex阻塞任務對象），根據其哈希值掛入不同的隊列：

通過上面的數據結構，只要有了futex word，那么我們就能根據hash key定位到其掛入的鏈表。當然，為了精準的匹配，還需要其futex key完全相等，具體請參考match_futex函數。關于優先級繼承相關的成員后面會詳細描述。

四、Futex wait的流程為何？

futex_wait函數的流程如下：

1、如果參數中給定了timeout，那么調用futex_setup_timer來創建一個hrtimer來打斷futex wait阻塞狀態。

2、通過三元組計算futex hash key，對于process-private類型的futex word，hash key是根據進程地址空間和futex word的虛擬地址來計算，也就是說三元組是( current->mm, address, 0 )。對于share類型的futex word，它會被放置到共享的內存中（通過mmap或者shmat）。在這種場景下，futex word在不同進程中有不同的虛擬地址，但是物理地址是相同的，通過地址空間中的虛擬地址來計算hash key是行不通的。因此share類型的futex word使用的三元組( inode->i_sequence, page->index, offset_within_page )這樣的組合來計算hash key。具體的細節請參考get_futex_key函數。

3、有了hash key，我們就可以通過這個key找到哈希表中對應的表頭（后文稱之hash bucket）。由于后續會把本次futex阻塞任務對象（futex_q）掛入hash bucket，因此需要上鎖。

4、在真正插入鏈表之前還需要校驗用戶空間傳遞來的期望值是否發生了變化（表示用戶空間有其他線程對該futex word進行了修改），如果保持不變，那么就可以放心插隊了，否則返回EWOULDBLOCK，當然，不要忘記解鎖。

5、插隊動作是在futex_wait_queue_me函數中完成。插隊是考慮了優先級的：對于rt線程，優先級高的排在隊首，低的在隊尾。對于cfs任務，不按照優先級排隊，而是采用了FIFO這樣的公平策略。同樣的，完成插隊后不要忘記解鎖。

6、馬上就要阻塞了，如果參數中給定了timeout，這時候就需要啟動步驟1中設置的hrtimer了。

7、在真正阻塞之前，還要進一步進行驗證，畢竟這時候有可能其他的執行線索（可能是其他線程的futex wake，也可能是timeout callback）完成出隊操作。這時候就不能阻塞，否者這個線程可能再也無法醒來。

8、在步驟7中阻塞后，可能有多個喚醒場景：如果任務被正常喚醒（futex wake喚醒），那么其實已經完成出隊的動作，這時候直接返回即可，當然，如果有啟動hrtimer，我們需要取消它。

9、如果本次futex阻塞任務對象（futex_q）仍然掛在hash bucket的鏈表上，那表示是有異常發生，需要進行相應的處理并在當前上下文完成出隊。具體有兩種情況：超時或者被信號打斷。

10、如果設置了超期時間，那么在當前上下文會定義hrtimer_sleeper的對象，如果的確是超期喚醒的話，在timer的上下文中會把hrtimer_sleeper中的task成員清掉（設置為NULL），通過這個可以判斷是否是超期喚醒。

11、如果當前任務有pending的信號，那說明是被信號打斷。如果沒有pending信號，那說明是spurious wakeup，需要再嘗試一次futex入隊操作。

12、一般而言，如果被信號打斷，直接返回ERESTARTSYS，讓用戶空間程序自己決定怎么后續處理就OK了。但是有一種情況例外，那就是設置了timeout（即還沒有超期就被信號打斷），這種場景需要restart syscall。

五、Futex wake的流程為何？

相比futex_wait，futex_wake就比較簡單了，其核心操作就是出隊和喚醒futex wait阻塞的任務，具體流程如下：

1、首先通過hash key找到對應的hash bucket，這個操作和futex_wait中是一樣的。

2、hash bucket中的鏈表上的futex阻塞任務對象（futex_q）只是由于hash key相同而走到一起的，實際上并非一定是對應的futex word，因此我們需要遍歷鏈表進行匹配。具體匹配的準則就是三元組完全相等。

3、三元組相等只能說明futex word是對應上了，但是futex機制也提供了用戶可以控制喚醒的方法：比特匹配。在futex wait的時候，上層的應用程序可以傳遞bitset參數來標記自己（FUTEX_WAIT_BITSET），在futex wake的時候，應用程序會傳遞bitset參數來通知內核自己想要喚醒哪些線程（FUTEX_WAKE_BITSET）。對于FUTEX_WAIT和FUTEX_WAKE，bitset做了特殊處理，設置為FUTEX_BITSET_MATCH_ANY，即futex wake的時候可以喚醒任何阻塞在該futex word的線程。

4、除了bitset，futex wake還可以控制喚醒線程的個數。為了完成多個線程的喚醒，這里使用了喚醒隊列（wake queue）。當找到匹配的futex_q的時候，將其從hash bucket的隊列中刪除，加入到喚醒隊列上來。需要注意的是：在進行這些隊列操作的時候需要持有hash buck的自旋鎖。

5、完成指定數量的掃描之后會結束遍歷，調用wake_up_q將wake queue的任務逐個喚醒。

六、Futex requeue是什么鬼？

在講requeue流程之前我們需要先明白為何會有requeue這個op code。我們以java中的wait-notify機制來說明這個問題。我們有如下的java代碼：

Java中的Wait和notify的功能是native實現，在虛擬機提供支持。Synchronized是java內嵌鎖，在虛擬機對應monitor lock（互斥鎖），A臨界區和B臨界區都由monitor lock保護，確保了只有一個線程進入。為了確保A、B臨界區的先后關系（A臨界區需要等待B臨界區的事件通知），我們引入了condition varible。在wait-notify場景中有兩個等待隊列：一個是monitor lock的等待隊列，另外一個是condition varible的等待隊列。而對于wait而言，它需要涉及兩個等待隊列的操作：一個是釋放monitor lock（喚醒其等待隊列的任務），一個是阻塞在條件變量上（把自己掛入其等待隊列）。如果沒有requeue，那么這樣的操作需要兩次futex的系統調用，有了futex requeue，一次futex就OK了。

了解了requeue的由來，其流程也是非常的簡單，特別是有了上面兩節futex wait和futex wake基礎。Requeue的流程如下（requeue有normal requeue和pi requeue，這里我們主要描述normal requeue的流程）：

1、Requeue涉及兩個futex，分別用uaddr1和uaddr2表示。這里需要喚醒nr_wake個uaddr1上的線程，同時把其上的nr_requeue個等待任務對象轉移到uaddr2對應的等待隊列上。首先調用get_futex_key獲取兩個futex的hash key，并根據hash key找到對應的hash bucket（hash_futex函數）

2、如果是FUTEX_CMP_REQUEUE，那么我們還需要校驗uaddr1中的值。需要特別說明的是：這里涉及內核空間訪問用戶空間的變量，讀操作是一個非常復雜的過程，具體參考get_futex_value_locked函數。這些邏輯和本文的主題關系不大，就不再贅述了。

3、遍歷uaddr1 等待隊列上的所有等待任務對象（futex_q），將nr_wake個futex_q通過mark_wake_futex暫存在wake_q喚醒隊列上。通過requeue_futex將uaddr1 等待隊列上nr_requeue個futex_q對象轉移到uaddr2的等待隊列上。注意，這些操作需要持有兩個hash bucket的自旋鎖。

4、調用wake_up_q函數喚醒之前掛入喚醒隊列的任務

七、為何futex要支持PI？

Non-PI futex引起的優先級翻轉（priority inversion）問題如下圖所示：

低優先級任務C首先持鎖，這樣當高優先級任務A試圖持鎖失敗進入D狀態。一般而言，C任務臨界區比較短，完成之后就釋放鎖，任務A就可以執行了。然而，在C執行過程中，中等優先級的任務B被喚醒，搶占了任務C的執行，這時候，所有優先級在A和C之間的任務都可以搶占C的執行，從而使得任務A無法在確定的時間內獲取到CPU資源。

PI futex中的PI就是priority inheritance，可以通過優先級繼承的方法來解決系統中出現的優先級翻轉問題。具體的方法就是當任務A持鎖失敗的時候，鎖的owner task（即任務C）需要臨時性的把優先級提升至任務A的優先級。而在釋放鎖的時候，將其優先級進行恢復原值。

當然，上面只是一個簡單的例子，實際系統會涉及更多的鎖和線程，但原理類似。對于線程，我們需要記錄：

1、該線程持鎖哪些鎖，這些鎖的top waiter是誰，對所有的top waiter按照優先級進行排序。

2、該線程阻塞在哪一把鎖上

對于鎖，我們需要記錄：

1、該鎖的owner是誰

2、阻塞在該鎖的線程們（按照優先級進行排序）。

注意，這里我們把優先級最高的那個阻塞線程叫做該所的top waiter。

有了這些信息，我們需要維持一個準則就OK了：一個任務的臨時優先級應該提升至其持有鎖的top waiter線程中最高的那個優先級。

八、Rt mutex的原理為何？

PI-futex是通過rt mutex來實現的，因此我們這里簡單的聊一聊內核的這個PI-aware mutex。

從rt mutex的視角看任務：

rt_mutex_waiter用來抽象一個阻塞在rt mutex的任務：task成員指向這個任務，lock成員指向對應的rt mutex對象，tree_entry是掛入blocker紅黑樹的節點，rt mutex對象的waiters成員就是這顆紅黑樹的根節點（wait_lock成員用來保護紅黑樹的操作）。而owner則指向持鎖的任務。需要特別說明的是waiters這個紅黑樹是按照任務優先級排序的，left most節點就是對應該鎖的top waiter。

從任務的視角來看rt mutex：

為了支持rt mutex，task struct也增加了若干的成員，最重要的就是pi_waiters。由于一個任務可以持有多把鎖，每把鎖都有top waiter，因此和一個任務關聯的top waiter也有非常多，這些top waiter形成了一個紅黑樹（同樣也是按照優先級排序），pi_waiters成員就是這顆紅黑樹的根節點。這顆紅黑樹的left most的任務優先級就是實現優先級繼承協議中規定要臨時提升的優先級。pi_top_task成員指向了left most節點對應的任務對象，我們稱之top pi waiter。Task struct的pi_blocked_on成員則指向其阻塞的rt_mutex_waiter對象。

有了上面的基本概念之后，我們講一下PI chain的概念。首先看看任務和鎖的基本關系，如下圖所示：

在上面的圖片中，task 1持有了Lock A和Lock B，阻塞在Lock C上。一個任務只能阻塞在一個鎖上，所以紅色箭頭只能是從任務到鎖，不能分叉。由于一個任務可以持有多把鎖，所以黑色箭頭會有多個鎖指向一個任務，即多把鎖匯聚于任務。有了這個基本的關系圖之后，我們可以形成更加復雜的任務和鎖的邏輯圖，如下：

在上面這張圖中有四條PI chain：

1、Lock D--->task 2

2、task 4--->Lock D--->task 2

3、Lock A--->task 1--->Lock C--->task 2

4、task 3--->Lock B--->task 1--->Lock C--->task 2

為了能夠讓PI正常起作用，PI chain中的任務必須維持這樣的關系：處于PI chain中右端的任務的優先級必須大于等于PI chain中左端的任務們。我們以第四條PI chain為例，任務2的優先級必須大于等于任務1和任務3的優先級，而任務1的優先級必須要大于等于任務3的優先級。

九、PI futex和rt mutex有什么關系？

熟悉Linux的工程師都了解內核中的mutex互斥鎖以及支持PI的互斥鎖版本rt mutex。如果想讓用戶空間的互斥鎖實現優先級繼承的功能，那么其實不需要futex模塊實現復雜的PI chain，實際上對PI狀態的跟蹤是通過rt mutex代理來完成的，原理圖如下：

我們先看接口部分，normal futex使用FUTEX_WAIT和FUTEX_WAKE操作碼來完成阻塞和喚醒的動作。對于PI futex而言，FUTEX_LOCK_PI用來執行上鎖，而FUTEX_UNLOCK_PI用來完成解鎖。這里的lock和unlock其實是對futex的代理rt mutex而言的。

無論是normal futex還是PI futex，阻塞于futex的任務都會有一個futex_q對象與之對應。對于normal futex，有了futex_q對象，掛入等待隊列和將其喚醒的功能都能輕松實現。對于PI futex，我們不僅僅需要掛入隊列和喚醒任務，最重要的是我們需要根據PI chain完成任務優先級的調整。為了完成這個功能，需要兩個額外的對象，一個是rt_mutex_waiter，表示一個阻塞在rt mutex的任務，其rt mutex指針指向了其阻塞在哪個rt mutex上。另外一個是futex_pi_state對象，它記錄了優先級翻轉的信息，包括該用戶空間上層鎖對應的內核態的rt mutex，rt mutex的owner任務的信息等。

十、Pi futex邏輯過程

Pi futex主要有兩個邏輯過程：通過FUTEX_LOCK_PI上鎖，通過FUTEX_UNLOCK_PI完成釋放鎖的邏輯。

這里的“上鎖”有點誤導，不是“試圖持鎖”的意思，而是競爭上層鎖失敗之后，陷入內核準備進入阻塞狀態。這里為了記錄PI state，所以需要對代理rt mutex執行上鎖的動作（基本上也是會阻塞在rt mutex上）。對于pi futex的。正常futex的部分，例如get hash key、找futex對應的hash bucket、插入hash隊列等操作，這里不再描述，主要看PI futex特有的部分。

第一次futex lock pi稍微復雜一點，需要完成owner持鎖和current task的阻塞在鎖上這兩個動作。注意：這里的鎖指的是rt mutex。當線程持上層鎖成功的時候，我們并不能同時對rt mutex持鎖成功并設置owner，因此這時候并不會有futex系統調用進入內核。當第一次阻塞的時候，會通過futex系統調用把owner id傳遞給內核，這時候我們需要分配一個futex pi state對象創建一個rt mutex，同時建立這個rt mutex和owner task的關系：

1、掛入owner task的futex pi state鏈表。一個任務可以持有多把上層鎖，所以需要鏈表管理，當然不一定每一個任務持有的上層鎖都有對應的futex pi state對象，沒有競爭也就不會陷入內核調用FUTEX_LOCK_PI。

2、futex pi state對象的owner成員指向對應的owner task

第二個重要的動作就是讓current task去獲取rt mutex，上面剛剛設定了owner，這里current task持鎖的結果大概率就是會阻塞，不過我們本來就是通過這個阻塞關系來完成PI 狀態的跟蹤的。rt_mutex_waiter對象抽象了一個阻塞在rt mutex的任務，我們需要建立rt_mutex_waiter對象、阻塞任務和rt mutex的關系，具體包括：

1、rt_mutex_waiter對象的lock成員指向對應于的rt mutex，表示該任務阻塞在這個鎖上。rt_mutex_waiter對象的task成員指向當前要阻塞的任務對象。

2、將rt_mutex_waiter對象插入rt mutex的waiters紅黑樹。

3、task struct的pi_blocked_on設置為該rt_mutex_waiter對象。

4、對于rt mutex而言，有了新的阻塞任務，如果優先級比目前該rt mutex的top waiter更高的話，那么需要更新owner task的top waiter，將舊的top waiter節點從紅黑樹中刪除，將新的top waiter插入owner task的top waiter紅黑樹。

5、根據新的top waiter更新owner task的動態優先級。一旦修改了owner task的優先級，那么其相關的PI chain都需要進行優先級調整。

第二次以及后續的FUTEX_LOCK_PI會簡單一點，因為不需要新建rt mutex對象了，只需要在bucket找到第一個futex_q對象，通過其pi state指針就可以定位rt mutex了。有了rt mutex，通過上鎖即可讓自己阻塞在這個rt mutex上了。

FUTEX_UNLOCK_PI的流程留給讀者自行分析了。

十一、小結

本文通過問答的形式簡單的介紹了內核futex機制，它是上層同步機制的基石。在PI Futex的介紹中，我們對rt mutex淺嘗輒止，讀者未能領略其全貌。





審核編輯：劉清