C++無鎖數(shù)據(jù)結(jié)構(gòu)的原子性、原子性原語分析

今天小編給大家分享一下C++無鎖數(shù)據(jù)結(jié)構(gòu)的原子性、原子性原語分析的相關(guān)知識點(diǎn)，內(nèi)容詳細(xì)，邏輯清晰，相信大部分人都還太了解這方面的知識，所以分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后有所收獲，下面我們一起來了解一下吧。

原子性操作可以簡單地分為讀寫（read and write）、原子性交換操作（read-modify-write，RMW）兩部分。原子操作可認(rèn)為是一個不可分的操作；要么發(fā)生，要么沒發(fā)生，我們看不到任何執(zhí)行的中間過程，不存在部分結(jié)果（partial effects）。簡單的讀寫操作甚至不具有原子性，例如，沒有內(nèi)存對齊的數(shù)據(jù)，該數(shù)據(jù)的讀取不具有原子性。在X86架構(gòu)的計算機(jī)中，這樣的讀操作會導(dǎo)致內(nèi)部回避。這樣，處理器讀取數(shù)據(jù)就被分成了好幾部分。在其它諸如Sparc、Intel Itanium架構(gòu)中，這樣的讀操作會導(dǎo)致段錯誤，這些操作要能被攔截并處理，而原子性操作不存在這樣的問題。在現(xiàn)代處理器中，原子性的讀寫操作僅僅作用于對齊后的完整類型（整數(shù)和指針）；而現(xiàn)代編譯器是volatile基本類型正確對齊的保障。如果你想4到8個比特大小的數(shù)據(jù)結(jié)構(gòu)具有原子性，那你就應(yīng)該謹(jǐn)慎行事，借助編譯器指令確保其正確對齊。每種編譯器都有其獨(dú)一無二的數(shù)據(jù)、類型對齊方法。順便說一下，libcds 庫支持一組備用類型和宏指令，當(dāng)你聲明對齊數(shù)據(jù)時，它們會隱藏編譯器依賴的部分。

Compare-and-swap

即便竭盡全力，設(shè)計一個僅僅使用讀寫的無鎖容器算法依然是困難重重（我不清楚針對線程隨機(jī)數(shù)的數(shù)據(jù)結(jié)構(gòu)）。這就是為什么處理器架構(gòu)開發(fā)人員采用 RMW 操作的原因。RMW可以原子性地執(zhí)行對齊內(nèi)存單元讀操作和針對它的寫操作：compare-and-swap (CAS)、fetch-and-add (FAA)、test-and-set (TAS) 等等。在學(xué)術(shù)圈，compare-and-swap (CAS）被認(rèn)為是最基本的一種操作。偽代碼如下：

bool CAS( int * pAddr, int nExpected, int nNew )

atomically {

    if ( *pAddr == nExpected ) {

         *pAddr = nNew ;

         return true ;

    }

    else

        return false ;

}

從字面意思上看，如果pAddr地址中的當(dāng)前變量值等于預(yù)期的 nExpected，那么將 nNew 的值賦給此變量，并返回true；否則返回false，變量值不變。所有執(zhí)行過程都是原子性的、不可分的，不會產(chǎn)生任何可見的部分結(jié)果。借助于CAS，其它的 RMW 操作都可以估值。如下的 fetch-and-add 是這樣的：

int FAA( int * pAddr, int nIncr )

{

     int ncur ;

     do {

          ncur = *pAddr ;

     } while ( !CAS( pAddr, ncur, ncur + nIncr ) ;

     return ncur ;

}

CAS 操作的學(xué)術(shù)性類型在實(shí)踐中并非那么得心應(yīng)手。CAS 失敗后，我們時常想知道內(nèi)存單元中的當(dāng)前值是多少。這時可以考慮另一個種CAS （所謂的 valued CAS，依然是原子性執(zhí)行）：

int CAS( int * pAddr, int nExpected, int nNew )

atomically {

      if ( *pAddr == nExpected ) {

           *pAddr = nNew ;

           return nExpected ;

       }

       else

            return *pAddr

}

C++11中的 compare_exchange函數(shù)包含了兩種衍生類型（嚴(yán)格地說，C++11沒有此類函數(shù)，它們是 ompare_exchange_strong 和 compare_exchange_weak，這些我稍后會告知大家）：

bool compare_exchange( int volatile * pAddr, int& nExpected, int nNew );

參數(shù)nExpected通過引用傳值，并且包含pAddr地址的預(yù)期變量值。在輸出端，返回變化之前的值。(譯者注，其實(shí)就是返回pAddr的舊地址。假如函數(shù)地址中存在值 nExpected，返回true，加入失敗了則返回false（nExpected 會包含地址 pAddr 的當(dāng)前變量值）。multipurpose CAS 操作構(gòu)建涵蓋了學(xué)術(shù) CAS定義的兩種衍生類型。但在實(shí)際應(yīng)用中，compare_exchange 會出現(xiàn)一些錯誤，你需要知道 nExpected 參數(shù)是傳引用，它是可以改變的，這一點(diǎn)是不能接受的。

但借助 compare_exchange 可以實(shí)現(xiàn) fetch-and-add 基本類型，代碼可以寫成下面這樣：

int FAA( int * pAddr, int nIncr )

{

     int ncur = *pAddr;

     do {} while ( !compare_exchange( pAddr, ncur, ncur + nIncr ) ;

     return ncur ;

}

ABA問題

CAS 基本類型適合多種方式。不過在應(yīng)用過程中，可能發(fā)生一個嚴(yán)重的問題，就是所謂的 ABA 問題。為了描述這個問題，我們需要考慮一種 CAS 操作應(yīng)用的典型模式：

int nCur = *pAddr ;

while (true) {

    int nNew = calculating new value

    if ( compare_exchange( pAddr, nCur, nNew ))

        break;

}

事實(shí)上，我們一直在循環(huán)中，直到CAS執(zhí)行才跳出循環(huán)。在讀取 pAddr 地址中的當(dāng)前變量值和計算新值 nNew，這個在 pAddr 地址中可被其它線程改變的變量之間，循環(huán)是必須的。

ABA 問題可以用下面的方式加以描述。假設(shè)線程A從共享內(nèi)存單元讀取A值，與此同時，該內(nèi)存單元指針指向某些數(shù)據(jù)；接著線程Y將內(nèi)存單元的值改為B，接著再改回 A，但此時指針指向了另一些數(shù)據(jù)。但線程 A 通過 CAS 基本類型試圖更改內(nèi)存單元值時，指針和前面讀取的 A 值比較是成功的，CAS 結(jié)果也正確。但此時 A 指向完全不一樣的數(shù)據(jù)。結(jié)果，線程就打破了內(nèi)部對象連接（internal object connections），最終導(dǎo)致失敗。

下面是一個無鎖棧的實(shí)現(xiàn)，重現(xiàn)了ABA 問題 [Mic04]：

// Shared variables

static NodeType * Top = NULL; // Initially null

 

Push(NodeType * node) {

            do {

/*Push2*/          NodeType * t = Top;

/*Push3*/          node->Next = t;

/*Push4*/   } while ( !CAS(&Top,t,node) );

}

 

NodeType * Pop() {

          Node * next ;

          do {

/*Pop1*/        NodeType * t = Top;

/*Pop2*/        if ( t == null )

/*Pop3*/             return null;

/*Pop4*/        next = t->Next;

/*Pop5*/   } while ( !CAS(&Top,t,next) );

/*Pop6*/   return t;

}

下面一系列活動導(dǎo)致棧結(jié)構(gòu)遭受破壞（需要注意的是，此序列不是引起 ABA 問題的唯一方式）。

ABA 問題是所有基于 CAS 基本類型的無鎖容器的一個巨大災(zāi)難。它會在多線程代碼中出現(xiàn)，當(dāng)且僅當(dāng)元素 A 從某個容器中被刪除，接著存入另一個元素 B，然后再改為元素A。即便其它線程使該指針指向某一元素，該元素可能正在被刪除。即使該線程物理刪除了A，接著調(diào)用new方法創(chuàng)建了一個新的元素，也不能保證 allocator 返回A的地址。此問題在超過兩個線程的場景中經(jīng)常出現(xiàn)。鑒于此，我們可以討論 ABCBA 問題、ABABA 問題等等。

為了處理 ABA 問題，你應(yīng)該物理刪除（延遲內(nèi)存單元再分配，或者安全內(nèi)存回收）該元素，并且是在不存在競爭性線程局部，或全局指向待刪除元素的情況下進(jìn)行。

因此，無鎖數(shù)據(jù)結(jié)構(gòu)中元素刪除包含兩個步驟：

• 第一步，將該元素逐出無鎖容器中；

• 第二步（延遲），不存在任何連接的情況下，物理移除該元素。

我會在接下來的某篇文章中詳細(xì)介紹延遲刪除的不同策略。

Load-Linked / Store-Conditional

我猜測，因為 CAS 中出現(xiàn)的ABA問題，促使處理器開發(fā)人員尋找另外一種不受 ABA 問題影響的 RMW 操作。于是找到了load-linked、store-conditional (LL/SC) 這樣的操作對。這樣的操作極其簡單，偽代碼如下：

word LL( word * pAddr ) {

      return *pAddr ;

}

 

bool SC( word * pAddr, word New ) {

      if ( data in pAddr has not been changed since the LL call) {

           *pAddr = New ;

           return true ;

      }

      else

         return false ;

}

LL/SC對以括號運(yùn)算符的形式運(yùn)行，Load-linked（LL） 運(yùn)算僅僅返回 pAddr 地址的當(dāng)前變量值。如果 pAddr 中的數(shù)據(jù)在讀取之后沒有變化，那么 Store-conditional（SC) ）操作會將LL讀取 pAddr 地址的數(shù)據(jù)存儲起來。這種變化之下，任何 pAddr 引用的緩存行修改都是明確無誤的。為了實(shí)現(xiàn) LL/SC 對，程序員不得不更改緩存結(jié)構(gòu)。簡而言之，每個緩存行必須含有額外的比特狀態(tài)值（status bit）。一旦LL執(zhí)行讀運(yùn)算，就會關(guān)聯(lián)此比特值。任何的緩存行一旦有寫入，此比特值就會被重置；在存儲之前，SC操作會檢查此比特值是否針對特定的緩存行。如果比特值為1，意味著緩存行沒有任何改變，pAddr 地址中的值會變更為新值，SC操作成功。否則本操作就會失敗，pAddr 地址中的值不會變更為新值。

CAS通過LL/SC對得以實(shí)現(xiàn)，具體如下：

bool CAS( word * pAddr, word nExpected, word nNew ) {

   if ( LL( pAddr ) == nExpected )

      return SC( pAddr, nNew ) ;

   return false ;

}

注意，盡管代碼中存在多個步驟，不過它確實(shí)執(zhí)行原子性的 CAS。目標(biāo)內(nèi)存單元內(nèi)容要么不變，要么發(fā)生原子性變化?？蚣苤袑?shí)現(xiàn)的 LL/SC 對，僅僅支持 CAS 基本類型是可能的，但不僅限于此種類型。在此，我不打算做進(jìn)一步討論。如果感興趣，可以參考引文[Mic04]。

現(xiàn)代處理器架構(gòu)分為兩大部分。第一部分支持計算機(jī)代碼中的 CAS 基本類型；第二部分是LL/SC 對。CAS 在X86、Intel Itanium、Sparc框架中有實(shí)現(xiàn)。基本類型第一次出現(xiàn)在IBM系統(tǒng)370基本類型中；而PowerPC、MIPS、Alpha、ARM架構(gòu)中的 LL/SC 對, 最早出現(xiàn)在DEC中。倘若 LL/SC 基本類型在現(xiàn)代架構(gòu)中沒有完美實(shí)現(xiàn)，那它就什么都不是。比如，采用不同的地址無法調(diào)用嵌入的 LL/SC ，連接標(biāo)簽存在錯誤遺棄的可能。

從C++的角度看，C++并沒有考慮 LL/SC 對，僅僅描述了原子性原語 compare_exchange (CAS)，以及由此衍生出來的原子性原語——fetch_add、fetch_sub、exchange等等。這個標(biāo)準(zhǔn)意味著通過 LL/SC 可以很容易地實(shí)現(xiàn) CAS；而通過 CAS 對 LL 的向后兼容實(shí)現(xiàn)絕對沒有那么簡單。因此，為了不增加 C++ 庫開發(fā)人員的難度，標(biāo)準(zhǔn)委員會僅僅引入了C++ compare_exchange。這足以用于無鎖算法實(shí)現(xiàn)。

偽共享（False sharing）

現(xiàn)代處理器中，緩存行的長度為64-128字節(jié)，在新的模型中有進(jìn)一步增加的趨勢。主存儲和緩存數(shù)據(jù)交換在 L 字節(jié)大小的 L 塊中進(jìn)行。即使緩存行中的一個字節(jié)發(fā)生變化，所有行都被視為無效，必需和主存進(jìn)行同步。這些由多處理器、多核架構(gòu)中緩存一致性協(xié)議負(fù)責(zé)管理。

假設(shè)不同的共享數(shù)據(jù)（相鄰地址的區(qū)域）存入同一緩存行，從處理的角度看，某個數(shù)據(jù)改變都將導(dǎo)致同一緩存行中的其它數(shù)據(jù)無效。這種場景叫做偽共享。對 LL/SC 基本類型而言，錯誤共享具有破壞性。這些基本類型的執(zhí)行依賴于緩存行。加載連接（LL）操作連接緩存行，而存儲狀態(tài)（SC)）操作在寫之前，會檢查本行中的連接標(biāo)志是否被重置。如果標(biāo)志被重置，寫就無法執(zhí)行，SC返回 false?？紤]到緩存行的長度 L 相當(dāng)長，那么任何緩存行的變更，即和目標(biāo)數(shù)據(jù)不一致，都會導(dǎo)致SC 基本類型返回 false 。結(jié)果產(chǎn)生一個活鎖現(xiàn)象：在此場景下，就算多核處理器滿負(fù)載運(yùn)行，依然無用。

為了處理錯誤共享，每個共享變量必須完全處理緩存行。通常借用填充（padding）來處理。緩存的物理結(jié)構(gòu)影響所有的操作，不僅僅是 LL/SC，也包含CAS。在一些研究中，采用一種特殊的方式創(chuàng)建數(shù)據(jù)結(jié)構(gòu)，該方式有考慮緩存結(jié)構(gòu)（主要是緩存行長度）。一旦數(shù)據(jù)結(jié)構(gòu)被恰當(dāng)?shù)貥?gòu)建，性能就會有極大的提升。

struct Foo {

       int volatile nShared1;

       char   _padding1[64];     // padding for cache line=64 byte

       int volatile nShared2;

       char   _padding2[64];     // padding for cache line=64 byte

};

CAS衍生類型

同樣，我樂意介紹兩種更有用的基本類型：double-word CAS (dwCAS) 和 double CAS (DCAS)。

Double-word CAS 和通用 CAS 相似，不同的是前者運(yùn)行在雙倍大小的內(nèi)存單元中：32位體系結(jié)構(gòu)是64比特，64位體系結(jié)構(gòu)是128比特（要求至少96比特）。有鑒于此架構(gòu)提供 LL/SC 而非CAS，LL/SC 應(yīng)該運(yùn)行在 double-word 之上。我了解的情況是僅有 X86 支持 dwCAS。那么為什么 dwCAS 如此有用呢？借助它可以組織一種 ABA 問題的解決方案——tagged pointers。此方案依賴于每種相關(guān)的共享 tagged pointer 整數(shù)。tagged pointer 可以通過以下結(jié)構(gòu)加以描述：

template <typename T>

struct tagged_pointer {

      T *       ptr ;

      uintptr_t tag ;

 

    tagged_pointer()

      : ptr( new T )

      , tag( 1 )

    {}

};

為了支持原子性，本類型的變量必須與 double-word 對齊：32位架構(gòu)是8字節(jié)，64位架構(gòu)是16字節(jié)。tag 包含 “版本號” 數(shù)據(jù)，ptr 指向此數(shù)據(jù)。我會在接下來的某篇文章中詳盡介紹 tagged pointers，集中介紹安全內(nèi)存回收和安全內(nèi)存回收。目前僅討論內(nèi)存，一旦涉及 T-type 數(shù)據(jù)（以及其對應(yīng)的tagged_pointer），都不應(yīng)該物理刪除，而是移入到一個 free—list 中（對每個T-type進(jìn)行隔離）。未來隨著tag增長，數(shù)據(jù)得以分布式存儲。ABA問題解決方案：現(xiàn)實(shí)中，此指針式很復(fù)雜的，tag 包含一個版本號（分布式位置編號）。如果 tagged_pointer 指針類型和 dwCAS 參數(shù)相同，但 tag 的值不同，那么 dwCAS 不會成功執(zhí)行。

第二種原子性原語——double CAS (DCAS) ，是純理論，沒有在任何現(xiàn)代處理器架構(gòu)中實(shí)現(xiàn)。DCAS 偽代碼如下：

bool DCAS( int * pAddr1, int nExpected1, int nNew1,

           int * pAddr2, int nExpected2, int nNew2 )

atomically {

    if ( *pAddr1 == nExpected1 && *pAddr2 == nExpected2 ) {

         *pAddr1 = nNew1 ;

         *pAddr2 = nNew2 ;

         return true ;

    }

    else

         return false

}

DCAS 運(yùn)行子兩個隨機(jī)排序內(nèi)存單元上。若當(dāng)前值與預(yù)期值一致，可改變這兩個內(nèi)存單元的值。

為何此基本類型如此有意思呢？因為它容易構(gòu)建一個無鎖雙鏈表（deque）。數(shù)據(jù)結(jié)構(gòu)是許多有趣算法的基礎(chǔ)。許多學(xué)術(shù)性工作關(guān)注的數(shù)據(jù)結(jié)構(gòu)，都基于 DCAS。盡管這個基本類型在硬件中還沒有實(shí)現(xiàn)，依然有一些工作（比如[Fra03]- 最流行的一種）描述了基于常規(guī) CAS 的 DCAS 構(gòu)建（針對任意多個 pAddr1…pAddrN 地址的 multi-CAS ）算法。

性能

那么原子性原語性能如何？

現(xiàn)代處理器是如此的復(fù)雜、難于預(yù)測，以至于程序員對計算機(jī)指令常常難以適從。特別是原子性指令，其工作機(jī)制涉及內(nèi)部同步、處理器總線信號等等。許多工作正在試著測試處理器指令長度。而我所提及的測試來自[McKen05]。在這篇文章中，作者比較了原子性增長（atomic increment）和 CAS 基本類型長度和nop（no-operation）長度。比如Intel Xeon 3.06 hHz 處理器（2005 model）原子性增長長度為400 nop，CAS 長度 850-1000 nop。IBM Power4 1.45 hHz 處理器原子性增長長度為180 nop， CAS長度為250 nop。測試時間有些久遠(yuǎn)，處理器架構(gòu)有了一些不小的進(jìn)步，不過我猜還是在同一數(shù)量級上。

正如你所看到的那樣，原子性原語是相當(dāng)復(fù)雜的。所以不加取舍，任何場景下都用它是相當(dāng)不利的。例如，二進(jìn)制樹搜索算法采用 CAS 讀取當(dāng)前樹的節(jié)點(diǎn)，我不看好此類算法。毫無意義，每一代Intel核心架構(gòu)，其CAS都會變得更快。顯然，Intel付出很多努力去改進(jìn)微型架構(gòu)。

Volatile和原子性

C++中有一個神秘的關(guān)鍵字Volatile。很多時候，Volatile被認(rèn)為與原子性以及校準(zhǔn)（regulation）有關(guān)。其實(shí)這是不對的，當(dāng)然存在這樣的認(rèn)識是有歷史原因的。Volatile僅僅是防止編譯器將值緩存入寄存器（編譯器優(yōu)化、寄存器越多，編譯器在其中緩存的數(shù)據(jù)也越多）。讀取Volatile變量意味著永遠(yuǎn)從內(nèi)存中讀取，Volatile變量的寫是直接寫入內(nèi)存中。倘若并發(fā)地改變Volatile數(shù)據(jù)，需要注意這一點(diǎn)。

實(shí)際上我們并沒有這么做，主要是缺乏內(nèi)存柵欄。某些語言如Java、C#，volatile被賦予一個神奇的狀態(tài)值來提供校準(zhǔn)。不過C++11中并沒有這么做。volatile 并沒有任何特殊的校準(zhǔn)，現(xiàn)在我們知道恰當(dāng)?shù)男?zhǔn)對原子性來說是必須的。

因此，在C++11兼容的編譯器沒有必要為原子性變量提供 volatile。不過在以往的編譯器中，采用volatile還是很有必要的，如果你想自己實(shí)現(xiàn)原子性。在下面的聲明中：

class atomic_int {

    int m_nAtomic;

  //….

};

編譯器有權(quán)優(yōu)化 m_nAtomic 調(diào)用（盡管是間接調(diào)用）。因此，時常在此聲明一個int volatile m_nAtomic是很有用的。

libcds

那么我們能從 libcds 庫得到什么？我們已經(jīng)在x86、amd64、 Intel Itanium и Sparc架構(gòu)中，以C++11的方式實(shí)現(xiàn)了原子性原語。倘若編譯器不支持C++11， libcds 可以采用自己的原子性實(shí)現(xiàn)。構(gòu)建無鎖數(shù)據(jù)結(jié)構(gòu)，除去常規(guī)的原子性寫讀，最主要的基本類型就是CAS，而DwCAS用的很少。截止目前，libcds庫還沒有DCAS和multi-CAS的實(shí)現(xiàn)，但未來這些都很有可能出現(xiàn)。很多研究表明，唯一的制約因素是，實(shí)現(xiàn)DCAS 算法[Fra03]太困難了。盡管如此，我已經(jīng)提到個別高效的準(zhǔn)則在無鎖的世界已經(jīng)存在。目前效率低下的是硬件部分，相信隨后的日子針對不同的硬件和任務(wù)，這些都會變得極其高效。

以上就是“C++無鎖數(shù)據(jù)結(jié)構(gòu)的原子性、原子性原語分析”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會為大家更新不同的知識，如果還想學(xué)習(xí)更多的知識，請關(guān)注億速云行業(yè)資訊頻道。