---
tags: linux2023
---

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

### 測驗 `1`
> 對應「並行和多執行緒程式設計」的 [Atomics 操作](https://hackmd.io/@sysprog/concurrency-atomics), [Thread Pool](https://hackmd.io/@sysprog/concurrency-thread-pool)

〈[UNIX 作業系統 fork/exec 系統呼叫的前世今生](https://hackmd.io/@sysprog/unix-fork-exec)〉提及 1963 年電腦科學家 Melvin Conway 博士提出的 fork-join 模型，亦即將任務切割成多個子任務，最終彙整各個子任務的結果並得到原任務之結果：
* Fork: 即把任務切割成多個子任務並並行運作
* Join: 合併切割後的子任務之執行結果，最終得到原任務之結果


[Work-stealing](https://en.wikipedia.org/wiki/Work_stealing) 演算法是指某個執行緒從其它工作佇列裡「竊取」(steal) 任務來執行，運作流程圖如下:

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

因此，那些經完成指派任務的執行緒會空閒下來。與其閒置，不如去幫助其他執行緒完成剩下的任務。於是，這個已沒有任務的執行緒就會去其他工作佇列中「竊取」(或說「認領」)一個任務來執行，於是，它們會存取到同一個工作佇列。為了減少竊取任務的執行緒與被竊取任務的執行緒之間的競爭，通常會使用雙向佇列 (double-ended queue，通常縮寫為 deque，發音為 [dek])，被竊取任務的執行緒永遠從雙向佇列的開端處取出任務來執行，而竊取任務的執行緒永遠從雙向佇列的尾端處取出任務來執行。
* 優點：充分地利用執行緒進行平行運算。
* 缺點：某些情況下仍然存在競爭，例如雙向佇列中只有一個任務時。除此之外，另一個缺點是它消耗更多的系統資源，例如建立多個執行緒及雙向佇列

延伸閱讀:
* Linux kernel: [Workqueue](https://www.kernel.org/doc/html/next/core-api/workqueue.html)
* [Can better task stealing make Linux faster?](https://blogs.oracle.com/linux/post/can-better-task-stealing-make-linux-faster)

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

$ 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` 均為表達式

:::success
延伸問題:
1. 研讀程式碼註解提及的論文〈[Cilk: An Efficient Multithreaded Runtime System](http://supertech.csail.mit.edu/papers/PPoPP95.pdf)〉，解釋程式碼運作原理
2. 指出上述程式碼可改進之處並著手進行
3. 利用 work stealing 改寫[第 1 次作業](https://hackmd.io/@sysprog/linux2023-summer-quiz0)測驗 $\gamma$ 提及的並行化快速排序程式碼，並確保能充分運用硬體資源
4. 研讀 Linux 核心的 [CMWQ](https://www.kernel.org/doc/html/next/core-api/workqueue.html)，討論其 work stealing 的實作手法
:::

---

### 測驗 `2`
> 對應「並行和多執行緒程式設計」的 [Atomics 操作](https://hackmd.io/@sysprog/concurrency-atomics), [Linux 核心同步機制](https://hackmd.io/@sysprog/linux-sync), [多核處理器](https://hackmd.io/@sysprog/multicore-locks)

為了檢驗學員對〈[建立相容於 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) 的文件和實作，指出其設計和實作考量
:::