您现在的位置：程式碼之家 >> 編程語言 > >> .NET 網頁程式設計 >> 關於.NET

並發數據結構：迷人的原子操作與無鎖編程

編輯：關於.NET

隨著多核 CPU 成為主流，並行程式設計已躍升為熱門研究領域。要充分發揮多核/多路 CPU 的強大算力，通常採用多線程開發應用程式。然而，僅將工作簡單分配到多個線程遠遠不夠，還必須確保線程大部分時間都在執行任務，而非陷入等待工作或爭奪共享數據結構的鎖定之中。

傳統同步機制：鎖的代價

當多個線程訪問共享數據時，同步機制不可或缺。若缺乏協調，不僅無法實現真正的並行，更會引發毀滅性錯誤。在 .NET 與 D 語言中，標準同步手段分別為 lock 與 synchronized 關鍵字。它們在 Windows 下基於臨界區實現，Linux 下則使用互斥鎖。無論底層實現如何，核心均是強制互斥，確保持鎖線程對共享數據的獨占訪問權，並保證可見性。

簡言之，基於鎖的多線程編程中，任何可能導致競爭條件的共享數據操作，都必須包裝為原子操作（即不可中斷的連續步驟）。只要線程持有鎖，便無需擔心其他線程干擾。

鎖帶來的隱患

這聽起來似乎完美，但「為所欲為」的代價極高：

線程飢餓與優先級倒置：持鎖線程若執行耗時 I/O，其他線程只能干等；高優先級線程被低優先級線程阻塞，即為優先級倒置。
死鎖：線程 A 持鎖 1 等鎖 2，線程 B 持鎖 2 等鎖 1，雙方僵持不下。
競爭開銷：成千上萬線程同時爭鎖，同步競爭的高昂成本會大幅降低 CPU 吞吐量。

雖可用 volatile 變量以較低成本存儲共享數據，但其局限性較大（詳見《談談 volatile 變量》）。

線程安全計數器：鎖版本

以線程安全計數器為例，.NET 與 D 均在每個方法加鎖：

.NET 實現

public class ThreadSafeCounter
{
    private int value;
    private object obj = new Object();

    public int GetValue()
    {
        lock (obj) { return value; }
    }

    public int Increment()
    {
        lock (obj) { return ++value; }
    }

    public int Decrement()
    {
        lock (obj) { return --value; }
    }
}

D 語言實現

public class ThreadSafeCounter
{
    private int value;

    public synchronized int GetValue() { return value; }
    public synchronized int Increment() { return ++value; }
    public synchronized int Decrement() { return --value; }
}

邁入 Lock-Free 世界：CAS 原語

現代處理器廣泛提供 CAS（Compare-And-Swap）硬件指令（x86 對應 lock cmpxchg）。.NET 使用 Interlocked.CompareExchange，D 語言可用 tango.core.Atomic(T).storeIf 或 system.threading.Atomic.compareAndSwap。

CAS 原子地比較內存地址處的值與期望值，相等則替換為新值。以下為模擬邏輯（非性能特徵）：

.NET 模擬

public T CAS<T>(ref T value, T newValue, T equalTo) where T : class
{
    lock (obj)
    {
        if (value == equalTo) value = newValue;
        return value;
    }
}

D 模擬

public synchronized bool CAS(T)(ref T value, T newValue, T equalTo)
{
    static assert(IsIntegerType!(T) || IsPointerType!(T));
    if (value == equalTo) value = newValue;
    return value;
}

ABA 問題：CAS 讀取值 A，準備寫入時發現仍為 A，實際上中間可能發生 A→B→A 的變化。解決方案通常引入版本號或標記，如 Java 的 AtomicStampedReference。位寬越長，ABA 概率越低。

無鎖計數器實現

基於 CAS 的 Lock-Free 算法，線程無需等待鎖。CAS 成功或失敗均在可預期時間內完成，失敗時可重試。

.NET 版

public class CASCounter
{
    private int value;

    public int GetValue() { return value; }

    public int Increment()
    {
        int oldValue;
        do
        {
            oldValue = value;
        }
        while (Interlocked.CompareExchange(ref value, oldValue + 1, oldValue) != oldValue);
        return oldValue + 1;
    }
}

D 版

public class CASCounter
{
    private int value;

    public int getValue() { volatile return value; }

    public int increment()
    {
        int oldValue;
        do
        {
            oldValue = value;
        }
        while (!Atomic.CompareAndSwap(value, oldValue + 1, oldValue));
        return oldValue + 1;
    }
}

注意：D 版在 getValue 加 volatile，因 D 語言規範未定義內存模型，需額外保證緩存一致性；.NET 內存模型已保證原子操作維持緩存一致性。實際生產中可直接用 Interlocked.Increment，此處僅示範 CAS 思想。