深入理解無鎖編程
本文轉載自微信公眾號「極客重生」，作者極客重生。轉載本文請聯系極客重生公眾號。
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
不同的 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 上運行成功但在其他處理器上失敗的無鎖代碼。
如果你對處理器需要內存排序的硬件細節感興趣，我推薦附錄的并行編程困難嗎? 請記住在任何情況下,由于編譯器指令重排序也會導致內存重新排序。
在這篇文章中，我沒有過多地談論無鎖編程的實際方面，例如：我們什么時候做?我們真正需要多少?我也沒有提到驗證無鎖算法的重要性。盡管如此，我希望對于一些讀者來說，這篇介紹已經提供了對無鎖概念的基本熟悉，因此您可以繼續深入閱讀其他文章而不會感到太困惑。
參考資料 & 擴展閱讀
- Anthony Williams’ blog and his book, C++ Concurrency in Action
- Dmitriy V’jukov’s website and various forum discussions
- Bartosz Milewski’s blog
- Charles Bloom’s Low-Level Threading series on his blog
- Doug Lea’s JSR-133 Cookbook
- Howells and McKenney’s memory-barriers.txt document
- Hans Boehm’s collection of links about the C++11 memory model
- Herb Sutter’s Effective Concurrency series
- http://preshing.com/20120612/an-introduction-to-lock-free-programming/
