C++無鎖數據結構的原子性、原子性原語分析

今天小編給大家分享一下C++無鎖數據結構的原子性、原子性原語分析的相關知識點，內容詳細，邏輯清晰，相信大部分人都還太了解這方面的知識，所以分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后有所收獲，下面我們一起來了解一下吧。

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

Compare-and-swap

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

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

atomically {

    if ( *pAddr == nExpected ) {

         *pAddr = nNew ;

         return true ;

    }

    else

        return false ;

}

從字面意思上看，如果pAddr地址中的當前變量值等于預期的 nExpected，那么將 nNew 的值賦給此變量，并返回true；否則返回false，變量值不變。所有執行過程都是原子性的、不可分的，不會產生任何可見的部分結果。借助于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 操作的學術性類型在實踐中并非那么得心應手。CAS 失敗后，我們時常想知道內存單元中的當前值是多少。這時可以考慮另一個種CAS （所謂的 valued CAS，依然是原子性執行）：

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

atomically {

      if ( *pAddr == nExpected ) {

           *pAddr = nNew ;

           return nExpected ;

       }

       else

            return *pAddr

}

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

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

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

但借助 compare_exchange 可以實現 fetch-and-add 基本類型，代碼可以寫成下面這樣：

int FAA( int * pAddr, int nIncr )

{

     int ncur = *pAddr;

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

     return ncur ;

}

ABA問題

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

int nCur = *pAddr ;

while (true) {

    int nNew = calculating new value

    if ( compare_exchange( pAddr, nCur, nNew ))

        break;

}

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

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

下面是一個無鎖棧的實現，重現了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;

}

下面一系列活動導致棧結構遭受破壞（需要注意的是，此序列不是引起 ABA 問題的唯一方式）。

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

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

因此，無鎖數據結構中元素刪除包含兩個步驟：

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

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

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

Load-Linked / Store-Conditional

我猜測，因為 CAS 中出現的ABA問題，促使處理器開發人員尋找另外一種不受 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對以括號運算符的形式運行，Load-linked（LL） 運算僅僅返回 pAddr 地址的當前變量值。如果 pAddr 中的數據在讀取之后沒有變化，那么 Store-conditional（SC) ）操作會將LL讀取 pAddr 地址的數據存儲起來。這種變化之下，任何 pAddr 引用的緩存行修改都是明確無誤的。為了實現 LL/SC 對，程序員不得不更改緩存結構。簡而言之，每個緩存行必須含有額外的比特狀態值（status bit）。一旦LL執行讀運算，就會關聯此比特值。任何的緩存行一旦有寫入，此比特值就會被重置；在存儲之前，SC操作會檢查此比特值是否針對特定的緩存行。如果比特值為1，意味著緩存行沒有任何改變，pAddr 地址中的值會變更為新值，SC操作成功。否則本操作就會失敗，pAddr 地址中的值不會變更為新值。

CAS通過LL/SC對得以實現，具體如下：

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

   if ( LL( pAddr ) == nExpected )

      return SC( pAddr, nNew ) ;

   return false ;

}

注意，盡管代碼中存在多個步驟，不過它確實執行原子性的 CAS。目標內存單元內容要么不變，要么發生原子性變化。框架中實現的 LL/SC 對，僅僅支持 CAS 基本類型是可能的，但不僅限于此種類型。在此，我不打算做進一步討論。如果感興趣，可以參考引文[Mic04]。

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

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

偽共享（False sharing）

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

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

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

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

template <typename T>

struct tagged_pointer {

      T *       ptr ;

      uintptr_t tag ;

 

    tagged_pointer()

      : ptr( new T )

      , tag( 1 )

    {}

};

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

第二種原子性原語——double CAS (DCAS) ，是純理論，沒有在任何現代處理器架構中實現。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 運行子兩個隨機排序內存單元上。若當前值與預期值一致，可改變這兩個內存單元的值。

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

性能

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

現代處理器是如此的復雜、難于預測，以至于程序員對計算機指令常常難以適從。特別是原子性指令，其工作機制涉及內部同步、處理器總線信號等等。許多工作正在試著測試處理器指令長度。而我所提及的測試來自[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。測試時間有些久遠，處理器架構有了一些不小的進步，不過我猜還是在同一數量級上。

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

Volatile和原子性

C++中有一個神秘的關鍵字Volatile。很多時候，Volatile被認為與原子性以及校準（regulation）有關。其實這是不對的，當然存在這樣的認識是有歷史原因的。Volatile僅僅是防止編譯器將值緩存入寄存器（編譯器優化、寄存器越多，編譯器在其中緩存的數據也越多）。讀取Volatile變量意味著永遠從內存中讀取，Volatile變量的寫是直接寫入內存中。倘若并發地改變Volatile數據，需要注意這一點。

實際上我們并沒有這么做，主要是缺乏內存柵欄。某些語言如Java、C#，volatile被賦予一個神奇的狀態值來提供校準。不過C++11中并沒有這么做。volatile 并沒有任何特殊的校準，現在我們知道恰當的校準對原子性來說是必須的。

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

class atomic_int {

    int m_nAtomic;

  //….

};

編譯器有權優化 m_nAtomic 調用（盡管是間接調用）。因此，時常在此聲明一個int volatile m_nAtomic是很有用的。

libcds

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

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