CS149 L16 細粒度鎖與 lock-free：從 test-and-set 到 ABA 問題

🌏 English version

本文依據 CS149 Fall 2025 版。 這是 Stanford CS149 導讀系列第 21 篇，接續 L15 同步實作與記憶體一致性，範圍是 Lecture 16「Fine-Grained Locking and Lock-Free Programming」（2025-11-20）。

用到的官方材料是 L16 投影片 PDF（66 頁，另有逐頁網頁版）。投影片封面的完整標題是「Implementing Locks, Fine-Grained Synchronization, and (a short intro to) Lock-Free Programming」，所以鎖的實作也在這一講。Fall 2025 錄影只在 Canvas，官方首頁指向的 2023 年版對應影片是 Lecture 13: Fine-Grained Synchronization and Lock-Free Programming，本文只把它列為聽講補充，內容以 2025 投影片為準。整門課的存取等級是 A3；這一講投影片完整公開，缺的是當期錄影。

Part 5 這幾篇和 AI 沒有直接關係，但你寫的每個 thread pool、每個多執行緒 runtime 都踩在這些原語上。PA2 的 task queue 就是一個要被多條 thread 同時存取的共享資料結構。

先分清楚三種「卡住」

投影片第 3 頁先定義三個詞，並註明 deadlock 與 livelock 是正確性問題，starvation 比較接近公平性問題：

第 8 頁列出 deadlock 的四個必要條件：mutual exclusion、hold and wait、no preemption、circular wait。後面判斷 hand-over-hand 為什麼不會 deadlock，靠的就是這張表。

鎖怎麼做：每一次嘗試都是一次寫入

第 15–16 頁先複習 MSI 協定，接著才講鎖。順序是刻意的：鎖的效能問題幾乎都是 cache coherence 流量問題。

test-and-set：簡單，但流量很大

ts R0, mem[addr] 原子地把記憶體讀進暫存器，如果是 0 就寫成 1。拿鎖就是不斷 ts，直到讀回 0。問題在於 test-and-set 對 coherence 協定來說永遠是寫入：每次嘗試都發出 BusRdX，把其他 cache 的那條 line 全部 invalidate。第 19 頁的時序圖裡，P1 握著鎖的整段時間，P2、P3 不停地互相搶那條 cache line。

第 21 頁的實驗圖（出自 Culler、Singh、Gupta 的教科書）顯示，處理器越多，單純取得與釋放鎖的時間越長，因為連放鎖的人都得先搶到 interconnect。

第 22 頁列出好鎖的五個指標：低延遲、低 interconnect 流量、可擴展、低儲存成本、公平。簡單 test-and-set 的評語是：低競爭時延遲低，流量大，擴展差，儲存只要一個 int，完全不管公平。

test-and-test-and-set：先讀，再搶

改法是先用一般的讀取在自己的 cache 裡 spin，看到鎖被釋放才真的做 test-and-set：

void Lock(int* lock) {
  while (1) {
    while (*lock != 0);              // 在本地 cache 讀，不產生匯流排流量
    if (test_and_set(*lock) == 0)    // 鎖看起來空了，才去搶
      return;
  }
}

第 25 頁的分析：無競爭時延遲略高（多一次讀），但流量少很多，每次釋放鎖時每個等待者只被 invalidate 一次。儲存成本不變，公平性依然沒有。

ticket lock：解決「一放鎖大家一起衝」

test-and-set 家族的共同問題是放鎖那一刻所有等待者同時去搶。Ticket lock 像銀行抽號碼牌：next_ticket 用 atomic increment 發號碼，now_serving 叫號，等待者只需要讀。第 26 頁的結論是每次釋放只造成一次 invalidation，而且天然照抽號順序拿鎖。

CAS、LL/SC 與 C++11 atomic

第 27 頁列出 CUDA 提供的 atomic 操作（atomicAdd、atomicCAS 等）。第 28 頁出了一個練習：只用 atomicCAS 組出 atomic_min。寫法是讀舊值、算新值，用 CAS 確認舊值沒被別人改過，失敗就重來。第 29 頁用 CAS 寫鎖，並問為什麼「先讀再 CAS」的版本在競爭下比較快，答案和 test-and-test-and-set 相同。

第 30 頁介紹 load-linked／store-conditional：這是一對指令，SC 只在 LL 之後沒有任何處理器寫過該位址時才成功，ARM 上對應 LDREX／STREX。投影片留了一個問題給你：在 cache coherent 的處理器上怎麼實作 LL/SC？這題在 Written 4 的 Problem 2 會再出現。

第 31 頁收在 C++11 的 atomic<T>：它提供整個物件的原子讀、寫、read-modify-write，預設記憶體順序是 sequential consistency，is_lock_free() 可以查實作到底有沒有用 mutex。

用鎖：一條排序 linked list 的三個版本

第 33 頁的範例是單向、排序的 linked list，只有 insert 和 delete。第 34–36 頁示範不加同步會怎樣：兩條 thread 同時插入 6 和 7，算出同一組 prev／cur，其中一個插入直接消失；一邊插入 6、一邊刪除 10，新節點可能接在已被刪除的節點後面。

版本一：一把鎖保護整個 list。 第 38 頁的評語：正確性容易做到，但所有操作被序列化，可能限制整個應用的平行度。

版本二：hand-over-hand locking。 每個節點帶一把鎖，走訪時先鎖下一個節點，再放掉上一個（第 40 頁配了一張《American Ninja Warrior》的照片當比喻）。第 45 頁的程式裡，insert 與 delete 都先鎖 list 再鎖第一個節點，然後一路「鎖 next、放 old_prev」往前推。

第 46 頁整理這個設計的帳：

• 收益：不同位置的操作可以同時進行，減少全域鎖的競爭。
• 難處：何時需要互斥不好判斷；投影片要你自己回答「為什麼一眼就知道這段程式不會 deadlock」。提示是回頭看四個必要條件：所有 thread 都從頭往尾、按同一順序拿鎖，circular wait 不可能成立。
• 成本：每走一步都要拿鎖（走訪變成會寫記憶體），每個節點多一把鎖的儲存。

投影片接著問有沒有折衷：用一把鎖保護一段連續節點，犧牲一點平行度換較低的開銷。這和 L5 選 task granularity 是同一個取捨。第 47 頁另留一個課後練習：為二元搜尋樹寫出支援 insert 與 delete 的細粒度鎖版本。

Lock-free：不拿鎖，改用 CAS 檢查「有沒有人動過」

為什麼鎖是 blocking 的

第 49 頁定義 blocking：一條 thread 可以無限期阻止其他 thread 完成操作。例如 thread 0 拿了某個節點的鎖，接著被 OS 換下、crash，或只是遇到 page fault，其他 thread 就都動不了。投影片特別強調：不管鎖是 spin 還是 preemption 實作，用鎖的演算法都是 blocking。

第 50 頁定義 lock-free：非阻塞，而且保證某個 thread 一定能前進。這個定義不防止個別 thread 餓死。

單一生產者、單一消費者佇列

第 51 頁的 bounded queue 是最簡單的 lock-free 結構：一個陣列，head 由消費者推進，tail 由生產者推進，兩條 thread 從不互相等待，佇列滿時 push 失敗、空時 pop 失敗。第 52–53 頁的 unbounded 版本（出處標為 Dr. Dobb's Journal）多一個 reclaim 指標：節點的配置與釋放都由生產者執行，push 時順便回收消費者已經走過的節點。

這幾頁都有星號註腳：先假設 sequentially consistent 的記憶體系統，或有適當的 memory fence，或使用 C++11 atomic<>。這就是 L15 記憶體一致性的用武之地。

Lock-free stack 與 ABA

第 54 頁的 stack：push 和 pop 都是「讀 top、準備新值、CAS 換上去，失敗就重來」。投影片點出它和細粒度鎖的差別：細粒度鎖鎖住資料結構的一部分；這裡的 thread 完全不持有鎖。

第 55 頁的 ABA 情境（A、B、C、D 是節點位址，不是值）：

1. Thread 0 開始 pop，讀到 old_top = A、new_top = B，還沒 CAS。
2. Thread 1 pop 走 A，push D，再把 A push 回去。現在 stack 是 A → D → B → C。
3. Thread 0 的 CAS 比對 top == A，成功，把 top 設成 B。D 從此遺失。

第 60 頁的 lock-free linked list 插入沒有拿鎖的開銷，也沒有每個節點一把鎖的儲存成本，但前提是 list 上只有插入。第 61 頁說明加入刪除會讓事情複雜許多：B 被刪除的同時有人在 B 後面插入 E，結果 B 指向 E，B 卻已不在 list 裡。投影片給了兩篇延伸閱讀：Harris 2001 與 Fomitchev 2004。

什麼時候真的需要 lock-free

第 62 頁引用 Hunt 2011 的實驗，比較 lock-free、細粒度鎖與 pthread mutex 在佇列與 linked list 上的執行時間。第 63 頁的結論值得原樣記住：

• 在這門課的情境裡，你通常假設機器上只有你的程式在跑（科學計算、圖學、機器學習、資料分析都是這樣）。這時寫得好的鎖版本可以和 lock-free 一樣快甚至更快，而且簡單得多。
• 鎖會出問題的情境是 thread 很多、而且 critical section 裡可能發生 page fault 或被搶佔的系統，例如資料庫和 web server。priority inversion、convoying、在 critical section 裡 crash 這些問題通常在 OS 課討論。

第 64 頁的總結補了兩句容易忽略的話：lock-free 在現代 relaxed consistency 硬體上依然需要適當的 memory fence；lock-free 也沒有消除競爭，競爭激烈時 CAS 會一直失敗、一直重試。

怎麼做：打開第 54 頁的 lock-free stack，在紙上照第 55 頁的時序跑一遍 ABA，然後自己寫出加了 pop_count 的 pop。能說清楚為什麼計數器讓第三步的 CAS 失敗，就代表你抓到了這一講的核心。

伏筆：把 CAS 的角色一般化

第 65 頁用一個問答收尾：lock-free 實作裡的 CAS 在做什麼？答案是判斷在這條 thread 操作到一半時，有沒有別的 thread 改過資料結構。下一講的 transactional memory 把這個想法一般化：讓系統推測一段操作能順利完成，被別人改動時就 abort。

第 66 頁列了延伸閱讀：Michael & Scott 1996 的多讀多寫 lock-free 佇列、Harris 2001、Michael Sullivan 的 RMC compiler，以及兩篇部落格文章。

這一篇可以確認與不能確認的

可以確認：L16 投影片 PDF 的內容、課程首頁上的講次日期與講題摘要。不能確認：Fall 2025 課堂上的口頭補充（錄影不公開）；第 62 頁實驗圖的具體數值（本文沒有讀圖取數）；2023 年錄影與 2025 投影片的逐頁差異。本文沒有依影片內容寫作。

延伸閱讀：OS 角度的鎖實作與 deadlock，可以讀 CS111 Lecture 6：實作鎖與 CS111 Lecture 7：Deadlock。

系列導覽：上一篇 L15 同步實作與記憶體一致性｜下一篇 L17–L18 Transactional memory + Written 4｜系列總覽

參考資料

• Stanford CS149 Fall 2025 課程首頁與講次表
• Lecture 16: Fine-Grained Locking and Lock-Free Programming（投影片 PDF）
• Lecture 16 逐頁網頁版
• CS149 2023 Lecture 13 錄影：Fine-Grained Synchronization and Lock-Free Programming（補充材料）
• CS149 2023 YouTube 播放清單
• Written Assignment 4（PDF）
• Michael Sullivan：RMC compiler（投影片列出的延伸閱讀）