Enter your search text in the box above

Select a result to preview

無鎖堆疊 (Lock-Free Stack)

#cpp-concurrency #concept #lock-free-ds #lock-free #memory-model #compare-exchange

Overview Table

概念 重點
結構選擇 以鏈結串列實作堆疊:std::atomic<node*> head 指向第一個節點
push 競爭窗口 「設定 next」與「更新 head」兩步之間,head 可能被別的執行緒改掉
CAS 迴圈 用 compare_exchange_weak 原子地「驗證 head 沒變才交換」;失敗時自動把 head 現值載入期望值再重試
pop 競爭窗口 兩執行緒讀到同一 head:重複彈出同一節點/解引用懸空指標
先漏記憶體版本 跳過 delete 讓節點洩漏,先解決競爭,回收問題留給 7.2.2–7.2.4
回傳值設計 回傳 std::shared_ptr<T>(不拋例外),不能用「傳引用」或「拷貝回傳」

push 的三步驟與競爭窗口

單執行緒 push 只要三步:1. 建立新節點 node;2. node->next 指向目前 head;3. head 指向 node。多執行緒下,第 2 步與第 3 步之間就是競爭窗口 (race window):

執行緒 A                          執行緒 B
--------                          --------
(2) nodeA->next = head ──┐
                         │窗口    (2) nodeB->next = head   ← 讀到同一個 head
(3) head = nodeA  ───────┘
                                  (3) head = nodeB         ← 覆蓋 A 的更新
結果:nodeA 從串列中「消失」(更新遺失)

無鎖 push:compare_exchange 迴圈

std::atomic<node*> head;
void push(T const& data) {
    node* const new_node = new node(data);           // 1 建構完整節點
    new_node->next = head.load();                    // 2 next 指向現任 head
    while(!head.compare_exchange_weak(
              new_node->next, new_node));            // 3 head 沒變才發布
}
無鎖演算法的通用模式

「讀取舊值 → 私下準備新值 → CAS 發布;失敗就用最新值重試」。CAS 迴圈 = 樂觀併發:假設沒人打擾,被打擾就重來。

pop 的競爭窗口分析

pop 概念上五步:1. 讀 head;2. 讀 head->next;3. 把 head 設為 next;4. 回傳取出節點的 data;5. delete 節點。多執行緒下有兩個問題:

執行緒 A                          執行緒 B
--------                          --------
(1) old_head = head ┐同值┌ (1) old_head = head
(2)(3) CAS 成功摘下節點  │
(4) 取出 data            │        (2) 讀 old_head->next … 咦?
(5) delete old_head ─────┘             ↑ 解引用懸空指標 → UB
無鎖記憶體回收的核心難題

CAS 能保證「只有一個執行緒摘下節點」,卻無法保證「沒有其他執行緒還在讀這個節點」。所以本節先跳過第 5 步,讓節點洩漏。

先漏記憶體的 pop 版本(代碼 7.3)

std::shared_ptr<T> pop() {
    node* old_head = head.load();
    while(old_head &&                                 // 空堆疊檢查
          !head.compare_exchange_weak(old_head, old_head->next));
    return old_head ? old_head->data : std::shared_ptr<T>();
}   // 注意:old_head 沒有 delete → 刻意洩漏

回傳值的異常安全(承第 3 章 stack 的教訓):

這個堆疊是 lock-free,不是 wait-free

push/pop 的 while 迴圈在高競爭下可能重試任意多次。另外,若使用有垃圾回收的語言(C#/Java),洩漏版就已是完整解;C++ 沒有 GC,必須自行處理回收 → 見 07-Lock-Free-Data-Structures/03-Memory-Reclamation-Strategies。

Exam/Test Patterns

情境/關鍵字 答案
「兩個執行緒同時 push,一個節點消失」 第 2/3 步競爭窗口:更新遺失;用 CAS 迴圈更新 head
「CAS 失敗後為何不用重新 load head?」 compare_exchange 失敗時會把現值寫回期望值參數(new_node->next)
「迴圈中用 weak 還是 strong?」 weak——偽失敗只多繞一圈,某些平台效能較佳
「pop 中為何不能 delete 節點?」 其他執行緒可能仍持有指標並將解引用 → 懸空指標/UB,先讓節點洩漏
「pop 回傳值怎麼設計才異常安全?」 回傳 std::shared_ptr<T>(拷貝不拋例外);在 push 端 make_shared 配置
「head 何時才能指向新節點?」 節點完全建構好之後——發布後立刻可能被其他執行緒讀取
「pop 忘了檢查空堆疊」 nullptr->next 是未定義行為,CAS 條件須先檢查 old_head 非空
「這個 stack 是 wait-free 嗎?」 否,CAS 重試次數無上限,只有 lock-free