深入理解無(wú)鎖編程

作者：極客重生 2021-07-26 07:47:37

無(wú)鎖編程是一個(gè)挑戰(zhàn)，不僅因?yàn)槿蝿?wù)本身的復(fù)雜性，還因?yàn)閺囊婚_(kāi)始就很難深入了解這個(gè)主題，因?yàn)樵撝黝}和底層技術(shù)（編譯器，CPU，內(nèi)存）息息相關(guān)，需要深厚底層功底。

[[412990]]

本文轉(zhuǎn)載自微信公眾號(hào)「極客重生」，作者極客重生。轉(zhuǎn)載本文請(qǐng)聯(lián)系極客重生公眾號(hào)。

hi，大伙好，今天介紹一下無(wú)鎖編程基礎(chǔ)知識(shí)，希望大家可以了解無(wú)鎖編程基本原理。

無(wú)鎖編程是一個(gè)挑戰(zhàn)，不僅因?yàn)槿蝿?wù)本身的復(fù)雜性，還因?yàn)閺囊婚_(kāi)始就很難深入了解這個(gè)主題，因?yàn)樵撝黝}和底層技術(shù)(編譯器，CPU，內(nèi)存)息息相關(guān)，需要深厚底層功底。

我學(xué)習(xí)無(wú)鎖編程是Bruce Dawson 出色而全面的白皮書(shū)Lockless Programming Considerations(無(wú)鎖編程的思考)。和許多技術(shù)一樣，需要將理論付諸實(shí)踐，在平臺(tái)上開(kāi)發(fā)和調(diào)試無(wú)鎖代碼。

在這篇文章中，我想重新介紹無(wú)鎖編程，首先是定義它，然后將大部分信息提煉為幾個(gè)關(guān)鍵概念。我將使用流程圖展示這些概念如何相互關(guān)聯(lián)，然后我們將深入研究細(xì)節(jié)。至少，任何從事無(wú)鎖編程的程序員都應(yīng)該已經(jīng)了解如何使用互斥鎖和其他高級(jí)同步對(duì)象(如信號(hào)量和事件)編寫正確的多線程代碼。

它是什么?

人們通常將無(wú)鎖編程描述為沒(méi)有互斥鎖的編程，互斥鎖也稱為鎖。這是真的，但這只是故事的一部分。基于學(xué)術(shù)文獻(xiàn)的普遍接受的定義更廣泛一些。從本質(zhì)上講，無(wú)鎖是一種用于描述某些代碼的屬性，而無(wú)需過(guò)多說(shuō)明該代碼的實(shí)際編寫方式。

基本上，如果您的程序的某些部分滿足以下條件，那么該部分可以理所當(dāng)然地被認(rèn)為是無(wú)鎖的。相反，如果代碼的給定部分不滿足這些條件，則該部分不是無(wú)鎖的。

從這個(gè)意義上說(shuō)，無(wú)鎖中的鎖并不直接指互斥鎖，而是指以某種方式“鎖定”整個(gè)應(yīng)用程序的可能性，無(wú)論是死鎖、活鎖——甚至是由于由你最大的敵人。最后一點(diǎn)聽(tīng)起來(lái)很有趣，但這是關(guān)鍵。共享互斥鎖被簡(jiǎn)單地排除在外，因?yàn)橐坏┮粋€(gè)線程獲得互斥鎖，您最大的敵人就再也不會(huì)調(diào)度該線程了。當(dāng)然，真正的操作系統(tǒng)不是這樣工作的——我們只是定義術(shù)語(yǔ)。

這是一個(gè)不包含互斥鎖但仍然不是無(wú)鎖的操作的簡(jiǎn)單示例。最初，X = 0。作為讀者的練習(xí)，考慮如何以一種方式調(diào)度兩個(gè)線程，使得兩個(gè)線程都不退出循環(huán)。

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

沒(méi)有人期望大型應(yīng)用程序是完全無(wú)鎖的。通常，我們從整個(gè)代碼庫(kù)中識(shí)別出一組特定的無(wú)鎖操作。例如，在一個(gè)無(wú)鎖隊(duì)列中，有可能是無(wú)鎖的操作，比如極少數(shù)的push，pop也許isEmpty等。

Herlihy & Shavit 是The Art of Multiprocessor Programming(多處理器編程的藝術(shù)) 的作者，傾向于將此類操作表示為類方法，并提供以下無(wú)鎖的簡(jiǎn)潔定義：

“在無(wú)限執(zhí)行中，某些方法調(diào)用會(huì)無(wú)限頻繁地結(jié)束”

換句話說(shuō)，只要程序能夠繼續(xù)調(diào)用那些無(wú)鎖操作，無(wú)論發(fā)生什么，完成的調(diào)用次數(shù)都會(huì)不斷增加。在這些操作期間，系統(tǒng)在算法上不可能鎖定。

無(wú)鎖編程的一個(gè)重要結(jié)論是，如果您掛起單個(gè)線程，它永遠(yuǎn)不會(huì)阻止其他線程作為一個(gè)組通過(guò)它們自己的無(wú)鎖操作取得進(jìn)展。這暗示了在編寫中斷處理程序和實(shí)時(shí)系統(tǒng)時(shí)無(wú)鎖編程的價(jià)值，其中某些任務(wù)必須在一定的時(shí)間限制內(nèi)完成，無(wú)論程序的其余部分處于什么狀態(tài)。

最后一個(gè)說(shuō)明：某些操作被設(shè)計(jì)為阻塞的并不意味是這就不是Lock-Free的。例如，當(dāng)隊(duì)列為空時(shí)，隊(duì)列的彈出操作可能會(huì)故意阻塞。其余的代碼路徑仍然可以被認(rèn)為是無(wú)鎖的。

無(wú)鎖編程技術(shù)

事實(shí)證明，當(dāng)您嘗試滿足無(wú)鎖編程的非阻塞條件時(shí)，會(huì)出現(xiàn)一整套技術(shù)：原子操作、內(nèi)存屏障、避免 ABA 問(wèn)題，僅舉幾例。這就是事情很快變得邪惡的地方。

那么這些技術(shù)如何相互關(guān)聯(lián)呢?為了說(shuō)明，我整理了以下流程圖。下面我將逐一詳述。

原子讀-修改-寫操作

原子操作是以一種看起來(lái)不可分割的方式操作內(nèi)存的操作：沒(méi)有線程可以觀察到半完成的操作。在現(xiàn)代處理器上，許多操作已經(jīng)是原子的。例如，簡(jiǎn)單類型的對(duì)齊讀取和寫入通常是原子的。

讀-修改-寫(RMW) 操作更進(jìn)一步，允許您以原子方式執(zhí)行更復(fù)雜的事務(wù)。當(dāng)無(wú)鎖算法必須支持多個(gè)寫入器時(shí)，它們特別有用，因?yàn)楫?dāng)多個(gè)線程在同一地址上嘗試 RMW 時(shí)，它們將有效地排成一行并一次執(zhí)行這些操作。我已經(jīng)在這篇博客中談到了 RMW 操作，例如實(shí)現(xiàn)輕量級(jí)互斥鎖、遞歸互斥鎖和輕量級(jí)日志系統(tǒng)時(shí)。

RMW 操作的示例包括_InterlockedIncrementWin32、OSAtomicAdd32iOS 和std::atomic::fetch_addC++11。請(qǐng)注意，C++11 原子標(biāo)準(zhǔn)并不能保證實(shí)現(xiàn)在每個(gè)平臺(tái)上都是無(wú)鎖的，因此最好了解您的平臺(tái)和工具鏈的功能。你可以使用std::atomic<>::is_lock_free確認(rèn)一下。

不同的 CPU 系列以不同的方式支持 RMW。諸如 PowerPC 和 ARM 之類的處理器公開(kāi)了load-link/store-conditional)條件指令，這有效地允許您在低級(jí)別實(shí)現(xiàn)自己的 RMW 原語(yǔ)，盡管這并不常見(jiàn)。常見(jiàn)的 RMW 操作通常就足夠了。

如流程圖所示，即使在單處理器系統(tǒng)上，原子 RMW 也是無(wú)鎖編程的必要部分。如果沒(méi)有原子性，線程可能會(huì)在事務(wù)中途中斷，從而可能導(dǎo)致?tīng)顟B(tài)不一致。

Compare-And-Swap Loops

也許最常討論的 RMW 操作是compare-and-swap(CAS)。在 Win32 上，CAS 是通過(guò)一系列內(nèi)在函數(shù)提供的，例如_InterlockedCompareExchange. 通常使用 CAS Loops 來(lái)完成對(duì)事務(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)仍然符合無(wú)鎖的條件，因?yàn)槿绻粋€(gè)線程的測(cè)試失敗，則意味著它必須在另一個(gè)線程上成功——盡管某些架構(gòu)提供了CAS的較弱變體，而這不一定是真的。每當(dāng)實(shí)現(xiàn) CAS 循環(huán)時(shí)，必須特別注意避免ABA 問(wèn)題。

順序一致性

順序一致性是指所有線程都同意內(nèi)存操作發(fā)生的順序，并且該順序與程序源代碼中的操作順序一致。

實(shí)現(xiàn)順序一致性的一種簡(jiǎn)單(但顯然不切實(shí)際)的方法是禁用編譯器優(yōu)化并強(qiáng)制所有線程在單個(gè)處理器上運(yùn)行。處理器永遠(yuǎn)不會(huì)看到它自己的內(nèi)存效果出問(wèn)題，即使線程在任意時(shí)間被搶占和調(diào)度。

一些編程語(yǔ)言即使對(duì)于在多處理器環(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();  
}

因?yàn)?C++11 原子類型保證順序一致性，結(jié)果 r1 = r2 = 0 是不可能的。為了實(shí)現(xiàn)這一點(diǎn)，編譯器會(huì)在幕后輸出額外的指令——通常是內(nèi)存柵欄和/或 RMW 操作。與程序員直接處理內(nèi)存排序的指令相比，這些附加指令可能會(huì)降低實(shí)現(xiàn)的效率。

內(nèi)存排序

正如流程圖所暗示的那樣，任何時(shí)候您對(duì)多核(或任何對(duì)稱多處理器)進(jìn)行無(wú)鎖編程，并且您的環(huán)境不保證順序一致性，您必須考慮如何防止內(nèi)存重新排序。

在當(dāng)今的體系結(jié)構(gòu)中，強(qiáng)制執(zhí)行正確內(nèi)存排序的工具通常分為三類，它們可以防止編譯器重新排序和處理器重新排序：

輕量級(jí)同步或柵欄指令;
一個(gè)完整的內(nèi)存柵欄指令;
提供獲取或釋放語(yǔ)義的內(nèi)存操作。

獲取語(yǔ)義防止在程序順序中跟隨它的操作的內(nèi)存重新排序，并且釋放語(yǔ)義防止在它之前的操作的內(nèi)存重新排序。這些語(yǔ)義特別適用于存在生產(chǎn)者/消費(fèi)者關(guān)系的情況，即一個(gè)線程發(fā)布一些信息而另一個(gè)線程讀取它。

不同的處理器有不同的內(nèi)存模型

不同的 CPU 系列在內(nèi)存重新排序方面有不同的習(xí)慣。這些規(guī)則由每個(gè) CPU 供應(yīng)商記錄，并由硬件嚴(yán)格遵守。例如，PowerPC 和 ARM 處理器可以更改相對(duì)于指令本身的內(nèi)存存儲(chǔ)順序，但通常情況下，Intel 和 AMD 的 x86/64 系列處理器不會(huì)。我們說(shuō)前者的處理器具有更寬松的內(nèi)存模型。

人們很容易抽象出這些特定于平臺(tái)的細(xì)節(jié)，尤其是 C++11 為我們提供了一種編寫可移植無(wú)鎖代碼的標(biāo)準(zhǔn)方法。但是目前，我認(rèn)為大多數(shù)無(wú)鎖程序員至少對(duì)平臺(tái)差異有一些了解。如果要記住一個(gè)關(guān)鍵區(qū)別，那就是在 x86/64 指令級(jí)別，每次從內(nèi)存加載都帶有獲取語(yǔ)義，并且每次存儲(chǔ)到內(nèi)存都提供釋放語(yǔ)義——至少對(duì)于非 SSE 指令和非寫組合內(nèi)存. 因此，過(guò)去常常編寫能在x86/64 上運(yùn)行成功但在其他處理器上失敗的無(wú)鎖代碼。

如果你對(duì)處理器需要內(nèi)存排序的硬件細(xì)節(jié)感興趣，我推薦附錄的并行編程困難嗎? 請(qǐng)記住在任何情況下,由于編譯器指令重排序也會(huì)導(dǎo)致內(nèi)存重新排序。

在這篇文章中，我沒(méi)有過(guò)多地談?wù)摕o(wú)鎖編程的實(shí)際方面，例如：我們什么時(shí)候做?我們真正需要多少?我也沒(méi)有提到驗(yàn)證無(wú)鎖算法的重要性。盡管如此，我希望對(duì)于一些讀者來(lái)說(shuō)，這篇介紹已經(jīng)提供了對(duì)無(wú)鎖概念的基本熟悉，因此您可以繼續(xù)深入閱讀其他文章而不會(huì)感到太困惑。

參考資料 & 擴(kuò)展閱讀