2022q1 第 6 週測驗題

目的: 檢驗學員對 《Demystifying the Linux CPU Scheduler》 和 並行和多執行緒程式設計 的認知

作答表單:

• 測驗 1 (Linux 核心設計)
• 測驗 2 (Linux 核心實作)

測驗 1

〈UNIX 作業系統 fork/exec 系統呼叫的前世今生〉提到 clone 系統呼叫，搭配閱讀〈Implementing a Thread Library on Linux〉，以下嘗試撰寫一套使用者層級的執行緒函式庫，程式碼可見: readers.c

預期執行輸出: (順序可能會變異)

Reader process in
Reader process out
Reader process in
Reader process out
Writer process in
Reader process in
Writers process out
Reader process out
Writer process in
Writers process out
Writer process in
Writers process out
Reader process in
Reader process in
Reader process out
Reader process out
Writer process in
Writers process out
Writer process in
Writers process out

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

• EXP1 和 EXP2 皆為表示式，應以符合一致程式碼風格的 C99 程式撰寫
• EXP1 和 EXP2 都不包含小括號 (即 ( 和 )) 或 ; 和 , 這樣的分隔符號
• 確保以最簡潔的形式書寫

延伸問題:

1. 解釋上述程式碼運作原理，並指出其設計和實作的缺失
2. 學習 uThread，實作效能分析，比較 POSIX Thread (NPTL) 和自行建立的 N:1 Threading model 之間的效能落差

---

測驗 2

在〈並行和多執行緒程式設計〉講座中，談及 lock-free 程式設計。我們延展第 5 週測驗題裡頭的 hazard pointer，考慮一個 lock-free hash table 實作，程式碼可見 gist，請補完程式碼，使其運作符合預期。參考執行輸出:

Loop 1. All values found. hashmap_put_retries=714, hashmap_put_head_fail=0, hashmap_put_replace_fail=0
Done. Loops=1
Done. Needed 1 loops

作答規範:

• KKKK, QQQQ 和 ZZZZ 皆為表示式，應以符合一致程式碼風格的 C99 程式撰寫
• KKKK, QQQQ 和 ZZZZ 都不包含小括號 (即 ( 和 )) 或 ; 和 , 這樣的分隔符號
• 確保以最簡潔的形式書寫

作答區

• KKKK = ?
• QQQQ = ?
• ZZZZ = ?

延伸問題:

1. 解釋上述程式碼運作原理，並指出其設計和實作的缺失 (如原本只接受 uin32_t 型態的輸入，無法處理字串作為 key)
2. 研讀 lfht (Lock-free wait-free hash table using C11 atomics) 程式碼及對應的論文 Lock-Free Linked Lists and Skip Lists
3. 參照 atomic_hash 及其內建的測試程式，用更大規模的來測試