Lock-free 資料結構實戰

在上一篇 《C++ 與 Rust 記憶體模型：從 Memory Ordering、硬體快取到 Safe Publication》 中，我們建立了對記憶體順序、編譯器重排、Store Buffer 與快取一致性的完整認知。我們明白了單一原子操作的成功，並不自動等同於周邊資料已經同步可見；唯有透過 Acquire-Release 配對，才能在多核心之間拉起堅固的因果同步橋樑。

掌握了記憶體模型這張入場券後，我們終於可以直面高效能並行程式設計的聖杯——無鎖資料結構（Lock-free Data Structures）。

許多人剛接觸無鎖程式設計時，常有一種美麗的幻想：「只要把所有 std::mutex 拿掉，改用 CAS（Compare-And-Swap）迴圈，程式碼就會奇蹟般地變快且沒有鎖衝突。」

然而，現實往往十分殘酷。當你拿掉互斥鎖的保護後，除了必須自行處理狀態移轉與記憶體順序外，還會立刻遭遇並行運算領域的兩大深水區：

1. 拓撲移轉的幽靈——ABA 問題：指標位址相同，真的代表鏈結結構沒有改變過嗎？
2. 記憶體生命週期的深淵——安全記憶體回收（Safe Memory Reclamation, SMR）：當一個節點被某個執行緒從資料結構中拔除時，其他並行的讀者執行緒可能正剛讀出指標準備解引用（dereference）。如果此時直接 delete 或釋放記憶體，就會引發致命的 Use-After-Free 記憶體損毀。

本文將以經典的 Treiber Stack 為基準，透過現代 C++20 與 Rust 的雙語言實作，深入解構 CAS 原語、狀態重試機制，並全面剖析 Tagged Pointer、Hazard Pointer、Epoch-Based Reclamation (EBR) 與 RCU 四大安全記憶體回收架構的設計權衡。

從 Memory Ordering 到 Lock-Free：思維範式轉移

在傳統的並行架構中，互斥鎖（Mutex）扮演著全能守護者的角色。當一個執行緒進入 mutex.lock() 與 mutex.unlock() 包夾的臨界區（Critical Section）時，Mutex 同時為我們解決了三件事：

當我們決定移除 Mutex 時，上述三項保護全部煙消雲散。我們必須：

1. 用 CAS（Compare-And-Swap） 取代臨界區互斥，讓多個執行緒樂觀競爭狀態轉移。
2. 用 Acquire / Release / Relaxed 精確標註每次原子讀寫，確保資料初始化與發布具備因果先後。
3. 引進 安全記憶體回收（SMR） 機制，接手原先由鎖保護的物件生命週期。

既然 Mutex 能如此滴水不漏地提供三重防護，為什麼並行系統工程師依然對「擺脫互斥鎖」如此執著？這就必須從 Mutex 在微觀硬體與宏觀作業系統排程中所背負的隱形成本談起。

互斥鎖的真實代價：從輕量原子到核心態深淵

許多人直覺認為「鎖就只是一道門，排隊通過即可」。但在現代多核心架構與搶佔式作業系統下，Mutex 的運作遠比想像中複雜。現代主流作業系統的 Mutex（如 Linux 的 Futex 或 Windows 的 SRWLock）均採用「快慢雙路徑」設計：

這套混合架構雖然極大化了無競爭情境的效能，但只要並發度提高並引發持續競爭，Mutex 的連鎖代價便會逐一浮現：

上下文切換與核心態調度開銷

在無競爭的快樂路徑（Happy Path）上，mutex.lock() 僅是一次純使用者態的原子操作，耗時通常在 10 到 25 奈秒之間。然而，一旦多個執行緒同時爭搶鎖，自旋未果的執行緒就必須發起系統呼叫（如 Linux 的 SYS_futex），將自己掛起並交出 CPU。

一次完整的上下文切換（Context Switch）涉及暫存器狀態保存、進入核心態排程器佇列、切換虛擬記憶體頁表與上下文環境。這段延遲直接暴增至 1,000 到 5,000 奈秒（數量級約在 1 到 5 微秒，視架構與負載而定），比一次純記憶體操作慢了整整兩到三個數量級。

快取污染與快取行彈跳

當一個被掛起的執行緒在數微秒後被排程器重新喚醒時，極有可能被分派到另一個閒置的 CPU 核心上執行。這會帶來嚴重的快取懲罰：

• 該執行緒原本在 L1/L2 快取中快取的熱點資料早已失效（Cold Cache Misses），甚至需要重新走 TLB 查表。
• 多個核心爭奪同一個 Mutex 內部狀態變數時，每次加鎖與解鎖的原子寫入都會觸發快取一致性協定（如 MESI/MOESI）在多核心互連架構上引發大量無效化訊息。這會造成嚴重的快取行彈跳（Cacheline Bouncing），使該快取行的互連流量飽和，甚至拖慢共享同一快取階層的其他無關工作。

護送效應與擴展性懸崖

當系統面臨高度並發時，鎖的等待佇列會形成惡性循環的「護送效應」（Convoy Effect）。由於每個執行緒被喚醒時都要承擔額外的核心調度延遲，即使臨界區內的運算只有短短 20 奈秒，整個系統的推進節奏也會被微秒級的喚醒排程完全綁架。

此時系統不僅面臨阿姆達爾定律（Amdahl’s Law）所定義的循序上限（臨界區限制了理論最大加速比），更會觸發嚴重的負向擴展（Negative Scaling）：增加更多的 CPU 核心非但無法提升吞吐量，反而因為更激烈的鎖競爭、快取行彈跳風暴與微秒級排程調度延遲放大，導致整體效能呈懸崖式暴跌。

優先權反轉

在具備執行緒優先權的即時或多工作業系統中，Mutex 存在著名的結構性缺陷——優先權反轉（Priority Inversion）：

• 低優先權執行緒獲取了鎖，進入臨界區。
• 隨後，中優先權執行緒搶佔了 CPU（中優先權工作不需要該鎖，但優先級高於低優先權）。
• 此時高優先權執行緒被喚醒，需要獲取同一個鎖，但由於低優先權執行緒被中優先權卡住而無法執行，高優先權執行緒被迫無限期等待。

1997 年美國 NASA 的火星探測器「火星拓荒者號」（Mars Pathfinder）便曾因為資訊匯流排 Mutex 發生優先權反轉，導致高優先權的資料收集任務嚴重逾時，觸發系統看門狗（Watchdog）不斷重新開機。

不可組合性與死鎖風險

鎖缺乏代數上的組合性（Locks do not compose）。兩個單獨看來無懈可擊、內部各自用 Mutex 保護的執行緒安全函式，在交叉呼叫時若未能嚴格遵循完全一致的加鎖順序，就會在多執行緒交錯下瞬間觸發死鎖（Deadlock）。

為什麼需要無鎖：不可妥協的場景與系統保證

正因為 Mutex 存在上述硬體與排程層面的代價，在特定工程領域中，我們並非單純為了「追求理論效能」，而是面對硬性約束時「不得不採用無鎖」。無鎖資料結構的核心價值在於提供兩大不可替代的保證：系統級進度保證與低且可預測的長尾延遲。

系統級進度保證：杜絕命運綁定

基於互斥鎖的系統存在著嚴重的命運綁定（Fate Sharing）：一旦持有鎖的執行緒因為任何非預期事件（被作業系統強制暫停、遭遇分頁置換 Page Fault、觸發例外、甚至被外部訊號直接殺死），所有正在等待該鎖的其他執行緒都將全數卡死或永久阻塞。

無鎖演算法消除了「鎖的所有權」概念。沒有任何一個執行緒具備獨佔資源的特權；執行緒之間只透過硬體原語競逐狀態轉移。即使某個執行緒在執行途中被作業系統隨機凍結，其他執行緒依然能各憑本事持續推進。

消除長尾延遲

在金融高頻交易（HFT）、即時競價、分散式儲存引擎與資料庫 WAL（Write-Ahead Log）的關鍵路徑上，系統衡量標準不是「平均延遲（P50）有多低」，而是「99.9% 甚至 99.99% 的長尾延遲（P99 / P99.9）有多穩定」。

Mutex 偶發的鎖競爭與 Context Switch 會在微秒層級造成嚴重的延遲抖動（Jitter）。Lock-Free 演算法將操作完全收斂在純使用者態與 CPU 執行單元內，徹底拔除了核心態排程介入的可能性，提供了極高確定性的延遲表現。

嚴格禁止睡眠的極限環境

在許多系統底層場景中，呼叫任何可能讓執行緒陷入睡眠的 Mutex 操作，在語法或規範上是被絕對嚴格禁止的：

• 中斷處理常式（ISR）與訊號處理函式（Signal Handlers）：硬體中斷與 Linux 訊號發生在特殊的非同步上下文，該上下文根本沒有獨立的排程實體可供掛起，且必須保證非同步信號安全（Async-Signal-Safe）。一旦在此處嘗試加鎖並陷入睡眠，將導致系統崩潰或瞬間死鎖。
• 即時音訊處理（Real-time Audio DSP）：在 CoreAudio、JACK 或 ASIO 等音訊框架中，處理回呼函式必須在數微秒至數百微秒的嚴格時限內將音訊緩衝區填滿。若因 Mutex 競爭觸發 Context Switch，哪怕只延誤了 10 微秒，都會引發音訊緩衝區欠載（Buffer Underrun），在使用者耳機中產生刺耳的破音或爆音。
• 非同步協程執行緒池（Async Runtime Worker Threads）：在 Tokio、Go Runtime 等 M:N 協程排程體系中，少數幾個工作執行緒負責輪番執行成千上萬個非同步協程（Coroutines / Tasks）。如果某個協程的工作函式呼叫了傳統的 Blocking Mutex 並陷入核心態睡眠，將導致該 OS 執行緒上排隊的所有其他協程一併陷入飢餓與癱瘓。

進度保證等級：Lock-Free、Wait-Free 與 Obstruction-Free

在學術與系統規格中，「無鎖」並非單純指「程式碼中沒有搜尋到 mutex 關鍵字」，而是對系統並行推進能力的嚴格數學承諾：

• Obstruction-Free（無障礙）：最弱的保證。只要一個執行緒在執行時其他執行緒全部暫停，該執行緒保證能在有限步驟內完成操作。若多個執行緒持續活鎖競爭，則不保證進展。
• Lock-Free（無鎖）：保證整個系統在巨觀上持續有進度（System-wide Progress）。即使作業系統在任何時刻隨機將某些執行緒掛起（Suspend）或降低優先權，剩餘的執行緒中至少有一個一定能持續完成操作。但個別執行緒可能會遭遇飢餓（Starvation）。
• Wait-Free（無等待）：最強的進度保證。每一個執行緒都保證能在有限的步驟內（Bounded Steps）完成操作，徹底杜絕了個別執行緒的飢餓現象。通常需要搭配昂貴的協同幫忙（Helping Scheme）機制。

一般的並行佇列與堆疊多半落在 Lock-Free 等級。

核心原子原語：Compare-And-Swap (CAS) 的運作機制

Lock-Free 資料結構的心臟是 CAS 操作。在 C++ 中體現為 atomic::compare_exchange_weak 與 compare_exchange_strong；在 Rust 中則為 AtomicPtr::compare_exchange_weak 與 compare_exchange。

CAS 操作將「比較目前值是否符合預期」與「寫入新數值」合併為語言層級不可分割的原子讀改寫（Read-Modify-Write, RMW）操作（在底層硬體上可能對應單一指令如 x86 CMPXCHG、或 ARM/RISC-V 的 LL/SC 指令對）：

如果目標記憶體目前的值等於 expected，硬體就將其替換為 desired 並回傳成功；如果不等於，硬體放棄寫入，並自動將目前記憶體的最新值寫回 expected 變數中，回傳失敗。

為什麼 CAS 需要兩個 Memory Ordering 參數？

檢視 C++ 與 Rust 的 CAS 函式簽名，你會發現它們都要求傳入兩個 ordering：

// C++
bool compare_exchange_weak(T& expected, T desired,
                           std::memory_order success,
                           std::memory_order failure);

// Rust
pub fn compare_exchange_weak(
    &self,
    current: *mut T,
    new: *mut T,
    success: Ordering,
    failure: Ordering
) -> Result<*mut T, *mut T>;

為什麼不能只用一個 ordering？

• 成功時（Success）：執行了實質的讀改寫（RMW），我們正在發布新的狀態給其他執行緒，因此可以使用 Release、Acquire、AcqRel 或 SeqCst。
• 失敗時（Failure）：沒有發生任何寫入操作！失敗的 CAS 本質上是一次純讀取的載入（將目標位址的最新值寫回 expected）。因為沒有寫入，所以在語意上失敗 ordering 不能要求 Release 或 AcqRel 效果；同時在 C++ 規範中，失敗 ordering 不得嚴於成功 ordering（例如成功為 Relaxed 時，失敗不得為 Acquire）；而在 Rust 中若傳入不合法的失敗 ordering 亦會在執行期引發 panic。

weak 與 strong 的本質差異

• compare_exchange_strong：保證只有在當前值不等於 expected 時才會回傳 false。
• compare_exchange_weak：允許在當前值明明等於 expected 的情況下，依然因為硬體因素（例如 ARM/RISC-V 的 LL/SC 快取行被踢出、中斷或 context switch）而發生虛假失敗（Spurious Failure）。

最佳實踐原則：在絕大多數 Lock-free 演算法中，CAS 本身就被包裹在一個重試迴圈裡。此時通常建議優先考慮 compare_exchange_weak。在弱記憶體架構（如 ARM64）上，weak 能直接映射到最精簡的單對 LL/SC（ldaxr/stlxr）指令，免去 strong 為了防止硬體虛假失敗所額外生成的內部重試迴圈包裝（但在 x86 等強記憶體架構上，兩者皆編譯為 lock cmpxchg，效能表現相同）。

經典實戰：Treiber Stack 雙語言基準實作（不含 SMR）

Treiber Stack（由 R. Kent Treiber 於 1986 年提出）是無鎖領域中最基礎、最優雅的資料結構。它本質上是一個單向鏈結串列，所有操作都僅集中在單一原子指標——head 上：

⚠️ 重要實作前提：本節程式碼為不含 SMR（安全記憶體回收）的教學基準實作，旨在精確解構 CAS 狀態轉移與 Acquire/Release 配對。它的正確性嚴格建立在三個限制邊界假設上：

1. 節點不得就地釋放（不得中途呼叫 delete 或歸還給記憶體配置器）。
2. 節點不得重複 push，且呼叫端不得在其他執行緒可能持有指標時修改節點欄位。
3. 節點生命週期維持至所有執行緒完全 join 離場後，由擁有者統一釋放（杜絕並行執行時的 Use-After-Free）。 在未引入後續章節探討的 SMR 安全回收協定前，切勿將此裸指標實作直接移植至生產環境！

C++20 實作

#include <atomic>
#include <cassert>
#include <iostream>
#include <thread>
#include <vector>

template <typename T>
class TreiberStack {
public:
    struct Node {
        T data;
        Node* next{nullptr};
        explicit Node(T val) : data(std::move(val)) {}
    };

private:
    // 注意：在主流 64 位元架構上 std::atomic<Node*>::is_always_lock_free 為 true。
    // 在特殊嵌入式或非原生字長環境下，需透過 is_lock_free() 確認硬體無鎖保證。
    std::atomic<Node*> head_{nullptr};

public:
    TreiberStack() = default;
    ~TreiberStack() = default;

    // 禁止複製與搬移以確保原子指標位址固定
    TreiberStack(const TreiberStack&) = delete;
    TreiberStack& operator=(const TreiberStack&) = delete;

    void push(Node* new_node) {
        // 步驟 1：使用 relaxed load 取得目前的 head
        // 理由：我們此處只是讀取指標位址賦予 new_node->next，
        // 尚未 dereference 舊節點，不需要任何跨執行緒同步。
        Node* old_head = head_.load(std::memory_order_relaxed);

        // 步驟 2：CAS 迴圈
        // 成功的 CAS 使用 release：確保 new_node 的 data 與 next 初始化完成後才發布。
        // 失敗的 CAS 使用 relaxed：若失敗，old_head 會被自動更新，直接進入下一輪。
        do {
            new_node->next = old_head;
        } while (!head_.compare_exchange_weak(
            old_head, new_node,
            std::memory_order_release,
            std::memory_order_relaxed));
    }

    Node* pop() {
        // 步驟 1：使用 acquire load 取得目前的 head
        // 理由：我們接下來必須安全讀取 old_head->next，因此必須與當初 push 該節點的 release store 同步！
        Node* old_head = head_.load(std::memory_order_acquire);

        while (old_head != nullptr) {
            // 讀取下一個節點（此時依賴前面 load 或上一次失敗 CAS 的 acquire 同步）
            Node* next_node = old_head->next;

            // 步驟 2：CAS 嘗試將 head 移向 next_node
            // 成功：使用 acquire 保持防禦性同步。
            // 失敗：關鍵！失敗 ordering 必須也是 acquire！
            // 理由：若 CAS 失敗，old_head 會被更新為另一個執行緒剛 push 上去的新節點；
            // 下一輪迴圈會立刻執行 old_head->next，此處的 acquire 才能與該執行緒 push 的 release 建立因果同步！
            if (head_.compare_exchange_weak(
                    old_head, next_node,
                    std::memory_order_acquire,
                    std::memory_order_acquire)) {
                return old_head;
            }
        }
        return nullptr; // stack 為空
    }
};

int main() {
    TreiberStack<int> stack;
    typename TreiberStack<int>::Node n1(10);
    typename TreiberStack<int>::Node n2(20);

    // 多執行緒並行 Push
    std::thread t1([&] { stack.push(&n1); });
    std::thread t2([&] { stack.push(&n2); });
    t1.join();
    t2.join();

    // 多執行緒並行 Pop
    typename TreiberStack<int>::Node* res1 = nullptr;
    typename TreiberStack<int>::Node* res2 = nullptr;

    std::thread t3([&] { res1 = stack.pop(); });
    std::thread t4([&] { res2 = stack.pop(); });
    t3.join();
    t4.join();

    assert(res1 != nullptr && res2 != nullptr);
    assert(res1 != res2);
    assert(res1->data + res2->data == 30);
    assert(stack.pop() == nullptr);

    std::cout << "Treiber Stack operations completed successfully.\n";
}

Rust 實作

在 Rust 中，裸指標的解引用屬於 unsafe 操作。Rust 的型別系統迫使我們明確寫出哪些假設是由程式員擔保的：

use std::sync::atomic::{AtomicPtr, Ordering};
use std::sync::Arc;
use std::thread;

pub struct Node<T> {
    pub data: T,
    pub next: *mut Node<T>,
}

impl<T> Node<T> {
    pub fn new(data: T) -> Self {
        Self {
            data,
            next: std::ptr::null_mut(),
        }
    }
}

pub struct TreiberStack<T> {
    head: AtomicPtr<Node<T>>,
}

// 實作 Send 與 Sync：這是作者對型別安全不變量的承諾
// 只要 T: Send，節點所有權在 pop 時即可安全轉移跨執行緒存取；
// 由於內部 head 為 AtomicPtr，亦滿足多執行緒共用參照的安全性。
unsafe impl<T: Send> Send for TreiberStack<T> {}
unsafe impl<T: Send> Sync for TreiberStack<T> {}

impl<T> TreiberStack<T> {
    pub fn new() -> Self {
        Self {
            head: AtomicPtr::new(std::ptr::null_mut()),
        }
    }

    pub fn push(&self, new_node: *mut Node<T>) {
        assert!(!new_node.is_null());
        let mut old_head = self.head.load(Ordering::Relaxed);
        loop {
            // 安全保證：呼叫者保證在此刻獨占 new_node
            unsafe {
                (*new_node).next = old_head;
            }

            // 成功 Release 發布新節點；失敗 Relaxed 載入最新 head 重試
            match self.head.compare_exchange_weak(
                old_head,
                new_node,
                Ordering::Release,
                Ordering::Relaxed,
            ) {
                Ok(_) => break,
                Err(actual) => old_head = actual,
            }
        }
    }

    pub fn pop(&self) -> *mut Node<T> {
        let mut old_head = self.head.load(Ordering::Acquire);
        while !old_head.is_null() {
            // 安全保證：基準範例保證節點在全部執行緒離場前不會被 free
            let next_node = unsafe { (*old_head).next };

            // 成功 Acquire 獲取；失敗 Acquire 確保下輪解引用 actual 時具備同步保護
            match self.head.compare_exchange_weak(
                old_head,
                next_node,
                Ordering::Acquire,
                Ordering::Acquire,
            ) {
                Ok(_) => return old_head,
                Err(actual) => old_head = actual,
            }
        }
        std::ptr::null_mut()
    }
}

// 輔助型別：封裝裸指標以符合 Send 要求，安全傳遞進 thread::spawn
struct SendPtr<T>(*mut Node<T>);
unsafe impl<T: Send> Send for SendPtr<T> {}
impl<T> SendPtr<T> {
    fn into_inner(self) -> *mut Node<T> {
        self.0
    }
}

fn main() {
    let stack = Arc::new(TreiberStack::new());
    let mut node1 = Box::new(Node::new(10));
    let mut node2 = Box::new(Node::new(20));

    let n1_ptr = SendPtr(&mut *node1 as *mut Node<i32>);
    let n2_ptr = SendPtr(&mut *node2 as *mut Node<i32>);

    let s1 = Arc::clone(&stack);
    let t1 = thread::spawn(move || s1.push(n1_ptr.into_inner()));
    let s2 = Arc::clone(&stack);
    let t2 = thread::spawn(move || s2.push(n2_ptr.into_inner()));
    t1.join().unwrap();
    t2.join().unwrap();

    let s3 = Arc::clone(&stack);
    let t3 = thread::spawn(move || SendPtr(s3.pop()));
    let s4 = Arc::clone(&stack);
    let t4 = thread::spawn(move || SendPtr(s4.pop()));

    let r1 = t3.join().unwrap().into_inner();
    let r2 = t4.join().unwrap().into_inner();

    assert!(!r1.is_null() && !r2.is_null());
    assert_ne!(r1, r2);

    let sum = unsafe { (*r1).data + (*r2).data };
    assert_eq!(sum, 30);
    assert!(stack.pop().is_null());

    println!("Rust TreiberStack executed safely.");
}

線性化點（Linearization Point）剖析

在並行驗證理論中，一個無鎖操作必須存在一個確切的原子瞬間，使得該操作在該時刻「邏輯生效」，這被稱為線性化點：

• push 的線性化點：CAS 成功將 head 指向 new_node 的那一瞬間。
• pop 的線性化點（非空）：CAS 成功將 head 指向 next_node 的那一瞬間。
• pop 的線性化點（為空）：當 head.load(Acquire) 讀到 nullptr 的那一瞬間。

致命幽靈：ABA 問題深度剖析

現在，讓我們放寬前面基準實作的假設：「允許節點被重複使用或歸還配置器」。災難立刻降臨。

這就是並行計算中最著名的陷阱——ABA 問題。

ABA 問題如何發生？

假設目前的 Stack 拓撲為 head -> [A] -> [B] -> [C]。

此時有兩個執行緒 T1 與 T2 正在執行 pop()：

拆解 ABA 的本質

當 T1 喚醒並嘗試執行 CAS 時，它僅僅比對了 head == A。 在 T1 的眼裡：「head 的記憶體位址依然是 A，代表沒有人動過這個 stack！」 但實際上，整個 Stack 經歷了 A → B → A 的劇烈變動：

1. B 早已被 T2 取走並可能已被 delete 釋放。
2. 節點 A 雖然位址回到頂端，但它的 next 已經從原先的 B 變成了 C。
3. T1 盲目地將 head 覆寫為暫存的 B，直接導致：
   • 資料遺失：節點 C 脫離了鏈結串列，發生記憶體洩漏。
   • 記憶體損毀（Use-After-Free）：head 指向了一個已經被 T2 釋放的無效位址 B，下一個呼叫 pop() 的執行緒解引用 head->next 時將立刻崩潰（Crash / Segment Fault）！

ABA 的核心教訓是：指標位址相等，絕不代表資料結構的內部拓撲與歷史狀態未曾改變！

四大安全記憶體回收機制（Safe Memory Reclamation）

為了解決 ABA 問題以及多執行緒並行釋放節點時的 Use-After-Free，學界與工業界發展出了四種主流機制。在深入細節前，我們必須先釐清一條核心界線：Tagged Pointer 與後三種 SMR 機制的防護目標有著本質區別：

• Tagged Pointer：本質是「狀態變更偵測協定」。它透過版本號偵測指標位址相同時的拓撲演變，但計數器仍有溢位循環（Wraparound）的理論可能，且它完全無法防護節點的解引用生命週期。
• Hazard Pointer / EBR / RCU：屬於真正的「安全記憶體回收（SMR）協定」。它們的主要目標是確保「只要有任何讀者可能解引用某個節點，該節點的物理記憶體就絕不會被釋放」。在工程實踐中，這直接消除了最常見的 ABA 根源（即節點被釋放後遭記憶體配置器原地重用）；但若演算法本身存在非記憶體重用引起的語意 ABA，仍需搭配版本號處理。

Tagged / Versioned Pointer（代數標記指標）

最直接的直覺是：既然只看指標會被騙，那我們在指標旁邊加上一個單調遞增的版本號（Tag / Counter）！

每次對 head 進行修改時，不僅更新指標，還將版本號加 1：

狀態演變：
(指標 A, 版本 1) ➜ (指標 B, 版本 2) ➜ (指標 C, 版本 3) ➜ (指標 A, 版本 4)

當 T1 甦醒嘗試執行 CAS 時：

• T1 預期的狀態是 (A, 1)。
• 目前 head 的實際狀態是 (A, 4)。
• CAS 判定兩者不相等，失敗！ABA 被成功攔截。

實作方式與限制

1. 雙倍寬度 CAS（DWCAS）：在 64-bit 系統上，指標佔 64-bit，計數器佔 64-bit，總共需要 128-bit 的原子 CAS（x86-64 的 CMPXCHG16B 或 AArch64 的 CASP）。需注意在部分平臺上 128-bit 原子操作可能非硬體原生無鎖（需透過 is_lock_free() 驗證），且在高頻競爭下版本計數器仍存在循環繞回（Wraparound）風險。
2. 指標壓縮（Pointer Packing）：在 64-bit 虛擬位址空間中，指標僅使用規範位址（Canonical Address）的低位元。在四級分頁（48-bit 虛擬位址）下，使用者空間位址的高 16 位元可被借用作為版本標記；若在五級分頁（57-bit 虛擬位址）架構下，則僅剩最高 7 位元可用。重大相容性限制：嵌入標記後的指標並非合法位址，解引用前必須先透過 bitmask 遮罩清除標記；且在 AArch64 架構上，硬體功能如頂部字節忽略（TBI）、記憶體標記擴展（MTE）與指標認證（PAC）皆會使用指標高位元，任意壓縮指標會破壞跨平台可攜性。
3. 重大盲點：Tagged Pointer 能偵測狀態改變，但完全無法保護記憶體生命週期！如果在 T1 讀取 old_head->next 的瞬間，節點 A 的記憶體已經被 T2 歸還給作業系統（munmap），T1 的讀取操作依然會直接觸發硬體分頁錯誤（Page Fault）崩潰！

Hazard Pointer（風險指標）

由 Maged Michael 於 2004 年提出（論文發表於 2002 年），已正式納入 C++26 標準庫（std::hazard_pointer）。

Hazard Pointer 的設計哲學是：讀者在存取某個節點前，先在全域公開的看板（Hazard Pointer Array）上宣告：「我正在閱讀指標 P，誰都不准釋放它！」

回收流程（Retire）

當某個執行緒成功將節點 P 從 Stack 中 pop 出來時，它不能立刻釋放 P。而是將 P 放入該執行緒私有的「待回收清單（Retired List）」。 當 Retired List 累積到一定閾值時，執行緒發動垃圾回收：

1. 掃描系統中所有執行緒目前登記的 Hazard Pointer 看板。
2. 如果節點 P 出現在任何一個看板上，說明仍有讀者正在讀取它，保留 P。
3. 如果沒有任何看板引用 P，說明所有讀者都已經知曉 P 已被移除，安全釋放 P（delete 或 free）。

• 優點：記憶體回收上限有嚴格保證，不會因個別執行緒暫停而導致記憶體無限制膨脹；對單一節點保護精確。
• 缺點：讀者存取節點時需寫入並重新驗證當前執行緒的 Hazard Slot，且回收端（Reclaimer）掃描所有執行緒看板時需負擔全域記憶體屏障開銷；此外走訪長鏈結串列時需要動態維護多個 Hazard Slot。

Epoch-Based Reclamation (EBR)

Epoch-Based Reclamation 是目前高效能無鎖資料結構（特別是 Rust 生態系，如標竿庫 crossbeam-epoch）最廣泛採用的方案。

EBR 不去逐一追蹤每一個節點，而是將整個系統的時間切分成 世代（Epoch，例如 0, 1, 2）：

EBR 的黃金準則

1. 任何執行緒在存取無鎖結構前，必須先呼叫 guard = epoch::pin()。這會將當前執行緒標記為活躍，並綁定在當前全域 Epoch。
2. 只要執行緒處於 pin() 狀態，它所看見的所有節點都保證不會被釋放。
3. 被移除的節點會被標記退役（Retire）並丟入當前 Epoch 的垃圾箱。
4. 推進世代：當系統發現所有曾活躍於前一世代的執行緒皆已離場（不再 pin 在較舊世代）時，全域 Epoch 即可安全推進至下一代。
5. 安全回收：處於 (E - 2) 世代的垃圾，保證沒有任何存活的讀者能看見，可以安全批次釋放！

• 優點：在 pin() 期間，讀取任何節點完全不需要任何原子寫入或硬體屏障，效能幾乎等同於讀取一般指標，非常適合走訪大規模樹狀結構或跳躍表（SkipList）。
• 缺點（致命傷）：若有任何一個執行緒呼叫了 pin() 後發生長久停頓（例如執行耗時計算、被作業系統搶佔或發生 I/O 阻塞），全域 Epoch 將無法推進。這會導致垃圾回收被無限期延宕，系統中累積的退役節點記憶體無界膨脹，最終引發 OOM（Out of Memory）！值得澄清的是，這只會卡住記憶體回收流程，其他執行緒在資料結構本身的 push/pop 運作依然能持續推進。

Read-Copy-Update (RCU)

RCU 是 Linux 核心中支撐百萬級網路轉發與檔案系統路由的核心機制，亦有使用者空間實作（Userspace RCU, liburcu）。此外，C++26 草案亦已正式納入 <rcu> 標頭檔支援。

RCU 特別針對 讀極多、寫極少（Read-Mostly）的資料結構設計：

• Reader：透過 rcu_read_lock() 進入臨界區，不執行任何鎖定、不修改任何共享計數器，直接讀取指標。讀取開銷近乎為零。
• Writer：不能就地修改資料。必須先複製一份舊資料副本，在副本上完成修改，接著透過原子指標替換（Release store）將入口切換到新版本。
• 寬限期（Grace Period）與非阻塞回呼：切換入口後，舊版本資料不能立刻釋放。Writer 可呼叫 synchronize_rcu() 阻塞等待，直到切換前就已進入臨界區的所有舊讀者全部執行完畢離場；或呼叫非阻塞的 call_rcu() 註冊回呼函式，待寬限期結束後由背景機制非同步安全銷毀舊版本資料。

四大記憶體回收機制架構對比

全部改成 SeqCst，也救不了生命週期

並行開發者常犯的一個危險認知是：「既然 memory ordering 這麼複雜，我乾脆把全專案的原子操作全部改成 std::memory_order_seq_cst 或 Ordering::SeqCst，這樣不就萬無一失了嗎？」

讓我們用一個最殘酷的時序交錯來擊碎這個幻想：

假設 head 指標全域採用 SeqCst，不使用任何 SMR 回收防護：

執行緒 1 (Reader)                     執行緒 2 (Reclaimer)
------------------------------------------------------------
Node* p = head.load(SeqCst);
// 此時 p 存放節點 A 的記憶體位址
                                      head.compare_exchange_strong(p, p->next, SeqCst);
                                      // 成功將 A 從鏈結中移除！
                                      delete p; // 釋放節點 A 的記憶體！

int val = p->data; // USE-AFTER-FREE 災難！
// 記憶體已被釋放，甚至已被作業系統收回，直接觸發 Segment Fault！

在這個時序中：

• 執行緒 1 的 load 是完全合法的 SeqCst。
• 執行緒 2 的 CAS 與 delete 也是完全合法的 SeqCst。
• 整個過程中沒有任何違反記憶體順序的情形發生！

然而，程式依然崩潰了。

這是因為：Memory Ordering 管的是變數寫入與觀察的可見性因果；而 SMR 管的是底層記憶體區塊實體是否依然存活合法！ 最強的記憶體順序也無法穿越空間，阻止作業系統將已經 free 掉的記憶體分頁標記為無效。

Lock-Free 程式碼審查三大檢驗清單

在審查任何無鎖演算法或資料結構時，請務必按照以下三大獨立維度逐一檢驗：

1. 狀態轉移正確性（State Transition & CAS）：
   • CAS 的條件是否足以代表系統真實狀態？
   • 是否存在指標重複配置造成的 ABA 偽成功？（是否需要 Tagged Pointer 或版本號？）
   • 失敗重試路徑是否會發生死迴圈或活鎖？
2. 可見性同步保證（Memory Ordering）：
   • 新節點在寫入原子變數對外發布前，內部資料是否使用 Release 確立因果？
   • 讀者在解引用指標前，是否使用 Acquire 與發布者建立 synchronizes-with？
   • CAS 的失敗 ordering 是否正確排除了 Release，並在需要重試解引用時維持了 Acquire？
3. 記憶體生命週期安全（Safe Memory Reclamation）：
   • 當指標被載入到執行緒暫存器後，到真正存取完畢期間，該記憶體區塊是否受到 HP 或 EBR 的保護？
   • 節點退役（Retire）後，是否有嚴格的寬限期或計數比對機制，確認所有並行讀者全數離場才執行物理釋放？

AI 在無鎖程式設計中的角色：輔助撰寫與形式驗證

隨著大型語言模型（LLM）與 AI 輔助程式設計工具（如 Claude Code）的普及，許多開發者開始嘗試讓 AI 撰寫或最佳化無鎖資料結構。在一般業務邏輯中，AI 能大幅提升產能；但在並行程式設計——尤其是弱記憶體模型與硬體原子原語的世界裡，AI 究竟是強大夥伴，還是潛伏的定時炸彈？

我們應該如何正確運用 AI 來輔助無鎖程式設計與程式碼驗證？

為什麼不能盲目信任 AI 寫出的 Lock-Free 程式碼？

無鎖程式設計本質上是極端交錯狀態下的離散數學。而現今的 LLM 是基於機率分佈預測下一個 token 的模型，擅長提取常見模式，但在面對非直覺的底層硬體特性時，極易產生隱蔽盲區：

• 幻覺與過度簡化（The Naive Loop Illusion）：當你要求 AI「用 C++ 寫一個無鎖 Stack」時，它幾乎千篇一律會給出教科書式的裸指標 CAS 迴圈。這段程式碼在單執行緒或低並發測試時完全正常，但 AI 往往對 ABA 問題隻字不提，更完全忽略了節點被 delete 後並行讀者引發的 Use-After-Free 崩潰。
• 記憶體順序的隨機性：在要求 AI 最佳化效能時，AI 經常在沒有精確因果依據的情況下，將 SeqCst 降級為 Relaxed，遺漏關鍵的 Acquire 讀取屏障或 Release 發布屏障；或者在 CAS 失敗分支上錯誤地配置了未定義的記憶體順序。
• 生命週期管理的缺失：實作一個健全的 Hazard Pointer 或 EBR 機制需要極度嚴謹的批次狀態機（包含執行緒註冊、看板掃描、世代三代推進等）。AI 往往只能生成空有函式骨架的虛構實作，在真實高並發壓力下瞬間被記憶體洩漏或懸置指標擊垮。

未經嚴格驗證的 AI 無鎖程式碼，最危險之處在於它看起來無比正確——編譯毫無警告，單元測試跑過一萬次也全數通過，卻在生產環境的 ARM64 伺服器連續運行數天後偶然觸發非法記憶體存取。

AI 的真實價值：作為對抗性審查員（Adversarial Reviewer）

既然不能讓 AI 閉眼裸寫核心無鎖邏輯，AI 的真正威力該如何發揮？答案是翻轉角色：不要讓 AI 當「架構師」，而是讓它擔任「對抗性質疑者」（Red Teaming Reviewer）。

人類工程師在審查自己撰寫的並行程式碼時，極容易陷入思維定勢（Confirmation Bias），預設執行緒會照著自己構想的理想順序前進。而 AI 沒有這種心理負擔，只要給予正確的約束，它能高效扮演挑錯的黑客角色。

提示詞設計策略：逼問邊界交錯

在請 AI 審查人類撰寫的無鎖程式碼時，避免使用「這段程式碼有沒有問題？」這種寬泛提問，而應當給予明確的底層架構約束：

針對弱記憶體模型的審查 Prompt 範例：
「請扮演資深並行系統核心工程師。審查以下 C++20 無鎖佇列的 pop() 實作。請特別假設運行於 ARM64 架構（具備 Store Buffer 與弱記憶體順序）：

1. 請檢查 head.load 與後續存取內部欄位之間，是否存在任何指令重排（Reordering）可能讀取到未初始化的資料？
2. 請構造一個精確的雙執行緒交錯時序（Interleaving trace），證明在特定的 CAS 失敗重試路徑上，是否可能發生 ABA 或存取已被釋放的記憶體？
3. 列出所有你認為可以進一步降級或必須升級的 std::memory_order，並嚴格給出因果依據。」

在這種對抗性約束下，AI 能極其迅速地指出人類肉眼容易漏看的分支細節，例如「CAS 失敗時 expected 更新與下一次重試讀取之間的屏障漏洞」。

終極閉環：AI 結合符號模型檢查（Formal Verification）

無論是人類專家還是 AI 審查，本質上都依賴經驗推演，無法窮舉龐大的並行交錯空間。要在工程上獲得真正的數學級確定性，必須將 AI 融入形式化驗證工具鏈（Formal Verification Toolchain）：

讓 AI 生成 Loom 與 GenMC 形式測試 Harness

撰寫形式化測試套件（如 Rust 的 loom 或 C++ 的 GenMC）相當繁瑣，需將所有原生型別替換為模型檢查器的特定原語。這恰好是 AI 的絕佳施展場域：

• Prompting 任務：「將以下這段生產級 Treiber Stack 的 Rust 實作，改寫為 loom 模型測試案例。使用 loom::sync::atomic 與 loom::thread，設定 2 個執行緒同時進行並行 push 與 pop，驗證是否滿足 LIFO 屬性與記憶體無外洩。」
• AI 能在數秒內生成規範的驗證環境，讓模型檢查器窮舉成千上萬種合法執行緒排程。

讓 AI 解讀反例追蹤日誌（Counterexample Trace）

當模型檢查器發現錯誤時，輸出的反例日誌往往龐大無比，列出數十個排程步驟與記憶體存取歷史。人類工程師需要花費數小時追蹤究竟是哪一個執行緒的哪一行指令觸發了狀態不一致。

此時將反例日誌餵給 AI：

「這是在執行 GenMC 模型檢查時回報的失敗日誌。請追蹤 Execution Graph，指出在第幾個 step 時發生了哪兩個記憶體存取的因果斷裂？是哪一行程式碼的 memory ordering 不足以建立 synchronizes-with？」

AI 具備強大的符號模式匹配能力，能精準從數百行交錯記錄中萃取出關鍵的因果漏洞，並給予精準的修復建議。

透過「人類定架構 ➔ AI 擬推演並編寫測試模型 ➔ 符號檢查器嚴密證明 ➔ AI 解讀反例日誌」的閉環體系，我們才能真正將 AI 的敏捷性與形式驗證的數學嚴謹性結合，打造出堅不可摧的生產級無鎖系統。

結語：何時該用 Lock-Free？

無鎖資料結構擁有極致的吞吐潛力與避免優先權反轉（Priority Inversion）的優雅特質，但它的實作代價無比高昂。每一行看似平凡的指標操作背後，都牽動著 CPU 管線排空、快取一致性廣播、ABA 防護與記憶體延後回收的複雜協同。

在工程實踐中，我們應當抱持審慎客觀的態度：

• 95% 的業務場景：優先使用現代作業系統高度最佳化的標準鎖（如基於 Futex 的 std::mutex 或 Rust 的 parking_lot::Mutex）。現代互斥鎖在無競爭情況下僅是一次輕量的原子 CAS，開銷僅數十奈秒，且心智負擔極低。
• 高頻交易、核心驅動與底層基礎設施：在極度要求低延遲、不可容忍鎖定阻塞（如即時音訊處理、高並發網路事件循環 Reactor）的關鍵路徑上，投入精力設計並驗證 Lock-Free 結構。
• 站在巨人的肩膀上：若需要使用無鎖結構，盡量選用經過工業級形式化驗證（如 TLA+）與龐大測試套件（如 ThreadSanitizer、Loom）錘鍊的成熟庫（如 Rust 的 crossbeam，C++ 的 Folly 或 Intel TBB），切忌在未經深思熟慮前自行在生產環境手寫無鎖記憶體回收器。

透過這兩篇文章的梳理，我們從底層硬體快取與記憶體模型的微觀世界，一路跨越至無鎖拓撲與安全記憶體回收的宏觀架構。並行程式設計雖然充滿挑戰，但只要掌握了因果順序與生命週期的雙重視角，看似詭譎多變的多執行緒世界，終將呈現出清晰嚴謹的工程之美。