無鎖併發資料結構練習題 (Practice - Lock-Free Data Structures)
Related Concepts
- 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/05-Lock-Free-Design-Guidelines
Key Patterns(點擊展開)
| 關鍵字 | 答案 |
|---|---|
| 至少一個執行緒有進展 | lock-free;每個執行緒有限步驟完成 = wait-free |
| 自旋鎖 | 非阻塞但有鎖,不是 lock-free |
| CAS 失敗 | 期望值參數被更新為現值 → 迴圈不必手動重讀 |
| 迴圈中 weak vs strong | 迴圈用 weak;失敗代價高(如重設 hazard pointer)用 strong |
| 刪節點的安全條件 | 無其他執行緒持有該節點指標(三種回收策略都在追蹤這件事) |
| hazard pointer | 設定後重讀 head 驗證;刪除前掃全表 |
| split reference count | 讀指標時外部 +1;歸還時 internal += external − 2 |
| ABA | CAS 只比值不比歷史;解法 = 指標附帶世代計數器 |
| 佇列忙等待 | next 原子化 + helping,等待者代做剩餘步驟 |
Question 1 - 非阻塞三層級 [recall]
「obstruction-free、lock-free、wait-free」三者的定義與進展保證各是什麼?自旋鎖屬於哪一類?
查看答案
- obstruction-free(無阻礙):若其他執行緒全部暫停,任一執行緒能在有限時間完成——最弱,常用來描述失敗的 lock-free 實作
- lock-free(無鎖):多執行緒併發操作時,至少一個執行緒在有限時間內完成(系統整體有進展,個別執行緒可能飢餓)
- wait-free(無等待):每個執行緒都在有限步驟內完成,不受其他執行緒影響
- 自旋鎖:沒有阻塞呼叫所以是非阻塞,但仍是一把鎖 → 「非阻塞—有鎖」,不是 lock-free
Question 2 - CAS 迴圈的細節 [recall]
無鎖堆疊的 push 中
while(!head.compare_exchange_weak(new_node->next, new_node));——CAS 失敗後為何不必重新 load head?為何用 weak 而不用 strong?
查看答案
- CAS 失敗時會把 head 的現值寫回第一個參數(期望值
new_node->next),所以下一輪迴圈自動用最新值重試,不必手動load - 反正在迴圈裡,weak 的偽失敗 (spurious failure) 只是多繞一圈,而 weak 在某些平台產生更精簡的機器碼——迴圈中優先用 weak
- 反例:hazard pointer 版 pop 用 strong,因為偽失敗會白白重做「設定 hazard pointer」這種高成本工作
Question 3 - hazard pointer 協定 [recall]
使用 hazard pointer(風險指標)時,讀者設定
hp.store(old_head)之後為什麼還要重新載入 head 比對?刪除者的完整流程是什麼?
查看答案
- 在「讀到 head」與「設好 hp」之間,節點可能已被別的執行緒摘除並刪掉;舊 head 被刪時 head 必已改變,所以重讀 head、不相等就重設 hp 再驗,直到一致才能安全解引用
- 刪除者流程:摘下節點後,呼叫
outstanding_hazard_pointers_for(p)掃描全域 hazard 表——有人引用 →reclaim_later(p)掛待回收鏈;無人引用 → 直接delete;最後delete_nodes_with_no_hazards()重掃待回收鏈 - 每執行緒的 hazard 槽位由
thread_local的hp_owner以 CAS 認領,解構時歸還
Question 4 - 分離引用計數的 −2 [recall]
引用計數無鎖堆疊中,pop 成功者執行
internal_count.fetch_add(external_count - 2)。為什麼是減 2?什麼條件下由誰刪除節點?
查看答案
- −2 的來源:(a) 節點已離開串列,head 不再引用它 → −1;(b) 本執行緒即將結束訪問 → −1
- 外部計數在每次讀取指標時 +1(與讀取同一個 CAS 完成),內部計數在結束訪問時 −1;兩計數總和歸 0 才能刪
- pop 成功者:
fetch_add回傳-count_increase(相加後歸 0)→ 自己 delete;競爭失敗者:fetch_sub(1)回傳 1(自己是最後引用)→ 自己 delete
Question 5 - ABA 問題 [recall]
什麼是 ABA 問題?哪類演算法最容易發生?一般解法是什麼?
查看答案
- 執行緒 1 讀到
x == A後被掛起;期間別的執行緒把 x 改成 B、讓 A 的相關資料失效,又把 x 改回 A(常見:新物件重用了舊位址);執行緒 1 恢復後 CAS 比對 A 成功,但拿到的是「錯誤的 A」→ 結構損毀 - 好發於使用 free list / 循環重用節點的演算法;節點直接還給分配器(配合 hazard pointer / 引用計數)則不會——本章演算法沒有 ABA 問題
- 解法:x 附帶 ABA 計數器(世代計數),CAS 對「值 + 計數」整體操作,每次修改遞增 → 值變回 A 時計數已不同,CAS 失敗
Question 6 - 無鎖佇列的節點計數 [recall]
無鎖佇列的節點為何需要「兩個外部計數器」(
external_counters:2)?為什麼它和internal_count必須放在同一個位域結構、用單一 CAS 更新?
查看答案
- 佇列節點同時被兩個外部計數指標引用:tail 與前一節點的 next,所以新節點初始
external_counters = 2 - 刪除條件是
internal_count == 0且external_counters == 0;若兩欄位分開更新,兩個執行緒可能都自認是最後引用者而重複 delete → 未定義行為 - 位域(30 bit + 2 bit)湊滿 32-bit 單一機器字,才能以單一 CAS 原子更新整個結構,並在 32/64 位平台都保持無鎖
Question 7 - 設計 pop 的回傳方式 [application]
你要為無鎖堆疊設計 pop 介面。同事提議「傳入
T&引用接收結果」或「直接以值回傳T」。指出兩者的問題並給出正確做法。
查看答案
- 以值回傳:節點摘下後才拷貝,拷貝若拋例外,值永久遺失(節點已離開串列)
- 傳引用接收:同樣不可行——必須先確定自己是唯一持有者才能拷貝,而拷貝可能失敗,節點卻已被移除;無鎖環境下無法「先拷貝再摘除」
- 正解:node 內存
std::shared_ptr<T> data,在 push 端make_shared配置(堆分配的例外風險移到 push);pop 只回傳智慧指標——回傳shared_ptr不會拋例外,空堆疊回傳空指標
Question 8 - 消除佇列的忙等待 [application]
實測發現:多生產者無鎖佇列中,一個 push 執行緒對 data 的 CAS 成功後若被排程延遲,其他 push 執行緒全部在空轉。請套用本章技巧修改演算法。
查看答案
- 診斷:其他 push 者在等成功者完成「設定 next、更新 tail」的私有步驟——忙等待,結構退化為半無鎖
- 套用 helping(執行緒互助):
- 把
next從普通成員改為std::atomic<counted_node_ptr> - CAS data 失敗的執行緒不再空轉,改用
compare_exchange_strong幫忙把 next 設為自己準備的新 dummy 節點,再呼叫set_new_tail()幫忙前移 tail - 成功者若發現 next 已被別人設好(自己的 CAS next 失敗),就 delete 自己多配的節點、沿用別人設的值
- 把
set_new_tail()用 weak CAS 迴圈,但 old_tail.ptr 一變就停手(別人已完成),避免把佇列繞成環
Question 9 - 三種回收策略選型 [analysis]
你的無鎖堆疊常態處於高負載(隨時有多個執行緒在 pop),且目標平台不支援雙字 CAS(DWCAS)。比較三種記憶體回收策略,該選哪個?
查看答案
- threads_in_pop + 待刪鏈:高負載下計數永不歸 1,
to_be_deleted無限成長(等同洩漏)→ 排除 - 引用計數(split count):
std::atomic<counted_node_ptr>在無 DWCAS 的平台會退化為內部用鎖,演算法不再無鎖 → 排除(除非能把計數塞進指標空閒位元的平台特定技巧) - hazard pointer:高負載下仍正確,代價是每次 pop 掃表的常數成本;可用「待回收鏈累積到 2×max_hazard_pointers 才回收」攤銷,或改用 thread_local 本地回收鏈 → 本場景的合理選擇(注意 IBM 專利授權問題)
- 結論:hazard pointer;若授權有疑慮且平台允許,再評估引用計數的替代實作
Question 10 - SPSC 佇列為何不能多生產者 [analysis]
代碼 7.14 的無鎖佇列在單生產者/單消費者下完全正確,兩個生產者卻會未定義行為。從先行發生關係與競爭窗口兩方面分析原因,並說明修復思路。
查看答案
- SPSC 正確性的來源:存 data 先行於存 tail(程式順序);store tail 同步於 load tail(原子操作);load tail 先行於讀 data → 消費者讀到的 data 必定完整。這條同步鏈只假設一個寫者、一個讀者
- 兩個生產者的競爭窗口:都
tail.load()讀到同一個 tail 節點,接著同時對該節點的非原子成員data/next寫入 → 資料競爭、未定義行為(不只是值遺失) - 修復思路:(1) 把
data改為std::atomic<T*>,用 CAS 從nullptr設值——成功者獨得該 tail 節點的所有權才能設 next、前移 tail;(2) tail 解引用前需引用計數保護(external counter),節點需兩個外部計數器;(3) 為避免新的忙等待,再加上 helping - 教訓:無鎖設計中「誰有權寫這個位置」必須由原子操作的勝負決定,不能靠使用約定
Pattern Summary(點擊展開)
| 關鍵字 | 答案 |
|---|---|
| 至少一個執行緒有進展 / 每個都有 | lock-free / wait-free |
| 自旋鎖 | 非阻塞—有鎖,非 lock-free |
| CAS 失敗自動更新期望值 | 迴圈不必重讀;迴圈用 weak,失敗代價高用 strong |
| pop 不能立刻 delete | 別的執行緒可能仍持有指標 → 需回收策略 |
| threads_in_pop 高負載 | 待刪鏈無限成長,只適合低負載 |
| hazard pointer | store 後重驗 head;刪前掃表;IBM 專利 |
| external − 2 | 離開串列 −1 + 本執行緒結束訪問 −1 |
| 佇列節點 external_counters = 2 | tail + 前節點 next 同時引用 |
| A→B→A 後 CAS 成功 | ABA 問題 → 世代計數器 |
| push 等 push | 忙等待 → next 原子化 + helping |
| 放寬內存序 | 先 seq_cst 寫對;CAS 失敗分支一律 relaxed;release 配 acquire |