Lock-free 資料結構實戰：從 Treiber Stack、ABA 問題到安全記憶體回收

在上一篇 《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） 機制，接手原先由鎖保護的物件生命週期。

進度保證等級：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 操作將「比較目前值是否符合預期」與「寫入新數值」合併為不可分割的單一硬體原子指令：

如果目標記憶體目前的值等於 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！如果傳入 Release，編譯器將直接報錯或觸發未定義行為。

weak 與 strong 的本質差異

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

最佳實踐原則：在絕大多數 Lock-free 演算法中，CAS 本身就被包裹在一個 while 重試迴圈裡。此時一律優先使用 compare_exchange_weak。因為在弱架構（如 ARM64）上，weak 能直接映射到最精簡的單對 LL/SC 指令，免去 strong 為了防止虛假失敗所額外生成的硬體重試迴圈包裝。

經典實戰：Treiber Stack 雙語言實作

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

為了清晰剖析 CAS 狀態移轉與記憶體順序，我們先建立一個教學基準實作。此處遵循三個安全邊界假設（後續章節再解構如何透過 SMR 解除這些限制）：

1. 每個節點在 push 前由發起執行緒完全獨占。
2. 節點一旦進入 stack，其內部欄位不可並行修改。
3. 節點生命週期維持至所有執行緒完全 join 離場後，由擁有者統一回收（杜絕中間釋放引發的 Use-After-Free）。

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:
    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) {
            // 讀取下一個節點
            Node* next_node = old_head->next;

            // 步驟 2：CAS 嘗試將 head 移向 next_node
            // 成功：使用 acquire 語意確保讀取到最新拓撲。
            // 失敗：關鍵！失敗 ordering 必須也是 acquire！
            // 理由：若 CAS 失敗，old_head 會被更新為另一個執行緒剛 push 上去的新節點；
            // 下一輪迴圈會立刻執行 old_head->next，如果失敗用 relaxed，就會失去對新節點內容的同步保護！
            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：保證 TreiberStack 可以跨執行緒共享
unsafe impl<T: Send> Send for TreiberStack<T> {}
unsafe impl<T: Sync> 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 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 || s3.pop());
    let s4 = Arc::clone(&stack);
    let t4 = thread::spawn(move || s4.pop());

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

    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 / 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）。這要求硬體支援並提供正確的對齊。
2. 指標壓縮（Pointer Packing）：在現代 64-bit 虛擬位址空間中，指標實際上常見只使用低 48 位元（四級分頁為 48 位元，五級分頁則為 57 位元）。高 16 位元可以被借用來當作版本標記，封裝在單一 64-bit 整數內。
3. 重大盲點：Tagged Pointer 能偵測狀態改變，但完全無法保護記憶體生命週期！ 如果在 T1 讀取 old_head->next 的瞬間，節點 A 的記憶體已經被 T2 歸還給作業系統（munmap），T1 的讀取操作依然會直接觸發硬體分頁錯誤（Page Fault）崩潰！

Hazard Pointer（風險指標）

由 Maged Michael 於 2004 年提出，已正式納入 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 陣列並發出昂貴的 SeqCst 記憶體屏障；且走訪長鏈結串列時需要動態維護多個 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 時，全域 Epoch 就推進到下一代。
5. 安全回收：處於 (E - 2) 世代的垃圾，保證沒有任何存活的讀者能看見，可以安全批次釋放！

• 優點：在 pin() 期間，讀取任何節點完全不需要任何原子寫入或硬體屏障，效能幾乎等同於讀取一般指標，非常適合走訪大規模樹狀結構或跳躍表（SkipList）。
• 缺點（致命傷）：若有任何一個執行緒呼叫了 pin() 後發生長久停頓（例如執行耗時計算、被作業系統搶佔或發生 I/O 阻塞），全域 Epoch 將永遠無法推進，導致系統中所有執行緒累積的垃圾記憶體迅速暴增，引發 OOM（Out of Memory）！

Read-Copy-Update (RCU)

RCU 是 Linux 核心中支撐百萬級網路轉發與檔案系統路由的核心機制，亦有使用者空間實作（Userspace RCU, liburcu）。

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

• Reader：透過 rcu_read_lock() 進入臨界區，不執行任何鎖定、不修改任何共享計數器，直接讀取指標。讀取開銷近乎為零。
• Writer：不能就地修改資料。必須先複製一份舊資料副本，在副本上完成修改，接著透過原子指標替換（Release store）將入口切換到新版本。
• 寬限期（Grace Period）：切換入口後，舊版本資料不能立刻釋放。Writer 呼叫 synchronize_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），切忌在未經深思熟慮前自行在生產環境手寫無鎖記憶體回收器。

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