無鎖程式設計介紹

原文位址：http://preshing.com/20120612/an-introduction-to-lock-free-programming

文章目錄

• 無鎖程式設計是什麼
• 無鎖程式設計技術
• • 原子的 Read-Modify-Write 操作
  • Compare-And-Swap 循環
  • 順序一緻性
  • 記憶體保序
  • 不同的處理器有不同的記憶體模型
• 參考文獻

無鎖程式設計是一項挑戰，不僅僅是因為自身的複雜性所緻，還與初次探索該課題的困難性相關。

我很幸運，我第一次介紹無鎖 (lock-free，也稱為 lockless) 程式設計，是 Bruce Dawson 的出色而全面的白皮書《無鎖程式設計注意事項》。和大多數人一樣，我有機會将 Bruce 的建議用到無鎖代碼的編寫和調試中，例如在 Xbox360 平台上的開發。

從那時起，出現了很多好的素材，包括抽象的理論、執行個體的正确性的證明以及一些硬體的細節。我在腳注中會有一些引用。有時，不同來源的資料是不同的。例如，一些材料假設了順序一緻性，這就回避了困擾 C/C++ 無鎖代碼的記憶體排序問題。新的 C++11 的原子操作庫标準提供了新的工具，這會挑戰現有的無鎖算法。

在本文中，我會重新介紹無鎖程式設計，首先對其進行定義，然後從衆多資訊提煉出少數重要的概念。我會使用流程圖來展示各個概念間的關系，然後我們将涉足一些細節問題。任何學習無鎖程式設計的程式員，都應該能了解如何在多線程代碼中使用互斥量，了解一些進階同步機制，例如信号和事件等。

無鎖程式設計是什麼

人們常常将無鎖程式設計描述成不使用 互斥量（Mutex，一種鎖的機制）的程式。這個說法是對的，但并不全面。被廣泛接受的基于學術報告的定義含有更廣義的含義。從本質上來說，無鎖程式設計是描述一些代碼的一個屬性，它并沒有過多描述代碼是如何寫的。

基本上，你的代碼的一些部分符合如下條件，即可被認為是無鎖的。反之，如果你的代碼一些部分不符合下述條件，則被認為不是無鎖的。

在該場景中，“無鎖” 中的 “鎖” 并不是直接指互斥量，而是指 “鎖定” 整個應用的所有可能的方式，不論是死鎖、活鎖甚至可能是線程排程的方式都是你最大的敵人。最後一點聽起來似乎很好笑，卻是至關重要的一點。首先，共享互斥量被排除了，因為一旦一個線程擷取了互斥量，你最大的敵人将永遠無法再次排程那個線程。當然，真實的作業系統不是那樣做的，隻是我們是如此定義的。

下面這個簡單的例子沒有使用互斥量，但仍然不是無鎖的。X初始值為0。作為練習題，請考慮如何排程兩個線程，才能使得兩個都不退出循環？

while (X == 0)
{
    X = 1 - X;
}
           

沒人期待整個大型的應用是完全無鎖的。通常，我們可以從整個代碼庫中識别出一系列無鎖操作。例如，在一個無鎖隊列中有少許的無鎖操作，像push、pop，或許還有isEmpty等等。

《多處理器程式設計藝術》的作者Herlihy和Shavit，趨向于将這些操作表達成類的方法，并提出了一個簡單的無鎖的定義（第150頁）：“在一個無限的執行過程中，會不停地有調用結束”。換句話說，程式能不斷地調用這些無鎖操作的同時，許多調用的也是不斷地在完成。從算法上來說，在這些操作的執行過程中，系統鎖定是不可能的。

無鎖程式設計的一個重要的特性就是，如果挂起一個單獨的線程，不會阻礙其它線程執行。作為一組線程，他們使用特定的無鎖操作來完成這個特性。這揭示了無鎖程式設計在中斷處理程式和實時系統方面的價值。因為在這些情況下，特定的操作必須在特定的時間内完成，不論程式的狀态如何。

最後的精确描述：設計用于阻塞的操作不會影響算法運作，這種代碼才是無鎖的。例如在無鎖隊列的操作中，當隊列為空時，隊列的彈出操作會有意地阻塞。但其它的代碼路徑仍然被認為是無鎖的。

無鎖程式設計技術

事實證明，當你試圖滿足無鎖程式設計的無阻塞條件時，會出現一系列技術：原子操作、記憶體屏障、避免ABA問題，等等。從這裡開始，事情很快變得棘手了。

那麼，這些技術間是如何互相關聯的？我将它們放在下面的流程圖中進行展示。下文将逐一闡述。

原子的 Read-Modify-Write 操作

所謂原子操作是指，通過一種看起來不可分割的方式來操作記憶體：線程無法看到原子操作的中間過程。在現代的處理器上，有很多操作本身就是的原子的。例如，對簡單類型的對齊的讀和寫通常就是原子的。

Read-Modify-Write（RMW）操作更進一步，它允許你按照原子的方式，操作更複雜的事務。當一個無鎖的算法必須支援多個寫入者時，原子操作會尤其有用，因為多個線程試圖在同一個位址上進行RMW時，它們會按“一次一個”的方式排隊執行這些操作。我已經在我的部落格中涉及了RMW操作了，如實作 輕量級互斥量、遞歸互斥量 和 輕量級日志系統。

RMW 操作的例子包括：Win32上 的

_InterlockedIncrement

，iOS 上的

OSAtomicAdd32

以及 C++11 中的

std::atomic<int>::fetch_add

。需要注意的是，C++11 的原子标準不保證其在每個平台上的實作都是無鎖的，是以最好要清楚你的平台和工具鍊的能力。你可以調用

std::atomic<>::is_lock_free

來确認一下。

不同的 CPU 系列支援 RMW 的方式也是不同的。例如，PowerPC 和 ARM 提供

load-link/store-conditional

指令，這實際上是允許你實作你自定義的底層 RMW 操作。常用的 RMW 操作就已經足夠了。

如上面流程圖所述，即使在單處理器系統上，原子的 RMW 操作也是無鎖程式設計的必要部分。沒有原子性的話，一個線程的事務會被中途打斷，這可能會導緻一個錯誤的狀态。

Compare-And-Swap 循環

或許，最常讨論的 RMW 操作是 compare-and-swap (CAS)。在Win32上，CAS 是通過如

_InterlockedCompareExchange

等一系列指令來提供的。通常，程式員會在一個事務中使用 CAS 循環。這個模式通常包括：複制一個共享的變量至本地變量，做一些特定的工作（改動），再試圖使用 CAS 釋出這些改動。

void LockFreeQueue::push(Node* newHead)
{
    for (;;)
    {
        // Copy a shared variable (m_Head) to a local.
        Node* oldHead = m_Head;

        // Do some speculative work, not yet visible to other threads.
        newHead->next = oldHead;

        // Next, attempt to publish our changes to the shared variable.
        // If the shared variable hasn't changed, the CAS succeeds and we return.
        // Otherwise, repeat.
        if (_InterlockedCompareExchange(&m_Head, newHead, oldHead) == oldHead)
            return;
    }
}
           

這樣的循環仍然有資格作為無鎖的，因為如果一個線程檢測失敗，意味着有其它線程成功—盡管某些架構提供一個 較弱的CAS變種 。無論何時實作一個CAS循環，都必須十分小心地避免 ABA 問題。

順序一緻性

順序一緻性（Sequential consistency）意味着，所有線程就記憶體操作的順序達成一緻。這個順序是和操作在程式源代碼中的順序是一緻的。在順序一緻性的要求下，像我 另一篇文章 示範的那樣的有意的記憶體重排序不再可能了。

一種實作順序一緻性的簡單（但顯然不切實際）的方法是禁用編譯器優化，并強制所有線程在單個處理器上運作。 即使線程在任意時間被搶占和排程，處理器也永遠不會看到自己的記憶體影響。

某些程式設計語言甚至可以為在多處理器環境中運作的優化代碼提供順序一緻性。 在C ++ 11中，可以将所有共享變量聲明為具有預設記憶體排序限制的C ++ 11原子類型。 在Java中，您可以将所有共享變量标記為

volatile

。下面是 我之前一個案例 用C++11風格重寫的例子。

std::atomic X(0), Y(0);
int r1, r2;
 
void thread1()
{
    X.store(1);
    r1 = Y.load();
}
 
void thread2()
{
    Y.store(1);
    r2 = X.load();
}
           

因為 C ++ 11 原子類型保證順序一緻性，是以結果 r1 = r2 = 0 是不可能的。 為此，編譯器會在背景輸出其他指令——通常是 記憶體圍欄 和/或 RMW 操作。 與程式員直接處理記憶體排序的指令相比，那些額外的指令可能會使實作效率降低。

記憶體保序

正如前面流程圖所建議的那樣，任何時候做多核（或者任何對稱多處理器）的無鎖程式設計，如果你的環境不能保證順序一緻性，你都必須考慮如何來防止 記憶體重新排序。

在當今的架構中，增強記憶體保序性的工具通常分為三類，它們既防止 編譯器重新排序 又防止 處理器重新排序：

• 一個輕型的同步或屏障指令，以後的文章會詳述；
• 一個完全的記憶體屏障指令，如之前所述；
• 提供擷取或釋放語義的記憶體操作。

擷取語義可防止按照程式順序對其進行操作的記憶體重新排序，而釋放語義則可防止對其進行操作前的記憶體重新排序。 這些語義尤其适用于存在生産者/消費者關系的情況，其中一個線程釋出一些資訊，而另一個線程讀取它。 在以後的文章中，我還将對此進行更多讨論。

不同的處理器有不同的記憶體模型

在記憶體重新排序方面，不同的CPU系列具有不同的習慣。 每個CPU供應商都記錄了這些規則，并嚴格遵循了硬體。 例如，PowerPC 和 ARM 處理器可以相對于指令本身更改記憶體存儲的順序，但是通常，英特爾和 AMD 的 x86 / 64 系列處理器不會。 我們說以前的處理器具有更寬松的記憶體模型。

有人傾向于将這些特定于平台的細節抽象出來，尤其是C ++ 11為我們提供了編寫可移植的無鎖代碼的标準方法。 但是目前，我認為大多數無鎖程式員至少對平台差異有所了解。 如果需要記住一個關鍵的差別，那就是在x86 / 64指令級别上，每次從記憶體中加載都會擷取語義，并且每次存儲到記憶體都将提供釋放語義–至少對于非SSE指令和非寫組合記憶體 。 是以，過去通常會編寫可在x86 / 64上運作但 在其他處理器上無法運作 的無鎖代碼。

如果你對硬體如何處理記憶體重新排序的細節感興趣，我建議看看《Is Pararllel Programming Hard》的附錄C。無論如何，請記住，由于編譯器對指令的重新排序，也會發生記憶體重新排序。

在這篇文章中，我沒有對無鎖程式設計的實際方面說太多，例如：什麼時候做？ 我們真正需要多少？ 我也沒有提到驗證無鎖算法的重要性。 盡管如此，我希望對某些讀者來說，本入門對無鎖概念有基本的了解，是以您可以繼續閱讀其他内容而不會感到困惑。

參考文獻

[1] 無鎖程式設計注意事項

[2] Locks Aren’t Slow; Lock Contention Is

[3] 實作自己的輕量級互斥量

[4] 實作一個遞歸互斥量

[5] 一個輕量級記憶體日志系統