--- tags: linux2023 --- # [2023q1](http://wiki.csie.ncku.edu.tw/linux/schedule) 第 11 週測驗題 :::info 目的: 檢驗學員對並行程式設計和 [CS:APP 第 9 章](https://hackmd.io/@sysprog/CSAPP-ch9)的認知 ::: ==[作答表單: 測驗 1](https://docs.google.com/forms/d/e/1FAIpQLSfNEyKnQpyqta3dWvFKRMxXV7Bk9MAy0Sz2iuL9rIvI11CI1w/viewform)== (針對 Linux 核心「設計」課程) ==[作答表單: 測驗 2](https://docs.google.com/forms/d/e/1FAIpQLSc4BH7fOammOHmy0OwvJ8AfYJVn0gwkR2YUnTKG20sjC6kr7g/viewform)== (針對 Linux 核心「實作」課程) ### 測驗 `1` 以下程式碼依據論文〈[Lock-Free Linked Lists and Skip Lists](http://www.cse.yorku.ca/~ruppert/papers/lfll.pdf)〉，嘗試實作 non-blocking singly-linked list，參見 [gist](https://gist.github.com/jserv/6cffe51fa2fbeb3f25c4573281a05c74)，新增和刪除的操作建立在一個 key 值唯一且由小到大排序的鏈結串列。已知測試程式碼不會遇到任何 assert 錯誤。 ![](https://hackmd.io/_uploads/SJQa3eSm3.png) Thoughput 及 Scability 隨著執行緒數量的增加而提升。 請補完程式碼，使其運作符合預期。作答規範: * `AAAA` 為 enum identifier * `BBBB`, `CCCC`, `DDDD` 為表示式，請以最精簡的 C11 程式碼撰寫，不包含小括號 (即 `(` 和 `)`) * 依據指定程式碼風格撰寫 :::success 延伸問題: 1. 解釋上述程式碼運作原理，指出其實作缺失並改進 2. 使用 ThreadSanitizer 可發現，上述程式碼會在執行時期遇到 data race，嘗試改進 3. 探討 Linux 核心的鏈結串列如何達到並行 (找出對應的應用情境)，以及如何確保 lock-free ::: --- ### 測驗 `2` 以下嘗試運用 [CS:APP 第 9 章](https://hackmd.io/@sysprog/CSAPP-ch9) 提到的 [mmap(2)](https://man7.org/linux/man-pages/man2/mmap.2.html) 撰寫簡易的記憶體配置器，編譯和測試: ```shell $ 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](https://gist.github.com/jserv/6ba3bacbbde6ccbf1f0a2b26f00b92a3) (部分遮蔽)，已知測試程式碼不會遇到任何 assert 錯誤。 請補完程式碼，使其運作符合預期。作答規範: * `AAAA` 為 identifier * `BBBB` 和 `CCCC`為表示式，請以最精簡的 C11 程式碼撰寫，不包含小括號 (即 `(` 和 `)`) * 依據指定程式碼風格撰寫 對照: * [第 5 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz5) * [第 6 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz6) 延伸閱讀: * [Lock-Free Linked List with Lockless Memory Allocation](https://hackmd.io/@Korin777/linux2022-final) * [mimalloc 改進](https://hackmd.io/@hankluo6/allocator) / [Issue #430](https://github.com/microsoft/mimalloc/pull/430) [mmap-malloc](https://github.com/mdukat/mmap-malloc) 支援多執行緒