---
tags: linux2023
---

# [2023 年暑期 Linux 核心課程](https://hackmd.io/@sysprog/linux2023-summer)第 1 次測驗題
==[作答表單](https://docs.google.com/forms/d/e/1FAIpQLScltJqNi_xtBFm-tsotSt3s_dHRtvV6y0yN6eGtYrRvn4uLJA/viewform)==

### 測驗 `1`
> 對應「並行和多執行緒程式設計」的[執行順序](https://hackmd.io/@sysprog/concurrency-ordering), [Atomics 操作](https://hackmd.io/@sysprog/concurrency-atomics), [POSIX Threads](https://hackmd.io/@sysprog/posix-threads)

為了充分支援 pthread_cond 的實作，特別是廣播 (broadcast) 操作，[futex(2)](https://man7.org/linux/man-pages/man2/futex.2.html) 引入 requeue 功能，並藉由 futex 系統呼叫提供相關操作介面，其中包括一對相互匹配的操作 `futex_wait_requeue_pi` 和 `futex_requeue`。

在多個臨界區段 (critical section，簡稱 CS) 之間，使用 mutex 保證互斥性，但無法滿足不同臨界區段之間的[前後順序](https://hackmd.io/@sysprog/concurrency-ordering)。因此，我們可使條件變數（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](https://en.wikipedia.org/wiki/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](https://docs.kernel.org/locking/futex-requeue-pi.html)
* [Futexes Are Tricky](https://dept-info.labri.fr/~denis/Enseignement/2008-IR/Articles/01-futex.pdf)
* [Requeue PI: Making Glibc Condvars PI Aware](https://www.osadl.org/fileadmin/dam/presentations/RTLWS11/dvhart-requeue-pi.pdf)
* [The path of the private futex](http://events17.linuxfoundation.org/sites/events/files/slides/2016_futex.pdf)
* Android: [Avoiding priority inversion](https://source.android.com/docs/core/audio/avoiding_pi?hl=en)

我們嘗試用 futex 實作一個精簡的 POSIX Threads 的替代品，並利用上述 futex requeue 機制，參見[原始程式碼](https://gist.github.com/jserv/ee66b80157f8553fd355ba4559e1b5c6) (部分遮蔽)。

編譯和測試:

$ 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_` 開頭的函式
* 以最精簡的方式撰寫

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