C# 無鎖併發佇列實作：Michael-Scott 演算法與 Interlocked.CAS

無鎖程式設計核心

• 目標：不使用 Lock 保證共享資料一致性。
• 基石：CAS (Compare-And-Swap)，.NET 對應 Interlocked.CompareExchange。
• 兩大特徵：
  1. 迴圈重試：CAS 失敗則重試，直到成功。
  2. 使用原始值比較：確保更新期間無其他執行緒修改。
• 進階技巧：協助其他執行緒完成操作 (Helping)，提升整體吞吐量。

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;
    private Node<T> _tail;

    public ConcurrentLinkedQueue()
    {
        _head = new Node<T>(default, 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) // A: tail 尚無後續節點
                {
                    // C: 嘗試將新節點連接到 tail.Next
                    if (Interlocked.CompareExchange(ref curTail.Next, newNode, residue) == residue)
                    {
                        // D: 嘗試推進 tail 指標
                        Interlocked.CompareExchange(ref _tail, newNode, curTail);
                        return;
                    }
                }
                else // B: 發現 tail.Next 已有節點 (其他執行緒已完成 C 但未完成 D)
                {
                    // 協助其他執行緒完成 D
                    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) // 確認 head 未變
            {
                if (next == null) // 佇列為空
                {
                    result = default;
                    return false;
                }
                if (curHead == curTail) // 僅有虛擬頭節點，Enqueue 進行中
                {
                    // 協助推進 tail
                    Interlocked.CompareExchange(ref _tail, next, curTail);
                }
                else
                {
                    // 先取值再 CAS，避免 ABA 問題
                    result = next.Item;
                    if (Interlocked.CompareExchange(ref _head, next, curHead) == curHead)
                        break; // 成功推進 head
                }
            }
        } while (true);
        return true;
    }
}

效能測試結論 (雙核 CPU)

• 輕/中度爭用：無鎖版本大幅優於鎖版本。
• 極高爭用 (≥100 threads/CPU)：鎖版本因上下文切換釋放 CPU，反而較佳；無鎖版本進入忙碌等待 (Busy-wait) 佔用 CPU。可用 Thread.SpinWait 緩解。
• 無鎖版本無死鎖風險，鎖版本測試中出現類似死鎖現象。
• 核心數越多，鎖版本效率下降越明顯；無鎖版本擴展性優。