編者按：對(duì)于Linux系統(tǒng)編程來(lái)說(shuō)，競(jìng)爭(zhēng)和同步是繞不開的話題。之前分享過(guò)Java的對(duì)象鎖，有讀者說(shuō)自己不做Java不太能理解，這次分享Linux中很基礎(chǔ)的同步機(jī)制：futex，內(nèi)容包括基本接口定義和對(duì)于優(yōu)先級(jí)反轉(zhuǎn)的處理，希望對(duì)大家的技術(shù)成長(zhǎng)有幫助。

一、什么是futex？

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

內(nèi)核空間的等待隊(duì)列

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

在沒(méi)有競(jìng)爭(zhēng)的場(chǎng)景下，鎖的獲取和釋放性能都非常高，不需要內(nèi)核的參與，僅僅是通過(guò)用戶空間的原子操作來(lái)修改futex word的狀態(tài)即可。在有競(jìng)爭(zhēng)的場(chǎng)景下，如果線程無(wú)法獲取futex鎖，那么把自己放入到 wait queue中（陷入內(nèi)核，有系統(tǒng)調(diào)用的開銷），而在owner task釋放鎖的時(shí)候，如果檢測(cè)到有競(jìng)爭(zhēng)（等待隊(duì)列中有阻塞任務(wù)），就會(huì)通過(guò)系統(tǒng)調(diào)用來(lái)喚醒等待隊(duì)列中的任務(wù)，使其恢復(fù)執(zhí)行，繼續(xù)去持鎖。如果沒(méi)有競(jìng)爭(zhēng)，那么也無(wú)需陷入內(nèi)核。

二、Futex用戶和內(nèi)核空間接口API是什么？

Futex接口函數(shù)的原型如下：

Futex系統(tǒng)調(diào)用的復(fù)雜性體現(xiàn)在其參數(shù)上，要理解futex需要充分理解其參數(shù)：

futex系統(tǒng)調(diào)用支持各種各樣的操作碼，如下：

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

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

3、FUTEX_WAIT_BITSET：同F(xiàn)UTEX_WAIT，只不過(guò)多提供一個(gè)mask的參數(shù)

4、FUTEX_WAKE_BITSET：同F(xiàn)UTEX_WAKE，只不過(guò)多提供一個(gè)mask參數(shù)用來(lái)選擇喚醒哪一個(gè)waiter。

5、FUTEX_LOCK_PI：PI版本的FUTEX_WAIT

6、FUTEX_UNLOCK_PI：PI版本的FUTEX_WAKE

7、FUTEX_REQUEUE：這個(gè)操作包括喚醒和移動(dòng)隊(duì)列兩個(gè)動(dòng)作。喚醒val個(gè)等待在uaddr上的waiter，如果還有其他的waiter，那么將這些等待在uaddr的waiter轉(zhuǎn)移到uaddr2的等待隊(duì)列上去（最多轉(zhuǎn)移val2個(gè)waiter）

8、FUTEX_CMP_REQUEUE：同上，不過(guò)需要對(duì)比val3這個(gè)uaddr的期望值。

除了futex wait和wake這樣的基本操作，futex還有其他應(yīng)用在復(fù)雜場(chǎng)景的操作碼，由于在手機(jī)場(chǎng)景沒(méi)有使用，本文不再介紹。

我們整理各個(gè)操作碼的參數(shù)如下：

三、對(duì)于normal futex，內(nèi)核中如何組織等待隊(duì)列？

Futex相關(guān)的數(shù)據(jù)結(jié)構(gòu)組織如下圖所示：

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

在初始化的時(shí)候，內(nèi)核會(huì)構(gòu)建hashsize個(gè)futex hash bucket結(jié)構(gòu)，每個(gè)bucket用來(lái)管理futex鏈表（hash key相同）。futex_hash_bucket數(shù)據(jù)結(jié)構(gòu)定義如下：

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

通過(guò)上面的數(shù)據(jù)結(jié)構(gòu)，只要有了futex word，那么我們就能根據(jù)hash key定位到其掛入的鏈表。當(dāng)然，為了精準(zhǔn)的匹配，還需要其futex key完全相等，具體請(qǐng)參考match_futex函數(shù)。關(guān)于優(yōu)先級(jí)繼承相關(guān)的成員后面會(huì)詳細(xì)描述。

四、Futex wait的流程為何？

futex_wait函數(shù)的流程如下：

1、如果參數(shù)中給定了timeout，那么調(diào)用futex_setup_timer來(lái)創(chuàng)建一個(gè)hrtimer來(lái)打斷futex wait阻塞狀態(tài)。

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

3、有了hash key，我們就可以通過(guò)這個(gè)key找到哈希表中對(duì)應(yīng)的表頭（后文稱之hash bucket）。由于后續(xù)會(huì)把本次futex阻塞任務(wù)對(duì)象（futex_q）掛入hash bucket，因此需要上鎖。

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

5、插隊(duì)動(dòng)作是在futex_wait_queue_me函數(shù)中完成。插隊(duì)是考慮了優(yōu)先級(jí)的：對(duì)于rt線程，優(yōu)先級(jí)高的排在隊(duì)首，低的在隊(duì)尾。對(duì)于cfs任務(wù)，不按照優(yōu)先級(jí)排隊(duì)，而是采用了FIFO這樣的公平策略。同樣的，完成插隊(duì)后不要忘記解鎖。

6、馬上就要阻塞了，如果參數(shù)中給定了timeout，這時(shí)候就需要啟動(dòng)步驟1中設(shè)置的hrtimer了。

7、在真正阻塞之前，還要進(jìn)一步進(jìn)行驗(yàn)證，畢竟這時(shí)候有可能其他的執(zhí)行線索（可能是其他線程的futex wake，也可能是timeout callback）完成出隊(duì)操作。這時(shí)候就不能阻塞，否者這個(gè)線程可能再也無(wú)法醒來(lái)。

8、在步驟7中阻塞后，可能有多個(gè)喚醒場(chǎng)景：如果任務(wù)被正常喚醒（futex wake喚醒），那么其實(shí)已經(jīng)完成出隊(duì)的動(dòng)作，這時(shí)候直接返回即可，當(dāng)然，如果有啟動(dòng)hrtimer，我們需要取消它。

9、如果本次futex阻塞任務(wù)對(duì)象（futex_q）仍然掛在hash bucket的鏈表上，那表示是有異常發(fā)生，需要進(jìn)行相應(yīng)的處理并在當(dāng)前上下文完成出隊(duì)。具體有兩種情況：超時(shí)或者被信號(hào)打斷。

10、如果設(shè)置了超期時(shí)間，那么在當(dāng)前上下文會(huì)定義hrtimer_sleeper的對(duì)象，如果的確是超期喚醒的話，在timer的上下文中會(huì)把hrtimer_sleeper中的task成員清掉（設(shè)置為NULL），通過(guò)這個(gè)可以判斷是否是超期喚醒。

11、如果當(dāng)前任務(wù)有pending的信號(hào)，那說(shuō)明是被信號(hào)打斷。如果沒(méi)有pending信號(hào)，那說(shuō)明是spurious wakeup，需要再嘗試一次futex入隊(duì)操作。

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

五、Futex wake的流程為何？

相比f(wàn)utex_wait，futex_wake就比較簡(jiǎn)單了，其核心操作就是出隊(duì)和喚醒futex wait阻塞的任務(wù)，具體流程如下：

1、首先通過(guò)hash key找到對(duì)應(yīng)的hash bucket，這個(gè)操作和futex_wait中是一樣的。

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

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

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

5、完成指定數(shù)量的掃描之后會(huì)結(jié)束遍歷，調(diào)用wake_up_q將wake queue的任務(wù)逐個(gè)喚醒。

六、Futex requeue是什么鬼？

在講requeue流程之前我們需要先明白為何會(huì)有requeue這個(gè)op code。我們以java中的wait-notify機(jī)制來(lái)說(shuō)明這個(gè)問(wèn)題。我們有如下的java代碼：

Java中的Wait和notify的功能是native實(shí)現(xiàn)，在虛擬機(jī)提供支持。Synchronized是java內(nèi)嵌鎖，在虛擬機(jī)對(duì)應(yīng)monitor lock（互斥鎖），A臨界區(qū)和B臨界區(qū)都由monitor lock保護(hù)，確保了只有一個(gè)線程進(jìn)入。為了確保A、B臨界區(qū)的先后關(guān)系（A臨界區(qū)需要等待B臨界區(qū)的事件通知），我們引入了condition varible。在wait-notify場(chǎng)景中有兩個(gè)等待隊(duì)列：一個(gè)是monitor lock的等待隊(duì)列，另外一個(gè)是condition varible的等待隊(duì)列。而對(duì)于wait而言，它需要涉及兩個(gè)等待隊(duì)列的操作：一個(gè)是釋放monitor lock（喚醒其等待隊(duì)列的任務(wù)），一個(gè)是阻塞在條件變量上（把自己掛入其等待隊(duì)列）。如果沒(méi)有requeue，那么這樣的操作需要兩次futex的系統(tǒng)調(diào)用，有了futex requeue，一次futex就OK了。

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

1、Requeue涉及兩個(gè)futex，分別用uaddr1和uaddr2表示。這里需要喚醒nr_wake個(gè)uaddr1上的線程，同時(shí)把其上的nr_requeue個(gè)等待任務(wù)對(duì)象轉(zhuǎn)移到uaddr2對(duì)應(yīng)的等待隊(duì)列上。首先調(diào)用get_futex_key獲取兩個(gè)futex的hash key，并根據(jù)hash key找到對(duì)應(yīng)的hash bucket（hash_futex函數(shù)）

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

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

4、調(diào)用wake_up_q函數(shù)喚醒之前掛入喚醒隊(duì)列的任務(wù)

七、為何futex要支持PI？

Non-PI futex引起的優(yōu)先級(jí)翻轉(zhuǎn)（priority inversion）問(wèn)題如下圖所示：

低優(yōu)先級(jí)任務(wù)C首先持鎖，這樣當(dāng)高優(yōu)先級(jí)任務(wù)A試圖持鎖失敗進(jìn)入D狀態(tài)。一般而言，C任務(wù)臨界區(qū)比較短，完成之后就釋放鎖，任務(wù)A就可以執(zhí)行了。然而，在C執(zhí)行過(guò)程中，中等優(yōu)先級(jí)的任務(wù)B被喚醒，搶占了任務(wù)C的執(zhí)行，這時(shí)候，所有優(yōu)先級(jí)在A和C之間的任務(wù)都可以搶占C的執(zhí)行，從而使得任務(wù)A無(wú)法在確定的時(shí)間內(nèi)獲取到CPU資源。

PI futex中的PI就是priority inheritance，可以通過(guò)優(yōu)先級(jí)繼承的方法來(lái)解決系統(tǒng)中出現(xiàn)的優(yōu)先級(jí)翻轉(zhuǎn)問(wèn)題。具體的方法就是當(dāng)任務(wù)A持鎖失敗的時(shí)候，鎖的owner task（即任務(wù)C）需要臨時(shí)性的把優(yōu)先級(jí)提升至任務(wù)A的優(yōu)先級(jí)。而在釋放鎖的時(shí)候，將其優(yōu)先級(jí)進(jìn)行恢復(fù)原值。

當(dāng)然，上面只是一個(gè)簡(jiǎn)單的例子，實(shí)際系統(tǒng)會(huì)涉及更多的鎖和線程，但原理類似。對(duì)于線程，我們需要記錄：

1、該線程持鎖哪些鎖，這些鎖的top waiter是誰(shuí)，對(duì)所有的top waiter按照優(yōu)先級(jí)進(jìn)行排序。

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

對(duì)于鎖，我們需要記錄：

1、該鎖的owner是誰(shuí)

2、阻塞在該鎖的線程們（按照優(yōu)先級(jí)進(jìn)行排序）。

注意，這里我們把優(yōu)先級(jí)最高的那個(gè)阻塞線程叫做該所的top waiter。

有了這些信息，我們需要維持一個(gè)準(zhǔn)則就OK了：一個(gè)任務(wù)的臨時(shí)優(yōu)先級(jí)應(yīng)該提升至其持有鎖的top waiter線程中最高的那個(gè)優(yōu)先級(jí)。

八、Rt mutex的原理為何？

PI-futex是通過(guò)rt mutex來(lái)實(shí)現(xiàn)的，因此我們這里簡(jiǎn)單的聊一聊內(nèi)核的這個(gè)PI-aware mutex。

從rt mutex的視角看任務(wù)：

rt_mutex_waiter用來(lái)抽象一個(gè)阻塞在rt mutex的任務(wù)：task成員指向這個(gè)任務(wù)，lock成員指向?qū)?yīng)的rt mutex對(duì)象，tree_entry是掛入blocker紅黑樹的節(jié)點(diǎn)，rt mutex對(duì)象的waiters成員就是這顆紅黑樹的根節(jié)點(diǎn)（wait_lock成員用來(lái)保護(hù)紅黑樹的操作）。而owner則指向持鎖的任務(wù)。需要特別說(shuō)明的是waiters這個(gè)紅黑樹是按照任務(wù)優(yōu)先級(jí)排序的，left most節(jié)點(diǎn)就是對(duì)應(yīng)該鎖的top waiter。

從任務(wù)的視角來(lái)看rt mutex：

為了支持rt mutex，task struct也增加了若干的成員，最重要的就是pi_waiters。由于一個(gè)任務(wù)可以持有多把鎖，每把鎖都有top waiter，因此和一個(gè)任務(wù)關(guān)聯(lián)的top waiter也有非常多，這些top waiter形成了一個(gè)紅黑樹（同樣也是按照優(yōu)先級(jí)排序），pi_waiters成員就是這顆紅黑樹的根節(jié)點(diǎn)。這顆紅黑樹的left most的任務(wù)優(yōu)先級(jí)就是實(shí)現(xiàn)優(yōu)先級(jí)繼承協(xié)議中規(guī)定要臨時(shí)提升的優(yōu)先級(jí)。pi_top_task成員指向了left most節(jié)點(diǎn)對(duì)應(yīng)的任務(wù)對(duì)象，我們稱之top pi waiter。Task struct的pi_blocked_on成員則指向其阻塞的rt_mutex_waiter對(duì)象。

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

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

在上面這張圖中有四條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中的任務(wù)必須維持這樣的關(guān)系：處于PI chain中右端的任務(wù)的優(yōu)先級(jí)必須大于等于PI chain中左端的任務(wù)們。我們以第四條PI chain為例，任務(wù)2的優(yōu)先級(jí)必須大于等于任務(wù)1和任務(wù)3的優(yōu)先級(jí)，而任務(wù)1的優(yōu)先級(jí)必須要大于等于任務(wù)3的優(yōu)先級(jí)。

九、PI futex和rt mutex有什么關(guān)系？

熟悉Linux的工程師都了解內(nèi)核中的mutex互斥鎖以及支持PI的互斥鎖版本rt mutex。如果想讓用戶空間的互斥鎖實(shí)現(xiàn)優(yōu)先級(jí)繼承的功能，那么其實(shí)不需要futex模塊實(shí)現(xiàn)復(fù)雜的PI chain，實(shí)際上對(duì)PI狀態(tài)的跟蹤是通過(guò)rt mutex代理來(lái)完成的，原理圖如下：

我們先看接口部分，normal futex使用FUTEX_WAIT和FUTEX_WAKE操作碼來(lái)完成阻塞和喚醒的動(dòng)作。對(duì)于PI futex而言，F(xiàn)UTEX_LOCK_PI用來(lái)執(zhí)行上鎖，而FUTEX_UNLOCK_PI用來(lái)完成解鎖。這里的lock和unlock其實(shí)是對(duì)futex的代理rt mutex而言的。

無(wú)論是normal futex還是PI futex，阻塞于futex的任務(wù)都會(huì)有一個(gè)futex_q對(duì)象與之對(duì)應(yīng)。對(duì)于normal futex，有了futex_q對(duì)象，掛入等待隊(duì)列和將其喚醒的功能都能輕松實(shí)現(xiàn)。對(duì)于PI futex，我們不僅僅需要掛入隊(duì)列和喚醒任務(wù)，最重要的是我們需要根據(jù)PI chain完成任務(wù)優(yōu)先級(jí)的調(diào)整。為了完成這個(gè)功能，需要兩個(gè)額外的對(duì)象，一個(gè)是rt_mutex_waiter，表示一個(gè)阻塞在rt mutex的任務(wù)，其rt mutex指針指向了其阻塞在哪個(gè)rt mutex上。另外一個(gè)是futex_pi_state對(duì)象，它記錄了優(yōu)先級(jí)翻轉(zhuǎn)的信息，包括該用戶空間上層鎖對(duì)應(yīng)的內(nèi)核態(tài)的rt mutex，rt mutex的owner任務(wù)的信息等。

十、Pi futex邏輯過(guò)程

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

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

第一次futex lock pi稍微復(fù)雜一點(diǎn)，需要完成owner持鎖和current task的阻塞在鎖上這兩個(gè)動(dòng)作。注意：這里的鎖指的是rt mutex。當(dāng)線程持上層鎖成功的時(shí)候，我們并不能同時(shí)對(duì)rt mutex持鎖成功并設(shè)置owner，因此這時(shí)候并不會(huì)有futex系統(tǒng)調(diào)用進(jìn)入內(nèi)核。當(dāng)?shù)谝淮巫枞臅r(shí)候，會(huì)通過(guò)futex系統(tǒng)調(diào)用把owner id傳遞給內(nèi)核，這時(shí)候我們需要分配一個(gè)futex pi state對(duì)象創(chuàng)建一個(gè)rt mutex，同時(shí)建立這個(gè)rt mutex和owner task的關(guān)系：

1、掛入owner task的futex pi state鏈表。一個(gè)任務(wù)可以持有多把上層鎖，所以需要鏈表管理，當(dāng)然不一定每一個(gè)任務(wù)持有的上層鎖都有對(duì)應(yīng)的futex pi state對(duì)象，沒(méi)有競(jìng)爭(zhēng)也就不會(huì)陷入內(nèi)核調(diào)用FUTEX_LOCK_PI。

2、futex pi state對(duì)象的owner成員指向?qū)?yīng)的owner task

第二個(gè)重要的動(dòng)作就是讓current task去獲取rt mutex，上面剛剛設(shè)定了owner，這里current task持鎖的結(jié)果大概率就是會(huì)阻塞，不過(guò)我們本來(lái)就是通過(guò)這個(gè)阻塞關(guān)系來(lái)完成PI 狀態(tài)的跟蹤的。rt_mutex_waiter對(duì)象抽象了一個(gè)阻塞在rt mutex的任務(wù)，我們需要建立rt_mutex_waiter對(duì)象、阻塞任務(wù)和rt mutex的關(guān)系，具體包括：

1、rt_mutex_waiter對(duì)象的lock成員指向?qū)?yīng)于的rt mutex，表示該任務(wù)阻塞在這個(gè)鎖上。rt_mutex_waiter對(duì)象的task成員指向當(dāng)前要阻塞的任務(wù)對(duì)象。

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

3、task struct的pi_blocked_on設(shè)置為該rt_mutex_waiter對(duì)象。

4、對(duì)于rt mutex而言，有了新的阻塞任務(wù)，如果優(yōu)先級(jí)比目前該rt mutex的top waiter更高的話，那么需要更新owner task的top waiter，將舊的top waiter節(jié)點(diǎn)從紅黑樹中刪除，將新的top waiter插入owner task的top waiter紅黑樹。

5、根據(jù)新的top waiter更新owner task的動(dòng)態(tài)優(yōu)先級(jí)。一旦修改了owner task的優(yōu)先級(jí)，那么其相關(guān)的PI chain都需要進(jìn)行優(yōu)先級(jí)調(diào)整。

第二次以及后續(xù)的FUTEX_LOCK_PI會(huì)簡(jiǎn)單一點(diǎn)，因?yàn)椴恍枰陆╮t mutex對(duì)象了，只需要在bucket找到第一個(gè)futex_q對(duì)象，通過(guò)其pi state指針就可以定位rt mutex了。有了rt mutex，通過(guò)上鎖即可讓自己阻塞在這個(gè)rt mutex上了。

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

十一、小結(jié)

本文通過(guò)問(wèn)答的形式簡(jiǎn)單的介紹了內(nèi)核futex機(jī)制，它是上層同步機(jī)制的基石。在PI Futex的介紹中，我們對(duì)rt mutex淺嘗輒止，讀者未能領(lǐng)略其全貌。





審核編輯：劉清