鎖無(wú)關(guān)的（Lock-Free）數(shù)據(jù)結(jié)構(gòu) 1
peakzhang 發(fā)表于: 2008-4-23 23:31
來(lái)源: ACE 開發(fā)者
C/C++ Users Journal October, 2004
鎖無(wú)關(guān)的（Lock-Free）數(shù)據(jù)結(jié)構(gòu)
在避免死鎖的同時(shí)確保線程繼續(xù)
http://blog.csdn.net/pongba/archive/2006/01/26/588638.aspx
Andrei Alexandrescu
劉未鵬
譯
Andrei Alexandrescu是華盛頓大學(xué)計(jì)算機(jī)科學(xué)系的在讀研究生，也是《Modern C++ Design》一書的作者。他的郵箱是 andrei@metalanguage.com。
在Generic<Programming>沉默了一期之后(研究生的學(xué)業(yè)總是使人不得不投入百分之百的精力),這一期文章的可寫內(nèi)容突然多得令人似乎有點(diǎn)無(wú)所適從.例如,其中之一就是關(guān)于構(gòu)造函數(shù)的討論,特別是轉(zhuǎn)發(fā)構(gòu)造函數(shù)(forwarding constructor),(構(gòu)造函數(shù)中的)異常處理,以及兩段式(two-stage)對(duì)象構(gòu)造.另一個(gè)可選主題是創(chuàng)建不完全類型的容器(例如list、vector或map)（順便再回顧一下Yanslander技術(shù)[2]），這一任務(wù)可以借助于一些有趣的技巧來(lái)完成（當(dāng)下的標(biāo)準(zhǔn)庫(kù)容器并不能保證可存放不完全類型的對(duì)象）。
雖說(shuō)以上兩個(gè)候選主題都挺誘人，不過(guò)跟所謂的“鎖無(wú)關(guān)（Lock-Free）”數(shù)據(jù)結(jié)構(gòu)一比就只能靠邊站了，后者是多線程編程的極重要技術(shù)之一。在今年的“Programming Language Design and Implementation”大會(huì)(http://www.cs.umd.edu/~pugh/pldi04/)上，Michael Maged展示了世界上第一個(gè)鎖無(wú)關(guān)的(lock-free)內(nèi)存分配器[7]，跟那些小心翼翼地設(shè)計(jì)的、基于鎖(lock-based)的，同時(shí)也更為復(fù)雜的內(nèi)存分配器相比，Michael的鎖無(wú)關(guān)的內(nèi)存分配器在諸多測(cè)試下都表現(xiàn)得更為優(yōu)越。
Michael的鎖無(wú)關(guān)內(nèi)存分配器代表著近來(lái)出現(xiàn)的許多鎖無(wú)關(guān)數(shù)據(jù)結(jié)構(gòu)和算法的最新進(jìn)展。
什么是“鎖無(wú)關(guān)(lock-free)”？
不
久前這個(gè)問(wèn)題正是我想要問(wèn)的。作為一個(gè)真正的主流多線程程序員，我對(duì)基于鎖的多線程算法并不感到陌生。在經(jīng)典的基于鎖的多線程程序設(shè)計(jì)中，只要你需要共享
某些數(shù)據(jù)，你就應(yīng)當(dāng)將對(duì)它的訪問(wèn)串行化。修改（共享）數(shù)據(jù)的操作必須以原子操作的形式出現(xiàn)，這樣才能保證沒(méi)有其它線程能在中途插一腳來(lái)破壞相應(yīng)數(shù)據(jù)的不變
式（invariant）。即便像++count_(count_是整型變量)這樣的簡(jiǎn)單操作也得加鎖，因?yàn)樵隽坎僮鲗?shí)際上是分三步進(jìn)行的：讀、改、寫（回），而這顯然不是原子的。
簡(jiǎn)而言之，在基于鎖的多線程編程中，你得確保任何針對(duì)共享數(shù)據(jù)的、且有可能導(dǎo)致競(jìng)爭(zhēng)條件（race conditions）的操作都被做成了原子操作（通過(guò)對(duì)一個(gè)互斥體（mutex）進(jìn)行加鎖解鎖）。從好的一面來(lái)說(shuō)，只要互斥體是在鎖狀態(tài)，你就可以放心地進(jìn)行任何操作，不用擔(dān)心其它線程會(huì)闖進(jìn)來(lái)搞壞你的共享數(shù)據(jù)。
然而，正是這種在互斥體的鎖狀態(tài)下可以為所欲為的事實(shí)同樣也帶來(lái)了問(wèn)題。例如，你可以在鎖期間讀鍵盤或進(jìn)行某些耗時(shí)較長(zhǎng)的I/O操
作，這便意味著其它想要占用你正占用著的互斥體的線程只能被晾在一旁等著。更糟的是，此時(shí)你可能會(huì)試圖對(duì)另一個(gè)互斥體進(jìn)行加鎖，后者彼時(shí)或許已經(jīng)被另一個(gè)
線程占用了，而這個(gè)線程倒過(guò)來(lái)又試圖去獲取已然被你的線程所占用的互斥體，如此一來(lái)兩個(gè)線程全都陷在那里動(dòng)彈不得，死鎖！
而
在鎖無(wú)關(guān)多線程編程的世界里，幾乎任何操作都是無(wú)法原子地完成的。只有很小一集操作可以被原子地進(jìn)行，這一限制使得鎖無(wú)關(guān)編程的難度大大地增加了。（實(shí)際
上，世界上肯定有不少鎖無(wú)關(guān)編程專家，而我則不在此列。不過(guò)幸運(yùn)的是，這篇文章中所提供的基本工具、內(nèi)容以及熱情可能會(huì)激發(fā)你成為一個(gè)這方面的專家。）鎖
無(wú)關(guān)編程帶來(lái)的好處是在線程進(jìn)展和線程交互方面，借助于鎖無(wú)關(guān)編程，你能夠?qū)€程的進(jìn)展和交互提供更好的保證。但話說(shuō)回來(lái)，剛剛我們所謂的“很小一集可以被原子地進(jìn)行的操作”又是指哪些操作呢？實(shí)際上，這個(gè)問(wèn)題相當(dāng)于，最少需要一集什么樣的原語(yǔ)才能夠允許我們實(shí)現(xiàn)出任何鎖無(wú)關(guān)的算法（如果存在這么一個(gè)“最小集”的話）？
如果你認(rèn)為這個(gè)問(wèn)題的基礎(chǔ)性使得它的解決者理當(dāng)獲得獎(jiǎng)賞的話，你并不是唯一一個(gè)這么認(rèn)為的。2003年，Maurice Herlihy因他在1991年發(fā)表的開創(chuàng)性論文“Wait-Free Synchronization”（ http://www.podc.org/dijkstra/2003.html）而獲得了分布式編程的Edsger W. Dijkstra獎(jiǎng)。在論文中，Herlihy證明了哪些原語(yǔ)對(duì)于構(gòu)造鎖無(wú)關(guān)數(shù)據(jù)結(jié)構(gòu)來(lái)說(shuō)是好的，哪些則是不好的。他的論述使得一些看似漂亮的硬件架構(gòu)突然變得一錢不值，同時(shí)他的論文還指明了在將來(lái)的硬件中應(yīng)當(dāng)實(shí)現(xiàn)哪些同步原語(yǔ)。
例如，Herlihy的論文指出，像test-and-set、swap、fetch-and-add、甚至原子隊(duì)列這樣的看似強(qiáng)大的工具都不足以良好地同步兩個(gè)以上的線程（這一結(jié)果很是令人驚訝，因?yàn)閹в性?/font>push和pop操作的隊(duì)列看上去提供了一個(gè)相當(dāng)強(qiáng)大的抽象）。從好的一面來(lái)說(shuō)，Herlihy同樣給出了一般性結(jié)論，他證明了一些簡(jiǎn)單的結(jié)構(gòu)就足以實(shí)現(xiàn)出任何針對(duì)任意數(shù)目的線程的鎖無(wú)關(guān)算法。
最簡(jiǎn)單、也是最普遍的一個(gè)通用原語(yǔ)就是CAS操作（Compare-And-Swap），這也是我一直使用的原語(yǔ)：
CODE:
template <class T>
bool CAS(T* addr, T expected, T value) {
if (*addr == expected) {
*addr = value;
return true;
}
return false;
}
CAS原語(yǔ)負(fù)責(zé)比較某個(gè)內(nèi)存地址處的內(nèi)容與一個(gè)期望值，如果比較成功則將該內(nèi)存地址處的內(nèi)容替換為一個(gè)新值。這整個(gè)操作是原子的。許多現(xiàn)代處理器都實(shí)現(xiàn)了不同位長(zhǎng)度的CAS或其等價(jià)原語(yǔ)（這里我用模板來(lái)表達(dá)它正是由于這個(gè)原因，我們可以假定一個(gè)具體的實(shí)現(xiàn)使用元編程來(lái)限制可能的T）。作為一個(gè)原則，CAS能夠操作的位數(shù)越多，使用它來(lái)實(shí)現(xiàn)鎖無(wú)關(guān)數(shù)據(jù)結(jié)構(gòu)就越容易。如今的32位處理器實(shí)現(xiàn)了64位的CAS，例如Intel匯編指令中稱它為CMPXCHG8（你得跟這些匯編助記符多親近親近）。
一點(diǎn)告誡
通常一篇C++文章中會(huì)伴隨著C++代碼片斷和示例。理想情況下這些代碼會(huì)是符合標(biāo)準(zhǔn)C++規(guī)范的，而且Generic<Programming>專欄的確盡量做到了這一點(diǎn)。
然而，當(dāng)文章涉及的內(nèi)容是多線程編程時(shí)，給出符合標(biāo)準(zhǔn)C++的示例代碼就是不可能的了，因?yàn)闃?biāo)準(zhǔn)C++中根本就沒(méi)有線程的概念，而你無(wú)法編碼不存在的東西。因此，這篇文章中的代碼某種意義上只不過(guò)是“偽碼”，而并非可移植的標(biāo)準(zhǔn)C++代碼。例如內(nèi)存屏障（memory barriers），對(duì)于本文中描述的算法來(lái)說(shuō)，真正的實(shí)現(xiàn)代碼要么是匯編寫的，要么得在C++代碼中到處插入所謂的“內(nèi)存屏障”（“內(nèi)存屏障”是一種處理器相關(guān)的機(jī)制，它能夠強(qiáng)制內(nèi)存讀寫的順序性）。為了不失討論重點(diǎn)，這里我并不打算對(duì)內(nèi)存屏障多作介紹，有興趣的讀者可以參考Butenhof的著作[3]，或者在下面的注中提到的一篇關(guān)于它的簡(jiǎn)單介紹[6]。為了方便討論，這里我假定我們的編譯器和硬件都沒(méi)有進(jìn)行過(guò)分的優(yōu)化（例如消除某些“冗余”的變量讀取，這在單線程環(huán)境下的確是個(gè)有效的優(yōu)化）。從技術(shù)上來(lái)講，這即是說(shuō)一個(gè)“順序一致”的模型，其中讀和寫操作的執(zhí)行順序跟它們?cè)谠创a中的順序是完全一樣的[8]。
等待無(wú)關(guān)（Wait-Free）/鎖無(wú)關(guān)（Lock-Free）與基于鎖（Lock-Based）的比較
一個(gè)“等待無(wú)關(guān)”的程序可以在有限步之內(nèi)結(jié)束，而不管其它線程的相對(duì)速度如何。
一個(gè)“鎖無(wú)關(guān)”的程序能夠確保執(zhí)行它的所有線程中至少有一個(gè)能夠繼續(xù)往下執(zhí)行。這便意味著有些線程可能會(huì)被任意地延遲，然而在每一步都至少有一個(gè)線程能夠往下執(zhí)行。因此這個(gè)系統(tǒng)作為一個(gè)整體總是在“前進(jìn)”的，盡管有些線程的進(jìn)度可能不如其它線程來(lái)得快。而基于鎖的程序則無(wú)法提供上述的任何保證。一旦任何線程持有了某個(gè)互斥體并處于等待狀態(tài)，那么其它任何想要獲取同一互斥體的線程就只好站著干瞪眼；一般來(lái)說(shuō)，基于鎖的算法無(wú)法擺脫“死鎖”或“活鎖”的
陰影，前者如兩個(gè)線程互相等待另一個(gè)所占有的互斥體，后者如兩個(gè)線程都試圖去避開另一個(gè)線程的鎖行為，就像兩個(gè)在狹窄走廊里面撞了個(gè)照面的家伙，都試圖去
給對(duì)方讓路，結(jié)果像跳交誼舞似的擺來(lái)擺去最終還是面對(duì)面走不過(guò)去。當(dāng)然，對(duì)于我們?nèi)藖?lái)說(shuō)，遇到這種情況打個(gè)哈哈就行了，但處理器卻不這么認(rèn)為，它會(huì)不知疲
倦地就這樣干下去直到你強(qiáng)制重啟。
等待無(wú)關(guān)和鎖無(wú)關(guān)算法的定義意味著它們有更多的優(yōu)點(diǎn)：
線程中止免疫：殺掉系統(tǒng)中的任何線程都不會(huì)導(dǎo)致其它線程被延遲。信號(hào)免疫：C和C++標(biāo)準(zhǔn)禁止在信號(hào)或異步中斷中調(diào)用某些系統(tǒng)例程（如malloc）。如果中斷與某個(gè)被中斷線程同時(shí)調(diào)用malloc的話，結(jié)果就會(huì)導(dǎo)致死鎖。而鎖無(wú)關(guān)例程則沒(méi)有這一問(wèn)題：線程可以自由地互相穿插執(zhí)行。
- 優(yōu)先級(jí)倒置免疫：所謂“優(yōu)先級(jí)倒置”就是指一個(gè)低優(yōu)先級(jí)線程持有了一個(gè)高優(yōu)先級(jí)線程所需要的互斥體。這種微妙的沖突必須由OS內(nèi)核來(lái)解決。而等待無(wú)關(guān)和鎖無(wú)關(guān)算法則對(duì)此免疫。
一個(gè)鎖無(wú)關(guān)的WRRM Map
寫專欄文章的好處之一就是你可以定義自己的縮寫，所以就讓我們來(lái)定義WRRM（Write Rarely Read Many）這一縮寫，一個(gè)WRRM Map是一個(gè)被讀比被寫的次數(shù)多得多的map。例如，對(duì)象工廠[1]，觀察者模式的許多具體實(shí)例[5]，以及一個(gè)將幣種跟匯率聯(lián)系在一起的map（許多時(shí)候你只是對(duì)它進(jìn)行讀取，而只有很少的時(shí)候才會(huì)更新），當(dāng)然還有許許多多其它的查找表。
WRRM Map可以通過(guò)std::map或“準(zhǔn)標(biāo)準(zhǔn)”的unordered_map（http://www.open-std.org/jtcl/sc22/wg21/docs/papers/2004/n1647.pdf）來(lái)予以實(shí)現(xiàn)，不過(guò)正如我在Modern C++ Design中所說(shuō)的，assoc_vector（一個(gè)已序的vector<pair>）也是一個(gè)不錯(cuò)的候選，因?yàn)樗酶滤俣葥Q取了查找速度。總而言之，鎖無(wú)關(guān)性質(zhì)是與具體的數(shù)據(jù)結(jié)構(gòu)選擇無(wú)關(guān)（正交）的；我們姑且就稱后者為Map<Key,Value>。同樣，出于這篇文章的意圖，當(dāng)我說(shuō)map時(shí)就是指那些提供了根據(jù)key來(lái)查找并能夠更新key-value對(duì)的表，下文將不再重申這一點(diǎn)。
讓我們來(lái)回顧一下一個(gè)基于鎖的WRRMMap是怎樣實(shí)現(xiàn)的：我們將一個(gè)Map對(duì)象與一個(gè)Mutex對(duì)象結(jié)合起來(lái)，像這樣：
CODE:
// WRRMMap的一個(gè)基于鎖的實(shí)現(xiàn)
template <class K, class V>
class WRRMMap {
Mutex mtx_;
Map<K, V> map_;
public:
V Lookup(const K& k) {
Lock lock(mtx_);
return map_[k];
}
void Update(const K& k,
const V& v) {
Lock lock(mtx_);
map_[k] = v;
}
};
為了避免所有權(quán)問(wèn)題以及無(wú)效引用問(wèn)題（這兩個(gè)問(wèn)題后面會(huì)給我們帶來(lái)大麻煩），Lookup按值返回其結(jié)果。這一做法雖說(shuō)穩(wěn)妥但有代價(jià)。每次查找都會(huì)導(dǎo)致對(duì)Mutex加鎖/解鎖，而實(shí)際上一是平行的查找并不需要相互加鎖，二是Update比Lookup發(fā)生的頻率要小得多。那么，現(xiàn)在就讓我們來(lái)實(shí)現(xiàn)一個(gè)更好的WRRMMap吧。
垃圾收集，你在何方？
對(duì)實(shí)現(xiàn)一個(gè)鎖無(wú)關(guān)的WRRMMap的第一番嘗試停在下面這幾個(gè)問(wèn)題上：
讀取操作(Read)沒(méi)有任何鎖。更新操作(Update)對(duì)整個(gè)map作一份拷貝，然后更新這份拷貝，最后再用這份拷貝來(lái)替換掉原來(lái)的舊map（通過(guò)CAS原語(yǔ)來(lái)進(jìn)行）。如果最后一步的CAS操作沒(méi)有成功的話，就循環(huán)嘗試“拷貝/更新/CAS回去”這一步驟直到成功。
- 由于CAS原語(yǔ)所能操作的字節(jié)數(shù)是有限制的，所以WRRMMap存放指向?qū)嶋HMap的指針，而不是一個(gè)Map。
CODE:
// WRRMMap的首個(gè)鎖無(wú)關(guān)的實(shí)現(xiàn)
// 只有當(dāng)你有GC的時(shí)候才行
template <class K, class V>
class WRRMMap {
Map<K, V>* pMap_;
public:
V Lookup (const K& k) {
// 瞧，沒(méi)有鎖！
return (*pMap_) [k];
}
void Update(const K& k,
const V& v) {
Map<K, V>* pNew = 0;
do {
Map<K, V>* pOld = pMap_;
delete pNew;
pNew = new Map<K, V>(*pOld);
(*pNew) [k] = v;
} while (!CAS(&pMap_, pOld, pNew));
// 別 delete pMap_;
}
};
這行得通！在一個(gè)循環(huán)當(dāng)中，Update()例程對(duì)整個(gè)map作了一份拷貝，并往該副本中加入了一個(gè)新項(xiàng)，最后再嘗試交換新舊兩個(gè)map的指針。這里，最后一步，一定要使用CAS原語(yǔ)而不是簡(jiǎn)單的賦值，這很關(guān)鍵，否則像下面這樣的一個(gè)執(zhí)行序列將會(huì)破壞該map：
線程A對(duì)該map作了一份副本線程B對(duì)該map作了一份副本并更新了副本線程A往其副本中加入新項(xiàng)
- 線程A用其改寫后的副本替換原有map，這里，線程A的改寫后的副本中沒(méi)有線程B所作的任何改動(dòng)。
而通過(guò)CAS，一切都能夠優(yōu)雅地完成，因?yàn)槊總€(gè)線程都相當(dāng)于作了如下的陳述：“假設(shè)該map自從我上次觀察它以來(lái)并沒(méi)有任何更動(dòng)，那么就進(jìn)行CAS（寫回改動(dòng)后的新map）。否則一切從頭來(lái)過(guò)。”
根據(jù)定義，這就使得Update成了一個(gè)鎖無(wú)關(guān)的算法，但它并不是等待無(wú)關(guān)的。例如，如果若干線程同時(shí)調(diào)用Update，那么它們每一個(gè)都可能會(huì)循環(huán)嘗試不確定的次數(shù)，然而總會(huì)有某個(gè)線程能夠確保成功更新該map，因而整體上的進(jìn)度總是在繼續(xù)的。另外，幸運(yùn)的是，Lookup是等待無(wú)關(guān)的。
在一個(gè)擁有垃圾收集的環(huán)境中，我們的工作就算完成了，而這篇文章也將在一片歡欣鼓舞中結(jié)束。然而，事實(shí)是我們并沒(méi)有垃圾收集，因而只得面對(duì)麻煩了。麻煩就是，我們不能簡(jiǎn)單地就將舊的pMap_扔掉（意即delete——譯注），如果正當(dāng)你試圖delete它的時(shí)候一幫其它線程沖上來(lái)想要訪問(wèn)它里面的數(shù)據(jù)（Lookup）該怎么辦呢？你是知道的，垃圾收集器可以訪問(wèn)所有線程的數(shù)據(jù)及私有棧，所以它對(duì)于“哪些pMap_所指的map不再被使用了”這個(gè)問(wèn)題有更清晰的認(rèn)識(shí)，而且它也能夠優(yōu)雅地將這些不再被使用的map清理掉。而如果沒(méi)有垃圾收集器的幫助，事情可就沒(méi)那么簡(jiǎn)單了。實(shí)際上，是難得多！而且看起來(lái)確定性的內(nèi)存歸還在鎖無(wú)關(guān)數(shù)據(jù)結(jié)構(gòu)方面是個(gè)基礎(chǔ)問(wèn)題。
寫鎖定(Write-Locked)的WRRM Map
為了弄清我們遇到的問(wèn)題有多棘手，讓我們先來(lái)試試用經(jīng)典的引用計(jì)數(shù)技術(shù)來(lái)實(shí)現(xiàn)WRRMMap，看看這有何不可。那么，考慮將一個(gè)引用計(jì)數(shù)器跟map的指針綁定在一起，并讓WRRMMap保存一個(gè)指向如此構(gòu)造出的數(shù)據(jù)結(jié)構(gòu)的指針。
CODE:
template <class K, class V>
class WRRMMap {
typedef std::pair<Map<K, V>*,
unsigned> Data;
Data* pData_;
...
};
嗯，看上去不賴。現(xiàn)在，Lookup會(huì)先遞增pData_->second，然后在map中進(jìn)行查找，最后再遞減pData_->second。當(dāng)pData_->second計(jì)數(shù)器的值下降到0的時(shí)候，pData_->first就可以被delete掉了，接著pData_自己也就可以被delete掉了。看起來(lái)簡(jiǎn)單穩(wěn)妥是不是，只不過(guò)…只不過(guò)它是幼稚的。試想下面這種情況，正當(dāng)某個(gè)線程注意到引用計(jì)數(shù)器的值下降到0并著手delete pData_時(shí)，另一個(gè)線程或另一堆線程插進(jìn)來(lái)拽住了垂死的pData_并
準(zhǔn)備從它進(jìn)行讀取！不管你怎么聰明地安排你的策略，你都逃不開一個(gè)基本的問(wèn)題：即要想讀取數(shù)據(jù)的指針，你得先遞增引用計(jì)數(shù)，但引用計(jì)數(shù)又必須得是你要讀取
的數(shù)據(jù)的一部分，因此倘不先讀取那個(gè)指針你就無(wú)法訪問(wèn)到該引用計(jì)數(shù)。這就好比一個(gè)將開關(guān)安放在其頂端的帶電鐵絲網(wǎng)：要想安全的爬上去你就得先將開關(guān)關(guān)掉，
但要想將開關(guān)關(guān)掉你就得先安全地爬上去啊！
那么，就讓我們來(lái)看看有沒(méi)有其它方法能夠正確地delete舊的map。一個(gè)方案是等待然后delete。考慮到隨著處理器時(shí)間（毫秒計(jì)）的推移，舊的pMap_對(duì)象會(huì)被越來(lái)越少的線程所訪問(wèn)（這是因?yàn)樾碌脑L問(wèn)是對(duì)新的map進(jìn)行的），于是一旦那些在CAS操作之前開始的Lookup操作結(jié)束了，對(duì)應(yīng)的（舊）pMap_也就可以去見閻王了。因此，我們的一個(gè)解決方案就是將舊的pMap_推入一個(gè)隊(duì)列，并由一個(gè)專門的清理線程，每隔，比如說(shuō)200毫秒，醒來(lái)一次，delete掉隊(duì)列中待得最久的一個(gè)pMap_。
但這并非一個(gè)理論上安全的方案（盡管從實(shí)際上來(lái)說(shuō)它可能絕大多數(shù)情況下都不會(huì)出什么意外）。比如說(shuō)，由于某種原因一個(gè)進(jìn)行Lookup的線程被延遲了，那么清理線程就會(huì)在該線程的眼皮子底下delete掉它正在訪問(wèn)的map。這可以通過(guò)總是給清理線程賦予一個(gè)比任何線程低的優(yōu)先級(jí)來(lái)予以避免，然而總的來(lái)說(shuō)，這個(gè)方案骨子里的劣根性是難以清除的。如果你也同意對(duì)于這樣一個(gè)技術(shù)我們沒(méi)法為其作任何正兒八經(jīng)的辯護(hù)的話，我們就繼續(xù)往下。
其它的方案[4]則依賴于一個(gè)擴(kuò)展的DCAS原子操作，該操作能夠compare-and-swap內(nèi)存中的兩個(gè)不必連續(xù)的字：
CODE:
template <class T1, class T2>
bool DCAS(T1* p1, T2* p2,
T1 e1, T2 e2,
T1 v1, T2 v2) {
if (*p1 == e1 && *p2 == e2) {
*p1 = v1; *p2 = v2;
return true;
}
return false;
}
這里所說(shuō)的兩個(gè)字當(dāng)然是指map的指針以及引用計(jì)數(shù)器。DCAS已經(jīng)由摩托羅拉68040處理器（非常低效地）實(shí)現(xiàn)了，然而其它處理器并沒(méi)有實(shí)現(xiàn)它。因此，基于DCAS的解決方案主要是被當(dāng)成理想方案來(lái)考慮的。
那么，在確定性析構(gòu)的大背景下，我們對(duì)于該問(wèn)題的嘗試首先是求助于不像DCAS那么要求苛刻的CAS2操作。再次說(shuō)明，許多32位的機(jī)器都實(shí)現(xiàn)了64位的CAS操作，被稱為CAS2（CAS2僅操作連續(xù)的字，所以它的能力顯然不及DCAS強(qiáng)大）。作為開始，讓我們將引用計(jì)數(shù)跟它所“保衛(wèi)”的map指針緊挨著存放在內(nèi)存中：
CODE:
template <class K, class V>
class WRRMMap {
typedef std::pair<Map<K, V>*,
unsigned> Data;
Data data_;
...
};
（注意，這一次，引用計(jì)數(shù)與它所保護(hù)的指針緊挨在一起了，這就消除了我們前面提到的“帶電鐵絲網(wǎng)-開關(guān)”的尷尬問(wèn)題。待會(huì)你就會(huì)看到這樣做的代價(jià)。）
那么，讓我們修改Lookup從而使其能夠在訪問(wèn)map之前先遞增引用計(jì)數(shù)，并在訪問(wèn)結(jié)束之后將其遞減回去。在下面的代碼片斷中，為了簡(jiǎn)潔起見，我并沒(méi)有考慮異常安全問(wèn)題（這個(gè)問(wèn)題可以用標(biāo)準(zhǔn)技術(shù)來(lái)解決）。
CODE:
V Lookup(const K& k) {
Data old;
Data fresh;
do {
old = data_;
fresh = old;
++fresh.second;
} while (CAS(&data_, old, fresh));
V temp = (*fresh.first)[k];
do {
old = data_;
fresh = old;
--fresh.second;
} while (CAS(&data_, old, fresh));
return temp;
}
最后，Update負(fù)責(zé)將該map替換為一個(gè)新的——僅當(dāng)其引用計(jì)數(shù)為1的時(shí)候。
CODE:
void Update(const K& k,
const V& v) {
Data old;
Data fresh;
old.second = 1;
fresh.first = 0;
fresh.second = 1;
Map<K, V>* last = 0;
do {
old.first = data_.first;
if (last != old.first) {
delete fresh.first;
fresh.first = new Map<K, V>(old.first);
fresh.first->insert(make_pair(k, v));
last = old.first;
}
} while (!CAS(&data_, old, fresh));
delete old.first; // whew
}
Update是這樣工作的：首先它定義old和fresh兩個(gè)變量（我們現(xiàn)在應(yīng)該非常熟悉這兩個(gè)變量了）。只不過(guò)這次old.second并非由data_.second賦值而來(lái)，而是始終為1。這意味著，Update會(huì)一直循環(huán)直到它等到data_.first指針的引用計(jì)數(shù)變成1（此時(shí)沒(méi)有任何線程在讀），并將其替換為另一個(gè)引用計(jì)數(shù)為1的新map的指針。說(shuō)白了這相當(dāng)于如下的陳述：“我將會(huì)把舊的map替換成一個(gè)更新過(guò)的，而且我會(huì)留神其它對(duì)于該map的更新，不過(guò)，僅當(dāng)現(xiàn)有map的引用計(jì)數(shù)為1的時(shí)候我才會(huì)進(jìn)行替換。”變量last及其相關(guān)代碼只不過(guò)是個(gè)優(yōu)化技巧：當(dāng)舊map并沒(méi)有被改動(dòng)，而只是其引用技術(shù)被改動(dòng)的時(shí)候，last可以幫助避免我們重建同一個(gè)map。
挺漂亮的手法，對(duì)不對(duì)？只可惜事實(shí)并非如此。Update現(xiàn)在實(shí)際上是基于鎖的：它得等待所有Lookup結(jié)束之后才能去更新該map。而鎖無(wú)關(guān)數(shù)據(jù)結(jié)構(gòu)的好處就在于一切都能夠如行云流水般進(jìn)行。特別地，在這種實(shí)現(xiàn)下，Update很容易就可以被餓死：你只需足夠頻繁地進(jìn)行Lookup就行了，讓它的引用計(jì)數(shù)永不降為1。總而言之，到目前為止我們得到的并非一個(gè)WRRM Map，而是一個(gè)WRRMBNTM（Write-Rarely-Read-Many-But-Not-Too-Many） Map。
結(jié)論
鎖無(wú)關(guān)數(shù)據(jù)結(jié)構(gòu)是大有前途的技術(shù)。它在線程中止、優(yōu)先級(jí)倒置以及信號(hào)安全等方面都有著良好的表現(xiàn)。它們永遠(yuǎn)不會(huì)死鎖或活鎖。在測(cè)試當(dāng)中，最近的鎖無(wú)關(guān)數(shù)據(jù)結(jié)構(gòu)遠(yuǎn)遠(yuǎn)超越了它們的基于鎖的版本[9]。然而，鎖無(wú)關(guān)編程的技巧性要求較高，特別是當(dāng)涉及到內(nèi)存釋放的時(shí)候。一個(gè)垃圾收集環(huán)境對(duì)此是大有裨益的，因?yàn)樗軌驎和２z視所有線程。不過(guò)，如果你想要確定性析構(gòu)的話，你就需要來(lái)自硬件或內(nèi)存分配器的特殊支持了。在下期的Generic<Programming>專欄中，我們將會(huì)考察優(yōu)化WRRMMap的途徑，使其在確定性析構(gòu)的基礎(chǔ)上實(shí)現(xiàn)鎖無(wú)關(guān)。
如果本期的垃圾收集map和WRRMBNTM Map并沒(méi)能滿足你的胃口的話，下面是個(gè)省錢小訣竅：Don't go watch the movie Alien vs. Predator, unless you like "so bad it's funny" movies.（譯注：one of the crap jokes I do not get）。
Acknowlegments
David
B. Held, Michael Maged, Larry Evans, and Scott Meyers provided very
helpful feedback. Also, Michael graciously agreed to coauthor the next
"Generic<Programming>" installment, which will greatly improve on
our WRRMap implementation.
References
[1] Alexandrescu, Andrei. Modern C++ Design, Addison-Wesley Longman, 2001.
[2] Alexandrescu, Andrei. "Generic<Programming>:yasli::vector Is On the Move," C/C++ Users Journal, June 2004.
[3] Butenhof, D.R. Programming with POSIX Threads, Addison-Wesley, 1997.
[4] Detlefs, David L., Paul A. Martin, Mark Moir, and Guy L. Steele, Jr. "Lock-free Reference Counting," Proceedings of the Twentieth Annual ACM Symposium on Principles of Distributed Computing, pages 190-199, ACM Press, 2001. ISBN 1-58113-383-9.
[5] Gamma, Erich, Richard Helm, Ralph E. Johnson, and John Vlissides. Design Patterns: Elements of Resusable Object-Oriented Software, Addison-Wesley, 1995.
[6] Meyers, Scott and Andrei Alexandrescu. "The Perils of Double-Checked Locking." Dr. Dobb's Journal, July 2004.
[7] Maged, Michael M. "Scalable Lock-free Dynamic Memory Allocation," Proceedings of the ACM SIGPLAN 2004 Conference on Programming Language Design and Implementation, pages 35-46. ACM Press, 2004. ISBN 1-58113-807-5.
[8] Robison, Arch. "Memory Consistency & .NET," Dr. Dobb's Journal, April 2003.
[9] Maged, Michael M. "CAS-Based Lock-Free Algorithm for Shared Deques," The Ninth Euro-Par Conference on Parallel Processing, LNCS volume 2790, pages 651-660, August 2003.