---
tags: linux2023
---
# [2023 年暑期 Linux 核心課程](https://hackmd.io/@sysprog/linux2023-summer)第 3 次作業
> :information_source: 請提交到 ==[作業區](https://hackmd.io/@sysprog/S1zfQwD62)==，預計九月安排作業檢討的線上講座
### 挑戰 `1`
:::success
作業描述:
1. 研讀[第 2 次測驗題](https://hackmd.io/@sysprog/linux2023-summer-quiz2)的測驗 `1`，研讀程式碼註解提及的論文〈[Cilk: An Efficient Multithreaded Runtime System](http://supertech.csail.mit.edu/papers/PPoPP95.pdf)〉，解釋程式碼運作原理
2. 指出 [work-stealing](https://github.com/sysprog21/concurrent-programs/tree/master/work-steal) 程式碼可改進之處並著手進行。(歡迎提交 pull request 到 [concurrent-programs](https://github.com/sysprog21/concurrent-programs))
3. 利用 work stealing 改寫[第 1 次作業](https://hackmd.io/@sysprog/linux2023-summer-quiz0)測驗 $\gamma$ 提及的並行化快速排序程式碼，並確保能充分運用硬體資源
4. 研讀 Linux 核心的 [CMWQ](https://www.kernel.org/doc/html/next/core-api/workqueue.html)，討論其 work stealing 的實作手法
:::
---
### 挑戰 `2`
[ticket spinlock](https://en.wikipedia.org/wiki/Ticket_lock) 藉由「抽號碼牌」的機制，讓每個處理器核都有機會持有 (acquire) lock。示範程式碼:
```c
struct spinlock {
unsigned short owner;
unsigned short next;
};
void spin_lock(struct spinlock *lock) {
unsigned short next = xadd(&lock->next, 1);
while (lock->owner != next);
}
void spin_unlock(struct spinlock *lock) {
lock->owner++;
}
```
其中 `xadd(a ,b)` 是 atomic 操作，回傳 a 的內含值並將 `a + b` 的結果寫回記憶體，整個動作一氣呵成 (atomic)。當上述程式碼的 Owner 等於 spin_lock() 中 next 的值時，也就代表號碼牌叫到該執行緒了，這時候，該執行緒就可以跳出迴圈並進入到 CS ，等到結束執行 CS 後，在將 lock 的擁有者交給下一個執行緒。
其中 `xadd(a, b)` 是個 atomic 操作，回傳變數 `a` 的內含值，並將結果 `a + b` 寫回到記憶體，整個過程是不可分割的（atomic）。當上述程式碼中的 `owner` 等於 `spin_lock()` 中 `next` 的值時，意味著著輪到該執行緒操作。這時，該執行緒可退出迴圈，進入到臨界區段 (criticial section)，在完成臨界區段操作後，將 lock 的持有權傳遞給下個執行緒。
透過上面的解說可以發現: 當搶佔鎖的執行緒一多，就會造成 Cache 被反覆的更新。這樣不止會浪費通道頻寬，更會增加存取速度的延遲。
也因為這樣，電腦科學家又設計了其他 Spinlock 試圖解決這些問題。
現在考慮 [ticket spinlock](https://en.wikipedia.org/wiki/Ticket_lock) 在現代處理器中可能引起的性能問題。假設有一個 4 核 (core) 的處理器，每個處理器核之上的執行緒都想存取 spinlock。在這種情況下，情況如下:
1. CPU~0~ 自主記憶體存取 spinlock、更新其 cache 並持有 spinlock
2. CPU~0~ 更新主記憶體中的 `next` 值。
3. CPU~1~ 自主記憶體中存取 spinlock 並更新其 cache
4. CPU~1~ 標記對應到 spinlock 的 cache 為失效 (invalidate) 並更新 `next` 的值，隨即發現 `next != owner`，於是等待
5. CPU~2~ 自主記憶體存取 spinlock，更新其 cache
6. CPU~2~ 標記對應到 spinlock 的 cache 為失效 (invalidate) 並更新 `next` 的值，隨即發現 `next != owner`，於是等待
7. CPU~3~ 自主記憶體中存取 spinlock 並更新其 cache
8. CPU~3~ 標記對應到 spinlock 的 cache 為失效 (invalidate) 並更新 `next` 的值，隨即發現 `next != owner`，於是等待
9. CPU~0~ 釋出 spinlock，更新對應的 cache 及 owner 的值，這使得其他 CPU cache 中的 spinlock 失效
10. CPU~1~ 注意到 cache 中的 `lock->owne`r 失效，更新 cache 並持有 spinlock（即 `next == lock->owner`）
由上可見，在多核處理器中，一旦多個執行緒競爭同一個 spinlock 時，將導致 cache 被反覆更新。這不僅會浪費記憶體存取的頻寬，還會造成存取速度的延遲，詳見〈[從 CPU cache coherence 談 Linux spinlock 可擴展能力議題](https://hackmd.io/@sysprog/linux-spinlock-scalability)〉。
為了避免 spinlock 操作過程中，因 cache 反覆更新致使嚴重性能衝擊，[MCS lock](https://lwn.net/Articles/590243/) 提出以解決這樣的問題。，其設計理念是讓每個處理器核各自持有一個 lock，每個獨立的處理器核只需要觀察並維護自身的 lock 即可。示意的結構體如下:
```c
struct mcs_spinlock {
struct mcs_spinlock *next;
int locked; /* 1 if lock acquired */
};
```
不僅每個處理器核持有一份 spinlock，MCS spinlock 尚有一個 main lock，作為該結構體的首位。當 main lock 被初始化時，其狀態如下圖:
當某個處理器核嘗試持有 spinlock 時，它會建立一個屬於自己的 MCS spinlock，然後與 main lock）進行 atomic 操作。若 main lock 的 `next` 為 `NULL`，就意味著目前沒有其他執行緒在等待，我們可將 main lock 指向該處理器核持有的 MCS spinlock，從而讓該處理器核持有 spinlock。對應的交換程式碼如下:
```c
swap(main_lock, cpu_lock) {
ret = main_lock;
&main_lock->next = cpu_lock;
&main_lock->locked = &cpu_lock->locked;
return ret;
}
```
藉由上述 atomic 操作，MCS spinlock 的狀態更新如下：
- [ ] 當 spinlock 已被他人持有時
假設 CPU~1~ 已持有 spinlock，現 CPU~2~ 嘗試存取 spinlock。藉由 atomic 操作，main lock 會指向 CPU~2~ 持有的 spinlock:
從 main lock 的狀態可見目前 spinlock 已被他人持有 (即 `main_lock->next != NULL`)，於是 CPU~2~ 只能等待，這時會將 CPU~1~ 的 MCS spinlock 指向 CPU~2~ 所持有的 MCS spinlock:
- [ ] 當 spinlock 被釋放
當 CPU~1~ 完成任務，會對 main lock 比較和交換，若 main lock 指向自身，代表沒有執行緒排隊等候，於是只要更新 main lock 的 `locked` 值，並讓 main lock 指向 `NULL`，最後將 CPU~1~ 持有的 MCS spinlock 釋放即可:
反之，若 main lock 指向的不是自身，那就變更 CPU~2~ 的 `locked` 值，再釋放自身持有的 MCS spinlock:
延伸閱讀:
* [A simple correctness proof of the MCS contention-free lock](https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=ba210c9f21b09ae56bb4b808c2331b2569e06639)
實作程式碼可見 [mcslock](https://github.com/sysprog21/concurrent-programs/tree/master/mcslock)。
:::success
作業描述:
1. 目前 [mcslock](https://github.com/sysprog21/concurrent-programs/tree/master/mcslock) 實作採用 [GCC atomic builtins](https://gcc.gnu.org/onlinedocs/gcc/_005f_005fatomic-Builtins.html)，請用 C11 Atomics 改寫，並確認實作行為與上述描述是否符合。 (歡迎提交 pull request 到 [concurrent-programs](https://github.com/sysprog21/concurrent-programs))
2. 研讀 Linux 核心的 [locking 實作](https://github.com/torvalds/linux/tree/master/kernel/locking)，闡述你對於 Linux 核心原始程式碼 [mcs_spinlock.h](https://github.com/torvalds/linux/blob/master/kernel/locking/mcs_spinlock.h) 的認知，對照閱讀核心文件 [locking](https://docs.kernel.org/locking/index.html)。
3. 針對 MCS lock 所要改進 ticket lock 在多核處理器的效能議題，請設計實驗來說明其效益。
:::
---
### 挑戰 `3`
[rwlock](https://en.wikipedia.org/wiki/Readers%E2%80%93writer_lock) 寓意為 reader-writer spin lock，不同於尋常的 spinlock，它區分「讀取」(read) 和「寫入」(write) 的操作：若目前沒有寫入者，那麼多個讀取者可同時持有該 rwlock，反之，若目前沒有任何讀取者，那寫入者可持有該 rwlock。
rwlock 限制讀取者與寫入者之間，及寫入者與寫入者之間的互斥性，但並未對讀取者與讀取者之間的互斥性做出限制。
舉例來說，當多個 CPU 需要對某個鏈結串列進行大部分是節點走訪和查詢的操作，而不需要新增、刪除或移動元素時，就適合使用 rwlock。
對於讀取者，使用 `read_lock()` 和 `read_unlock()` 來限制讀取臨界區段。
```c
read_lock(); /* --> queued_read_lock() */
/* 臨界區段 */
read_unlock(); /* --> queued_read_unlock() */
```
當一個讀取者進入臨界區段時，需要將讀取臨界區的引用計數 (reference count) 加 `1`，離開時則減 `1`。只有當此引用計數為 `0` 時，寫入者才能執行其臨界區程式碼。
```c
#define _QR_BIAS (1U << 9)
void queued_read_lock_slowpath(struct qrwlock *lock)
{
atomic_add(_QR_BIAS, &lock->cnts);
/* ... */
}
```
對於寫入者，使用 `write_lock()` 和 `write_unlock()` 來限制寫入臨界區段。
```c
write_lock(); // --> queued_write_lock()
/* 臨界區段 */
write_unlock(); // --> queued_write_unlock()
```
不同讀取者的臨界區可以平行進行，但一個寫入者的臨界區段不得與其他寫入者/讀取者的臨界區並行運作。
看似 rwlock 較原本的 spinlock 更細緻地控制讀取和寫入的情境，這似乎讓應用場景更高效，對嗎？然而，rwlock 存在一個問題：若有多個讀取者正在使用某個 rwlock，寫入者需要等待所有讀取者釋放該 rwlock，方可持有 rwlock，這可能導致寫入者的執行被延遲，這種情況被稱為「飢餓」(starvation)。而且，在寫入者等待的過程中，讀取者仍可持續加入並執行，這對於寫入者來說顯然是不公平的。即使寫入者的優先順序更高，他們也不能在優先順序更低的讀取者之前執行。換言之，在 rwlock 中，讀取者還是寫入者這樣的身份決定一切。
由於上述的限制，其他 spinlock 實作出現在 Linux 核心，也有開發者改用 RCU。
seqlock 全名是「序列鎖」(sequential lock)，相較於 rwlock，seqlock 進一步解除讀取者與寫入者之間的互斥性，僅保留了寫入者與寫入者之間的互斥性：只要沒有其他寫入者持有此 seqlock (即使目前有讀取者持有該 seqlock)，試圖獲取該 seqlock 的第一個寫入者就能成功持有。
倘若當讀取者在讀取共享變數的同時，寫入者對變數進行修改，是否會導致讀取的資料不一致呢？
首先，我們來觀察 Linux 核心 seqlock 結構體定義（程式碼位於 [include/linux/seqlock.h](https://github.com/torvalds/linux/blob/master/include/linux/seqlock.h)):
```c
typedef struct {
struct seqcount seqcount;
spinlock_t lock;
} seqlock_t;
```
可見 seqlock 在尋常 spinlock 的基礎上新增名為 seqcount 的成員，而 seqlock 正是利用這個 seqcount 的序列號 (sequence number) 來確保資料的一致性。
- [ ] 開始寫入
每當寫入者成功持有 seqlock 後，序列號的值會增加 1：
```c
static inline void write_seqlock(seqlock_t *sl)
{
spin_lock(&sl->lock);
sl->seqcount.sequence++;
}
```
- [ ] 結束寫入
當寫入者在釋放 seqlock 前，序列號的值再次增加 1：
```c
static inline void write_sequnlock(seqlock_t *sl)
{
sl->seqcount.sequence++;
spin_unlock(&sl->lock);
}
```
初始情況下，序列號的值是一個偶數 (even)，因此當寫入者持有 seqlock 時，序列號的值會是奇數 (odd)，在寫入操作完成並釋放鎖後，序列號的值又會變回偶數。這樣的設計確保序列號的值的奇偶性，可用來標記是否存在寫入操作，進而幫助確保讀取者在讀取期間不會看到不一致的資料。
- [ ] 開始讀取
當讀取者在讀取共享變數之前，首先需要讀取序列號的值。若該序列號為奇數，表示目前有寫入者正在修改此變數，因此讀取者需要等待，直到序列號變為偶數，方可開始進行變數讀取。
```c
static inline unsigned __read_seqcount_begin(const seqcount_t *s)
{
unsigned ret;
repeat:
ret = READ_ONCE(s->sequence);
if (unlikely(ret & 1)) {
cpu_relax();
goto repeat;
}
return ret;
}
```
- [ ] 結束讀取
在讀取完成變數後，讀取者需要再次讀取序列號的值，並將其與之前讀取前的序列號進行比較，以判斷是否相等。若相等，則表明在此期間內未有寫入者的操作。
```c
static inline int __read_seqcount_retry(const seqcount_t *s, unsigned start)
{
return unlikely(s->sequence != start);
}
```
- [ ] 適用場景
在 seqlock 中，讀取者可隨時讀取 (相當於在讀取一側未加鎖)。在此過程中，寫入者的操作不會受到影響，但讀取者可能需要進行多次讀取。寫入者只會被其他寫入者影響，不再受到讀取者的影響。
顯然，此設計傾向於寫入者。seqlock 適用於讀取者較多而寫入者較少的情況，在 Linux 核心中，它的重要應用之一是表示時間的 jiffies，後者記錄自系統啟動後的時鐘節拍數。
```c
do {
seq = read_seqbegin(&jiffies_lock);
ret = jiffies_64;
} while (read_seqretry(&jiffies_lock, seq));
```
實作程式碼可見 [seqlock](https://github.com/sysprog21/concurrent-programs/tree/master/seqlock)。
延伸閱讀:
* [Eliminating rwlocks and IRQF_DISABLED](https://lwn.net/Articles/364583/)
* [Sequence counters and sequential locks](https://docs.kernel.org/locking/seqlock.html)
* [Rust: SeqLock](https://docs.rs/seqlock/latest/seqlock)
:::success
作業描述:
1. 目前 [seqlock](https://github.com/sysprog21/concurrent-programs/tree/master/seqlock) 實作採用 [GCC atomic builtins](https://gcc.gnu.org/onlinedocs/gcc/_005f_005fatomic-Builtins.html)，請用 C11 Atomics 改寫，並確認實作行為與上述描述是否符合。 (歡迎提交 pull request 到 [concurrent-programs](https://github.com/sysprog21/concurrent-programs))
2. 研讀 Linux 核心的 [seqlock.h](https://github.com/torvalds/linux/blob/master/include/linux/seqlock.h) 實作，闡述你對於 Linux 核心原始程式碼的認知，對照閱讀核心文件 [locking](https://docs.kernel.org/locking/index.html)。
3. 參照[第 2 次測驗題](https://hackmd.io/@sysprog/linux2023-summer-quiz2)的測驗 `2` 提及的 [mpmc](https://github.com/sysprog21/concurrent-programs/tree/master/mpmc) 及 [spmc](https://github.com/sysprog21/concurrent-programs/tree/master/spmc) 程式碼，改寫為大量讀取者－單一寫入者 (multiple-reader/single-write) 的場景，並運用上述 seqlock 程式碼，談及其具體效益。 (歡迎提交 pull request 到 [concurrent-programs](https://github.com/sysprog21/concurrent-programs))
:::
---
### 挑戰 `4`
考慮 cmap 是個仿效 C++ [std::unordered_map](https://en.cppreference.com/w/cpp/container/unordered_map) 的並行實作，比照 [Linux 核心的 RCU 機制](https://hackmd.io/@sysprog/linux-rcu)，針對大量讀取者－單一寫入者 (multiple-reader/single-write) 的場景，以 C11 Atomics 開發。測試程式 `test-cmap` 預設建立 3 個讀取端執行緒及單一寫入端執行緒，在 5 秒內進行並行讀寫 (可由命令列參數變更數量及時間)，參考執行輸出:
```
$ ./test-cmap
#checks: 4, #inserts: 0, #removes: 0, cmap elements: 49, utilization: 0.00
#checks: 13698, #inserts: 2281, #removes: 1265, cmap elements: 1065, utilization: 0.59
#checks: 27386, #inserts: 4562, #removes: 2769, cmap elements: 1842, utilization: 1.37
#checks: 41034, #inserts: 6842, #removes: 4242, cmap elements: 2649, utilization: 0.85
#checks: 54706, #inserts: 9124, #removes: 5753, cmap elements: 3420, utilization: 1.20
#checks: 68213, #inserts: 11385, #removes: 7383, cmap elements: 4051, utilization: 1.49
#checks: 81784, #inserts: 13666, #removes: 8749, cmap elements: 4966, utilization: 0.76
#checks: 95345, #inserts: 15945, #removes: 10190, cmap elements: 5804, utilization: 0.97
#checks: 109042, #inserts: 18223, #removes: 11749, cmap elements: 6523, utilization: 1.16
#checks: 122738, #inserts: 20503, #removes: 13376, cmap elements: 7176, utilization: 1.33
#checks: 136430, #inserts: 22785, #removes: 15040, cmap elements: 7794, utilization: 1.48
#checks: 150123, #inserts: 25065, #removes: 16651, cmap elements: 8463, utilization: 0.60
#checks: 163809, #inserts: 27344, #removes: 17985, cmap elements: 9408, utilization: 0.71
#checks: 177196, #inserts: 29568, #removes: 19341, cmap elements: 10276, utilization: 0.82
#checks: 190831, #inserts: 31830, #removes: 20846, cmap elements: 11033, utilization: 0.92
#checks: 204352, #inserts: 34064, #removes: 22341, cmap elements: 11772, utilization: 1.01
#checks: 217901, #inserts: 36307, #removes: 23824, cmap elements: 12532, utilization: 1.10
#checks: 231488, #inserts: 38573, #removes: 25409, cmap elements: 13213, utilization: 1.19
#checks: 245149, #inserts: 40843, #removes: 26979, cmap elements: 13913, utilization: 1.27
#checks: 258702, #inserts: 43094, #removes: 28560, cmap elements: 14583, utilization: 1.35
```
程式碼可見 [cmap](https://github.com/sysprog21/concurrent-programs/tree/master/cmap)。
:::success
作業描述:
1. 說明上述程式碼運作原理，目前 [cmap](https://github.com/sysprog21/concurrent-programs/tree/master/cmap) 無法通過 ThreadSanitizer，請指出其問題並修正。 (歡迎提交 pull request 到 [concurrent-programs](https://github.com/sysprog21/concurrent-programs))
2. 上述程式碼的輸出有一欄是 utilization，解釋其計算基準，並探討如何進一步提升 throughput/scalability，請善用 futex 和第二次作業的成果。
3. 嘗試執行 [kernel-module-rcu-test](https://github.com/sbcd90/kernel-module-rcu-test) 並將上述程式碼移植到 Linux 核心 (使用 Linux 核心的 RCU, spinlock, mutex, condition variable)，過程中你應該會重新體會到 Linux 核心的並行機制。
:::
---
Sign in with Wallet
Connect another wallet