深入理解無鎖編程

hi，大夥好，今天介紹一下無鎖編程基礎知識，希望大家可以瞭解無鎖編程基本原理。

無鎖編程是一個挑戰，不僅因爲任務本身的複雜性，還因爲從一開始就很難深入瞭解這個主題，因爲該主題和底層技術（編譯器，CPU，內存）息息相關，需要深厚底層功底。

我學習無鎖編程是 Bruce Dawson 出色而全面的白皮書 Lockless Programming Considerations(無鎖編程的思考)。和許多技術一樣，需要將理論付諸實踐，在平臺上開發和調試無鎖代碼。

在這篇文章中，我想重新介紹無鎖編程，首先是定義它，然後將大部分信息提煉爲幾個關鍵概念。我將使用流程圖展示這些概念如何相互關聯，然後我們將深入研究細節。至少，任何從事無鎖編程的程序員都應該已經瞭解如何使用互斥鎖和其他高級同步對象（如信號量和事件）編寫正確的多線程代碼。

它是什麼？

人們通常將無鎖編程描述爲沒有互斥鎖的編程，互斥鎖也稱爲鎖。這是真的，但這只是故事的一部分。基於學術文獻的普遍接受的定義更廣泛一些。從本質上講，無鎖是一種用於描述某些代碼的屬性，而無需過多說明該代碼的實際編寫方式。

基本上，如果您的程序的某些部分滿足以下條件，那麼該部分可以理所當然地被認爲是無鎖的。相反，如果代碼的給定部分不滿足這些條件，則該部分不是無鎖的。

從這個意義上說，無鎖中的鎖並不直接指互斥鎖，而是指以某種方式 “鎖定” 整個應用程序的可能性，無論是死鎖、活鎖——甚至是由於由你最大的敵人。最後一點聽起來很有趣，但這是關鍵。共享互斥鎖被簡單地排除在外，因爲一旦一個線程獲得互斥鎖，您最大的敵人就再也不會調度該線程了。當然，真正的操作系統不是這樣工作的——我們只是定義術語。

這是一個不包含互斥鎖但仍然不是無鎖的操作的簡單示例。最初，X = 0。作爲讀者的練習，考慮如何以一種方式調度兩個線程，使得兩個線程都不退出循環。

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

沒有人期望大型應用程序是完全無鎖的。通常，我們從整個代碼庫中識別出一組特定的無鎖操作。例如，在一個無鎖隊列中，有可能是無鎖的操作，比如極少數的push，pop也許isEmpty等。

Herlihy & Shavit 是 The Art of Multiprocessor Programming（多處理器編程的藝術） 的作者，傾向於將此類操作表示爲類方法，並提供以下無鎖的簡潔定義：

“在無限執行中，某些方法調用會無限頻繁地結束” 

換句話說，只要程序能夠繼續調用那些無鎖操作，無論發生什麼，完成的調用次數都會不斷增加。在這些操作期間，系統在算法上不可能鎖定。

無鎖編程的一個重要結論是，如果您掛起單個線程，它永遠不會阻止其他線程作爲一個組通過它們自己的無鎖操作取得進展。這暗示了在編寫中斷處理程序和實時系統時無鎖編程的價值，其中某些任務必須在一定的時間限制內完成，無論程序的其餘部分處於什麼狀態。

最後一個說明：某些操作被設計爲阻塞的並不意味是這就不是 Lock-Free 的。例如，當隊列爲空時，隊列的彈出操作可能會故意阻塞。其餘的代碼路徑仍然可以被認爲是無鎖的。

無鎖編程技術

事實證明，當您嘗試滿足無鎖編程的非阻塞條件時，會出現一整套技術：原子操作、內存屏障、避免 ABA 問題，僅舉幾例。這就是事情很快變得邪惡的地方。

那麼這些技術如何相互關聯呢？爲了說明，我整理了以下流程圖。下面我將逐一詳述。

原子讀 - 修改 - 寫操作

原子操作是以一種看起來不可分割的方式操作內存的操作：沒有線程可以觀察到半完成的操作。在現代處理器上，許多操作已經是原子的。例如，簡單類型的對齊讀取和寫入通常是原子的。

讀 - 修改 - 寫 (RMW) 操作更進一步，允許您以原子方式執行更復雜的事務。當無鎖算法必須支持多個寫入器時，它們特別有用，因爲當多個線程在同一地址上嘗試 RMW 時，它們將有效地排成一行並一次執行這些操作。我已經在這篇博客中談到了 RMW 操作，例如實現輕量級互斥鎖、遞歸互斥鎖和輕量級日誌系統時。

RMW 操作的示例包括_InterlockedIncrementWin32、OSAtomicAdd32iOS 和 std::atomic::fetch_addC++11。請注意，C++11 原子標準並不能保證實現在每個平臺上都是無鎖的，因此最好了解您的平臺和工具鏈的功能。你可以使用 std::atomic<>::is_lock_free 確認一下。

不同的 CPU 系列以不同的方式支持 RMW。諸如 PowerPC 和 ARM 之類的處理器公開了 load-link/store-conditional）條件指令，這有效地允許您在低級別實現自己的 RMW 原語，儘管這並不常見。常見的 RMW 操作通常就足夠了。

如流程圖所示，即使在單處理器系統上，原子 RMW 也是無鎖編程的必要部分。如果沒有原子性，線程可能會在事務中途中斷，從而可能導致狀態不一致。

Compare-And-Swap Loops

也許最常討論的 RMW 操作是 compare-and-swap**(CAS)**。在 Win32 上，CAS 是通過一系列內在函數提供的，例如_InterlockedCompareExchange. 通常使用 CAS Loops 來完成對事務的原子處理：

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 問題。

順序一致性

順序一致性是指所有線程都同意內存操作發生的順序，並且該順序與程序源代碼中的操作順序一致。

實現順序一致性的一種簡單（但顯然不切實際）的方法是禁用編譯器優化並強制所有線程在單個處理器上運行。處理器永遠不會看到它自己的內存效果出問題，即使線程在任意時間被搶佔和調度。

一些編程語言即使對於在多處理器環境中運行的優化代碼也提供順序一致性。在 C++11 中，您可以將所有共享變量聲明爲具有默認內存排序約束的 C++11 原子類型。在 Java 中，您可以將所有共享變量標記爲volatile. 這是我上一篇文章中的示例，以 C++11 風格重寫：

std::atomic< int > 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 處理器可以更改相對於指令本身的內存存儲順序，但通常情況下，Intel 和 AMD 的 x86/64 系列處理器不會。我們說前者的處理器具有更寬鬆的內存模型。

人們很容易抽象出這些特定於平臺的細節，尤其是 C++11 爲我們提供了一種編寫可移植無鎖代碼的標準方法。但是目前，我認爲大多數無鎖程序員至少對平臺差異有一些瞭解。如果要記住一個關鍵區別，那就是在 x86/64 指令級別，每次從內存加載都帶有獲取語義，並且每次存儲到內存都提供釋放語義——至少對於非 SSE 指令和非寫組合內存.  因此，過去常常編寫能在 x86/64 上運行成功但在其他處理器上失敗的無鎖代碼。

如果你對處理器需要內存排序的硬件細節感興趣，我推薦附錄的並行編程困難嗎？ 請記住在任何情況下, 由於編譯器指令重排序也會導致內存重新排序。

在這篇文章中，我沒有過多地談論無鎖編程的實際方面，例如：我們什麼時候做？我們真正需要多少？我也沒有提到驗證無鎖算法的重要性。儘管如此，我希望對於一些讀者來說，這篇介紹已經提供了對無鎖概念的基本熟悉，因此您可以繼續深入閱讀其他文章而不會感到太困惑。

參考資料 & 擴展閱讀

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/y6OcjmAxnW-DJJlUeJzmGA

猜你喜歡