---
tags: linux2023
---

# [2023q1](http://wiki.csie.ncku.edu.tw/linux/schedule) 第 12 週測驗題

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

==[作答表單](https://docs.google.com/forms/d/e/1FAIpQLSeaNhpZc-F68CDR9dDdTKB-9K9SBXYtZLCKfkyKVI6rVJCCmw/viewform)==

### 測驗 `1`

〈[Linux 核心的 hash table 實作](https://hackmd.io/@sysprog/linux-hashtable)〉提及的實作並未考慮到並行，在此我們著手實作支援多執行緒的版本，並考慮到以下:
* [deep copy](https://en.wikipedia.org/wiki/Object_copying)
* 運用 [callback](https://en.wikipedia.org/wiki/Callback_(computer_programming)) 處理數值傳遞和資源釋放
* 呼叫 [sched_yield](https://man7.org/linux/man-pages/man2/sched_yield.2.html)
* 利用 [libut](https://github.com/xant/libut) 進行 unit test

程式碼可見: [gist](https://gist.github.com/jserv/924ff747e0c8b4aaeb12bc124aa0b483) (部分遮蔽)

延伸閱讀:
* [Split-Ordered Lists: Lock-Free Extensible Hash Tables](https://ldhulipala.github.io/readings/split_ordered_lists.pdf)
* [High Performance Dynamic Lock-Free Hash Tables and List-Based Sets](https://docs.rs/crate/crossbeam/0.2.4/source/hash-and-skip.pdf)
* [Safe memory reclamation for dynamic lock-free objects using atomic reads and writes](https://dl.acm.org/doi/10.1145/571825.571829) (使用 hazard pointer)

:::success
延伸問題:
1. 解釋上述程式碼運作原理，並利用 C11 Atomics 改寫程式
2. 探討效能表現，並提出改進方案
:::