3.2 互斥鎖的硬體支援（test-and-set、compare-and-swap）與無鎖演算法#

為什麼軟體不夠：多處理機的衝擊#

3.1 節的軟體解（Dijkstra/Peterson）依賴一個前提：對共享變數的讀寫是原子的且全序可見（順序一致性）。1960 年代後期開始，多處理機系統（IBM System/360 Model 67、Burroughs、DEC）普及後，兩個問題浮現：

匯流排競爭：每條 load/store 都要搶記憶體匯流排，Peterson 演算法在忙碌等待時瘋狂發出讀取，拖慢整個系統。
記憶體模型：為了效能，CPU 加入 write buffer、快取與亂序執行，load/store 的可見順序不再等於程式順序。Peterson 演算法在 x86（較強的 TSO 模型）上勉強可行，在 ARM/RISC-V（弱記憶體模型）上直接錯誤，需要明確的記憶體屏障。

結論：互斥的根基必須下沉到硬體——需要一條原子讀改寫（atomic read-modify-write）指令。IBM System/360（1964）即提供 Test-and-Set 指令；DEC 的 PDP-11 提供匯流排鎖定；x86 加入帶 LOCK 前綴的指令；現代主流則是 CAS（compare-and-swap） 與 LL/SC（load-linked/store-conditional，MIPS、ARM、PowerPC 路線）。

原子指令的硬體原理#

在單核心上，關中斷即可讓「載入—運算—存回」序列原子化。多核心上則需保證其他核心「插不進來」，硬體有兩大做法：

匯流排/快取行鎖定：x86 的 LOCK 前綴使該指令對快取行的存取獨佔——現代實作靠快取一致性協定（MESI）把該快取行變成 Modified 狀態並鎖住，遠比鎖整條匯流排便宜。
LL/SC（load-linked/store-conditional）：LL 讀取並「登記監視」，SC 只有在監視的快取行未被他人動過時才成功。用「樂觀+重試」替代「悲觀+鎖定」，避免匯流排瓶頸，但帶來 ABA 問題（後述）。

用原子指令造鎖#

Test-and-Set 自旋鎖#

// 原子指令：回傳舊值，並把值設為 1
bool test_and_set(int *lock);

void acquire(int *lock) {
    while (test_and_set(lock) == 1)
        ;   // 拿到 1 表示別人先搶走 → 繼續轉
}
void release(int *lock) { *lock = 0; }

正確性關鍵：「讀舊值與寫新值」之間沒有任何指令能插入，兩個 CPU 同時 test_and_set 必有先後，只有一個拿到 0。

CAS 與簡單自旋鎖#

// 原子比較交換：若 *p == old 則 *p = new，回傳舊值
int compare_and_swap(int *p, int old, int new);

void acquire(int *lock) {
    while (compare_and_swap(lock, 0, 1) != 0)
        ;
}

CAS 更通用：它可以原子地做任意條件更新，這使它成為無鎖程式設計的萬用積木。x86-64 對應指令為 lock cmpxchg。

優化自旋鎖：test-and-test-and-set（TTAS）#

純 TAS 在等待期間不斷寫入鎖變數，每次寫都透過 MESI 把快取行在核心間踢來踢去（快取行乒乓），匯流排爆炸。改良：先唯讀自旋，看到鎖釋放才用原子指令搶：

void acquire(int *lock) {
    for (;;) {
        while (*lock == 1)        // 階段一：唯讀自旋，
            ;                     // 快取行以 Shared 狀態被所有核共用
        if (test_and_set(lock) == 0)
            return;               // 階段二：才發原子寫
    }
}

再進一步是排隊鎖（ticket lock）與 MCS 鎖：ticket lock 用兩個號碼牌變數保證 FIFO 釋放順序；MCS 鎖（Mellor-Crummey & Scott, 1991）讓每個等待者自旋在自己的快取行上，徹底消除乒乓，是 Linux 核心大型鎖的選擇。這一系列演進的教訓：在多核上，快取一致性流量比指令數更昂貴。

記憶體屏障：原子指令不等於一切#

即使有原子指令，一般的 load/store 仍可能被 CPU 與編譯器重排。例如雙重檢查鎖定（double-checked locking）的經典錯誤：

// 錯誤示範：無屏障的 DCL
if (instance == NULL) {          // 讀
    lock();
    if (instance == NULL) {
        instance = new Obj();    // 寫指標 ← 可能先於建構子寫入被外部可見！
    }
    unlock();
}

在弱記憶體模型上，另一執行緒可能看到「指標非空但物件欄位尚未初始化」。修正必須在寫後加 release 屏障、讀前加 acquire 屏障（C++11 的 memory_order_release/acquire、Java 的 volatile 都是在語言層提供此保證）。這一主題的正式化是 C++11 記憶體模型（2011，統一了三十年來的混亂），它是理解現代所有併發程式碼的地基。

無鎖（lock-free）演算法#

自旋鎖只是把忙碌等待包裝起來；無鎖演算法更進一步：整個資料結構的操作不含任何鎖，且系統層面保證有人會推進（無鎖），或甚至每條執行緒都推進（wait-free，Herlihy 1991 定義並證明其一致性階層）。基石仍是 CAS：

無鎖計數器#

void atomic_inc(int *v) {
    int old;
    do {
        old = *v;
    } while (compare_and_swap(v, old, old + 1) != old);
}

失敗就重試，不需要鎖。x86 直接提供 lock xadd（fetch-and-add）一步完成；Herlihy 證明 fetch-and-add 與 CAS 具有同等的一致性能力。

無鎖堆疊（Treiber stack）與 ABA 問題#

void push(node_t **head, node_t *n) {
    node_t *old;
    do {
        old = *head;
        n->next = old;
    } while (CAS(head, old, n) != old);
}
node_t *pop(node_t **head) {
    node_t *old, *next;
    do {
        old = *head;
        if (old == NULL) return NULL;
        next = old->next;
    } while (CAS(head, old, next) != old);
    return old;
}

pop 有著名的 ABA 問題：執行緒 A 讀到 head=X（next=Y），被搶佔；期間 X 被彈出又恰好重新壓回同一位址 X（next 已變），A 的 CAS 仍成功，但 next 已錯。解法：

版本號 CAS（tagged pointer）：把計數器併入指標一起比較（x86 可用雙字 cmpxchg）。
危險指標（hazard pointer，Michael 2004）／時代回收（epoch-based reclamation）：延遲釋放直到確認無人引用——這正是 Linux RCU 做的事。
LL/SC 架構天然部分緩解（監視會偵測任何寫入）。

鎖與無鎖的取捨#

面向	鎖	無鎖
推理難度	較易（臨界區語意）	極難（交錯無窮）
死結	可能	不可能
搶佔後行為	持鎖者被停即全局停頓	其他執行緒仍可推進
適用	多數複雜結構	佇列、計數、棧等小結構

實務鐵律：先用鎖，量測到瓶頸且結構夠簡單才上無鎖。Java 的 ConcurrentLinkedQueue（Michael & Scott 演算法）、Linux RCU、現代 CPU 內建原子 API（C11 <stdatomic.h>）都建立在上述理論之上。

與編譯器/VM 的關聯#

編譯器必須「知道」原子性：volatile 不等於原子；C11/C++11 的 atomic 型別禁止編譯器將其重排或拆解。JIT（如 V8、HotSpot）在生成機器碼時直接發射 lock 前綴指令，Java 的 synchronized 在無競爭時被 JIT 最佳化為偏向鎖/薄鎖（CAS 一次的快速路徑），有競爭才膨脹為 OS mutex——語言執行期在「自旋」與「系統呼叫」之間做兩階段適應，正是 3.1 節 adaptive mutex 的 JVM 版。
GC 與無鎖回收：JVM 的分代 GC 在回收期間移動物件，因此 Java 不能直接做 Treiber stack 的指標 CAS——需要壓縮指標（compressed oops）與 GC 配合的引用語意。這說明無鎖演算法與記憶體管理策略（誰能釋放節點）深度耦合。
事務記憶體（TM）：Herlihy & Moss（1993）提出硬體事務記憶體（HTM），把「一段程式碼」整體原子化（Intel TSX，2013；因側信道漏洞於 2019+ 停用/關閉）。它可視為「把樂觀併發（資料庫的兩階段鎖替代方案）搬進 CPU」，與 CAS 重試是同一哲學的粗粒度版本。

重點整理#

多處理機下互斥必須由硬體原子指令（TAS/CAS/LL-SC）兜底；Peterson 等軟體解僅具理論與教學價值。
快取一致性流量（乒乓）決定了真實鎖的效能；TTAS、ticket、MCS 的演進都是圍繞它展開。
CAS 是無鎖演算法的萬用積木，但 ABA 與記憶體回收是其兩大深坑，RCU/hazard pointer 是工業解。
記憶體模型（C++11）與 JIT 的鎖膨脹技術，顯示同步問題已從 OS 深入編譯器與語言執行期。