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 錯誤。

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

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
  • BBBBCCCC為表示式,請以最精簡的 C11 程式碼撰寫,不包含小括號 (即 ())
  • 依據指定程式碼風格撰寫

對照:

延伸閱讀:

mmap-malloc 支援多執行緒