深入理解無鎖編程
本文轉(zhuǎn)載自微信公眾號「極客重生」，作者極客重生。轉(zhuǎn)載本文請聯(lián)系極客重生公眾號。
hi，大伙好，今天介紹一下無鎖編程基礎(chǔ)知識，希望大家可以了解無鎖編程基本原理。
無鎖編程是一個挑戰(zhàn)，不僅因為任務(wù)本身的復(fù)雜性，還因為從一開始就很難深入了解這個主題，因為該主題和底層技術(shù)(編譯器，CPU，內(nèi)存)息息相關(guān)，需要深厚底層功底。
我學(xué)習(xí)無鎖編程是Bruce Dawson 出色而全面的白皮書Lockless Programming Considerations(無鎖編程的思考)。和許多技術(shù)一樣，需要將理論付諸實踐，在平臺上開發(fā)和調(diào)試無鎖代碼。
在這篇文章中，我想重新介紹無鎖編程，首先是定義它，然后將大部分信息提煉為幾個關(guān)鍵概念。我將使用流程圖展示這些概念如何相互關(guān)聯(lián)，然后我們將深入研究細(xì)節(jié)。至少，任何從事無鎖編程的程序員都應(yīng)該已經(jīng)了解如何使用互斥鎖和其他高級同步對象(如信號量和事件)編寫正確的多線程代碼。
它是什么?
人們通常將無鎖編程描述為沒有互斥鎖的編程，互斥鎖也稱為鎖。這是真的，但這只是故事的一部分?；趯W(xué)術(shù)文獻(xiàn)的普遍接受的定義更廣泛一些。從本質(zhì)上講，無鎖是一種用于描述某些代碼的屬性，而無需過多說明該代碼的實際編寫方式。
基本上，如果您的程序的某些部分滿足以下條件，那么該部分可以理所當(dāng)然地被認(rèn)為是無鎖的。相反，如果代碼的給定部分不滿足這些條件，則該部分不是無鎖的。
從這個意義上說，無鎖中的鎖并不直接指互斥鎖，而是指以某種方式“鎖定”整個應(yīng)用程序的可能性，無論是死鎖、活鎖——甚至是由于由你最大的敵人。最后一點聽起來很有趣，但這是關(guān)鍵。共享互斥鎖被簡單地排除在外，因為一旦一個線程獲得互斥鎖，您最大的敵人就再也不會調(diào)度該線程了。當(dāng)然，真正的操作系統(tǒng)不是這樣工作的——我們只是定義術(shù)語。
這是一個不包含互斥鎖但仍然不是無鎖的操作的簡單示例。最初，X = 0。作為讀者的練習(xí)，考慮如何以一種方式調(diào)度兩個線程，使得兩個線程都不退出循環(huán)。
- while(X == 0 ) {
- X = 1 - X;
- }
沒有人期望大型應(yīng)用程序是完全無鎖的。通常，我們從整個代碼庫中識別出一組特定的無鎖操作。例如，在一個無鎖隊列中，有可能是無鎖的操作，比如極少數(shù)的push，pop也許isEmpty等。
Herlihy & Shavit 是The Art of Multiprocessor Programming(多處理器編程的藝術(shù)) 的作者，傾向于將此類操作表示為類方法，并提供以下無鎖的簡潔定義：
“在無限執(zhí)行中，某些方法調(diào)用會無限頻繁地結(jié)束”
換句話說，只要程序能夠繼續(xù)調(diào)用那些無鎖操作，無論發(fā)生什么，完成的調(diào)用次數(shù)都會不斷增加。在這些操作期間，系統(tǒng)在算法上不可能鎖定。
無鎖編程的一個重要結(jié)論是，如果您掛起單個線程，它永遠(yuǎn)不會阻止其他線程作為一個組通過它們自己的無鎖操作取得進(jìn)展。這暗示了在編寫中斷處理程序和實時系統(tǒng)時無鎖編程的價值，其中某些任務(wù)必須在一定的時間限制內(nèi)完成，無論程序的其余部分處于什么狀態(tài)。
最后一個說明：某些操作被設(shè)計為阻塞的并不意味是這就不是Lock-Free的。例如，當(dāng)隊列為空時，隊列的彈出操作可能會故意阻塞。其余的代碼路徑仍然可以被認(rèn)為是無鎖的。
無鎖編程技術(shù)
事實證明，當(dāng)您嘗試滿足無鎖編程的非阻塞條件時，會出現(xiàn)一整套技術(shù)：原子操作、內(nèi)存屏障、避免 ABA 問題，僅舉幾例。這就是事情很快變得邪惡的地方。
那么這些技術(shù)如何相互關(guān)聯(lián)呢?為了說明，我整理了以下流程圖。下面我將逐一詳述。
原子讀-修改-寫操作
原子操作是以一種看起來不可分割的方式操作內(nèi)存的操作：沒有線程可以觀察到半完成的操作。在現(xiàn)代處理器上，許多操作已經(jīng)是原子的。例如，簡單類型的對齊讀取和寫入通常是原子的。
讀-修改-寫(RMW) 操作更進(jìn)一步，允許您以原子方式執(zhí)行更復(fù)雜的事務(wù)。當(dāng)無鎖算法必須支持多個寫入器時，它們特別有用，因為當(dāng)多個線程在同一地址上嘗試 RMW 時，它們將有效地排成一行并一次執(zhí)行這些操作。我已經(jīng)在這篇博客中談到了 RMW 操作，例如實現(xiàn)輕量級互斥鎖、遞歸互斥鎖和輕量級日志系統(tǒng)時。
RMW 操作的示例包括_InterlockedIncrementWin32、OSAtomicAdd32iOS 和std::atomic
不同的 CPU 系列以不同的方式支持 RMW。諸如 PowerPC 和 ARM 之類的處理器公開了load-link/store-conditional)條件指令，這有效地允許您在低級別實現(xiàn)自己的 RMW 原語，盡管這并不常見。常見的 RMW 操作通常就足夠了。
如流程圖所示，即使在單處理器系統(tǒng)上，原子 RMW 也是無鎖編程的必要部分。如果沒有原子性，線程可能會在事務(wù)中途中斷，從而可能導(dǎo)致狀態(tài)不一致。
Compare-And-Swap Loops
也許最常討論的 RMW 操作是compare-and-swap(CAS)。在 Win32 上，CAS 是通過一系列內(nèi)在函數(shù)提供的，例如_InterlockedCompareExchange. 通常使用 CAS Loops 來完成對事務(wù)的原子處理：
- 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;
- }
- }
這樣的循環(huán)仍然符合無鎖的條件，因為如果一個線程的測試失敗，則意味著它必須在另一個線程上成功——盡管某些架構(gòu)提供了CAS的較弱變體，而這不一定是真的。每當(dāng)實現(xiàn) CAS 循環(huán)時，必須特別注意避免ABA 問題。
順序一致性
順序一致性是指所有線程都同意內(nèi)存操作發(fā)生的順序，并且該順序與程序源代碼中的操作順序一致。
實現(xiàn)順序一致性的一種簡單(但顯然不切實際)的方法是禁用編譯器優(yōu)化并強(qiáng)制所有線程在單個處理器上運(yùn)行。處理器永遠(yuǎn)不會看到它自己的內(nèi)存效果出問題，即使線程在任意時間被搶占和調(diào)度。
一些編程語言即使對于在多處理器環(huán)境中運(yùn)行的優(yōu)化代碼也提供順序一致性。在 C++11 中，您可以將所有共享變量聲明為具有默認(rèn)內(nèi)存排序約束的 C++11 原子類型。在 Java 中，您可以將所有共享變量標(biāo)記為volatile. 這是我上一篇文章中的示例，以 C++11 風(fēng)格重寫：
- 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 原子類型保證順序一致性，結(jié)果 r1 = r2 = 0 是不可能的。為了實現(xiàn)這一點，編譯器會在幕后輸出額外的指令——通常是內(nèi)存柵欄和/或 RMW 操作。與程序員直接處理內(nèi)存排序的指令相比，這些附加指令可能會降低實現(xiàn)的效率。
內(nèi)存排序
正如流程圖所暗示的那樣，任何時候您對多核(或任何對稱多處理器)進(jìn)行無鎖編程，并且您的環(huán)境不保證順序一致性，您必須考慮如何防止內(nèi)存重新排序。
在當(dāng)今的體系結(jié)構(gòu)中，強(qiáng)制執(zhí)行正確內(nèi)存排序的工具通常分為三類，它們可以防止編譯器重新排序和處理器重新排序：
- 輕量級同步或柵欄指令;
- 一個完整的內(nèi)存柵欄指令;
- 提供獲取或釋放語義的內(nèi)存操作。
獲取語義防止在程序順序中跟隨它的操作的內(nèi)存重新排序，并且釋放語義防止在它之前的操作的內(nèi)存重新排序。這些語義特別適用于存在生產(chǎn)者/消費(fèi)者關(guān)系的情況，即一個線程發(fā)布一些信息而另一個線程讀取它。
不同的處理器有不同的內(nèi)存模型
不同的 CPU 系列在內(nèi)存重新排序方面有不同的習(xí)慣。這些規(guī)則由每個 CPU 供應(yīng)商記錄，并由硬件嚴(yán)格遵守。例如，PowerPC 和 ARM 處理器可以更改相對于指令本身的內(nèi)存存儲順序，但通常情況下，Intel 和 AMD 的 x86/64 系列處理器不會。我們說前者的處理器具有更寬松的內(nèi)存模型。
人們很容易抽象出這些特定于平臺的細(xì)節(jié)，尤其是 C++11 為我們提供了一種編寫可移植無鎖代碼的標(biāo)準(zhǔn)方法。但是目前，我認(rèn)為大多數(shù)無鎖程序員至少對平臺差異有一些了解。如果要記住一個關(guān)鍵區(qū)別，那就是在 x86/64 指令級別，每次從內(nèi)存加載都帶有獲取語義，并且每次存儲到內(nèi)存都提供釋放語義——至少對于非 SSE 指令和非寫組合內(nèi)存. 因此，過去常常編寫能在x86/64 上運(yùn)行成功但在其他處理器上失敗的無鎖代碼。
如果你對處理器需要內(nèi)存排序的硬件細(xì)節(jié)感興趣，我推薦附錄的并行編程困難嗎? 請記住在任何情況下,由于編譯器指令重排序也會導(dǎo)致內(nèi)存重新排序。
在這篇文章中，我沒有過多地談?wù)摕o鎖編程的實際方面，例如：我們什么時候做?我們真正需要多少?我也沒有提到驗證無鎖算法的重要性。盡管如此，我希望對于一些讀者來說，這篇介紹已經(jīng)提供了對無鎖概念的基本熟悉，因此您可以繼續(xù)深入閱讀其他文章而不會感到太困惑。
參考資料 & 擴(kuò)展閱讀
- 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/
