無鎖資料結構：包含 C++、Java 和 .NET 範例的完整指南

互斥鎖很簡單。你鎖定它，修改共享狀態，然後解鎖。每個想要訪問的執行緒都按順序等待。問題在於“按順序等待”，在高核心數和高吞吐量的情況下，這種串行化會成為效能瓶頸。持有鎖的執行緒可能被搶佔，導致所有其他執行緒空閒。優先權反轉會導致低優先權執行緒阻塞高優先權執行緒。在每秒處理數百萬次操作、跨越數十個核心的系統中，互斥鎖爭用不僅會降低速度，還會嚴重影響吞吐量。

無鎖資料結構用原子操作取代了互斥。它們並非防止衝突，而是容忍衝突並從中恢復。執行緒在比較和交換操作失敗後會使用更新後的狀態重試。任何線程都不會阻塞其他線程。至少總是有一個線程在繼續執行。其結果是：在高競爭情況下吞吐量顯著提高，延遲可預測且無擁塞效應，並且從設計上消除了死鎖和優先反轉。代價是實現複雜度增加：ABA 問題、記憶體回收冒險、偽共享以及微妙的記憶體排序要求等陷阱在基於鎖定的程式碼中並不存在。本文將透過具體程式碼範例來講解所有這些問題。

無鎖、無等待、互斥鎖：該用哪一種？

在選擇實現方案之前，正確的問題是系統實際上需要哪個進度保證。這三種模式在線程競爭時所承諾的進度保證有所不同。

型號	進度保證	典型潛伏期	複雜	最適合
基於互斥鎖/鎖	阻塞，線程等待	爭執中難以預測	低	低競爭共享狀態，簡單的正確性要求
無鎖	系統範圍內，至少有一個執行緒正在推進。	競爭激烈	高	高吞吐量佇列、堆疊、計數器
無需等待	每個線程都在限定的步數內完成。	有界最壞情況	很高	即時系統、安全關鍵型系統、嚴格的延遲服務等級協議
無障礙	單人進度，僅在無人幹擾的情況下進行	低無爭議	媒材	事務性記憶原型、研究背景

對於高並發生產系統而言，無鎖實際上是預設選擇。 Michael-Scott 佇列、Treiber 堆疊以及大多數生產級 MPMC 環形緩衝區都採用了無鎖機制。在極端競爭情況下，單一執行緒可能會出現飢餓現象，但整個系統仍能正常運作。

無等待演算法保證每個執行緒的進度有界，但需要更複雜的演算法。雖然存在通用構造，但開銷很高。無等待演算法適用於硬實時場景，在這些場景中，尾延遲比平均吞吐量更重要。

無阻礙性很少直接用於生產環境。它出現在一些事務記憶體實作中，並在證明演算法正確性時作為墊腳石。

對於大多數高並發系統：當競爭較少且正確性要求不高時使用互斥鎖，當競爭下的吞吐量很重要時使用無鎖，僅當最壞情況下的每線程延遲是硬性要求時才使用無等待。

什麼是無鎖資料結構？

如果一個資料結構能夠保證，無論其他執行緒正在做什麼或如何調度，在其上操作的所有執行緒中至少有一個執行緒能夠在有限的步驟內完成操作，那麼這個資料結構就是無鎖的。這個形式化的定義蘊含著一個明確的結論：任何無鎖演算法都不會發生死鎖。即使一個執行緒停止、掛起或運行緩慢，其他執行緒仍然可以繼續執行。

此機制是原子操作，即作為一個不可分割的單元執行的 CPU 指令。通用原語是比較交換（CAS）：

CAS(location, expected, new_value):
  if *location == expected:
    *location = new_value
    return true
  else:
    return false  // someone else changed it first

CAS 在硬體層面是原子操作。在 x86 架構上，它是 CMPXCHG 指令。在 ARM 架構上，它是透過以下方式實現的： LDXR/STXR （載入獨佔/儲存獨佔），這是 LL/SC（載入連結/儲存條件）變體。線程讀取一個值，計算一個新值，並且僅在在此期間沒有其他線程更改該值時才使用 CAS 安裝它。如果 CAS 失敗，則執行緒將使用新值重試。

在 C++11 及更高版本中，這可以透過以下方式公開： std::atomic:

CPP

#include <atomic>

// Atomic increment using CAS loop
void atomic_add(std::atomic<int>& counter, int delta) {
    int expected = counter.load(std::memory_order_relaxed);
    while (!counter.compare_exchange_weak(
        expected,
        expected + delta,
        std::memory_order_release,
        std::memory_order_relaxed))
    {
        // expected is updated on failure -- retry with fresh value
    }
}

compare_exchange_weak 是 CAS 原語。失敗時會更新 expected 自動更新為目前值，使重試循環符合慣例。

ABA問題：無鎖系統最危險的陷阱

ABA問題是無鎖定編程中最反直覺的正確性風險。 CAS會在安裝新值之前檢查記憶體位置是否仍包含預期值。它無法偵測到在讀取操作和CAS執行操作之間，該值是否已更改過。該位置看起來仍然像原始值，但係統的底層狀態已經發生了CAS無法察覺的變化。

場景逐步詳解

考慮使用單一指標的無鎖棧 top:

1. 線程 A 內容如下： top = Node1Node1 的下一個指標指向 Node2。
2. 線程 A 在完成彈出操作之前被搶佔。
3. 線程 B 彈出 Node1（top 變成 Node2），然後彈出 Node2（top 變成 null）。
4. 線程 B 推送了一個新節點，恰好分配在與 Node1 相同的記憶體位址（這在空閒清單分配器中很常見）。 Top = Node1（相同的指針，不同的內容）。
5. 線程 A 恢復運行。其 CAS 檢測到 top == Node1 （期望值）成功，並設定 top = Node2但是Node2已經被釋放了。糟糕。

ABA問題在不同的資料類型中表現不同：

• 堆CAS 操作成功，但安裝了一個過時的 next 指針，導致釋放後使用。
• 隊列頭部或尾部指針看起來沒有變化，但結構已改變。
• 鍊錶節點看似仍在原位，但已被移除並重新分配。

LL/SC 是否能避免 ABA 問題？

是的，LL/SC（載入連結/儲存條件）比CAS提供了更強的語義，並且自然地避免了ABA。 LL將載入的記憶體位址標記為「已連結」。如果自LL之後對該位址進行了任何儲存操作，即使值已恢復到其原始狀態，SC操作也會失敗。修改歷史是在硬體層面追蹤的，而不僅僅是當前值。

然而，在實際硬體上實現 LL/SC 存在一些實際限制。在 ARM 和 POWER 架構上，即使沒有衝突（例如上下文切換、快取驅逐），也可能出現虛假的 LL/SC 故障。程式碼必須考慮即使沒有實際衝突也會發生重試循環的情況。在 x86 架構上，沒有原生的 LL/SC；CAS 是硬體原語。對於 x86 程式碼，必須在軟體層面防止 ABA 故障。

修復ABA：三種方法

1. 版本計數器（帶標籤的指針）

將版本計數器打包到與指標相同的原子字中。每次成功的 CAS 操作都會增加計數器。即使指標返回到其原始值，計數器也會發生變化：

CPP

#include <atomic>
#include <cstdint>

struct TaggedPtr {
    uintptr_t ptr : 48;  // pointer (48-bit virtual address space)
    uintptr_t tag : 16;  // version counter
};

std::atomic<TaggedPtr> top;

bool cas_with_tag(std::atomic<TaggedPtr>& loc,
                  TaggedPtr expected,
                  void* new_ptr) {
    TaggedPtr desired = { (uintptr_t)new_ptr, expected.tag + 1 };
    return loc.compare_exchange_strong(expected, desired);
}

這是實務上的標準做法。 16 位元標籤在 65,536 次操作後會循環，理論上這是不安全的，但實際上對大多數系統來說已經足夠了，因為線程在同一位置連續 65,536 個 CAS 週期被搶佔的可能性極低。

2. 危險提示

每個執行緒維護著一小組“危險指標”，這些指標指向它目前正在存取的節點。在釋放任何節點之前，執行緒會檢查所有危險指標暫存器，以確認沒有其他執行緒正在存取該節點。出現在危險指標中的節點將被延遲執行，直到該指標被清除為止。

CPP

// Simplified hazard pointer pattern
thread_local void* hazard_ptr = nullptr;

void* safe_load(std::atomic<void*>& head) {
    void* ptr;
    do {
        ptr = head.load(std::memory_order_acquire);
        hazard_ptr = ptr;                          // announce we are using this
        // memory fence ensures announcement is visible before validation
        std::atomic_thread_fence(std::memory_order_seq_cst);
    } while (ptr != head.load(std::memory_order_acquire)); // validate still valid
    return ptr;
}

void safe_release() {
    hazard_ptr = nullptr;
}

危險指針會阻止記憶體回收等級的 ABA：只要有任何執行緒持有指向某個節點的危險指針，該節點就無法被重複使用。這需要在釋放記憶體之前掃描所有執行緒的危險指針，從而增加與執行緒數成正比的開銷。

3. 基於時期的土地復墾（EBR）

線程在全域追蹤的“紀元”中運行。已退役的節點會按紀元進行緩衝，只有當所有執行緒都已運行到該節點退役的紀元之後才會釋放。與危險指標相比，EBR 更易於使用，且每次操作的開銷更低，但代價是在空閒期間記憶體增長有限但不可預測。

在Java中， AtomicStampedReference 透過將引用與整數戳配對，直接解決 ABA 問題：

Java的

import java.util.concurrent.atomic.AtomicStampedReference;

AtomicStampedReference<Node> top =
    new AtomicStampedReference<>(null, 0);

void push(Node newNode) {
    int[] stamp = new int[1];
    Node current;
    do {
        current = top.get(stamp);
        newNode.next = current;
    } while (!top.compareAndSet(current, newNode, stamp[0], stamp[0] + 1));
}

無鎖隊列實現

隊列是最常用的無鎖資料結構。典型的無鎖隊列是 Michael-Scott 隊列，它使用兩個指針（頭指針和尾指針）和一個哨兵節點來支援並發入隊和出隊操作。

SPSC隊列：以最小的同步實現最大的效能

單一生產者單一消費者佇列消除了所有寫-寫和讀-讀爭用。一個執行緒寫入佇列尾部；一個執行緒從佇列頭部讀取資料。生產者和消費者之間隻共享隊列頭部指針：

CPP

#include <atomic>
#include <array>

template<typename T, size_t Capacity>
class SPSCQueue {
    std::array<T, Capacity> buffer;
    alignas(64) std::atomic<size_t> head{0}; // consumer reads head
    alignas(64) std::atomic<size_t> tail{0}; // producer writes tail
    // alignas(64) puts each on a separate cache line -- prevents false sharing

public:
    bool push(const T& item) {
        size_t t = tail.load(std::memory_order_relaxed);
        size_t next = (t + 1) % Capacity;
        if (next == head.load(std::memory_order_acquire))
            return false; // full
        buffer[t] = item;
        tail.store(next, std::memory_order_release);
        return true;
    }

    bool pop(T& item) {
        size_t h = head.load(std::memory_order_relaxed);
        if (h == tail.load(std::memory_order_acquire))
            return false; // empty
        item = buffer[h];
        head.store((h + 1) % Capacity, std::memory_order_release);
        return true;
    }
};

这 alignas(64) 頭部和尾部的快取位置至關重要。如果沒有這種區分，兩者都會佔用相同快取行。每次寫入尾部都會觸發快取行失效，而讀取頭部的快取也會受到影響；反之亦然，這種偽共享機制會將原本獨立的操作串行化。

MPMC隊列：多生產者多消費者

完全並發的MPMC隊列要複雜得多。生產環境中的實作使用每個時隙一個序號來協調生產者和消費者，而無需使用鎖定：

CPP

#include <atomic>
#include <array>

template<typename T, size_t Capacity>
class MPMCQueue {
    struct Slot {
        std::atomic<size_t> sequence;
        T data;
    };

    alignas(64) std::array<Slot, Capacity> slots;
    alignas(64) std::atomic<size_t> enqueue_pos{0};
    alignas(64) std::atomic<size_t> dequeue_pos{0};

public:
    MPMCQueue() {
        for (size_t i = 0; i < Capacity; ++i)
            slots[i].sequence.store(i, std::memory_order_relaxed);
    }

    bool push(const T& item) {
        size_t pos = enqueue_pos.fetch_add(1, std::memory_order_relaxed);
        Slot& slot = slots[pos % Capacity];
        size_t seq = slot.sequence.load(std::memory_order_acquire);
        // wait for the slot to be ready for writing
        while (seq != pos) {
            seq = slot.sequence.load(std::memory_order_acquire);
        }
        slot.data = item;
        slot.sequence.store(pos + 1, std::memory_order_release);
        return true;
    }

    bool pop(T& item) {
        size_t pos = dequeue_pos.fetch_add(1, std::memory_order_relaxed);
        Slot& slot = slots[pos % Capacity];
        size_t seq = slot.sequence.load(std::memory_order_acquire);
        while (seq != pos + 1) {
            seq = slot.sequence.load(std::memory_order_acquire);
        }
        item = slot.data;
        slot.sequence.store(pos + Capacity, std::memory_order_release);
        return true;
    }
};

.NET 並發佇列：其內部運作原理

.NET 的 ConcurrentQueue<T> .NET 5+ 使用分段數組結構。每個段都是一個固定大小的數組，帶有頭索引和尾索引，由 .NET 管理。 Interlocked 操作（映射到底層硬體上的CAS）。段透過易失性連結連結。 _nextSegment 指針。入隊操作會將資料追加到目前尾段，當尾段鏈滿時，鏈會持續成長。出隊操作會從頭段讀取數據，並原子性地推進頭段索引。

關鍵的設計決策在於避免全球鎖定。生產者只在當前細分市場的尾部指數上競爭，消費者只在頭部指數上競爭。生產者之間並沒有直接的競爭關係。這使得… ConcurrentQueue<T> 對生產者-消費者管道來說非常有效率：

尖銳的

using System.Collections.Concurrent;
using System.Threading;

// .NET ConcurrentQueue -- lock-free, thread-safe, FIFO
var queue = new ConcurrentQueue<int>();

// Producer thread
var producer = Task.Run(() => {
    for (int i = 0; i < 1_000_000; i++)
        queue.Enqueue(i);
});

// Consumer thread
var consumer = Task.Run(() => {
    long sum = 0;
    while (!queue.IsEmpty || !producer.IsCompleted) {
        if (queue.TryDequeue(out int item))
            sum += item;
        else
            Thread.SpinWait(1);  // brief spin before retry
    }
    return sum;
});

await Task.WhenAll(producer, consumer);

無鎖定程式碼中的快取一致性和偽共享

在無鎖實作中，快取一致性是一個隱形的效能變數。當一個核心寫入某個記憶體位置時，包含該位置的整個 64 位元組快取行在所有其他核心的快取中都會失效。它們必須先取得更新後的快取行才能進行讀取。在頻繁進行原子更新的無鎖定程式碼中，這種快取行失效可能成為主要的效能開銷。

當兩個執行緒修改恰好共享相同快取行的不同變數時，就會發生偽共享。雖然兩個執行緒存取的並非相同的數據，但快取一致性協定會將整個快取行視為競爭數據。

CPP

// BAD: head and tail on the same cache line
struct BadQueue {
    std::atomic<size_t> head;   // bytes 0-7
    std::atomic<size_t> tail;   // bytes 8-15
    // both fit in the same 64-byte cache line
    // producer writing tail invalidates head in consumer's cache
};

// GOOD: head and tail on separate cache lines
struct GoodQueue {
    alignas(64) std::atomic<size_t> head;
    alignas(64) std::atomic<size_t> tail;
    // each on its own cache line -- no false sharing
};

MESI 協定（修改、獨佔、共用、無效）描述了 x86 CPU 如何協調快取行的所有權。當一個核心想要寫入一個與其他核心共享的快取位置（共享狀態）時，它必須廣播一個寫入請求，等待所有共享者的確認，然後轉換到修改狀態。在多路系統中，這種與快取一致性協定的往返過程需要 50 到 300 多個時​​脈週期。偽共享會將獨立的執行緒局部操作轉換為快取一致性流量，從而導致效能下降，而效能本應與核心數呈線性成長。

檢測虛假共享： 使用 perf stat -e cache-misses,L1-dcache-load-misses 在 Linux 系統上或 Windows 系統上的 Visual Studio CPU 效能分析器中，如果多執行緒程式能夠完全載入到快取中，卻出現較高的 L1 快取未命中率，這強烈表示有偽共享現象。

記憶體排序：為什麼 memory_order_relaxed 並不總是足夠

C + +中 std::atomic 操作會暴露 C++11 記憶體模型中所有可能的記憶體順序。選擇錯誤的記憶體順序是無鎖定程式碼中第二常見的錯誤，僅次於 ABA 問題。

CPP

// The five memory orderings and when each applies:

// relaxed: no synchronization, only atomicity
// Use for: counters where only the final value matters
counter.fetch_add(1, std::memory_order_relaxed);

// acquire: reads see all writes by threads that released this location
// Use for: reading shared state protected by a flag
if (ready.load(std::memory_order_acquire)) {
    use(data); // guaranteed to see all writes made before ready was set
}

// release: writes are visible to threads that acquire this location
// Use for: publishing shared state
data = compute();
ready.store(true, std::memory_order_release);

// acq_rel: acquire + release in one operation
// Use for: read-modify-write operations like CAS in the middle of a chain
node.compare_exchange_strong(expected, desired,
    std::memory_order_acq_rel,   // success
    std::memory_order_acquire);  // failure

// seq_cst: total order across all seq_cst operations, all cores
// Use for: when you need a global consistent view (but slowest)
flag.store(true, std::memory_order_seq_cst);

一個常見的錯誤：使用 relaxed 用於發布標誌。一個設定線程 ready = true - relaxed 排序並不能保證先前的寫入操作能夠成功。 data 其他閱讀該帖子的帖子可以看到 ready取得/發布這一對關係建立了作者和讀者之間的「先發生後發生」的關係。

Treiber棧：C++中的無鎖棧

Treiber堆疊是最簡單的非平凡無鎖資料結構。它使用單一寄存器上的CAS循環。 top 指針：

CPP

#include <atomic>

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

    std::atomic<Node*> top{nullptr};

public:
    void push(T data) {
        Node* node = new Node(std::move(data));
        node->next = top.load(std::memory_order_relaxed);
        while (!top.compare_exchange_weak(
            node->next,          // expected -- updated on failure
            node,                // desired
            std::memory_order_release,
            std::memory_order_relaxed))
        { /* retry */ }
    }

    bool pop(T& result) {
        Node* node = top.load(std::memory_order_acquire);
        while (node) {
            if (top.compare_exchange_weak(
                node,
                node->next,      // new top
                std::memory_order_acquire,
                std::memory_order_relaxed))
            {
                result = std::move(node->data);
                // WARNING: cannot free node here safely without hazard pointers or EBR
                // delete node; -- ABA hazard if another thread reads node->next
                return true;
            }
        }
        return false; // empty
    }
};

的評論 delete node 這一點至關重要：直接刪除節點就是前面提到的 ABA 風險。在生產環境的 Treiber 堆疊中，節點回收需要風險指標、基於紀元的回收機製或垃圾回收（Java/C# 會自動處理）。

Java 無鎖資料結構

Java 標準函式庫提供了生產級無鎖實作。 java.util.concurrent:

課程	結構體	進展	筆記
AtomicReference<T>	單值	無鎖	CAS 對物件引用
AtomicStampedReference<T>	價值 + 郵票	無鎖	透過版本計數器預防 ABA 故障
ConcurrentLinkedQueue<T>	麥可·斯科特隊列	無鎖	先進先出，無界
ConcurrentLinkedDeque<T>	無鎖雙端佇列	無鎖	兩端
LongAdder	計數器	無鎖	條紋狀高通量計數

LongAdder 這一點尤其值得注意。它並非使用一個在所有執行緒間相互競爭的原子計數器，而是維護一個條帶狀計數器數組，每個計數器由一部分執行緒存取。爭用分散在各個條帶上，而不是集中在一個位置。總和是惰性求和的。 sum()對於跨多個執行緒的高頻遞增操作， LongAdder 表現顯著優於 AtomicLong.incrementAndGet():

Java的

import java.util.concurrent.atomic.LongAdder;

// BAD for high-concurrency counting: all threads contend on one location
AtomicLong counter = new AtomicLong(0);
counter.incrementAndGet(); // single CAS -- all threads collide

// GOOD for high-concurrency counting: contention distributed across stripes
LongAdder adder = new LongAdder();
adder.increment();  // updates thread-local stripe -- minimal contention
long total = adder.sum(); // sum all stripes lazily

SMART TS XL 支援無鎖系統開發

無鎖程式碼是最難寫的程式碼之一。這類程式碼的缺陷具有不確定性，僅在特定的交錯執行條件下才會出現，而且通常只有在大規模生產環境中才會發生。靜態分析透過在程式碼執行前檢查其結構屬性來解決這個問題，而不是等待競態條件出現。

SMART TS XL 它分析並發程式碼的完整執行路徑，追蹤原子操作與其所保護的記憶體位置之間的關係。對於混合了無鎖程式碼、遺留元件或多語言架構的系統，它提供了單語言工具無法實現的跨邊界可見性：例如，無鎖 C++ 元件存取的共享記憶體區域與從中讀取資料的 Java 服務之間的關係，或者並發隊列如何流入基於 COBOL 的處理管道。

靜態程式碼分析功能可以識別與並發風險相關的模式：例如，缺少相應獲取語義的原子加載、失敗時未更新預期值的 CAS 循環，以及不同線程訪問的字段位於同一位置且未進行對齊填充的共享資料結​​構。影響分析功能可以追蹤下游元件對共享並發資料結構的依賴關係，以便在進行變更之前正確評估結構介面或回收策略的變更範圍。

對於企業系統而言，無鎖元件必須與傳統批次、訊息佇列中間件和現代服務層共存， SMART TS XL“ 依賴映射 提供了整個系統堆疊中並發資料路徑如何連接用不同語言編寫的元件的架構視圖。

當無鎖設計成為錯誤選擇時

無鎖結構並非總是優於互斥鎖。無鎖結構的優勢取決於工作負載的實際爭用情況。在執行緒數較少或爭用較低的情況下，實現良好的互斥鎖速度更快，因為它避免了原子重試循環和跨核心快取行失效帶來的開銷。

在以下情況下使用互斥鎖：

• 線程數低（低於 4-8）或爭用不頻繁
• 關鍵部分很長也很複雜（相對於該部分而言，無鎖循環的成本很高）。
• 正確性比吞吐量更重要，而且使用鎖可以使演算法更簡單。
• 該平台具有高效的基於 futex 的鎖定機制（Linux）。 pthread_mutex（Windows SRWLOCK）

無需鎖定即可使用的情況：

• 線程數高，爭用持續存在。
• 操作時間短（CAS循環開銷相對於操作而言很小）
• 阻塞是不可接受的（即時執行緒、中斷處理程序、訊號處理程序）。
• 與其他無鎖結構組合時，如果使用鎖，就會引入鎖順序依賴性。

何時使用無需等待：

• 無論其他線程如何，每個線程都必須在限定時間內完成。
• 對於需要嚴格即時或安全保障且不允許資源不足的情況，
• 該演算法可以設計成支援每個執行緒的有限步驟完成。

無鎖編程的原則不是在所有地方都選擇無鎖編程，而是在無鎖編程的特性（例如非阻塞進度、消除死鎖、容忍搶佔）與系統的實際需求相匹配的地方精確地選擇無鎖編程。