C# 高效能並發程式設計：無鎖佇列（Lock-Free Queue）Michael-Scott 演算法實作解析

前言：為何需要無鎖程式設計？

傳統多執行緒同步仰賴 lock（互斥鎖），雖簡單易懂，但在高競爭情境下會導致執行緒阻塞、上下文切換開銷大，甚至發生死鎖。無鎖程式設計透過硬體支援的原子操作（CAS, Compare-And-Swap），在不封鎖執行緒的前提下保證共享資料一致性，能顯著提升高併發場景的吞吐量。

核心原理：CAS 與 Interlocked.CompareExchange

.NET 提供 System.Threading.Interlocked.CompareExchange 實作 CAS 語意：

public static T CompareExchange(ref T location, T value, T comparand)

若 location 當前值等於 comparand，則原子性地更新為 value 並回傳原值；否則不更新並回傳當前值。呼叫端依據回傳值判斷是否成功，失敗則重試（自旋）。

無鎖演算法兩大特徵

1. 迴圈重試機制：更新失敗時持續迴圈嘗試，直到成功。
2. CAS 條件更新：每次更新前讀取共享變數快照，CAS 時比對快照，確保無其他執行緒竄改。

Michael-Scott 無鎖佇列實作

以下為單向佇列核心程式碼（節錄關鍵邏輯）：

public class ConcurrentLinkedQueue<T> {
    private class Node<K> {
        internal K Item;
        internal Node<K> Next;
        public Node(K item, Node<K> next) { Item = item; Next = next; }
    }

    private Node<T> _head, _tail;

    public ConcurrentLinkedQueue() {
        _head = new Node<T>(default(T), null);
        _tail = _head;
    }

    public bool IsEmpty => _head.Next == null;

    // 入佇列
    public void Enqueue(T item) {
        var newNode = new Node<T>(item, null);
        while (true) {
            var curTail = _tail;
            var residue = curTail.Next;

            if (curTail == _tail) { // 確認 tail 未被竄改
                if (residue == null) { // 尾節點尚無後續
                    // 嘗試將新節點接在尾端
                    if (Interlocked.CompareExchange(ref curTail.Next, newNode, residue) == residue) {
                        // 成功則嘗試推進 tail 指標
                        Interlocked.CompareExchange(ref _tail, newNode, curTail);
                        return;
                    }
                } else {
                    // 協助其他執行緒推進 tail（消除中間狀態）
                    Interlocked.CompareExchange(ref _tail, residue, curTail);
                }
            }
        }
    }

    // 出佇列
    public bool TryDequeue(out T result) {
        Node<T> curHead, curTail, next;
        do {
            curHead = _head;
            curTail = _tail;
            next = curHead.Next;

            if (curHead == _head) {
                if (next == null) { // 佇列為空
                    result = default(T);
                    return false;
                }
                if (curHead == curTail) { // 僅有一個節點正在入佇中
                    // 協助推進 tail
                    Interlocked.CompareExchange(ref _tail, next, curTail);
                } else {
                    // 先取值再 CAS 更新 head，避免 ABA 問題
                    result = next.Item;
                    if (Interlocked.CompareExchange(ref _head, next, curHead) == curHead)
                        break;
                }
            }
        } while (true);
        return true;
    }
}

關鍵設計細節解析

1. 偽頭節點

佇列初始化建立一個不存放資料的偽頭節點，_head 與 _tail 初始均指向它。這簡化邊界條件：空佇列時 _head.Next == null。

2. 入佇列「協助機制」

當發現 curTail.Next != null 表示有其他執行緒已完成節點連結但尚未更新 _tail，目前執行緒主動協助推進 _tail，避免殘留中間狀態阻塞後續操作。

3. 出佇列 ABA 問題防範

取值 result = next.Item 必須在 CAS(_head, next, curHead) 之前，確保節點未被回收再利用。此處採用偽頭節點配合單向鏈表，天然緩解 ABA 風險（實務中高併發長時間運行仍建議加上標記計數器或 Hazard Pointers）。

效能基準測試（雙核環境）

• 輕/中度競爭：無鎖佇列吞吐率遠超 lock 版本。
• 極高競爭（>100 執行緒/核心）：lock 因阻塞釋放 CPU 優勢反超無鎖自旋；可引入 Thread.SpinWait 緩解。
• 穩定性：測試中 lock 曾出現類死鎖現象，無鎖版本零事故。
• 核心數擴展性：核心數越多，鎖競爭開銷指數級增長，無鎖優勢愈發明顯。

適用場景與建議

• 高併發、低延遲、多核心環境（如即時交易系統、遊戲伺服器、高頻資料管線）。
• 單機單程序內部共享資料結構；跨程序/分散式場景需搭配其他機制。
• .NET Core / .NET 5+ 內建 System.Collections.Concurrent.ConcurrentQueue<T> 已高度優化，生產環境優先使用標準庫，自行實作僅供教學或極致調優。