2023q1 第 11 週測驗題

目的: 檢驗學員對並行程式設計和 CS:APP 第 9 章的認知

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

測驗 1

以下程式碼依據論文〈Lock-Free Linked Lists and Skip Lists〉，嘗試實作 non-blocking singly-linked list，參見 gist，新增和刪除的操作建立在一個 key 值唯一且由小到大排序的鏈結串列。已知測試程式碼不會遇到任何 assert 錯誤。

Thoughput 及 Scability 隨著執行緒數量的增加而提升。

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

• AAAA 為 enum identifier
• BBBB, CCCC, DDDD 為表示式，請以最精簡的 C11 程式碼撰寫，不包含小括號 (即 ( 和 ))
• 依據指定程式碼風格撰寫

延伸問題:

1. 解釋上述程式碼運作原理，指出其實作缺失並改進
2. 使用 ThreadSanitizer 可發現，上述程式碼會在執行時期遇到 data race，嘗試改進
3. 探討 Linux 核心的鏈結串列如何達到並行 (找出對應的應用情境)，以及如何確保 lock-free

---

測驗 2

以下嘗試運用 CS:APP 第 9 章 提到的 mmap(2) 撰寫簡易的記憶體配置器，編譯和測試:

$ cc -c -Wall -Wextra -I. -O2 -std=gnu99 alloc.c -o alloc.o
$ cc -Wall -Wextra -I. -O2 -std=gnu99 test.c alloc.o -o test.elf
$ ./test.elf 

參考執行輸出:

largest successfull alloc: 136 GB

程式碼可見 alloc (部分遮蔽)，已知測試程式碼不會遇到任何 assert 錯誤。

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

• AAAA 為 identifier
• BBBB 和 CCCC為表示式，請以最精簡的 C11 程式碼撰寫，不包含小括號 (即 ( 和 ))
• 依據指定程式碼風格撰寫

對照:

• 第 5 週測驗題
• 第 6 週測驗題

延伸閱讀:

• Lock-Free Linked List with Lockless Memory Allocation
• mimalloc 改進 / Issue #430

mmap-malloc 支援多執行緒