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

測驗 `1`

對應「並行和多執行緒程式設計」的 Atomics 操作, Thread Pool

〈UNIX 作業系統 fork/exec 系統呼叫的前世今生〉提及 1963 年電腦科學家 Melvin Conway 博士提出的 fork-join 模型，亦即將任務切割成多個子任務，最終彙整各個子任務的結果並得到原任務之結果：

Fork: 即把任務切割成多個子任務並並行運作
Join: 合併切割後的子任務之執行結果，最終得到原任務之結果

Work-stealing 演算法是指某個執行緒從其它工作佇列裡「竊取」(steal) 任務來執行，運作流程圖如下:

設想目前的情境下有個較大的任務，我們可將這個任務分解成許多彼此獨立的子任務。為了減少執行緒之間的競爭，我們將這些子任務分別放入不同的工作佇列 (workqueue) 中，並為每個佇列建立一個獨立的執行緒來執行工作佇列中的任務。執行緒與工作佇列逐一對應，例如執行緒 A負責處理工作佇列 A 中的任務。然而，有些執行緒可能會先完成自身佇列中的任務，其他執行緒對應的工作佇列中卻仍有任務在等待處理。

因此，那些經完成指派任務的執行緒會空閒下來。與其閒置，不如去幫助其他執行緒完成剩下的任務。於是，這個已沒有任務的執行緒就會去其他工作佇列中「竊取」(或說「認領」)一個任務來執行，於是，它們會存取到同一個工作佇列。為了減少竊取任務的執行緒與被竊取任務的執行緒之間的競爭，通常會使用雙向佇列 (double-ended queue，通常縮寫為 deque，發音為 [dek])，被竊取任務的執行緒永遠從雙向佇列的開端處取出任務來執行，而竊取任務的執行緒永遠從雙向佇列的尾端處取出任務來執行。

優點：充分地利用執行緒進行平行運算。
缺點：某些情況下仍然存在競爭，例如雙向佇列中只有一個任務時。除此之外，另一個缺點是它消耗更多的系統資源，例如建立多個執行緒及雙向佇列

延伸閱讀:

Linux kernel: Workqueue
Can better task stealing make Linux faster?

我們嘗試以 C11 Atomics 撰寫 work stealing 程式碼，參見 work-steal.c (部分遮蔽)，編譯和測試: (執行順序可能略有不同)

$ gcc -O2 -Wall -std=c11 -o work-steal work-steal.c -lpthread
$ ./work-steal
...
work ter 1 finished
work item 10 finished
work item 11 finished
work item 14 finished
work item 6 finished
work item 16 finished
Expect 506 lines of output (including this one)

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

使用一致的程式碼風格撰寫，並用最精簡的形式，例如不該寫作 x+y，而是 x + y (+ 運算子前後各有一個空白字元)
表示式若存在變數名稱和數值，應該讓變數名稱先出現，例如不該寫作 1 + x，而是 x + 1，除非後者會導致不同的運算結果
AAAA, BBBB, CCCC, DDDD, EEEE 均為表達式

延伸問題:

研讀程式碼註解提及的論文〈Cilk: An Efficient Multithreaded Runtime System〉，解釋程式碼運作原理
指出上述程式碼可改進之處並著手進行
利用 work stealing 改寫第 1 次作業測驗
$γ$ 提及的並行化快速排序程式碼，並確保能充分運用硬體資源
研讀 Linux 核心的 CMWQ，討論其 work stealing 的實作手法

測驗 `2`

對應「並行和多執行緒程式設計」的 Atomics 操作, Linux 核心同步機制, 多核處理器

為了檢驗學員對〈建立相容於 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 為巨集名稱
均以最簡化的形式書寫，不包含小括號 (即 ( 和 ))

延伸問題:

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

提示: 加上編譯參數 -fsanitize=thread
以 C11 Atomics 改寫，注意 explicit memory model
研讀 Linux 核心 Concurrency Managed Workqueue 的文件和實作，指出其設計和實作考量

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

測驗 1

測驗 2

測驗 `1`

測驗 `2`