無鎖佇列與記憶體順序 (Lock-Free Queue and Memory Ordering)

#cpp-concurrency #concept #lock-free-ds #lock-free #reference-counting #memory-model #acquire-release

Overview Table

概念	重點
放寬內存序的方法論	先用 seq_cst 寫對,再分析操作間依賴、從執行緒視角找先行發生 (happens-before) 關係,逐一放寬
push/pop 同步鏈	push 的 release CAS 與 pop 端 `increase_head_count` 的 acquire CAS 構成同步發生 (synchronizes-with)
CAS 失敗分支	失敗時什麼都沒改變且會重試 → 一律可用 `memory_order_relaxed`
引用計數的收尾	`fetch_add` 成功分支用 release;把計數減到 0 的執行緒補一個 acquire load 再 delete
SPSC 無鎖佇列	靠 `tail` 的 store/load 建立先行關係;只限單生產者/單消費者
多生產者 push	把 `data` 指標原子化,用 CAS 搶 tail 節點所有權;tail 本身也要引用計數
兩個外部計數器	佇列節點同時被 tail 與前節點 next 引用 → `node_counter` 位域:`internal_count:30` + `external_counters:2`
helping(執行緒互助)	push 中的忙等待使結構「半無鎖」;讓等待者替慢執行緒完成剩餘步驟以恢復無鎖屬性

放寬無鎖堆疊的內存序(7.2.5)

07-Lock-Free-Data-Structures/03-Memory-Reclamation-Strategies 的引用計數堆疊(代碼 7.11–7.12)預設全用 memory_order_seq_cst,昂貴。放寬前先確認哪些資料必須跨執行緒可見,再決定每個原子操作的最低內存序(選項總覽見 05-Memory-Model-and-Atomics/04-Memory-Ordering-Options):

三個關鍵資料:(1) head(counted_node_ptr)、(2) head 引用的 node、(3) node 指向的資料項 data
push 執行緒:建構 data 與 node → 設定 next → CAS 發布 head;pop 執行緒:load head → 增加外部計數 → 讀 node → 讀 next
next 是非原子成員 → 必須讓 push 的儲存先行發生於 pop 的載入,唯一的原子接點就是 head 上的 CAS

push() 執行緒                              pop() 執行緒
------------                               ------------
建構 node、data
next = head.load(relaxed)
head.CAS 成功(release) ──synchronizes-with──▶ increase_head_count:
                                              head.CAS 成功(acquire)
                                                   │ happens-before
                                                   ▼
                                              讀 ptr->next、swap ptr->data  ✓ 安全

逐一推理的結果(代碼 7.13):

操作	內存序(成功/失敗)	理由
push:初始 `head.load()`	relaxed	之後 CAS 會驗證並更新
push:`head.compare_exchange_weak`	release / relaxed	發布 node 內容;失敗時什麼都沒改、繼續迴圈
`increase_head_count` 的 CAS	acquire / relaxed	與 push 的 release 同步,取得 node 內容
pop:摘節點的 `compare_exchange_strong`	relaxed	acquire 已由 `increase_head_count` 完成;`swap()` 時無人能碰同一節點
pop 成功分支:`internal_count.fetch_add`	release	保證 `swap()` 先行於(別的執行緒的)delete
pop 失敗分支:`fetch_add(-1)`	relaxed + acquire load	只有把計數減到 0 的執行緒要 delete,歸零者補 `load(acquire)` 即可

多執行緒交錯修改 head 不需更嚴格的內存序:head 只被 CAS 這種「讀-改-寫」操作修改,它們構成釋放序列 (release sequence)——即使 release 與最終 acquire 之間隔了許多其他 push/pop,兩者仍同步(見 05-Memory-Model-and-Atomics/05-Release-Sequences-and-Fences)
引用計數的收尾若用「成功分支 release + 失敗分支 acquire」雖正確但矯枉過正:只有一個執行緒會 delete,所以只有歸零者需要 acquire;fetch_add 本身是 RMW、屬釋放序列的一部分,歸零後補一次 load(acquire) 即可建立同步

放寬內存序的三條經驗法則

(1) CAS 失敗分支永遠可以 relaxed——失敗代表沒發布任何東西;(2) 「發布資料」的一方用 release,「將解引用非原子成員」的一方用 acquire;(3) 由 RMW 串成的修改鏈是釋放序列,中間操作不必逐一加強。

單生產者/單消費者無鎖佇列(代碼 7.14)

佇列與堆疊不同:push 與 pop 操作兩個不同端點(tail/head),同步需求是「一端的修改對另一端可見」。以第 6 章佇列為基礎,把 head、tail 換成 std::atomic<node*>,並沿用虛擬節點 (dummy node) 技巧(建構時 head = tail = new node):

std::shared_ptr<T> pop() {                 // 消費者
    node* old_head = head.load();
    if(old_head == tail.load()) return {}; // 1 空佇列
    head.store(old_head->next);
    auto res = old_head->data;             // 2 讀 data
    delete old_head; return res;
}
void push(T new_value) {                   // 生產者
    auto new_data = std::make_shared<T>(new_value);
    node* p = new node;                    // 3 新的 dummy
    node* const old_tail = tail.load();    // 4
    old_tail->data.swap(new_data);         // 5 先填資料
    old_tail->next = p;                    // 6
    tail.store(p);                         // 7 最後發布 tail
}

同步鏈:存 data ⑤ 先行於存 tail ⑦;存 tail ⑦ 同步於載入 tail ①;載入 tail ① 先行於讀 data ② → pop 讀到的 data 必定完整——完美的 SPSC 佇列
兩個生產者:讀到同一個 tail ④,同時寫同一節點的 data/next ⑤⑥ → 資料競爭、未定義行為
兩個消費者:讀到同一個 head → 同一節點被回傳兩次 + 懸空指標——與無鎖堆疊 pop 相同,用 CAS + 引用計數解決

SPSC 佇列的適用前提是「約定」而非「保證」

代碼 7.14 的正確性完全依賴恰好一個執行緒 push、恰好一個執行緒 pop。這個約束不由型別系統強制,誤用即未定義行為。

多生產者 push:搶 tail 所有權

讓多個生產者安全共用 tail 的兩個選項:

選項	作法	缺點
(1) 真實節點之間加 dummy 節點	對目前 tail 的 `next` 做 CAS,成功者即完成加入	pop 要跳過 dummy(常刪兩個節點);每次 push 配置兩份記憶體
(2) data 指標原子化(採用)	`std::atomic<T> data` 用 CAS 從 `nullptr` 設為新值,成功者獨得 tail 節點*,才有權設定 next、更新 tail	`shared_ptr` 原子操作多半非無鎖 → 改存裸指標、pop 回傳 `std::unique_ptr<T>`

但這還不夠:push 中 tail.load() 之後解引用,節點可能同時被 pop 端回收——與堆疊相同的懸空指標問題,所以 tail 也需要外部計數。

每個節點有兩個外部計數來源(tail 與前一節點的 next),因此把「外部計數器的個數」也記進節點(代碼 7.16):

struct node_counter {
    unsigned internal_count:30;
    unsigned external_counters:2;   // 最多 2 個外部計數器
};
struct node {
    std::atomic<T*> data;
    std::atomic<node_counter> count; // 位域湊滿 32-bit → 單一機器字、可整體 CAS
    std::atomic<counted_node_ptr> next;
};

新節點初始:internal_count = 0、external_counters = 2(加入佇列時同時被 tail 和前節點的 next 指向)
刪除條件:internal_count == 0 且 external_counters == 0
release_ref():CAS 迴圈把 internal_count 減 1(count 是結構體,不能直接 fetch_sub)
free_external_counter():單一 CAS 同時做 --external_counters 與 internal_count += external_count - 2(−2 的推理同堆疊)

兩個計數必須在同一個 CAS 中更新

若分開更新,兩個執行緒可能各自認為自己是最後一個引用者而都執行 delete → 重複刪除、未定義行為。位域湊成一個機器字,就是為了讓整個 node_counter 能單指令原子更新。

忙等待與 helping(代碼 7.21–7.22)

引用計數版 push 有個隱藏的鎖:對 data 的 CAS 成功者在設好 next、更新 tail 之前,其他 push 執行緒只能空轉重試——忙等待 (busy-wait) 消耗 CPU,首個 push 完成前其他 push 實質被阻塞,結構退化為「半無鎖 (no longer lock-free)」。

解法出自「無鎖技巧包」:等待的執行緒去幫慢的執行緒完成工作 (helping)。

前提:把 next 改為 std::atomic<counted_node_ptr>,pop 也改用原子 load() 讀 next
需要做的事是固定的:「tail 節點的 next 指向新 dummy、tail 前移」——誰來做都一樣

push 成功者(CAS data 成功)              push 失敗者(CAS data 失敗)
--------------------------              --------------------------
CAS(next: {0} → 我的新節點)             CAS(next: {0} → 我的新節點)  ← 幫忙!
 ├ 成功 → next 是我設的                  ├ 成功 → 成功者會沿用它;
 └ 失敗 → 有人幫我設好了:               │         自己再配一個新節點下輪用
          delete 我的新節點、沿用 next   └ 失敗 → 別人已設好,直接沿用
set_new_tail(old_tail, next)            set_new_tail(old_tail, next)

set_new_tail():用 compare_exchange_weak 迴圈更新 tail,但只在 old_tail.ptr 仍是原節點時繼續重試——CAS 失敗僅因 external_count 變動就再試;若 ptr 變了代表其他執行緒已把 tail 更新完,立刻停手(否則會把佇列繞成環)
更新成功者呼叫 free_external_counter(old_tail);被別人搶先者只 release_ref() 釋放自己那一次引用
成本考量:節點在 push 中 new、pop 中 delete,記憶體分配器效率直接決定擴展性;可用每執行緒專屬分配器或節點回收鏈改善——但回收重用節點會引入 ABA 問題(見 07-Lock-Free-Data-Structures/05-Lock-Free-Design-Guidelines)

helping 的本質

把「只有得勝者能做的私有步驟」改寫成「任何人都能替它做的原子步驟」(非原子成員 → 原子成員 + CAS)。這是消除無鎖演算法中忙等待的通用手法。

Exam/Test Patterns

情境/關鍵字	答案
「放寬內存序的第一步?」	先用 seq_cst 寫對,再分析依賴關係、從執行緒視角找 happens-before
「CAS 失敗分支用什麼內存序?」	relaxed——失敗時什麼都沒改變,只會重試
「push 的 CAS 成功為何要 release?」	`next`/data 是非原子資料,靠 release→acquire 讓 pop 端安全解引用
「許多執行緒交錯改 head,同步會斷嗎?」	不會——CAS 是 RMW,構成釋放序列,release 仍同步於最終的 acquire
「歸零刪除者為何補一個 load(acquire)?」	讓所有 `swap()` 先行於 delete;比「所有 fetch_add 都 acquire」便宜(只有刪除者需要)
「SPSC 佇列多執行緒 push 會怎樣?」	兩生產者寫同一 tail 節點的 data/next → 資料競爭、未定義行為
「多生產者怎麼搶 tail?」	data 指標原子化,CAS 由 `nullptr` 設值,成功者獨得設定 next / 更新 tail 的權利
「external_counters 為何是 2?」	佇列節點同時被 tail 與前節點的 next 引用
「internal 與 external_counters 分開更新?」	不行——兩執行緒會都自認最後引用者而重複 delete;必須單一 CAS 更新整個位域結構
「push 等別的 push 設 next = ?」	忙等待,結構只剩半無鎖;用 helping(next 原子化、等待者代做)恢復無鎖
「set_new_tail 何時停止重試?」	CAS 成功,或 old_tail.ptr 已變(別人已完成 tail 更新)