深度講解futex問答（下)
七、為何futex要支持PI？
Non-PI futex引起的優(yōu)先級翻轉(zhuǎn)（priority inversion）問題如下圖所示：
低優(yōu)先級任務(wù)C首先持鎖，這樣當高優(yōu)先級任務(wù)A試圖持鎖失敗進入D狀態(tài)。一般而言，C任務(wù)臨界區(qū)比較短，完成之后就釋放鎖，任務(wù)A就可以執(zhí)行了。然而，在C執(zhí)行過程中，中等優(yōu)先級的任務(wù)B被喚醒，搶占了任務(wù)C的執(zhí)行，這時候，所有優(yōu)先級在A和C之間的任務(wù)都可以搶占C的執(zhí)行，從而使得任務(wù)A無法在確定的時間內(nèi)獲取到CPU資源。
PI futex中的PI就是priority inheritance，可以通過優(yōu)先級繼承的方法來解決系統(tǒng)中出現(xiàn)的優(yōu)先級翻轉(zhuǎn)問題。具體的方法就是當任務(wù)A持鎖失敗的時候，鎖的owner task（即任務(wù)C）需要臨時性的把優(yōu)先級提升至任務(wù)A的優(yōu)先級。而在釋放鎖的時候，將其優(yōu)先級進行恢復原值。
當然，上面只是一個簡單的例子，實際系統(tǒng)會涉及更多的鎖和線程，但原理類似。對于線程，我們需要記錄：
1、該線程持鎖哪些鎖，這些鎖的top waiter是誰，對所有的top waiter按照優(yōu)先級進行排序。
2、該線程阻塞在哪一把鎖上
對于鎖，我們需要記錄：
1、該鎖的owner是誰
2、阻塞在該鎖的線程們（按照優(yōu)先級進行排序）。
注意，這里我們把優(yōu)先級最高的那個阻塞線程叫做該所的top waiter。
有了這些信息，我們需要維持一個準則就OK了：一個任務(wù)的臨時優(yōu)先級應(yīng)該提升至其持有鎖的top waiter線程中最高的那個優(yōu)先級。
【文章福利】小編推薦自己的Linux內(nèi)核技術(shù)交流群:【891587639】整理了一些個人覺得比較好的學習書籍、視頻資料共享在群文件里面，有需要的可以自行添加哦！?。。ê曨l教程、電子書、實戰(zhàn)項目及代碼)? ??
PI-futex是通過rt mutex來實現(xiàn)的，因此我們這里簡單的聊一聊內(nèi)核的這個PI-aware mutex。
從rt mutex的視角看任務(wù)：
rt_mutex_waiter用來抽象一個阻塞在rt mutex的任務(wù)：task成員指向這個任務(wù)，lock成員指向?qū)?yīng)的rt mutex對象，tree_entry是掛入blocker紅黑樹的節(jié)點，rt mutex對象的waiters成員就是這顆紅黑樹的根節(jié)點（wait_lock成員用來保護紅黑樹的操作）。而owner則指向持鎖的任務(wù)。需要特別說明的是waiters這個紅黑樹是按照任務(wù)優(yōu)先級排序的，left most節(jié)點就是對應(yīng)該鎖的top waiter。
從任務(wù)的視角來看rt mutex：
為了支持rt mutex，task struct也增加了若干的成員，最重要的就是pi_waiters。由于一個任務(wù)可以持有多把鎖，每把鎖都有top waiter，因此和一個任務(wù)關(guān)聯(lián)的top waiter也有非常多，這些top waiter形成了一個紅黑樹（同樣也是按照優(yōu)先級排序），pi_waiters成員就是這顆紅黑樹的根節(jié)點。這顆紅黑樹的left most的任務(wù)優(yōu)先級就是實現(xiàn)優(yōu)先級繼承協(xié)議中規(guī)定要臨時提升的優(yōu)先級。pi_top_task成員指向了left most節(jié)點對應(yīng)的任務(wù)對象，我們稱之top pi waiter。Task struct的pi_blocked_on成員則指向其阻塞的rt_mutex_waiter對象。
有了上面的基本概念之后，我們講一下PI chain的概念。首先看看任務(wù)和鎖的基本關(guān)系，如下圖所示：
在上面的圖片中，task 1持有了Lock A和Lock B，阻塞在Lock C上。一個任務(wù)只能阻塞在一個鎖上，所以紅色箭頭只能是從任務(wù)到鎖，不能分叉。由于一個任務(wù)可以持有多把鎖，所以黑色箭頭會有多個鎖指向一個任務(wù)，即多把鎖匯聚于任務(wù)。有了這個基本的關(guān)系圖之后，我們可以形成更加復雜的任務(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)先級必須大于等于PI chain中左端的任務(wù)們。我們以第四條PI chain為例，任務(wù)2的優(yōu)先級必須大于等于任務(wù)1和任務(wù)3的優(yōu)先級，而任務(wù)1的優(yōu)先級必須要大于等于任務(wù)3的優(yōu)先級。
九、PI futex和rt mutex有什么關(guān)系？
熟悉Linux的工程師都了解內(nèi)核中的mutex互斥鎖以及支持PI的互斥鎖版本rt mutex。如果想讓用戶空間的互斥鎖實現(xiàn)優(yōu)先級繼承的功能，那么其實不需要futex模塊實現(xiàn)復雜的PI chain，實際上對PI狀態(tài)的跟蹤是通過rt mutex代理來完成的，原理圖如下：
我們先看接口部分，normal futex使用FUTEX_WAIT和FUTEX_WAKE操作碼來完成阻塞和喚醒的動作。對于PI futex而言，F(xiàn)UTEX_LOCK_PI用來執(zhí)行上鎖，而FUTEX_UNLOCK_PI用來完成解鎖。這里的lock和unlock其實是對futex的代理rt mutex而言的。
無論是normal futex還是PI futex，阻塞于futex的任務(wù)都會有一個futex_q對象與之對應(yīng)。對于normal futex，有了futex_q對象，掛入等待隊列和將其喚醒的功能都能輕松實現(xiàn)。對于PI futex，我們不僅僅需要掛入隊列和喚醒任務(wù)，最重要的是我們需要根據(jù)PI chain完成任務(wù)優(yōu)先級的調(diào)整。為了完成這個功能，需要兩個額外的對象，一個是rt_mutex_waiter，表示一個阻塞在rt mutex的任務(wù)，其rt mutex指針指向了其阻塞在哪個rt mutex上。另外一個是futex_pi_state對象，它記錄了優(yōu)先級翻轉(zhuǎn)的信息，包括該用戶空間上層鎖對應(yīng)的內(nèi)核態(tài)的rt mutex，rt mutex的owner任務(wù)的信息等。
十、Pi futex邏輯過程
Pi futex主要有兩個邏輯過程：通過FUTEX_LOCK_PI上鎖，通過FUTEX_UNLOCK_PI完成釋放鎖的邏輯。
這里的“上鎖”有點誤導，不是“試圖持鎖”的意思，而是競爭上層鎖失敗之后，陷入內(nèi)核準備進入阻塞狀態(tài)。這里為了記錄PI state，所以需要對代理rt mutex執(zhí)行上鎖的動作（基本上也是會阻塞在rt mutex上）。對于pi futex的。正常futex的部分，例如get hash key、找futex對應(yīng)的hash bucket、插入hash隊列等操作，這里不再描述，主要看PI futex特有的部分。
第一次futex lock pi稍微復雜一點，需要完成owner持鎖和current task的阻塞在鎖上這兩個動作。注意：這里的鎖指的是rt mutex。當線程持上層鎖成功的時候，我們并不能同時對rt mutex持鎖成功并設(shè)置owner，因此這時候并不會有futex系統(tǒng)調(diào)用進入內(nèi)核。當?shù)谝淮巫枞臅r候，會通過futex系統(tǒng)調(diào)用把owner id傳遞給內(nèi)核，這時候我們需要分配一個futex pi state對象創(chuàng)建一個rt mutex，同時建立這個rt mutex和owner task的關(guān)系：
1、掛入owner task的futex pi state鏈表。一個任務(wù)可以持有多把上層鎖，所以需要鏈表管理，當然不一定每一個任務(wù)持有的上層鎖都有對應(yīng)的futex pi state對象，沒有競爭也就不會陷入內(nèi)核調(diào)用FUTEX_LOCK_PI。
2、futex pi state對象的owner成員指向?qū)?yīng)的owner task
第二個重要的動作就是讓current task去獲取rt mutex，上面剛剛設(shè)定了owner，這里current task持鎖的結(jié)果大概率就是會阻塞，不過我們本來就是通過這個阻塞關(guān)系來完成PI 狀態(tài)的跟蹤的。rt_mutex_waiter對象抽象了一個阻塞在rt mutex的任務(wù)，我們需要建立rt_mutex_waiter對象、阻塞任務(wù)和rt mutex的關(guān)系，具體包括：
1、rt_mutex_waiter對象的lock成員指向?qū)?yīng)于的rt mutex，表示該任務(wù)阻塞在這個鎖上。rt_mutex_waiter對象的task成員指向當前要阻塞的任務(wù)對象。
2、將rt_mutex_waiter對象插入rt mutex的waiters紅黑樹。
3、task struct的pi_blocked_on設(shè)置為該rt_mutex_waiter對象。
4、對于rt mutex而言，有了新的阻塞任務(wù)，如果優(yōu)先級比目前該rt mutex的top waiter更高的話，那么需要更新owner task的top waiter，將舊的top waiter節(jié)點從紅黑樹中刪除，將新的top waiter插入owner task的top waiter紅黑樹。
5、根據(jù)新的top waiter更新owner task的動態(tài)優(yōu)先級。一旦修改了owner task的優(yōu)先級，那么其相關(guān)的PI chain都需要進行優(yōu)先級調(diào)整。
第二次以及后續(xù)的FUTEX_LOCK_PI會簡單一點，因為不需要新建rt mutex對象了，只需要在bucket找到第一個futex_q對象，通過其pi state指針就可以定位rt mutex了。有了rt mutex，通過上鎖即可讓自己阻塞在這個rt mutex上了。
FUTEX_UNLOCK_PI的流程留給讀者自行分析了。
十一、小結(jié)
本文通過問答的形式簡單的介紹了內(nèi)核futex機制，它是上層同步機制的基石。在PI Futex的介紹中，我們對rt mutex淺嘗輒止，讀者未能領(lǐng)略其全貌。后續(xù)我們會出一篇關(guān)于rt mutex的文章，敬請期待。
原文作者：內(nèi)核工匠
