共計(jì) 8545 個(gè)字符，預(yù)計(jì)需要花費(fèi) 22 分鐘才能閱讀完成。
今天丸趣 TV 小編給大家分享一下 C ++ 無鎖數(shù)據(jù)結(jié)構(gòu)的原子性、原子性原語分析的相關(guān)知識(shí)點(diǎn)，內(nèi)容詳細(xì)，邏輯清晰，相信大部分人都還太了解這方面的知識(shí)，所以分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后有所收獲，下面我們一起來了解一下吧。
原子性操作可以簡單地分為讀寫（read and write）、原子性交換操作（read-modify-write，RMW）兩部分。原子操作可認(rèn)為是一個(gè)不可分的操作；要么發(fā)生，要么沒發(fā)生，我們看不到任何執(zhí)行的中間過程，不存在部分結(jié)果（partial effects）。簡單的讀寫操作甚至不具有原子性，例如，沒有內(nèi)存對齊的數(shù)據(jù)，該數(shù)據(jù)的讀取不具有原子性。在 X86 架構(gòu)的計(jì)算機(jī)中，這樣的讀操作會(huì)導(dǎo)致內(nèi)部回避。這樣，處理器讀取數(shù)據(jù)就被分成了好幾部分。在其它諸如 Sparc、Intel Itanium 架構(gòu)中，這樣的讀操作會(huì)導(dǎo)致段錯(cuò)誤，這些操作要能被攔截并處理，而原子性操作不存在這樣的問題。在現(xiàn)代處理器中，原子性的讀寫操作僅僅作用于對齊后的完整類型（整數(shù)和指針）；而現(xiàn)代編譯器是 volatile 基本類型正確對齊的保障。如果你想 4 到 8 個(gè)比特大小的數(shù)據(jù)結(jié)構(gòu)具有原子性，那你就應(yīng)該謹(jǐn)慎行事，借助編譯器指令確保其正確對齊。每種編譯器都有其獨(dú)一無二的數(shù)據(jù)、類型對齊方法。順便說一下，libcds 庫支持一組備用類型和宏指令，當(dāng)你聲明對齊數(shù)據(jù)時(shí)，它們會(huì)隱藏編譯器依賴的部分。
Compare-and-swap
即便竭盡全力，設(shè)計(jì)一個(gè)僅僅使用讀寫的無鎖容器算法依然是困難重重（我不清楚針對線程隨機(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í)行過程都是原子性的、不可分的，不會(huì)產(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 失敗后，我們時(shí)常想知道內(nèi)存單元中的當(dāng)前值是多少。這時(shí)可以考慮另一個(gè)種 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，這些我稍后會(huì)告知大家）：
bool compare_exchange( int volatile * pAddr, int nExpected, int nNew );
參數(shù) nExpected 通過引用傳值，并且包含 pAddr 地址的預(yù)期變量值。在輸出端，返回變化之前的值。(譯者注，其實(shí)就是返回 pAddr 的舊地址。假如函數(shù)地址中存在值 nExpected，返回 true，加入失敗了則返回 false（nExpected 會(huì)包含地址 pAddr 的當(dāng)前變量值）。multipurpose CAS 操作構(gòu)建涵蓋了學(xué)術(shù) CAS 定義的兩種衍生類型。但在實(shí)際應(yīng)用中，compare_exchange 會(huì)出現(xiàn)一些錯(cuò)誤，你需要知道 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ā)生一個(gè)嚴(yán)重的問題，就是所謂的 ABA 問題。為了描述這個(gè)問題，我們需要考慮一種 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)前變量值和計(jì)算新值 nNew，這個(gè)在 pAddr 地址中可被其它線程改變的變量之間，循環(huán)是必須的。
ABA 問題可以用下面的方式加以描述。假設(shè)線程 A 從共享內(nèi)存單元讀取 A 值，與此同時(shí)，該內(nèi)存單元指針指向某些數(shù)據(jù)；接著線程 Y 將內(nèi)存單元的值改為 B，接著再改回 A，但此時(shí)指針指向了另一些數(shù)據(jù)。但線程 A 通過 CAS 基本類型試圖更改內(nèi)存單元值時(shí)，指針和前面讀取的 A 值比較是成功的，CAS 結(jié)果也正確。但此時(shí) A 指向完全不一樣的數(shù)據(jù)。結(jié)果，線程就打破了內(nèi)部對象連接（internal object connections），最終導(dǎo)致失敗。
下面是一個(gè)無鎖棧的實(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òng)導(dǎo)致棧結(jié)構(gòu)遭受破壞（需要注意的是，此序列不是引起 ABA 問題的唯一方式）。
Thread XThread YCalls Pop().
Line Pop4 is performed,
variables values: t == A
next == A- next NodeType * pTop = Pop()
pTop == top of the stack, i.e. A
Pop()
Push(pTop)
Now the top of the stack is A again
Note, that A- next has changedPop5 line is being performed.
CAS is successful, but the field Top- next
is assigned with another value,
which doesn’t exist in the stack,
as Y thread has pushed A and A- next out,
of a stack and the local variable next
has the old value of A- next
ABA 問題是所有基于 CAS 基本類型的無鎖容器的一個(gè)巨大災(zāi)難。它會(huì)在多線程代碼中出現(xiàn)，當(dāng)且僅當(dāng)元素 A 從某個(gè)容器中被刪除，接著存入另一個(gè)元素 B，然后再改為元素 A。即便其它線程使該指針指向某一元素，該元素可能正在被刪除。即使該線程物理刪除了 A，接著調(diào)用 new 方法創(chuàng)建了一個(gè)新的元素，也不能保證 allocator 返回 A 的地址。此問題在超過兩個(gè)線程的場景中經(jīng)常出現(xiàn)。鑒于此，我們可以討論 ABCBA 問題、ABABA 問題等等。
為了處理 ABA 問題，你應(yīng)該物理刪除（延遲內(nèi)存單元再分配，或者安全內(nèi)存回收）該元素，并且是在不存在競爭性線程局部，或全局指向待刪除元素的情況下進(jìn)行。
因此，無鎖數(shù)據(jù)結(jié)構(gòu)中元素刪除包含兩個(gè)步驟：
第一步，將該元素逐出無鎖容器中；
第二步（延遲），不存在任何連接的情況下，物理移除該元素。
我會(huì)在接下來的某篇文章中詳細(xì)介紹延遲刪除的不同策略。
Load-Linked / Store-Conditional
我猜測，因?yàn)?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 對以括號(hào)運(yùn)算符的形式運(yùn)行，Load-linked（LL）運(yùn)算僅僅返回 pAddr 地址的當(dāng)前變量值。如果 pAddr 中的數(shù)據(jù)在讀取之后沒有變化，那么 Store-conditional（SC)）操作會(huì)將 LL 讀取 pAddr 地址的數(shù)據(jù)存儲(chǔ)起來。這種變化之下，任何 pAddr 引用的緩存行修改都是明確無誤的。為了實(shí)現(xiàn) LL/SC 對，程序員不得不更改緩存結(jié)構(gòu)。簡而言之，每個(gè)緩存行必須含有額外的比特狀態(tài)值（status bit）。一旦 LL 執(zhí)行讀運(yùn)算，就會(huì)關(guān)聯(lián)此比特值。任何的緩存行一旦有寫入，此比特值就會(huì)被重置；在存儲(chǔ)之前，SC 操作會(huì)檢查此比特值是否針對特定的緩存行。如果比特值為 1，意味著緩存行沒有任何改變，pAddr 地址中的值會(huì)變更為新值，SC 操作成功。否則本操作就會(huì)失敗，pAddr 地址中的值不會(huì)變更為新值。
CAS 通過 LL/SC 對得以實(shí)現(xiàn)，具體如下：
bool CAS( word * pAddr, word nExpected, word nNew ) {
if ( LL( pAddr ) == nExpected )
return SC( pAddr, nNew ) ;
return false ;
}
注意，盡管代碼中存在多個(gè)步驟，不過它確實(shí)執(zhí)行原子性的 CAS。目標(biāo)內(nèi)存單元內(nèi)容要么不變，要么發(fā)生原子性變化。框架中實(shí)現(xiàn)的 LL/SC 對，僅僅支持 CAS 基本類型是可能的，但不僅限于此種類型。在此，我不打算做進(jìn)一步討論。如果感興趣，可以參考引文[Mic04]。
現(xiàn)代處理器架構(gòu)分為兩大部分。第一部分支持計(jì)算機(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)簽存在錯(cuò)誤遺棄的可能。
從 C ++ 的角度看，C++ 并沒有考慮 LL/SC 對，僅僅描述了原子性原語 compare_exchange (CAS)，以及由此衍生出來的原子性原語——fetch_add、fetch_sub、exchange 等等。這個(gè)標(biāo)準(zhǔn)意味著通過 LL/SC 可以很容易地實(shí)現(xiàn) CAS；而通過 CAS 對 LL 的向后兼容實(shí)現(xiàn)絕對沒有那么簡單。因此，為了不增加 C++ 庫開發(fā)人員的難度，標(biāo)準(zhǔn)委員會(huì)僅僅引入了 C ++ compare_exchange。這足以用于無鎖算法實(shí)現(xiàn)。
偽共享（False sharing）
現(xiàn)代處理器中，緩存行的長度為 64-128 字節(jié)，在新的模型中有進(jìn)一步增加的趨勢。主存儲(chǔ)和緩存數(shù)據(jù)交換在 L 字節(jié)大小的 L 塊中進(jìn)行。即使緩存行中的一個(gè)字節(jié)發(fā)生變化，所有行都被視為無效，必需和主存進(jìn)行同步。這些由多處理器、多核架構(gòu)中緩存一致性協(xié)議負(fù)責(zé)管理。
假設(shè)不同的共享數(shù)據(jù)（相鄰地址的區(qū)域）存入同一緩存行，從處理的角度看，某個(gè)數(shù)據(jù)改變都將導(dǎo)致同一緩存行中的其它數(shù)據(jù)無效。這種場景叫做偽共享。對 LL/SC 基本類型而言，錯(cuò)誤共享具有破壞性。這些基本類型的執(zhí)行依賴于緩存行。加載連接（LL）操作連接緩存行，而存儲(chǔ)狀態(tài)（SC)）操作在寫之前，會(huì)檢查本行中的連接標(biāo)志是否被重置。如果標(biāo)志被重置，寫就無法執(zhí)行，SC 返回 false。考慮到緩存行的長度 L 相當(dāng)長，那么任何緩存行的變更，即和目標(biāo)數(shù)據(jù)不一致，都會(huì)導(dǎo)致 SC 基本類型返回 false。結(jié)果產(chǎn)生一個(gè)活鎖現(xiàn)象：在此場景下，就算多核處理器滿負(fù)載運(yùn)行，依然無用。
為了處理錯(cuò)誤共享，每個(gè)共享變量必須完全處理緩存行。通常借用填充（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)建，性能就會(huì)有極大的提升。
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 包含“版本號(hào)”數(shù)據(jù)，ptr 指向此數(shù)據(jù)。我會(huì)在接下來的某篇文章中詳盡介紹 tagged pointers，集中介紹安全內(nèi)存回收和安全內(nèi)存回收。目前僅討論內(nèi)存，一旦涉及 T-type 數(shù)據(jù)（以及其對應(yīng)的 tagged_pointer），都不應(yīng)該物理刪除，而是移入到一個(gè) free—list 中（對每個(gè) T -type 進(jìn)行隔離）。未來隨著 tag 增長，數(shù)據(jù)得以分布式存儲(chǔ)。ABA 問題解決方案：現(xiàn)實(shí)中，此指針式很復(fù)雜的，tag 包含一個(gè)版本號(hào)（分布式位置編號(hào)）。如果 tagged_pointer 指針類型和 dwCAS 參數(shù)相同，但 tag 的值不同，那么 dwCAS 不會(huì)成功執(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)行子兩個(gè)隨機(jī)排序內(nèi)存單元上。若當(dāng)前值與預(yù)期值一致，可改變這兩個(gè)內(nèi)存單元的值。
為何此基本類型如此有意思呢？因?yàn)樗菀讟?gòu)建一個(gè)無鎖雙鏈表（deque）。數(shù)據(jù)結(jié)構(gòu)是許多有趣算法的基礎(chǔ)。許多學(xué)術(shù)性工作關(guān)注的數(shù)據(jù)結(jié)構(gòu)，都基于 DCAS。盡管這個(gè)基本類型在硬件中還沒有實(shí)現(xiàn)，依然有一些工作（比如[Fra03]- 最流行的一種）描述了基于常規(guī) CAS 的 DCAS 構(gòu)建（針對任意多個(gè) pAddr1…pAddrN 地址的 multi-CAS）算法。
性能
那么原子性原語性能如何？
現(xiàn)代處理器是如此的復(fù)雜、難于預(yù)測，以至于程序員對計(jì)算機(jī)指令常常難以適從。特別是原子性指令，其工作機(jī)制涉及內(nèi)部同步、處理器總線信號(hào)等等。許多工作正在試著測試處理器指令長度。而我所提及的測試來自[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。測試時(shí)間有些久遠(yuǎn)，處理器架構(gòu)有了一些不小的進(jìn)步，不過我猜還是在同一數(shù)量級(jí)上。
正如你所看到的那樣，原子性原語是相當(dāng)復(fù)雜的。所以不加取舍，任何場景下都用它是相當(dāng)不利的。例如，二進(jìn)制樹搜索算法采用 CAS 讀取當(dāng)前樹的節(jié)點(diǎn)，我不看好此類算法。毫無意義，每一代 Intel 核心架構(gòu)，其 CAS 都會(huì)變得更快。顯然，Intel 付出很多努力去改進(jìn)微型架構(gòu)。
Volatile 和原子性
C++ 中有一個(gè)神秘的關(guān)鍵字 Volatile。很多時(shí)候，Volatile 被認(rèn)為與原子性以及校準(zhǔn)（regulation）有關(guān)。其實(shí)這是不對的，當(dāng)然存在這樣的認(rèn)識(shí)是有歷史原因的。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 被賦予一個(gè)神奇的狀態(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)用）。因此，時(shí)常在此聲明一個(gè) 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)提到個(gè)別高效的準(zhǔn)則在無鎖的世界已經(jīng)存在。目前效率低下的是硬件部分，相信隨后的日子針對不同的硬件和任務(wù)，這些都會(huì)變得極其高效。
以上就是“C++ 無鎖數(shù)據(jù)結(jié)構(gòu)的原子性、原子性原語分析”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，丸趣 TV 小編每天都會(huì)為大家更新不同的知識(shí)，如果還想學(xué)習(xí)更多的知識(shí)，請關(guān)注丸趣 TV 行業(yè)資訊頻道。
