Futex 重新排隊 PI¶

將任務從非 PI futex 重新排隊到 PI futex 需要特殊處理，以確保底層的 rt_mutex 在有等待者的情況下永遠不會沒有所有者；這樣做會破壞 PI 提升邏輯 [參見 RT-mutex 實現設計]。為了簡潔起見，本文件中將此操作稱為“requeue_pi”。優先順序繼承在全文中縮寫為“PI”。

動機¶

如果沒有 requeue_pi，pthread_cond_broadcast() 的 glibc 實現必須求助於喚醒所有等待 pthread_condvar 的任務，並讓它們嘗試以經典的驚群效應形式理清哪個任務首先執行。一個理想的實現是喚醒最高優先順序的等待者，並讓其餘的等待者透過與 condvar 關聯的互斥鎖的解鎖來自然喚醒。

考慮簡化的 glibc 呼叫

/* caller must lock mutex */
pthread_cond_wait(cond, mutex)
{
        lock(cond->__data.__lock);
        unlock(mutex);
        do {
        unlock(cond->__data.__lock);
        futex_wait(cond->__data.__futex);
        lock(cond->__data.__lock);
        } while(...)
        unlock(cond->__data.__lock);
        lock(mutex);
}

pthread_cond_broadcast(cond)
{
        lock(cond->__data.__lock);
        unlock(cond->__data.__lock);
        futex_requeue(cond->data.__futex, cond->mutex);
}

一旦 pthread_cond_broadcast() 重新排隊了任務，cond->mutex 就有了等待者。請注意，pthread_cond_wait() 僅在其返回到使用者空間後才嘗試鎖定互斥鎖。這將使底層的 rt_mutex 有等待者，但沒有所有者，從而破壞了前面提到的 PI 提升演算法。

為了支援具有 PI 感知的 pthread_condvar，核心需要能夠將任務重新排隊到 PI futexes。這種支援意味著，在成功的 futex_wait 系統呼叫之後，呼叫者將返回到使用者空間，並已經持有 PI futex。 glibc 實現將修改如下

/* caller must lock mutex */
pthread_cond_wait_pi(cond, mutex)
{
        lock(cond->__data.__lock);
        unlock(mutex);
        do {
        unlock(cond->__data.__lock);
        futex_wait_requeue_pi(cond->__data.__futex);
        lock(cond->__data.__lock);
        } while(...)
        unlock(cond->__data.__lock);
        /* the kernel acquired the mutex for us */
}

pthread_cond_broadcast_pi(cond)
{
        lock(cond->__data.__lock);
        unlock(cond->__data.__lock);
        futex_requeue_pi(cond->data.__futex, cond->mutex);
}

實際的 glibc 實現可能會測試 PI，並在現有呼叫中進行必要的更改，而不是為 PI 情況建立新的呼叫。 pthread_cond_timedwait() 和 pthread_cond_signal() 也需要類似的更改。

實現¶

為了確保 rt_mutex 在有等待者的情況下有一個所有者，requeue 程式碼和等待程式碼都必須能夠在返回到使用者空間之前獲取 rt_mutex。 requeue 程式碼不能簡單地喚醒等待者並讓它獲取 rt_mutex，因為它會在 requeue 呼叫返回到使用者空間和等待者喚醒並開始執行之間開啟一個競爭視窗。這在無競爭的情況下尤其如此。

該解決方案涉及兩個新的 rt_mutex 輔助例程，rt_mutex_start_proxy_lock() 和 rt_mutex_finish_proxy_lock()，它們允許 requeue 程式碼代表等待者獲取無競爭的 rt_mutex，並將等待者排隊到有競爭的 rt_mutex。兩個新的系統呼叫提供了核心<->使用者介面來 requeue_pi：FUTEX_WAIT_REQUEUE_PI 和 FUTEX_CMP_REQUEUE_PI。

FUTEX_WAIT_REQUEUE_PI 由等待者 (pthread_cond_wait() 和 pthread_cond_timedwait()) 呼叫，以阻止初始 futex 並等待重新排隊到具有 PI 感知的 futex。該實現是 futex_wait() 和 futex_lock_pi() 之間高速碰撞的結果，帶有一些額外的邏輯來檢查額外的喚醒場景。

FUTEX_CMP_REQUEUE_PI 由喚醒者 (pthread_cond_broadcast() 和 pthread_cond_signal()) 呼叫，以重新排隊並可能喚醒等待的任務。在內部，此係統呼叫仍由 futex_requeue 處理（透過傳遞 requeue_pi=1）。在重新排隊之前，futex_requeue() 嘗試代表最頂層的等待者獲取 requeue 目標 PI futex。如果可以，則喚醒此等待者。 futex_requeue() 然後繼續將剩餘的 nr_wake+nr_requeue 任務重新排隊到 PI futex，在每次重新排隊之前呼叫 rt_mutex_start_proxy_lock()，以準備將該任務作為底層 rt_mutex 的等待者。如果在這個階段也可以獲取鎖，那麼下一個等待者會被喚醒以完成鎖的獲取。

FUTEX_CMP_REQUEUE_PI 接受 nr_wake 和 nr_requeue 作為引數，但它們的總和才是真正重要的。 futex_requeue() 將喚醒或重新排隊最多 nr_wake + nr_requeue 個任務。它只會喚醒它可以獲取鎖的任務，在大多數情況下應該是 0，因為良好的程式設計習慣表明 pthread_cond_broadcast() 或 pthread_cond_signal() 的呼叫者在進行呼叫之前獲取互斥鎖。 FUTEX_CMP_REQUEUE_PI 要求 nr_wake=1。 nr_requeue 對於廣播應為 INT_MAX，對於訊號應為 0。

Linux 核心

目錄

本頁

Futex 重新排隊 PI¶

動機¶

實現¶