# 第十三講：淺談同步機制
> 本筆記僅為個人紀錄，相關教材之 Copyright 為[jserv](http://wiki.csie.ncku.edu.tw/User/jserv)及其他相關作者所有
* 直播：==Linux 核心設計：淺談同步機制 - 2018/11/22==
* 詳細共筆：[Linux 核心設計: 淺談同步機制](https://hackmd.io/@sysprog/linux-sync)
* 主要參考資料：
* [Linux kernel synchronization](http://www.cs.unc.edu/~porter/courses/cse506/s16/slides/sync.pdf)
* [Memory Consistency](http://www.cs.unc.edu/~porter/courses/cse506/s16/slides/consistency.pdf)
---
## 引言
本課將探討 Linux 核心中的同步機制。同步問題不僅是軟體設計的挑戰，更與現代計算機結構、多核心處理器 (multi-core processor) 的物理特性、以及記憶體一致性 (memory consistency) 模型緊密相連。本課將從歷史演進、基本理論，一路剖析至 Linux 核心中具體的實作細節與效能考量。
---
## 充斥歷史痕跡的同步機制
同步機制的發展與作業系統的演進密不可分。早在 1961 年，分時多工作業系統 [Compatible Time-Sharing System](https://en.wikipedia.org/wiki/Compatible_Time-Sharing_System) (CTSS) 就已進行示範，而電腦科學家 Melvin Conway 在 1963 年的論文〈[A Multiprocessor System Design](https://archive.org/details/AMultiprocessorSystemDesignConway1963/page/n7)〉中提出了 `fork` 的思想。幾乎在同一時間，另一位電腦科學巨擘 Edsger Dijkstra 以數學的嚴謹性定義了 **Semaphore (號誌)** 的概念。這些早期的思維奠定了現代作業系統同步機制的基礎。
同步問題的核心在於如何管理對共享資源的存取，確保在多個執行單元並行時的正確性。這引出了 **Critical Section (關鍵區域)**，簡稱 `CS` 的概念。
<center><img src="https://i.imgur.com/El3wtFd.png" alt="image" width="75%" /></center>
<!--
```c
do {
entry section // 控制對 CS 的進入，並取得所需資源的 LOCK
critical section // 存取共享資源的關鍵程式碼
exit section // 釋放 LOCK，通知其他執行單元 CS 已結束
remainder section // 剩餘的非關鍵程式碼
} while (TRUE);
```
-->
一個合格的 CS 解決方案必須滿足以下三個條件：
1. **Mutual Exclusion (互斥)**：在任何一個時間點，只允許一個 process 或 thread 進入指定的 CS 內部。
2. **Progress (前進)**：
* 不想進入 CS 的執行單元，不得阻礙其他想進入的執行單元。
* 當 CS 為空時，必須在有限時間內，從那些希望進入 CS 的執行單元中挑選一個，使其能夠立即進入。
3. **Bounded Waiting (有限等待)**：任何一個請求進入 CS 的執行單元，其等待時間必須是有限的。換言之，若有 $N$ 個執行單元在等待，任何一個單元至多等待 $N-1$ 次的資源釋放即可進入。
在早期缺乏硬體原子指令支援的年代，開發者設計了純軟體的演算法來解決 CS 問題，例如：
* [Dekker's algorithm](https://en.wikipedia.org/wiki/Dekker%27s_algorithm) (1960 年)
* [Lamport's bakery algorithm](https://en.wikipedia.org/wiki/Lamport%27s_bakery_algorithm) (1973 年)
* [Peterson's algorithm](https://en.wikipedia.org/wiki/Peterson%27s_algorithm) (1981 年)
然而，現代處理器架構都已提供簡單而高效的 **Atomic Instructions (原子指令)**，使得上述這些純軟體演算法在實用上已被淘汰。
Dijkstra 提出的 semaphore 概念，主要被應用於兩大類問題：
* **CS 保護**：如同前述，確保共享資源的互斥存取。
* **Signaling (信號通知)**：執行單元之間需要通知彼此「某些條件已經改變」的情境。例如，在經典的生產者-消費者問題中，可以使用兩個 semaphores，一個表示「有資料可用」，另一個表示「有空間可存放」。
隨著硬體原子指令的普及，[Mutex](https://en.wikipedia.org/wiki/Lock_(computer_science)) (互斥鎖)，或稱 lock，成為作業系統實作中的重要機制。一般而言，兩者的使用場景可以簡潔地區分：
* **Mutex**：用於 **保護共享資源**。上鎖和解鎖的操作永遠是同一個執行單元。
* **Semaphore**：用於 **執行單元間的同步與通知**。等待 (wait) 和通知 (signal) 的通常是不同的執行單元。
---
## Mutex 與 Semaphore 的區別
Mutex 與 semaphore 的差異是面試中常見的問題，也是理解同步機制的關鍵。兩者雖然都用於保護 CS，但設計初衷和應用場景不同。
* **Mutex**：
* **核心概念**：「所有權」。
* **作法**：一個執行單元取得了 Mutex，在完成對資源的存取後，**必須由同一個執行單元** 來釋放它。它就像是資源的一把鑰匙，誰鎖上就必須由誰來打開，即所謂 「解鈴還須繫鈴人」。
* **主要用途**：保護 **單一共享資源**，確保互斥存取。
> **額外考量**：由於具有所有權概念，Mutex 的實作通常需要處理 **[Priority Inversion (優先權反轉)](https://barrgroup.com/Embedded-Systems/How-To/RTOS-Priority-Inversion)** 問題。
> * **問題**：在嚴格的即時系統中，一個持有 mutex 的低優先權任務，可能會被一個中優先權的任務搶佔，導致等待該 mutex 的高優先權任務被無限期延遲。
> * **解決**：mutex 的實作通常會包含 **Priority Inheritance (優先權繼承)** 機制，允許等待鎖的高優先權任務，將其優先權暫時「借」給持有鎖的低優先權任務，使其能盡快完成並釋放鎖。
> <center><img src="https://barrgroup.com/images/glossary/PriorityInversion-Figure1.gif" alt="image" width="75%" /></center>
* **Semaphore**：
* **核心概念**：「計數」與「信號」。
* **作法**：執行單元之間透過它來通知彼此「某個事件已發生」或「某個資源可用」。一個執行單元執行 `wait()` (等待/減少計數/ P 操作)，而 **另一個不同的執行單元** 可以執行 `signal()` (發信號/增加計數/ V 操作)。
* **主要用途**：解決 **thread 間的信號問題 (signaling)**，例如經典的「生產者-消費者問題」。它可以是 **Binary Semaphore** (計數器為 0 或 1) 或 **Counting Semaphore** (計數器可大於 1)，後者可用於管理多個相同類型的資源池。
| | Mutex | Semaphore |
|:------------:|:------------------:|:-------------------------------:|
| **核心概念** | 「所有權」 | 「計數」與「信號」 |
| **解鎖者** |自己 | 別的執行單元|
| **適用場景** | 搶佔資源並保證互斥 | thread 間互相通知、協調執行順序 |
> [!Tip]Binary semaphore 和 mutex 的程式可能非常像，取決於作業系統的實作。
在 Linux 核心的發展中，一開始只有 Semaphore。直到 v2.6.16，Mutex 才從 Semaphore 的實作中被獨立出來，並針對其特定場景進行了深度最佳化，引入了 Fast path、Mid path、Slow path 等複雜機制，使其 **在無競爭情況下效能極高**，但也付出了更大的記憶體開銷 (在 x86-64 上約 40 bytes，semaphore 僅需 24 bytes) 的代價，也對 CPU cache 的使用效率和快取一致性 (cache coherence) 帶來了更大的挑戰。
1. **Fast path**：嘗試使用硬體的原子操作，直接對計數器進行遞減來取得鎖。這是最快、最理想的情況。
2. **Mid path**：若 fast path 失敗，表示鎖已被持有。此時，系統會判斷持鎖者是否仍在執行且沒有更高優先權的任務，若是，則推斷鎖會很快被釋放。這時，等待者會進入一個特化的 **MCS spinlock** 進行短暫的忙碌等待 (busy-wait)。
3. **Slow path**：若 mid path 的等待超時或被更高優先權的任務打斷，表示鎖無法在短時間內取得。此時，等待的任務會將自己加入 wait-queue (等待佇列)並進入休眠狀態 (sleep)，讓出 CPU，等待鎖被釋放時再由系統喚醒。
> 延伸閱讀：
> * [Mutexes and Semaphores Demystified](https://barrgroup.com/Embedded-Systems/How-To/RTOS-Mutex-Semaphore)
> * [淺談 Semaphore 與 Mutex](https://www.youtube.com/watch?v=JEXwO_EoyZo) - YouTube 解說
> * [Mutex, Semaphore, the difference, and Linux kernel](https://blog.louie.lu/2016/10/22/mutex-semaphore-the-difference-and-linux-kernel/) - (面試回答技巧)
---
## 鎖的基礎觀念
在深入探討各種鎖之前，先建立一些基礎觀念。
### Big Kernel Lock (巨大核心鎖, BLK)：
[BKL](https://kernelnewbies.org/BigKernelLock) 是一個歷史性的鎖，它透過 `lock_kernel()` 和 `unlock_kernel()` 將整個 Linux 核心鎖定。這是早期為了讓不具備 `Symmetric Multi-Processing (SMP，對稱多處理)` 設計的程式碼能在多處理器環境下安全執行而引入的粗粒度鎖。
* **特點**：
* 整個核心只有一個 BKL。
* 持有 BKL 的行程 **允許** 被排程器排程出去。當排程發生時，核心會暫時釋放 BKL，讓其他行程有機會執行；當該行程被排程回來時，再重新獲取 BKL。
* **與 spinlock 的區別**：spinlock 用於保護特定的、小範圍的共享資源，且在持有期間 **不允許** 發生排程。
* **現況**：BKL 嚴重影響了系統的 Scalability (可擴展性)，已在 Linux v2.6.39 中被[徹底移除](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=4ba8216cd90560bc402f52076f64d8546e8aefcb)。
### Coarse vs. Fine-grained Locking (粗粒度與細粒度鎖)
鎖保護範圍的大小和複雜度的權衡。
* **Coarse-grained locking**：使用一個鎖保護一大片相關或不相關的資源。
* **優點**：設計簡單，開發者責任較小。
* **缺點**：並行度低，效能差，容易成為系統瓶頸。BKL 是其典型例子。
* **Fine-grained locking**：使用多個「小」鎖，每個鎖只保護一個特定的、小範圍的資料結構。
* **優點**：允許多個不相關的活動並行，系統效能和並行度高。
* **缺點**：設計複雜度急遽增加，開發者需要小心處理多個鎖之間的交互關係，容易引發 **Deadlock (死鎖)**。
:::info
現代高效能作業系統的發展趨勢，就是從 Coarse-grained locking 不斷向 Fine-grained locking 演進的過程。
:::
### Atomic Instructions (原子指令)：
硬體提供的一系列不可中斷的指令，是所有同步機制的基石。常見的原子指令包括：
* **Atomic increment/decrement (`x++` or `x--`)**：主要用於實現引用計數 (reference counting)。其本質是 `load -> modify -> store` 三個步驟的原子化組合。
* **Test and Set Lock (TSL)**：
* 語意：`lock` == TRUE 時，代表有人在 CS 內。
* 偽碼：
```c=
bool test_and_set(bool *lock) { // Atomic
bool tmp = *lock;
*lock = TRUE;
return tmp; // 返回 *lock 原始的值
}
```
* Atomic instruction + locks：
```c=
while (1) {
while (test_and_set(&lock)); // 等別人把 lock 變成 FALSE
... /* critical section */
lock = FALSE; // 將 lock 還原成 FALSE，讓別人可使用
... /* remainder section */
}
```
* **Compare and Swap (CAS)**：是實現許多 [lock-free data structures](https://preshing.com/20120612/an-introduction-to-lock-free-programming/) 的基石。
* 語意：`if (x == y) x = z;`，等別人傳 `y` 值給你。
* 偽碼：
```c=
int compareAndSwap(int *x, int y, int z) { // Atomic
int tmp = *x;
if (tmp == y) *x = z;
return tmp; // 無論如何，都返回 *x 原始的值
}
```
* Atomic instruction + locks：
```c=
while (1) {
key_i = TRUE;
while (!compare_and_swap(&lock, 0, 1)); // 等別人傳 FALSE key 給自己
... /* critical section */
lock = FALSE; // 釋出 FALSE key
... /* remainder section */
}
```
### Lock-Free Programming：
`Lock-Free` 是一個更進階的概念，它描述了一種特性：**執行該程式的所有 thread 中，至少有一個能夠持續向前推進，而不會被無限期阻塞**，排除了 dead lock、live lock 或因排程導致的 starvation 問題。這並不等同於「沒有 Mutex」。
一個未使用任何鎖的程式也可能不符合 Lock-Free 屬性，例如下面的程式碼，在特定排程下，兩個 thread 可能交替設定 `x` 的值，導致雙方都陷入無限迴圈，即 `Livelock (活鎖)`。
```c=
// 初始 x = 0
while (x == 0) {
x = 1 - x;
}
```
Lock-Free 的目標是避免因死鎖、活鎖或優先權反轉等問題導致的系統停滯，通常依賴於 **Compare and Swap (CAS)** 等原子指令來實現。
### 等待策略 (Waiting Strategies)
當一個執行單元無法獲得鎖時，有兩種主要的等待策略：
1. **Spinning (自旋)**：在一個迴圈中不斷地檢查鎖的狀態，直到鎖被釋放。這種方式會持續佔用 CPU，是一種 **Busy-Waiting**。
* **適用場景**：鎖的持有時間非常短，短到進行上下文切換的成本都比等待的時間長。
* **代表**：`spinlock`。
2. **Blocking (阻塞)**：將當前執行單元放入一個等待佇列 (wait queue)，然後讓出 CPU，觸發排程器去執行其他任務，是一種 **Non-Busy-Waiting**。
* **適用場景**：鎖的持有時間可能很長，例如等待 I/O 操作完成。
* **代表**：`mutex`、`semaphore`。
> 參照：[Linux kernel synchronization](http://www.cs.unc.edu/~porter/courses/cse506/s16/slides/sync.pdf)
---
## spinlock 核心實作
**spinlock (自旋鎖)** 是 Linux 核心中使用最頻繁的鎖定機制之一。當一個 thread 嘗試獲取一個已被持有的 spinlock 時，它不會進入休眠，而是在原地進行「自旋」 (執行一個 busy-waiting 的迴圈)，直到鎖被釋放。因為它不會引起排程，所以 spinlock 特別適用於 **interrupt context (中斷上下文)** 中，因為在中斷處理程序中是不能休眠的。
<center><img src="https://i.imgur.com/EwV16F3.png" alt="image" width="70%" /></center>
傳統的 spinlock 存在不公平性問題，即釋放鎖時，所有等待的 thread 會立刻開始競爭，可能導致某個 thread 被「餓死」。為了確保公平性，現代 Linux 核心採用了 **Ticket lock (票號鎖)** 機制。
其機制類似於銀行的叫號系統：
* 兩個 counter：
* **`owner`**：當前正在服務的號碼（持有鎖的票號）。
* **`next`**：下一個將要發放的號碼（下一個申請者的票號）。
* 當一個 thread 想獲取鎖時：
1. 原子性地取得 `next` 的當前值作為自己的票號，並將 `next` 加 1。
2. 開始自旋，不斷地檢查 `owner` 的值是否等於自己的票號。
3. 一旦相等，便獲得鎖，可以進入 CS。
* 當 thread 釋放鎖時：
1. 簡單地將 `owner` 的值加 1，相當於叫下一個號。
這樣就保證了先到先服務 (FIFO) 的公平性。
### ARM 架構的 spinlock 的結構體與簡化實作：
* **結構定義**
`arch/arm/include/asm/spinlock_types.h`
```c=11
typedef struct {
union {
u32 slock;
struct __raw_tickets {
u16 owner;
u16 next;
} tickets;
};
} arch_spinlock_t;
```
* **上鎖操作**
`arch/arm/include/asm/spinlock.h`
```c
static inline void arch_spin_lock(arch_spinlock_t *lock) {
arch_spinlock_t local_lock;
local_lock.slock = lock->slock; // 1. 取得當前票號資訊
lock->tickets.next++; // 2. 票號機更新下一個號碼
/**
* 1, 2 實際用組合語言實作，各自為原子性操作
* prefetchw(&lock->slock);
* __asm__ __volatile__(...);
*/
while (local_lock.tickets.next != local_lock.tickets.owner) { // 3. 檢查是否輪到自己
wfe(); // 4. 若未輪到，執行 WFE 指令使 CPU 進入低功耗等待
local_lock.tickets.owner = lock->tickets.owner; // 5. 醒來後，再次更新櫃檯號碼
}
}
```
這裡的 [`wfe` (Wait For Event)](https://developer.arm.com/documentation#q=wfe&numberOfResults=48) 是 ARM 架構的指令，它讓 CPU 進入低功耗狀態，直到有事件發生 (例如其他 CPU 執行了 `SEV` 指令) 才被喚醒，這比單純的空轉迴圈更節能。
* **解鎖操作**
`arch/arm/include/asm/spinlock.h`
```c
static inline void arch_spin_unlock(arch_spinlock_t *lock) {
smp_mb();
lock->tickets.owner++; // 1. 將 owner 加一，叫下一個號
dsb_sev(); // 2. 執行 SEV 指令，喚醒所有在 WFE 中等待的 CPU
}
```
> 延伸閱讀：[Linux内核同步机制之（一）：原子操作](http://www.wowotech.net/kernel_synchronization/atomic.html)
### Linux spinlock 的實作與 Cache 效應
一個簡化的 spinlock 實作看起來可能像這樣：
```c=
while (0 != atomic_dec(&lock->counter)) {
// 忙碌等待
}
```
但為了效能，Linux 的實作遠比這複雜，特別是考慮到 **[cache line bouncing (快取行彈跳)](https://www.quora.com/What-is-cache-line-bouncing-How-may-a-spinlock-trigger-this-frequently)** 問題。在多處理器系統中，每個 CPU 都有自己的 cache。當多個 CPU 都在同一個 lock 變數上自旋 (spin) 時，它們會不斷地嘗試讀寫該變數所在的 cache line。這會導致該 cache line 在不同 CPU 的 cache 之間頻繁地傳輸和失效 (invalidate)，耗費大量的記憶體匯流排頻寬，嚴重拖慢整個系統。==**"Cache Line “ping-pongs” back and forth"**==
<center><img src="https://hackmd.io/_uploads/BybBDvyweg.png" alt="image" width="80%" /></center>
為了解決這個問題，Linux 引入了 **Test-Test-and-Set Lock** 的概念，並利用處理器的 **`PAUSE` 指令**：==**"Line shared in read mode until unlocked"**==
```c=
while (0 != atomic_dec(&lock->counter)) { // 外層迴圈：嘗試寫入 (Test-and-Set)
do {
// CPU 執行 "PAUSE 指令"，進入低功耗模式，
// 直到有 cache 一致性事件 (如其他 CPU 釋放鎖) 發生才醒來。
// 避免了在 memory 總線上產生大量流量。
} while (lock->counter <= 0); // 內層迴圈：僅讀取 (Test)
}
```
* **內部迴圈 (Test)**：等待者先在一個內部迴圈中 **唯讀** `lock->counter` 的值。因為是唯讀，多個 CPU 可以共享同一個 Cache Line 的副本而不會引發寫入衝突和 Cache Line Bouncing。
* **外部迴圈 (Test-and-Set)**：只有當內部迴圈觀察到鎖可能被釋放時 (`lock->counter > 0`)，才會跳出，嘗試執行外部迴圈中昂貴的原子寫入操作來真正獲取鎖。
<center><img src="https://hackmd.io/_uploads/BJw8vDyDee.png" alt="image" width="80%" /></center>
這種雙迴圈結構，讓等待的 CPU 在內層迴圈中只讀取 lock 變數，共享同一個 cache line 的唯讀副本，只有在偵測到鎖可能被釋放時，才跳到外層迴圈嘗試進行原子寫入操作，從而大大減少了 cache line bouncing。
> 延伸閱讀：
> * [從 CPU cache coherence 談 Linux spinlock 擴展議題](https://hackmd.io/@sysprog/linux-spinlock-scalability) - jserv
> * [spinlock](https://www.slideshare.net/slideshow/spinlockpdf/254977958) - Adrian Huang
---
## semaphore 核心實作
**semaphore (號誌)** 是一種允許 thread 因無法取得資源而 **進入休眠** 的同步機制，因此它會觸發排程器進行上下文切換 (context switch)。它由荷蘭電腦科學家 Edsger W. Dijkstra 於 1965 年提出，因此有時也稱為 Dijkstra Counters。
<center><img src="https://i.imgur.com/opGlAN9.png" alt="image" width="70%" /></center>
### semaphore 的結構：
一個 semaphore 主要包含兩部分：
* `count`：一個整數計數器，表示可用資源的數量。
* `wait_list`：一個等待佇列 (在 Linux 中是一個 double-linked list)，用於存放因無法獲取 semaphore 而休眠的行程。
`include/linux/semaphore.h`
```c=15
struct semaphore {
raw_spinlock_t lock; // 保護 semaphore 內部資料結構的 spinlock
unsigned int count;
struct list_head wait_list;
};
```
在 Linux 中，還需要一個結構體記錄目前的 process 的資訊 (task_struct)：
`kernel/locking/semaphore.c`
```c=202
struct semaphore_waiter {
struct list_head list;
struct task_struct *task; // 目前的 process 的資訊
bool up; // 指示當前要用 up() 還是中斷喚醒
};
```
### semaphore 的操作：
Semaphore 的核心操作有兩個，以荷蘭語命名：
* **`P` (proberen te verlagen, 嘗試減去)**：通常實現為 `down()` 或 `wait()`。它會嘗試將 `count` - 1。如果 `count` 已經是 0，則 thread 會被加入 `wait_list` 並進入休眠。
* **`V` (verhogen, 增加)**：通常實現為 `up()` 或 `signal()`。它會將 `count` + 1。如果 `wait_list` 中有等待的 thread ，它會喚醒其中一個。
以下是 Linux 核心中簡化的實作：
* **P / Down / wait 操作**
`kernel/locking/semaphore.c`
```c=55
void __sched down(struct semaphore *sem)
{
unsigned long flags;
might_sleep();
raw_spin_lock_irqsave(&sem->lock, flags);
if (likely(sem->count > 0)) // 1. 如果還有資源
sem->count--; // 直接取得並返回
else
__down(sem); // 2. 否則 ...
raw_spin_unlock_irqrestore(&sem->lock, flags);
}
...
static inline int __sched ___down_common(struct semaphore *sem, long state,
long timeout)
{
struct semaphore_waiter waiter;
list_add_tail(&waiter.list, &sem->wait_list); // 將當前行程加入 wait_list
waiter.task = current;
waiter.up = false;
for (;;) {
...
raw_spin_unlock_irq(&sem->lock);
timeout = schedule_timeout(timeout); // 觸發排程器，讓出 CPU
raw_spin_lock_irq(&sem->lock);
...
}
...
}
```
* **V / Up / signal 操作**
`kernel/locking/semaphore.c`
```c=184
void __sched up(struct semaphore *sem)
{
....
raw_spin_lock_irqsave(&sem->lock, flags);
if (likely(list_empty(&sem->wait_list))) // 1. 如果沒有行程在等待
sem->count++; // 直接增加資源計數
else
__up(sem, &wake_q); // 2. 否則 ...
raw_spin_unlock_irqrestore(&sem->lock, flags);
...
}
...
static noinline void __sched __up(struct semaphore *sem,
struct wake_q_head *wake_q)
{
struct semaphore_waiter *waiter = list_first_entry(&sem->wait_list,
struct semaphore_waiter, list);
list_del(&waiter->list); // 從 wait_list 中取出第一個行程
waiter->up = true; // 喚醒它
wake_q_add(wake_q, waiter->task);
}
```
---
## read-write lock (rwlock)
對於 **讀多寫少的場景**，使用 spinlock 或 semaphore (同一時間只允許一個 thread 進入 CS) 會顯得效率低下。**rwlock (讀寫鎖)** 是一種優化，它允許多個「讀者 (reader)」同時進入 CS，但「寫者 (writer)」仍然是互斥的。
### rwlock 的性質：
* 同一時間只能有一個 writer 進入 CS。
* 當沒有 writer 時，可以有多個 reader 同時進入 CS。
* reader 和 writer 不能同時進入 CS。
### rwlock 的結構：
在 Linux 核心中，spinlock 類型的 rwlock 實現得非常巧妙，僅用一個 32 位元的整數來同時表示 **reader 數量** 和 **writer 狀態**：
* **Bit 31**：writer 標記位。為 1 表示有 writer 持有鎖。
* **Bits 30-0**：reader 計數器。記錄當前在 CS 中的 reader 數量。
`arch/arm/include/asm/spinlock_types.h`
```c=28
typedef struct {
u32 lock;
} arch_rwlock_t;
```
```graphviz
digraph rwlock_layout {
rankdir=TB;
node [shape=plaintext, fontname="Arial"];
main_table [label=<<table border="1" cellborder="1" cellspacing="0" cellpadding="10">
<tr>
<td port="bit31" width="40" bgcolor="#DEFFAC"><b>31</b></td>
<td width="40" bgcolor="#FFFFB9"><b>30</b></td>
<td port="bits30_0" width="400" bgcolor="#FFFFB9"><b>...</b></td>
<td width="40" bgcolor="#FFFFB9"><b>0</b></td>
</tr>
</table>
>];
writer_label [label="[31] Writer Lock Flag", shape=plaintext];
reader_label [label="[30:0] Reader Counter", shape=plaintext];
main_table:bit31:s -> writer_label;
main_table:bits30_0:s -> reader_label;
main_table -> {writer_label reader_label} [style=invis];
}
```
### rwlock 的操作：
* **獲取讀鎖 (read_lock)**：
1. 檢查 bit 31 是否為 1 (即是否有 writer)。
2. 如果是，則自旋等待。
3. 如果否，則原子性地將 reader counter + 1。
```c=
static inline void arch_read_lock(arch_rwlock_t *rw) {
while(rw->lock & (1 << 31)) {
wfe(); // 低功耗自旋等待
}
rw->lock++;
}
```
* **釋放讀鎖 (read_unlock)**：
1. 原子性地將 reader counter - 1。
```c=
static inline void arch_read_unlock(arch_rwlock_t *rw) {
rw->lock--;
}
```
* **獲取寫鎖 (write_lock)**：
1. 自旋等待，直到整個 32 位元整數變為 0 (即沒有任何 reader 和 writer)。
2. 原子性地將 bit 31 設為 1。
```c=
static inline void arch_write_lock(arch_rwlock_t *rw) {
while (rw->lock) {
wfe(); // 低功耗自旋等待
}
rw->lock = 1 << 31;
}
```
* **釋放寫鎖 (write_unlock)**：
1. 原子性地將整個 32 位元整數設為 0。
```c=
static inline void arch_write_unlock(arch_rwlock_t *rw) {
rw->lock = 0;
}
```
這種設計極大地提升了讀多寫少場景下的並行度。但在實現上存在一個微妙的問題：如果 reader 源源不斷地到來，writer 可能會餓死。
> 以上皆為等價之 c code，實際上為組合語言實作，參見 [`arch/arm/include/asm/spinlock.h`](https://elixir.bootlin.com/linux/v6.16-rc7/source/arch/arm/include/asm/spinlock.h)。
> 延伸閱讀：[Linux内核同步机制之（五）：Read/Write spin lock](http://www.wowotech.net/kernel_synchronization/rw-spinlock.html)
---
## seqlock
**seqlock (順序鎖)** 是 rwlock 的一種變體，明確地給予 writer 極高的優先權，甚至可能導致 reader 飢餓。它適用於 reader 絕對不能延遲 writer 的場景，例如更新系統時間。
* **核心機制**：維護一個循序計數器 (sequence number)。
```c=
volatile seq;
```
* **寫者 (Writer)**：
1. 進入前，將計數器 + 1 (使其變為奇數)。
2. 執行寫入操作。
3. 完成後，再將計數器 + 1 (使其變回偶數)。
> 外圍通常需要一個 spinlock 把區塊包起來，使 writer 互斥。
```c=2
spinlock(&lck);
seq++;
wmb(); // 寫入屏障 (防止指令重排)
...
wmb(); // 寫入屏障 (防止指令重排)
seq++;
spinunlock(&lck);
```
* **讀者 (Reader)**：
1. 讀取資料前，先記錄下當前的計數器值 (若是奇數，則自旋等待 writer)。
2. 讀取共享資料。
3. 讀取完畢後，再次檢查計數器。如果計數器值與第一步記錄的值不同，或變成了奇數，代表在讀取過程中被 writer 打斷，資料可能不一致，必須 **放棄這次讀取並重試**。
```c=9
do {
do {
lastseq = seq;
} while (lastseq & 1);
rmb(); // 讀取屏障 (防止指令重排)
} while (lastseq != seq); // 計數器改變，重新讀取
```
作為一種 optimistic lock (樂觀鎖，預設讀寫衝突不頻繁)，seqlock 的優點是 reader 完全不會阻塞 writer，writer 可以隨時進入，非常適合 **更新頻繁** 但 **讀取時可以接受重試** 的場景，例如 Linux 核心中對系統時間的讀取。
> 延伸閱讀：
> * [Linux內核同步機制之（六）：Seqlock](http://www.wowotech.net/kernel_synchronization/seqlock.html)
> * [Chapter 5. Concurrency and Race Conditions](https://www.oreilly.com/library/view/linux-device-drivers/0596005903/ch05.html)
---
## 進階議題與未來方向
### Queued/MCS Spinlock
傳統的 Ticket spinlock 雖然確保了公平性，但在高度競爭的 NUMA 環境下，所有等待的 CPU 核心都會在同一個共享的鎖變數上「自旋」。這個行為會引發劇烈的 **cache line bouncing (快取行彈跳)**，即保護鎖的那個 cache line 在不同 CPU 的 cache 之間被頻繁地來回傳輸，導致大量的匯流排流量與延遲，嚴重扼殺了系統的 scalability。
為了解決這個問題，**Queued Spinlocks** 或稱 **MCS (Mellor-Crummey and Scott) Spinlock** 被提出。它的核心思想極具巧思：**避免在共享變數上自旋，而是讓每個等待者在各自私有的本地變數上自旋**。
#### 運作機制：
1. **形成佇列**：所有嘗試獲取鎖的 thread，會被組織成一個 linked-list queue。
2. **本地自旋**：每個在佇列中等待的 thread，只會在它自己的佇列節點中的一個旗標 (flag) 上自旋。這個節點是該 thread 私有的，因此會被快取在本地 CPU 的 cache 中，不會引發 cache line bouncing。
3. **直接交棒**：當一個 thread 釋放鎖時，它會直接檢查其在佇列中的後繼者 (next)。如果後繼者存在，它會直接修改後繼者節點中的旗標，等於是直接「喚醒」或「交棒」給下一個 thread。
這種「傳球」而非「搶球」的模式，徹底消除了因競爭共享鎖變數而產生的全域 Cache Line Bouncing 效能瓶頸，使 spinlock 在超多核心系統上也能保持良好的 scalability。MCS lock 對於擁有多於 4 個 CPU 插槽 (socket) 的大型系統尤其重要，可以將系統從崩潰的邊緣拯救回來。
:::info
Linux 核心中的 qspinlock 就是基於 MCS 鎖思想的實作。
:::
有趣的是，由於其解鎖操作更為簡單 (一個普通的 `store` 指令，而非 Ticket spinlock 需要的原子 `CAS` 或 `XADD` 指令)，在無競爭的情況下，MCS lock 的延遲甚至可能比 Ticket spinlock 更低。
> 延伸閱讀：
> * [Futex Scaling for Multi-core Systems](https://www.slideshare.net/davidlohr/futex-scaling-for-multicore-systems)
> * [Much Ado About Blocking: Wait/Wake in the Linux Kernel](https://www.slideshare.net/davidlohr/much-ado-about-blocking-waitwakke-in-the-linux-kernel)
> * [MCS locks and qspinlocks](https://lwn.net/Articles/590243/) - LWN
### Read-Copy-Update (RCU)
[RCU](https://hackmd.io/@sysprog/linux-rcu) 是 Linux 核心中一種極為重要且高效的 Lock-Free 同步機制，專為「reader 操作遠多於 writer 操作」的場景設計。其核心思想是讓 **reader 在無鎖的情況下直接存取資料**，而 writer 則通過「複製-修改-稍後釋放」的方式來更新資料，確保不會干擾正在進行的讀取操作。RCU 的細節較為複雜，將在後續課程中深入探討。
> 延伸閱讀：[第十五講：RCU 同步機制](https://hackmd.io/@Jaychao2099/Linux-kernel-15)
<!-- 當追求極致的讀取效能時，即使是 `rwlock` 也可能成為瓶頸，因為reader 仍然需要獲取鎖，這涉及到原子操作和 cache line 的爭用。`Read-Copy-Update (RCU)` 是 Linux 核心中一種非常重要且高效的同步機制，它為「讀多寫少」的場景提供了近乎完美的解決方案，其殺手級特性是：**reader 在存取受 RCU 保護的資料時，完全不需要任何鎖、spin、或原子指令**。
RCU 的運作哲學是「讀者暢行無阻，寫者稍作迂迴」。
#### 寫入端 (Update) 的運作方式
當一個 writer 需要修改一個共享資料結構時，它遵循「先複製後更新」的原則：
1. **複製 (Copy)**：writer 首先會為它要修改的部分建立一個副本。例如，如果要修改鏈結串列中的一個節點，它會分配一個新節點，並複製原節點的內容。
2. **修改副本**：所有的修改操作都在這個副本上進行，此時完全不會影響到正在讀取舊資料的任何 reader。
3. **更新 (Update)**：當副本修改完成後，writer 會執行一個**原子性的指標切換操作** (例如使用 `rcu_assign_pointer()`)，將指向舊資料的指標，改為指向剛建立好的新副本。從這一刻起，所有**新來**的 reader 都將會看到更新後的資料。
#### 讀取端 (Read) 的運作方式
reader 端的流程極其簡單：
1. **標記臨界區**：reader 在進入讀取區域前，使用 `rcu_read_lock()` 進行標記。這**不是一個真正的鎖**，它通常只是關閉核心搶佔，以確保 reader 在臨界區內不會被遷移到其他 CPU。
2. **安全地存取指標**：reader 使用 `rcu_dereference()` 來獲取指向共享資料的指標。這個宏確保了在指標讀取過程中不會發生非預期的編譯器或硬體重排序。
3. **自由讀取**：reader 可以自由地遍歷和讀取資料結構，無需擔心資料在讀取過程中被修改，因為它們看到的是一個「快照 (snapshot)」。
4. **結束標記**：讀取完畢後，呼叫 `rcu_read_unlock()` 來結束 RCU 讀取端的臨界區。
#### 核心難題：寬限期 (Grace Period)
既然 writer 用新資料替換了舊資料，那麼舊的資料何時才能被安全地釋放 (free) 呢？這就是 RCU 的核心難點。舊資料必須等到**所有在指標切換前就已經進入臨界區的 reader 全部離開**後，才能被回收。這段等待所有「釘子戶」reader 離開的時間，就被稱為 **Grace Period (寬限期)**。
Linux 核心透過一個巧妙的機制來偵測 Grace Period 的結束。它會等待系統中**每一個 CPU 都至少發生過一次上下文交換 (context switch)** 或其他處於「靜止狀態 (quiescent state)」的事件。因為一個 CPU 發生了上下文交換，就意味著在該 CPU 上於 Grace Period 開始前運行的所有 RCU reader 都已經完成了它們的讀取操作。當所有 CPU 都經歷過靜止狀態後，一個 Grace Period 就結束了。此時，RCU 子系統會執行先前 writer 註冊的回呼函式 (callback)，來安全地釋放舊資料的記憶體。
總結來說，RCU 以延遲釋放記憶體為代價，換取了 reader 端極致的效能和無鎖的並行能力。
-->
### 學術前沿：機率鎖
傳統的鎖難以分析其最壞情況下的執行時間 (Worst-Case Execution Time, WCET)，這對即時系統 (Real-Time Systems) 是致命的。學術界正研究如 [Probabilistic Write Copy Select (PWCS)](https://askra.de/papers/pwcs-nfm.pdf) 和 [pBseq](https://opentech.at/assets/slides/pBseq.pdf) 等基於機率模型的鎖，嘗試為鎖的行為提供可量化的分析，這對 Linux 邁向更嚴格的即時應用領域具有重要意義。
---
## Scalability 可擴展性
### Universal Scalability Law (USL)
為了量化評估系統的可擴展性，[Neil Gunther](https://en.wikipedia.org/wiki/Neil_J._Gunther) 博士提出了通用可擴展性定律 (USL)。$$C(N)={\frac {N}{1+\alpha (N-1)+\beta N(N-1)}}$$其中 $N$ 是負載 (如處理器數量)，$C(N)$ 是系統的吞吐量。
* $\alpha$ 係數代表 **資源爭奪 (Contention)**：由於需要序列化存取共享資源而產生的開銷。
* $\beta$ 係數代表 **一致性延遲 (Coherency)**：由於確保 **各處理器間資料一致性** 而產生的延遲開銷 (如 cache line 的同步)。
當 $\beta = 0$ 時，USL 會退化為著名的 **[Amdahl's law (阿姆達爾定律)](https://en.wikipedia.org/wiki/Amdahl%27s_law)**，它只考慮了系統中可並行與不可並行部分的比例，而忽略了多處理器之間協調本身的開銷。USL 則提供了一個更貼近真實硬體行為的模型。實際上，在多處理器環境中，鎖的競爭 (Contention) 和快取一致性 (Coherency) 是限制系統可擴展性的兩大殺手。
> 延伸閱讀：
> * [Scalability Modeling using Universal Scalability Law (USL)](https://wso2.com/blog/research/scalability-modeling-using-universal-scalability-law)
> * [Scalability is Quantifiable: The Universal Scalability Law | Data Council NYC '18](https://www.youtube.com/watch?v=EfOXY5XY9s8)
### lock 對 scalability 衝擊極大
一個看似無害的短小鎖，在多核心環境下可能成為巨大的效能殺手。UNSW 的一份教材 [SMP, Multicore, Memory Ordering & Locking](https://www.cse.unsw.edu.au/~cs9242/18/lectures/08-smp_locking.pdf) 展示了一個驚人的案例：
在一台 48 核的伺服器上對郵件傳輸代理 (MTA) [Exim](https://www.exim.org/) 進行壓力測試，發現在核心數超過 40 後，系統吞吐量不升反降。
<center><img src="https://i.imgur.com/A7bkoCP.png" alt="image" width="60%" /></center>
透過效能分析工具 oprofile 追蹤，發現瓶頸在於 `lookup_mnt` 函式中的一個 spinlock：`vfsmount_lock`。
```c
struct vfsmount *lookup_mnt(struct path *path) {
struct vfsmount *mnt;
spin_lock(&vfsmount_lock); // <-- 效能瓶頸
mnt = hash_get(mnts, path);
spin_unlock(&vfsmount_lock);
return mnt;
}
```
儘管 CS 非常短，但在 40 多個核心的高強度競爭下，傳統 ticket spinlock 造成的 cache line bouncing 消耗了大量的系統資源，導致了效能的急劇下降。這個例子清楚地說明，僅僅避免 deadlock 是不夠的，鎖的 scalability 對現代多核心系統有致命的影響。
為了徹底解決這類問題，Linux 核心引入了更先進的同步機制，例如 **Sequential locks (seqlock)** 和 **Read-Copy-Update (RCU)**，它們旨在某些特定場景下提供 lock-free 的存取，從而獲得極高的擴展性。
> 延伸閱讀：[第十四講：多核處理器和 spinlock](https://hackmd.io/@Jaychao2099/Linux-kernel-14)
---
## 結論
Linux 核心的同步機制是一個複雜且不斷演進的領域。從早期的 Big Kernel Lock 到現代的各種精細化同步機制，每一次改進都是為了緊密地跟隨著硬體從單核到眾核的變革，在正確性、效能和可維護性之間找到更好的平衡。
理解同步機制不僅需要掌握程式設計技巧，更需要深入了解：
- 計算機結構和 cache 系統
- 多處理器架構和 NUMA 拓撲
- 編譯器最佳化和記憶體模型
- 作業系統排程和中斷處理
隨著硬體架構的持續演進和應用需求的不斷變化，Linux 核心的同步機制也將繼續發展。作為學習者，需要保持學習的心態，跟上這個充滿活力的技術領域的發展步伐。
### 整理
| 同步機制 | 核心思想 | 優點 | 缺點 | 適用場景 |
| :--- | :--- | :--- | :--- | :--- |
| **Mutex / Semaphore** | 休眠等待 (Sleeping lock) | 持鎖時可讓出 CPU，不會浪費運算資源 | 延遲高，涉及上下文交換與排程器 | 持鎖時間較長，可能涉及 I/O 操作等會引起休眠的情境。 |
| **Spinlock (Ticket)** | 忙碌等待 (Busy-wait)，排隊 | 延遲極低，不涉及排程，適用於中斷上下文 | 在高競爭下會因 cache bouncing 導致效能崩潰，浪費 CPU 週期 | 保護的臨界區非常短，且確定不會休眠。 |
| **RW-Lock** | 讀共享、寫獨佔 | 顯著提升「讀多寫少」場景下的並行度 | 仍有鎖的開銷，可能導致 writer starvation | 讀取操作遠多於寫入操作的共享資料結構。 |
| **Seqlock** | writer 優先，reader 驗證重試 | 保障 writer 的低延遲，reader 完全不阻塞 writer | reader 可能需要多次重試，在高寫入競爭下會導致 reader 活鎖 (livelock) | 寫入操作極為重要，且 reader 可以接受重試成本的場景 (如讀取系統時間)。 |
| **MCS Lock** | 佇列化，本地自旋 | 解決了 `spinlock` 的 scalability 問題，在高競爭下效能穩定 | 相較於 `spinlock`，在無競爭下延遲略高，實作較複雜 | 高度競爭、核心數眾多的大型 SMP 系統中的短臨界區。 |
| **RCU** | reader 無鎖，writer 複製更新 | reader 端效能達到極致，無鎖、無延遲、無競爭 | writer 端較複雜，有記憶體開銷和延遲回收的問題 | 讀取操作極度頻繁，寫入相對稀少，且能容忍資料更新延遲的場景 (如路由表)。 |
---
回[主目錄](https://hackmd.io/@Jaychao2099/Linux-kernel)
Sign in with Wallet
Connect another wallet