--- tags: linux2023 --- # [2023q1](http://wiki.csie.ncku.edu.tw/linux/schedule) 第 9 週測驗題 :::info 目的: 檢驗學員對並行程式設計的認知 ::: ==[作答表單: 測驗 1](https://docs.google.com/forms/d/e/1FAIpQLSez5FvTjZfSGTsX6XgRE1PkfXM4BYXhvG6uAl7G5ngVms4fSg/viewform)== (針對 Linux 核心「設計」課程) ==[作答表單: 測驗 2](https://docs.google.com/forms/d/e/1FAIpQLSetDYMBH3_qB1nIxlqh44fFDtL6utFxPQL14Cfe8dqQDTR47Q/viewform)== (針對 Linux 核心「實作」課程) ### 測驗 `1` 為了檢驗學員對〈[建立相容於 POSIX Thread 的實作](https://hackmd.io/@sysprog/concurrency-thread-package)〉的認知,以下嘗試使用 GCC [Built-in Functions for Memory Model Aware Atomic Operations](https://gcc.gnu.org/onlinedocs/gcc/_005f_005fatomic-Builtins.html) 和 [futex](https://en.wikipedia.org/wiki/Futex) 來實作 multiple-producer/multiple-consumer (MPMC): ![](https://hackmd.io/_uploads/Hy0mZYzfh.png) [futex](https://en.wikipedia.org/wiki/Futex) 全名為 fast user-space mutex locking,是 Linux 核心一種機制,主要提供使用者層級中有效與多執行緒的同步方式,並降低 Linux 核心的介入。可參考 [Basics of Futexes](https://eli.thegreenplace.net/2018/basics-of-futexes/)。futex 主要有 wait 和 wake 等二個操作,其定義如下: ```cpp /* uaddr 指向一個地址,val 代表這個地址期待的值, 當 *uaddr == val 時,才會進行 wait */ int futex_wait(int *uaddr, int val); /* 喚醒 n 個 uaddr 指向的 lock 變數,對應到等待中的行程或執行緒 */ int futex_wake(int *uaddr, int n); ``` 編譯方式: ```shell $ gcc -Wall -std=c11 -o mpmc mpmc.c -lpthread ``` 參考執行輸出如下: ``` Amount: 10000000 #0 ints[1-10000000] have been verified through elapsed time: 0.835668 seconds DONE #0 #1 ints[1-10000000] have been verified through elapsed time: 0.837184 seconds DONE #1 #2 ints[1-10000000] have been verified through elapsed time: 0.829464 seconds DONE #2 ... #7 ints[1-10000000] have been verified through elapsed time: 0.761233 seconds DONE #7 ``` 原始程式碼可見 [mpmc.c](https://gist.github.com/jserv/c7957a65f810205da462909491dae4bf) (部分遮蔽)。請補完程式碼,使其運作符合預期。作答規範: * `ZAAA` 和 `ZCCC` 為整數 * `ZBBB` 為表示式,使用 lab0-c 的程式碼風格 * `ZDDD` 為巨集名稱 * 均以最簡化的形式書寫,不包含小括號 (即 `(` 和 `)`) :::success 延伸問題: 1. 解釋上述程式碼運作原理,指出實作上的限制 > 提示: 加上編譯參數 `-fsanitize=thread` 2. 以 C11 Atomics 改寫,注意 explicit memory model 3. 研讀 Linux 核心 [Concurrency Managed Workqueue](https://www.kernel.org/doc/html/latest/core-api/workqueue.html) 的文件和實作,指出其設計和實作考量 ::: --- ### 測驗 `2` 以下程式碼嘗試用 POSIX Thread 重新實作 [Linux 核心設計: RCU 同步機制](https://hackmd.io/@sysprog/linux-rcu),提供下列操作介面: * `rcu_read_lock` * `rcu_read_unlock` * `synchronize_rcu` * `rcu_assign_pointer` `rculist.h` 是重寫 Linux 核心同名的標頭檔,搭配閱讀 [A Tour Through RCU's Requirements](https://www.kernel.org/doc/Documentation/RCU/Design/Requirements/Requirements.html): > RCU's grace-period guarantee allows updaters to wait for the completion of all pre-existing RCU read-side critical sections. An RCU read-side critical section begins with the marker `rcu_read_lock()` and ends with the marker `rcu_read_unlock()`. These markers may be nested, and RCU treats a nested set as one big RCU read-side critical section. `__CHECKER__` 的標示是針對 [Sparse](https://www.kernel.org/doc/html/latest/dev-tools/sparse.html) 這套程式碼靜態分析器。 程式碼可見: [thread-rcu](https://gist.github.com/jserv/f1460f9c542e123e371988ac8bef788a) (部分遮蔽) 參考執行輸出: ``` $ ./test [tracer] loop 1000 : 465075987.000000 ns ``` 請補完程式碼,使其運作符合預期。作答規範: * `AAAA` 為表示式,使用 lab0-c 的程式碼風格 * `BBBB` 為整數,用最精簡的形式書寫 * `CCCC` 為函式名稱,使用 GCC [Built-in Functions for Memory Model Aware Atomic Operations](https://gcc.gnu.org/onlinedocs/gcc/_005f_005fatomic-Builtins.html) :::success 延伸問題: 1. 解釋上述程式碼運作原理,指出實作上的限制 > 提示: 加上編譯參數 `-fsanitize=thread` 2. 以 C11 Atomics 改寫,注意 explicit memory model 3. 與 [Userspace RCU](https://liburcu.org/) 進行比較,討論上述程式碼的涵蓋狀況,並提及現有缺失和如何改進 > 搭配閱讀 [Userspace RCU](https://hackmd.io/@cccccs100203/Userspace-RCU) :::