---
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):

[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 等二個操作，其定義如下:

/* uaddr 指向一個地址，val 代表這個地址期待的值， 當 *uaddr == val 時，才會進行 wait */
int futex_wait(int *uaddr, int val);

/* 喚醒 n 個 uaddr 指向的 lock 變數，對應到等待中的行程或執行緒 */
int futex_wake(int *uaddr, int n);

編譯方式:

$ 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)
:::