2023 年暑期 Linux 核心課程第 1 次測驗題

作答表單

測驗 1

對應「並行和多執行緒程式設計」的執行順序, Atomics 操作, POSIX Threads

為了充分支援 pthread_cond 的實作，特別是廣播 (broadcast) 操作，futex(2) 引入 requeue 功能，並藉由 futex 系統呼叫提供相關操作介面，其中包括一對相互匹配的操作 futex_wait_requeue_pi 和 futex_requeue。

在多個臨界區段 (critical section，簡稱 CS) 之間，使用 mutex 保證互斥性，但無法滿足不同臨界區段之間的前後順序。因此，我們可使條件變數（condition variable，簡稱 condvar 或 cond）在一個臨界區段 A 中等待另一臨界區段 B 的訊號 (signal)。

condvar 不僅是互斥的同步機制，還要一種方式等待其他執行緒進行某些操作。當我們需要在臨界區段 A 中等待臨界區段 B 先完成某些操作時，可用 condvar。

一個 condvar 必須與一個 mutex 配對使用，因此等待 condvar 的過程實際上涉及二次等待：

• 等待 condvar 的訊號（通常由其他執行緒的發出)
• 等待所屬的 mutex lock 的釋放

這也意味著等待的執行緒需要兩次等待 (wait) 和兩次喚醒 (wake)。

發送 condvar 訊號（signal）會喚醒等待在 condvar 上的一個執行緒，該執行緒接著將等待轉移至所屬的 mutex lock。使用 broadcast 的方法則是喚醒所有等待在 condvar 上的執行緒。

為了避免浪費喚醒操作所導致的執行緒切換，可將等待在二個佇列之間的執行緒縮減為一次呼叫，以減少競爭 mutex lock 的次數。這就是 futex 提供的 requeue 功能。

被 requeue 的等待者（即呼叫 futex_wait_requeue_pi 阻塞的執行緒），必須等待所屬的 condvar 的 mutex lock 的釋放。當被呼叫的執行緒從 futex_wait_requeue_pi 呼叫中被喚醒，並不意味著它已持有 (acquire) 所屬的 condvar 的 mutex lock，它需要去競爭該 lock。

requeue 在此過程中將 condvar 和 mutex 鎖視為 futex1 和 futex2。

futex_requeue 函式原型如下：

static int futex_requeue(u32 __user *uaddr1, unsigned int flags,
                         u32 __user *uaddr2, int nr_wake, int nr_requeue,
                         u32 *cmpval, int requeue_pi);

該函式的功能是，將 uaddr1 對應的 futex 等待佇列最多移出 (nr_wake + nr_requeue) 個 futex_q，先喚醒 nr_wake 個 futex_q，然後將剩餘的 futex_q 重新加入到 uaddr2 對應的 futex 等待佇列。而 pthread_cond_broadcast 固定設定參數 nr_wake = 1，nr_requeue = INT_MAX。這意味著在廣播操作時只會喚醒一個執行緒去競爭 uaddr2 所對應的 futex，而其餘在 uaddr1 等待的執行緒將重新加入到 uaddr2 對應的等待佇列。

requeue-pi 是指所屬的 condvar mutex 使用 priority inheritance (PI) 協定的 mutex，即 futex2 是 pi-futex。requeue-pi 對非 PI futex 的等待者進行移出再加入到 pi-futex 的等待佇列進行特殊的最佳化。futex_requeue 函式只會喚醒那些可立即持有 pi-futex lock 的執行緒，也就是說，對於每個被重新加入到 pi-futex 的等待者佇列，它們只有在成功鎖定 pi-futex 後才能被喚醒。這可確保只有一個被喚醒的執行緒可持有 pi-futex 鎖，其餘的等待者將直接重新加入到 pi-futex 的等待佇列中，而不再進行鎖定的嘗試。雖然 futex_proxy_trylock_atomic 不像 futex_lock_pi 需要呼叫 rt_mutex_trylock，但與非 PI 到非 PI 的 requeue 一樣，這會增加額外的嘗試。

延伸閱讀:

• Futex Requeue PI
• Futexes Are Tricky
• Requeue PI: Making Glibc Condvars PI Aware
• The path of the private futex
• Android: Avoiding priority inversion

我們嘗試用 futex 實作一個精簡的 POSIX Threads 的替代品，並利用上述 futex requeue 機制，參見原始程式碼 (部分遮蔽)。

編譯和測試:

$ make check

參考執行輸出:

Running test_pthread ... [OK]
Running test_linux ... [OK]

對於大部分的主機來說，test_linux 應在 10 秒內可完成執行

請補完程式碼，使得 main.c 規範的測試行為得以符合預期，並保持 POSIX Thread 的相容性，注意程式執行時間應該要相仿。

作答規範:

• AAAA 為 MUTEX_ 開頭的巨集
• BBBB, CCCC, DDDD 為 0 或 1 的數值
• EEEE 和 FFFF 為 futex_ 開頭的函式
• 以最精簡的方式撰寫

延伸問題:

• 解釋上述程式碼運作原理，應該涵蓋測試方法、futex 使用方式、Linux 核心開發者針對 POSIX Threads 強化哪些相關 futex 實作機制等等
• 修改第 1 次作業的測驗
  $\gamma$ 提供的並行版本快速排序法實作，使其得以搭配上述 futex 程式碼運作
• 研讀〈並行程式設計: 建立相容於 POSIX Thread 的實作〉，在上述程式碼的基礎之上，實作 priority inheritance mutex 並確認與 glibc 實作行為相同，應有對應的 PI 測試程式碼
• 比照 skinny-mutex，設計 POSIX Threads 風格的 API，並利用內附的 perf.c (斟酌修改) 確認執行模式符合預期，過程中也該比較 glibc 的 POSIX Threads 效能表現