無鎖設計指導建議 (Lock-Free Design Guidelines)

Overview Table

第 6 章的併發設計通用準則(見 06-Lock-Based-Data-Structures/01-Concurrent-Design-Guidelines)依然適用;以下是從本章例子萃取、專屬無鎖結構的四條建議。

建議一:原型設計先用 std::memory_order_seq_cst

seq_cst 讓所有操作構成一個全域總序,推理最簡單。本章所有例子都是先用 seq_cst 寫到正確,才逐步放寬。

• 放寬內存序是優化:必須先看過「整套」操作資料結構的程式碼,才可能判斷哪些操作可以放寬——過早放寬等於在還不確定不變量時就削弱保證
• 用其他內存序的無鎖程式碼即使通過測試,也不保證內存序正確——執行緒交錯的組合無法窮舉,除非用能系統性檢查所有可見性組合的演算法檢查器驗證
• 放寬的推理流程示範見 07-Lock-Free-Data-Structures/04-Lock-Free-Queue-and-Memory-Ordering;各選項語義見 05-Memory-Model-and-Atomics/04-Memory-Ordering-Options

建議二:對無鎖記憶體回收制定方案

無鎖程式碼與基於鎖的程式碼最大的差異就是記憶體管理:只要還有執行緒在訪問節點,就不能 delete;但為了控制記憶體用量,又希望越早刪越好。本章三種技術(詳見 07-Lock-Free-Data-Structures/03-Memory-Reclamation-Strategies):

• 等待靜止再刪:確認無執行緒訪問資料結構時,統一刪除待刪清單上的物件(threads_in_pop + to_be_deleted 鏈)
• hazard pointer:讀者先標識「我正在用這個物件」,刪除者掃描後只刪無人標識的物件
• 引用計數:每個物件統計訪問中的執行緒數,歸零才刪

共同思想:追蹤有多少執行緒正在訪問指定物件。其他替代方案:

• 垃圾回收器:理想情況下比手寫演算法容易——只需讓回收器知道節點是否仍被引用
• 循環使用節點 (recycle):節點不還給分配器、只在結構銷毀時才真正釋放。因為記憶體永不非法,避開了未定義行為,但代價是引入「ABA 問題」(見建議三)

建議三:小心 ABA 問題

定義:基於 CAS 的演算法中,CAS 只比較「值是否相同」,無法察覺「值曾經變過又變回來」。書中流程:

1. 執行緒 1 讀原子變數 x,值為 A
2. 執行緒 1 基於 A 做了些事(解引用指標、查詢等)
3. 作業系統把執行緒 1 掛起
4. 其他執行緒把 x 改成 B
5. 又有執行緒修改了 A 相關的資料,使執行緒 1 手上關於 A 的資訊失效(如釋放了 A 指向的記憶體,或改了其中的值)
6. 再有執行緒把 x 改回 A——若 A 是指標,可能是新物件恰好重用了舊位址
7. 執行緒 1 恢復,對 x 做 CAS 比對 A:成功,但這是「錯誤的 A」——第 2 步讀到的資料早已失效,後續操作損毀資料結構

以「重用節點的無鎖堆疊 pop」為例:

堆疊: head → A → B → C            執行緒 1 想 pop A

執行緒 1                           其他執行緒
--------                           ----------
old_head = A
next = A->next(= B)
   ── 被 OS 掛起 ──
                                   pop A、pop B(A 被回收進 free list)
                                   push D、push「新節點」→ 重用 A 的位址
                                   堆疊: head → A' → D → C
恢復執行
CAS(head: A → B) 成功!             ← 位址仍是 A,比較通過
                                     但 A' 的 next 其實是 D
結果: head → B(已刪除的節點!)      → 懸空指標、D 遺失、結構損毀

解法:ABA 計數器(世代計數)——讓 x 附帶一個計數器,CAS 對「值 + 計數」的整體操作,每次修改計數遞增。即使值變回 A,計數已不同,過期的 CAS 必定失敗。

struct counted_ptr {         // CAS 的單位是整個結構體
    node*    ptr;
    unsigned aba_count;      // 每次成功修改 +1
};
std::atomic<counted_ptr> x;  // 需能放進平台原子指令(如 DWCAS)

• 好發場景:使用 free list(釋放鏈)或循環使用節點的演算法——位址被快速重用,「A→B→A」很常見
• 不會發生的情況:節點直接還給分配器(本章例子的作法),配合 hazard pointer 或引用計數保證「使用中的節點不會被刪除/重用」——所以本章的演算法沒有 ABA 問題

建議四:識別忙等待迴圈,並幫助其他執行緒

• 症狀:某執行緒卡在迴圈裡,等另一個執行緒完成它的私有步驟才能前進——如佇列例子中,push 必須等前一個 push 設定完 next/tail。這種忙等待既浪費 CPU,又形同阻塞(結構退化為半無鎖),效果和互斥鎖無異
• 處方 (helping):修改演算法,把「只有那個執行緒能做的非原子步驟」改成原子變數 + CAS,讓等待者能代替慢執行緒把剩餘步驟做完——無論誰完成,結果相同,忙等待者不再被阻塞,資料結構恢復真正的無鎖屬性
• 佇列例子的具體改法:next 由普通成員改為 std::atomic<counted_node_ptr>,失敗的 push 者用 CAS 幫成功者設定 next、再幫忙 set_new_tail()(詳見 07-Lock-Free-Data-Structures/04-Lock-Free-Queue-and-Memory-Ordering)
• 更複雜的結構需要更多對應修改,但原則不變:可代做的步驟就開放給所有人做

Exam/Test Patterns

Related Notes

• 07-Lock-Free-Data-Structures/01-Lock-Free-Concepts-and-Tradeoffs
• 07-Lock-Free-Data-Structures/02-Lock-Free-Stack
• 07-Lock-Free-Data-Structures/03-Memory-Reclamation-Strategies
• 07-Lock-Free-Data-Structures/04-Lock-Free-Queue-and-Memory-Ordering
• 07-Lock-Free-Data-Structures/Practice-Lock-Free-Data-Structures
• 05-Memory-Model-and-Atomics/04-Memory-Ordering-Options
• 06-Lock-Based-Data-Structures/01-Concurrent-Design-Guidelines
• 11-Testing-and-Debugging/02-Locating-and-Testing-Concurrency-Bugs