HackMD
Linux 核心設計: Synchronization
- Linux 核心設計: 淺談同步機制
- Linux 核心設計: 多核處理器和 spinlock
- 從 CPU cache coherence 談 Linux spinlock 可擴展能力議題
- 搭配 CSAPP: Chapter 12
一起服用風味更佳
Mutex 與 Semaphore
Mutex 與 semaphore 是經常被混用的觀念(尤其是 binary semaphore = mutex 這種理解)，做為系統的開發者(雖然我還不是)，勢必需要釐清其中的差異。
對於 mutex 來說，解鎖只能由上鎖的 thread 來完成，經常使用的情境是對於資源的保護 / 互斥。就像是對於一個房間，只存在一把鑰匙，拿到的人就可以進入房間，而其他的人必須排隊等待，直到那個人出來。
semaphore 可以由原本的 thread 或是另外一個 thread 解開，因此可以讓數個 producer 與數個 consumer 在計數器的基礎上進行合作。經常的使用情境是在兩個 thread 間的同步上，當 thread 進行至某個點時，去通知 thread B 可以繼續往下執行。
另一個 mutex 與 binary semaphore 的差異在於，mutex 的使用可能產生副作用: priority inversion。假設有優先權從高至低的三個 thread T1、T2、T3，其中 T1 和 T3 需要一個由 mutex 保護的資源:
- 最開始沒有其他 thread 在運行，因此 T3 先執行並拿到 mutex
- T2 一段時間後產生，因為 T2 priority 較高，因此 interrupt 時排程器讓 T2 先執行
- T1 一段時間後產生，因為 T1 priority 最高，理論上該由 T1 先執行，但是因為資源被 T3 佔用了，因此 CPU 只能先讓給 T2 執行，這就是 priority inversion
為此， mutex 實作中需要採用一些機制來防止 priority inversion。但是，因為 semaphore 是為了不同 thread 間同步而存在，實作上就不必為此煩惱。
換句話說，你可以透過 binary semaphore 來做資源的保護，但是因為實作面上 binary semaphore 不是為資源保護設計的，所以 binary semaphore 無法保證 priority inversion 不會發生。
Reference:
Linux kernel synchronization
Reference to Linux kernel synchronization
首先要思考的問題是，在單核心的作業系統上，我們有需要做同步嗎？
答案是 Yes! 當然，如果只是要實作一個簡單的作業系統，我們可以不需要考慮同步的機制，只要讓所有要求 kernel 服務的機制都不能被打斷就可以了，但是這包含可能需要等待即長時間的 I/O，想像一下當作業系統等待輸入時，播放音樂的 process 就被沒辦法被 concurrent 執行，聽起來很笨吧？
為此，即使在單核的環境下，為了使得等待 I/O 的任務可以讓其他的任務先行執行，我們就需要考慮同步的問題。一種相對簡單的作法，如早期的 linux 的 big kernel lock，想像整個 kernel 就是一個資源，一次只能由一個 thread 持有，其他需要 kernel 服務的人就需要等待，而那些不需要 thread 的人則可以繼續參與排程。不過也不難想像，如果我們能把保護的範圍縮小(fine-grained)，讓不同的鎖保護不同的 kernel 中特定支援，kernel 就有機會服務更多 process。
Scalability
假設我們擁用的 CPU 從 1 個擴增到 2 個，則可以得到兩倍的表現嗎？
如果是，這就是 perfect scalability。不過在真實的世界中，要達到 perfect scalability 是相當困難的，如果處理的不恰當，使用更多的 CPU 反而還可能比只使用一個來得更慢。而原因就是因為 synchronization，CPU 再多，但是資源同時允許存取的數量卻是有限的，為了確保執行的正確性而使用的 lock 的機制，同時也帶來了執行效率上的成本。
我們可以把 lock 分成 coarse-grained 和 fine-grained 兩類。
- coarse-grained lock: 一個 lock 鎖起一段執行中的所有資源，一旦有其中一個 thread 進入該段落則上鎖(例如 big kernel lock 就是一種極度的 coarse-grained)。優點是比較不容易出錯(要做到資源互斥最笨的方法就是讓只有一個 thread 可以去存取它)，而缺點也顯而易見，為了保護多個資源而鎖住很長的時間，很可能導致 lock 的成本變大。
- fine-grained lock: 對於每個獨立的資源的擁有自己的 lock，這使得 lock 被持有時間的時間可以變短，但也導致資源管理的難度變高。
Atomic instructions
即使是 x++ 這樣看似簡單的指令，也有多個 CPU cycle 要去執行(讀出 x 到 register -> register 加一 -> register 寫回 x)，如果多個對 x 的 load 和 store 交錯執行，很可能會導致結果非預期。因此 CPU 提供了 atomic operation 的機制，以上面的例子為例，保證在讀出 x 到寫回 x 之間不會有其他的指令交錯進來，藉此保證執行的正確性。
藉由 atomic instruction 的特性，我們可以實作出 lock。因為 lock 的本質就是一個 counter 而已。舉例來說，一個初始為 1 的 lock counter，如果需要該 lock，則試著透過 atomic 減法把 counter 減一：
- 如果結果為 0，得到 lock 然後前進
- 如果結果 < 0，維持 counter 為 0 然後等待
- 因為 atomic 減法，所以同時只有一個 CPU 可以把 counter 減為 0 然後前進
- 釋放時，把 counter 設回 1
lock strategies
lock 的策略主要可以分為兩種：
- spinning: 需要資源的 thread 在 busy loop 中不斷去詢問 counter 的值(因此 thread 還是會使用到 CPU)。這個策略對於馬上就會被釋放的 lock 來說會比較適合(等待的 thread 如果進入 wait queue 又馬上被喚醒，產生 context switch 的成本)
- linux 中的 spinlock, seqlock, completions
- blocking: 把需要資源的 thread 擺進 kernel 中的 wait queue 然後就睡覺，把 CPU 讓給其他需要的人。直到擁有資源的人釋放，再回去 wait queue 中把資源交給在等待的人。如果 lock 是需要一段時間才會被釋放的，則這種方法會比較恰當(CPU 不至於長時間空轉)。
- linux 中的 mutex, semaphore
spinlock
在 linux 中，spinlock 的設計邏輯大致如下程式。
如果只是想要達到 spinlock 預期的功能，事實上，只要有最外層的迴圈就可以了，那麼為甚麼這裡會是 2 層迴圈的設計呢？
問題就在讓人又愛又恨的 cache。在多 CPU 的系統上，例如 CPU A，去 load / store 某個 cacheable 的記憶體位置時，會把內容也填到 CPU 自己擁有的 cache 上。為了保證所有的 CPU 看到正確的記憶體資料，如果 CPU A 有更動過這個 cache，當其他的 CPU 也要讀寫同一位置時，需根據 cache coherence 把這個 cacheline 搬到另一個 CPU 上，然後再把處理後的結果搬回 CPU A，這就是 cache line bouncing。
在 spinlock 中，許多的 CPU 都在對相同的 「 lock 所在的地址 」 做 test and set:
function TestAndSet(boolean_ref lock) {
boolean initial = lock;
lock = true;
return initial;
}
這牽涉到對 lock 的 write 操作，因此就需要不斷做 cache invalidate，更新其他的 cache，導致 cache line bouncing 發生，其中的成本是不容小覷的。
Reference：
不過，顯然很多時候 lock 的值其實是沒有更動的。為此，linux 上對此做了最佳化，因為在內層的迴圈只需要讀取 cache，因此不需要額外更新 cacheline 的成本。
Reader-writer locks
linux 中一種 RW-spinlock 機制如圖，使用一個 bitstring 來表示 lock 的狀態。當 reader 要讀時，嘗試對這個 bitsting 減一，如果減一之後不小於 0 表示可以讀，否則等待，並且使 lock 的狀態維持在 0。當 writer 要寫時，lock 的狀態必須是 0x01000000，表示沒有人在讀，然後把 lock 設成 0 後即可寫入。
不過這個機制顯然對於 readers 比較有利：如果有大量的 reader 不斷進來，writer 會不被允許執行而導致 starvation。在不同的情境下，我們可能會希望 writer 可以比較優先執行。
Seqlocks
在 linux 中使用 seqlock 來滿足需要以 writer 為優先的情境。
Reference: Linux内核同步机制之（六）：Seqlock
在 seqlock 中，會有一個 writer 可以持有的鎖，以及一個 version number。version number 會在 writer 進入和離開 critical section 時加一。對於 reader 來說，進入 critical section 時去檢查 version number 是否為偶數，如果是，表示沒有 writer，則可以進入，並且在離開 critical section 時檢查 version number 是否和進入時一樣，如果相同則繼續執行，如果不同，表示資料被更動過，就需要回到起點重新讀過。
seqlock 隱性的以 writer 為優先，適用在 read 頻繁，但又不希望 write 容易等待的情境下。
Ordering blocking and spinlock
注意如果要混用 blocking 和 spinlock，則 blocking lock 需要最先被取得並且最後被釋放。
- 如果一個拿著 blocking lock 和 spinlock 的 task A 先把 blocking lock 釋放，下一個等待此 lock 的 task B 可能會被叫醒
- 如果此時 A 拿著的 spinlock 也是 B 需要的資源
- task B 因此陷入 busy waiting 等待 spinlock，強奪了 CPU 的使用，task A 因此不能被排程到，所以也不能把資源釋放給 B
Ticket spinlock
原始的 spinlock 最大的問題在於其不公平性。一旦鎖被釋放出來，能得到的人是最先發現的人，事實上，考慮到 CPU topology 與 cache 的特性，如果釋放的 thread 馬上又需要持有鎖，那麼大概率它又可以最先搶到。
就像是一輛公車，誰先擠進去誰就可以上車一樣。那麼作為一個文明人(?)，為了公平，我們自然會想到讓大家好好排隊。
ticket spinlock 通過一個 owner 以及 next 來表示鎖的狀態。
你可以想像 next 就是領到的號碼牌，owner 是現在正在服務的號碼。那麼用一個 pseudocode 來表達 ticket spinlock 的概念就是:
- 取鎖
ticketLock_acquire(int *next, int *owner)
{
my_ticket = fetch_and_inc(next);
while (*owner != my_ticket) {}
}
- 解鎖
ticketLock_release(int *owner)
{
++(*owner);
}
ticket spinlock 雖然對公平性的問題提出了解決，然而其與舊的 spinlock 都有因 cache coherance 導致的 overhead 問題。為了對每個 CPU cacheline 上的 owner 做更新，影響了 ticket spinlock 對 CPU 增加與效能提升之間的 scalibility。當 spinlock 的數量達到一定規模，cache line 更新的時間過久，可能反而導致使用更多 CPU 有害無益。
延伸閱讀: Ticket spinlocks
MCS spinlock
為了解決舊有 spinlok 的 cache-line bouncing 問題，MCS spinlock 被提出，其大致的資料結構可以表示成:
struct mcs_spinlock {
struct mcs_spinlock *next;
int locked; /* 1 if lock acquired */
};
Acquire lock
如下圖，這是 MCS spinlock 的初始狀態，這個初始的 MCS lock 可以姑且稱為 main lock。
當有 CPU 1 想要取得鎖，CPU 1 會建立一個自己的 MCS spinlock 結構，和 main lock 做 atomic exchange 後，把 next 指向 CPU 1 的 lock 物件，所以狀況就像下圖:
atomic exchange 會回傳 main lock 的 next 指向的位置，如果回傳的是 NULL，那就表示 CPU 獲得 lock。因此目前 CPU 1 獲得 lock。
當 CPU 2 嘗試獲得 lock，同樣會建立自己的 MCS spinlock 結構，然後和 main MCS lock 做 atomic 交換，把 next 改指向 CPU 2 的 lock 物件。由於 main lock 原本的 next 指向 CPU 1 的 MCS lock 物件，回傳的不是 NULL，因此 CPU 2 無法持有這個 lock
由於 CPU 2 排在 CPU 1 的下一個，因此 CPU 1 的 next 指向 CPU 2。
參考如下上鎖的程式碼會更有感覺。
// 自己的排隊節點 node 需要自己在外部初始化，它将被排隊到 lock 指示的等鎖隊列中。
void mcs_spin_lock(struct mcs_spinlock **lock, struct mcs_spinlock *node) {
struct mcs_spinlock *prev;
/* Init node */
node->locked = 0;
node->next = NULL;
// 原子執行 *lock = node 並返回原来的 *lock
prev = xchg(lock, node);
if (likely(prev == NULL)) {
return;
}
// 原子執行 prev->next = node;
// 這相當於一個排入隊的操作。記為(*)
WRITE_ONCE(prev->next, node);
while (0 == &node->locked) ;
// 在自己的 locked 變數上自旋等待！
}
其中 xchg 就是我們提到的 atomic exchange，其概念可以大概簡化為:
xchg(*ptr, x)
{
ret = *ptr;
*ptr = x;
return ret;
}
lock 就是 main lock -> next，因此可以看到 lock 和 node 交換內容後，會回傳原本的 lock，如果為 NULL 則得到鎖可以馬上繼續執行。
當 CPU 2 要求鎖的時候，得到的回傳不是 NULL，因此就會執行到 WRITE_ONCE(prev->next, node)，將自己排在 CPU 1 的後面。
因為等待 lock 的 CPU 是根據自己 local 資料結構中的 locked，因此就不牽涉到 cache coherence 的問題。隨著對 lock 的爭奪增加，重複這個過程，每個 CPU 會將自己排在已經存在的 CPU 後面，並且每個 CPU 都根據自己的 lock 副本 spinning。而 main lock 中的 pointer 則始終指著等待隊列的尾部。
Release lock
當 CPU 1 要釋放，會對 main lock 做 compare and swap，如果 pointer 指向自己的 MCS lock 結構，就將 main lock 的 next 設為 NULL，表示成功，lock 不被任何人等待。如果其他 CPU 改變了 pointer，則 compare and swap 將失敗。在這種情況下，CPU 1 不會更改 main lock，而是去更改 CPU 2 結構中的 locked 值，並將其自己從隊列中移除。
CPU 2 被的 locked 被設成 1 後，表示獲得 lock，就可以往下執行。
void mcs_spin_unlock(struct mcs_spinlock **lock, struct mcs_spinlock *node) {
// 原子獲取 node 的下一個節點。
struct mcs_spinlock *next = READ_ONCE(node->next);
if (likely(!next)) {
// 二次確認真的是NULL，則返回，說明自己是最後一個，什麼都不需要做。
if (likely(cmpxchg_release(lock, node, NULL) == node))
return;
// 否則說明在 if 判斷 next 為 NULL 和 cmpxchg 原子操作之間有 node 插入，随即等待它的 mcs_spin_lock 調用完成，即上面 mcs_spin_lock 中的(*)注釋那句完成以後
while (!(next = READ_ONCE(node->next)))
cpu_relax_lowlatency();
}
// 原子執行 next->locked = 1;
arch_mcs_spin_unlock_contended(&next->locked);
}
cmpxchg(*ptr, old, new)
{
ret = *ptr;
if (*ptr == old)
*ptr = new;
return ret;
}
從程式碼中可以更好的理解。以釋放 CPU 1 為例，會做二次檢查，一是判斷 CPU 1 的下一個是否為 NULL，二是透過 cmpxchg_release，也就是對 main lock 做 compare and swap 二次確認，檢查自己是不是最後一個排隊的 CPU。如果下一個存在，就去更改下一個 MCS lock 的 locked 值為 1，表示轉交 lock。
延伸閱讀:
