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

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) 撰寫簡易的記憶體配置器，編譯和測試:

$ 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) 支援多執行緒