2023q1 第 9 週測驗題

目的: 檢驗學員對並行程式設計的認知

作答表單: 測驗 1 (針對 Linux 核心「設計」課程)
作答表單: 測驗 2 (針對 Linux 核心「實作」課程)

測驗 1

為了檢驗學員對〈建立相容於 POSIX Thread 的實作〉的認知，以下嘗試使用 GCC Built-in Functions for Memory Model Aware Atomic Operations 和 futex 來實作 multiple-producer/multiple-consumer (MPMC):

futex 全名為 fast user-space mutex locking，是 Linux 核心一種機制，主要提供使用者層級中有效與多執行緒的同步方式，並降低 Linux 核心的介入。可參考 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 (部分遮蔽)。請補完程式碼，使其運作符合預期。作答規範:

• ZAAA 和 ZCCC 為整數
• ZBBB 為表示式，使用 lab0-c 的程式碼風格
• ZDDD 為巨集名稱
• 均以最簡化的形式書寫，不包含小括號 (即 ( 和 ))

延伸問題:

1. 解釋上述程式碼運作原理，指出實作上的限制

   提示: 加上編譯參數 -fsanitize=thread

2. 以 C11 Atomics 改寫，注意 explicit memory model
3. 研讀 Linux 核心 Concurrency Managed Workqueue 的文件和實作，指出其設計和實作考量

---

測驗 2

以下程式碼嘗試用 POSIX Thread 重新實作 Linux 核心設計: RCU 同步機制，提供下列操作介面:

• rcu_read_lock
• rcu_read_unlock
• synchronize_rcu
• rcu_assign_pointer

rculist.h 是重寫 Linux 核心同名的標頭檔，搭配閱讀 A Tour Through RCU's Requirements:

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 這套程式碼靜態分析器。
程式碼可見: thread-rcu (部分遮蔽)

參考執行輸出:

$ ./test 
[tracer] loop 1000 : 465075987.000000 ns

請補完程式碼，使其運作符合預期。作答規範:

• AAAA 為表示式，使用 lab0-c 的程式碼風格
• BBBB 為整數，用最精簡的形式書寫
• CCCC 為函式名稱，使用 GCC Built-in Functions for Memory Model Aware Atomic Operations

延伸問題:

1. 解釋上述程式碼運作原理，指出實作上的限制

   提示: 加上編譯參數 -fsanitize=thread

2. 以 C11 Atomics 改寫，注意 explicit memory model
3. 與 Userspace RCU 進行比較，討論上述程式碼的涵蓋狀況，並提及現有缺失和如何改進

   搭配閱讀 Userspace RCU