C/C++ Users Journal October, 2004
鎖無(wú)關(guān)的（Lock-Free）數據結構
在避免死鎖的同時(shí)確保線(xiàn)程繼續
Andrei Alexandrescu
劉未鵬 譯
Andrei Alexandrescu是華盛頓大學(xué)計算機科學(xué)系的在讀研究生，也是《Modern C++ Design》一書(shū)的作者。他的郵箱是 andrei@metalanguage.com。
在Generic<Programming>沉默了一期之后(研究生的學(xué)業(yè)總是使人不得不投入百分之百的精力),這一期文章的可寫(xiě)內容突然多得令人似乎有點(diǎn)無(wú)所適從.例如,其中之一就是關(guān)于構造函數的討論,特別是轉發(fā)構造函數(forwarding constructor),(構造函數中的)異常處理,以及兩段式(two-stage)對象構造.另一個(gè)可選主題是創(chuàng )建不完全類(lèi)型的容器(例如list、vector或map)（順便再回顧一下Yanslander技術(shù)[2]），這一任務(wù)可以借助于一些有趣的技巧來(lái)完成（當下的標準庫容器并不能保證可存放不完全類(lèi)型的對象）。
雖說(shuō)以上兩個(gè)候選主題都挺誘人，不過(guò)跟所謂的“鎖無(wú)關(guān)（Lock-Free）”數據結構一比就只能靠邊站了，后者是多線(xiàn)程編程的極重要技術(shù)之一。在今年的“Programming Language Design and Implementation”大會(huì )(http://www.cs.umd.edu/~pugh/pldi04/)上，Michael Maged展示了世界上第一個(gè)鎖無(wú)關(guān)的(lock-free)內存分配器[7]，跟那些小心翼翼地設計的、基于鎖(lock-based)的，同時(shí)也更為復雜的內存分配器相比，Michael的鎖無(wú)關(guān)的內存分配器在諸多測試下都表現得更為優(yōu)越。
Michael的鎖無(wú)關(guān)內存分配器代表著(zhù)近來(lái)出現的許多鎖無(wú)關(guān)數據結構和算法的最新進(jìn)展。
什么是“鎖無(wú)關(guān)(lock-free)”？
不久前這個(gè)問(wèn)題正是我想要問(wèn)的。作為一個(gè)真正的主流多線(xiàn)程程序員，我對基于鎖的多線(xiàn)程算法并不感到陌生。在經(jīng)典的基于鎖的多線(xiàn)程程序設計中，只要你需要共享某些數據，你就應當將對它的訪(fǎng)問(wèn)串行化。修改（共享）數據的操作必須以原子操作的形式出現，這樣才能保證沒(méi)有其它線(xiàn)程能在中途插一腳來(lái)破壞相應數據的不變式（invariant）。即便像++count_(count_是整型變量)這樣的簡(jiǎn)單操作也得加鎖，因為增量操作實(shí)際上是分三步進(jìn)行的：讀、改、寫(xiě)（回），而這顯然不是原子的。
簡(jiǎn)而言之，在基于鎖的多線(xiàn)程編程中，你得確保任何針對共享數據的、且有可能導致競爭條件（race conditions）的操作都被做成了原子操作（通過(guò)對一個(gè)互斥體（mutex）進(jìn)行加鎖解鎖）。從好的一面來(lái)說(shuō)，只要互斥體是在鎖狀態(tài)，你就可以放心地進(jìn)行任何操作，不用擔心其它線(xiàn)程會(huì )闖進(jìn)來(lái)搞壞你的共享數據。
然而，正是這種在互斥體的鎖狀態(tài)下可以為所欲為的事實(shí)同樣也帶來(lái)了問(wèn)題。例如，你可以在鎖期間讀鍵盤(pán)或進(jìn)行某些耗時(shí)較長(cháng)的I/O操作，這便意味著(zhù)其它想要占用你正占用著(zhù)的互斥體的線(xiàn)程只能被晾在一旁等著(zhù)。更糟的是，此時(shí)你可能會(huì )試圖對另一個(gè)互斥體進(jìn)行加鎖，后者彼時(shí)或許已經(jīng)被另一個(gè)線(xiàn)程占用了，而這個(gè)線(xiàn)程倒過(guò)來(lái)又試圖去獲取已然被你的線(xiàn)程所占用的互斥體，如此一來(lái)兩個(gè)線(xiàn)程全都陷在那里動(dòng)彈不得，死鎖！
而在鎖無(wú)關(guān)多線(xiàn)程編程的世界里，幾乎任何操作都是無(wú)法原子地完成的。只有很小一集操作可以被原子地進(jìn)行，這一限制使得鎖無(wú)關(guān)編程的難度大大地增加了。（實(shí)際上，世界上肯定有不少鎖無(wú)關(guān)編程專(zhuān)家，而我則不在此列。不過(guò)幸運的是，這篇文章中所提供的基本工具、內容以及熱情可能會(huì )激發(fā)你成為一個(gè)這方面的專(zhuān)家。）鎖無(wú)關(guān)編程帶來(lái)的好處是在線(xiàn)程進(jìn)展和線(xiàn)程交互方面，借助于鎖無(wú)關(guān)編程，你能夠對線(xiàn)程的進(jìn)展和交互提供更好的保證。但話(huà)說(shuō)回來(lái)，剛剛我們所謂的“很小一集可以被原子地進(jìn)行的操作”又是指哪些操作呢？實(shí)際上，這個(gè)問(wèn)題相當于，最少需要一集什么樣的原語(yǔ)才能夠允許我們實(shí)現出任何鎖無(wú)關(guān)的算法（如果存在這么一個(gè)“最小集”的話(huà)）？
如果你認為這個(gè)問(wèn)題的基礎性使得它的解決者理當獲得獎賞的話(huà)，你并不是唯一一個(gè)這么認為的。2003年，Maurice Herlihy因他在1991年發(fā)表的開(kāi)創(chuàng )性論文“Wait-Free Synchronization”（ http://www.podc.org/dijkstra/2003.html）而獲得了分布式編程的Edsger W. Dijkstra獎。在論文中，Herlihy證明了哪些原語(yǔ)對于構造鎖無(wú)關(guān)數據結構來(lái)說(shuō)是好的，哪些則是不好的。他的論述使得一些看似漂亮的硬件架構突然變得一錢(qián)不值，同時(shí)他的論文還指明了在將來(lái)的硬件中應當實(shí)現哪些同步原語(yǔ)。
例如，Herlihy的論文指出，像test-and-set、swap、fetch-and-add、甚至原子隊列這樣的看似強大的工具都不足以良好地同步兩個(gè)以上的線(xiàn)程（這一結果很是令人驚訝，因為帶有原子push和pop操作的隊列看上去提供了一個(gè)相當強大的抽象）。從好的一面來(lái)說(shuō)，Herlihy同樣給出了一般性結論，他證明了一些簡(jiǎn)單的結構就足以實(shí)現出任何針對任意數目的線(xiàn)程的鎖無(wú)關(guān)算法。
最簡(jiǎn)單、也是最普遍的一個(gè)通用原語(yǔ)就是CAS操作（Compare-And-Swap），這也是我一直使用的原語(yǔ)：
template <class T>
bool CAS(T* addr, T expected, T value) {
if (*addr == expected) {
*addr = value;
return true;
}
return false;
}
CAS原語(yǔ)負責比較某個(gè)內存地址處的內容與一個(gè)期望值，如果比較成功則將該內存地址處的內容替換為一個(gè)新值。這整個(gè)操作是原子的。許多現代處理器都實(shí)現了不同位長(cháng)度的CAS或其等價(jià)原語(yǔ)（這里我用模板來(lái)表達它正是由于這個(gè)原因，我們可以假定一個(gè)具體的實(shí)現使用元編程來(lái)限制可能的T）。作為一個(gè)原則，CAS能夠操作的位數越多，使用它來(lái)實(shí)現鎖無(wú)關(guān)數據結構就越容易。如今的32位處理器實(shí)現了64位的CAS，例如Intel匯編指令中稱(chēng)它為CMPXCHG8（你得跟這些匯編助記符多親近親近）。
一點(diǎn)告誡
通常一篇C++文章中會(huì )伴隨著(zhù)C++代碼片斷和示例。理想情況下這些代碼會(huì )是符合標準C++規范的，而且Generic<Programming>專(zhuān)欄的確盡量做到了這一點(diǎn)。
然而，當文章涉及的內容是多線(xiàn)程編程時(shí)，給出符合標準C++的示例代碼就是不可能的了，因為標準C++中根本就沒(méi)有線(xiàn)程的概念，而你無(wú)法編碼不存在的東西。因此，這篇文章中的代碼某種意義上只不過(guò)是“偽碼”，而并非可移植的標準C++代碼。例如內存屏障（memory barriers），對于本文中描述的算法來(lái)說(shuō)，真正的實(shí)現代碼要么是匯編寫(xiě)的，要么得在C++代碼中到處插入所謂的“內存屏障”（“內存屏障”是一種處理器相關(guān)的機制，它能夠強制內存讀寫(xiě)的順序性）。為了不失討論重點(diǎn)，這里我并不打算對內存屏障多作介紹，有興趣的讀者可以參考Butenhof的著(zhù)作[3]，或者在下面的注中提到的一篇關(guān)于它的簡(jiǎn)單介紹[6]。為了方便討論，這里我假定我們的編譯器和硬件都沒(méi)有進(jìn)行過(guò)分的優(yōu)化（例如消除某些“冗余”的變量讀取，這在單線(xiàn)程環(huán)境下的確是個(gè)有效的優(yōu)化）。從技術(shù)上來(lái)講，這即是說(shuō)一個(gè)“順序一致”的模型，其中讀和寫(xiě)操作的執行順序跟它們在源代碼中的順序是完全一樣的[8]。
等待無(wú)關(guān)（Wait-Free）/鎖無(wú)關(guān)（Lock-Free）與基于鎖（Lock-Based）的比較
一個(gè)“等待無(wú)關(guān)”的程序可以在有限步之內結束，而不管其它線(xiàn)程的相對速度如何。
一個(gè)“鎖無(wú)關(guān)”的程序能夠確保執行它的所有線(xiàn)程中至少有一個(gè)能夠繼續往下執行。這便意味著(zhù)有些線(xiàn)程可能會(huì )被任意地延遲，然而在每一步都至少有一個(gè)線(xiàn)程能夠往下執行。因此這個(gè)系統作為一個(gè)整體總是在“前進(jìn)”的，盡管有些線(xiàn)程的進(jìn)度可能不如其它線(xiàn)程來(lái)得快。而基于鎖的程序則無(wú)法提供上述的任何保證。一旦任何線(xiàn)程持有了某個(gè)互斥體并處于等待狀態(tài)，那么其它任何想要獲取同一互斥體的線(xiàn)程就只好站著(zhù)干瞪眼；一般來(lái)說(shuō)，基于鎖的算法無(wú)法擺脫“死鎖”或“活鎖”的陰影，前者如兩個(gè)線(xiàn)程互相等待另一個(gè)所占有的互斥體，后者如兩個(gè)線(xiàn)程都試圖去避開(kāi)另一個(gè)線(xiàn)程的鎖行為，就像兩個(gè)在狹窄走廊里面撞了個(gè)照面的家伙，都試圖去給對方讓路，結果像跳交誼舞似的擺來(lái)擺去最終還是面對面走不過(guò)去。當然，對于我們人來(lái)說(shuō)，遇到這種情況打個(gè)哈哈就行了，但處理器卻不這么認為，它會(huì )不知疲倦地就這樣干下去直到你強制重啟。
等待無(wú)關(guān)和鎖無(wú)關(guān)算法的定義意味著(zhù)它們有更多的優(yōu)點(diǎn)：
一個(gè)鎖無(wú)關(guān)的WRRM Map
寫(xiě)專(zhuān)欄文章的好處之一就是你可以定義自己的縮寫(xiě)，所以就讓我們來(lái)定義WRRM（Write Rarely Read Many）這一縮寫(xiě)，一個(gè)WRRM Map是一個(gè)被讀比被寫(xiě)的次數多得多的map。例如，對象工廠(chǎng)[1]，觀(guān)察者模式的許多具體實(shí)例[5]，以及一個(gè)將幣種跟匯率聯(lián)系在一起的map（許多時(shí)候你只是對它進(jìn)行讀取，而只有很少的時(shí)候才會(huì )更新），當然還有許許多多其它的查找表。
WRRM Map可以通過(guò)std::map或“準標準”的unordered_map（http://www.open-std.org/jtcl/sc22/wg21/docs/papers/2004/n1647.pdf）來(lái)予以實(shí)現，不過(guò)正如我在Modern C++ Design中所說(shuō)的，assoc_vector（一個(gè)已序的vector<pair>）也是一個(gè)不錯的候選，因為它用更新速度換取了查找速度?？偠灾?，鎖無(wú)關(guān)性質(zhì)是與具體的數據結構選擇無(wú)關(guān)（正交）的；我們姑且就稱(chēng)后者為Map<Key,Value>。同樣，出于這篇文章的意圖，當我說(shuō)map時(shí)就是指那些提供了根據key來(lái)查找并能夠更新key-value對的表，下文將不再重申這一點(diǎn)。
讓我們來(lái)回顧一下一個(gè)基于鎖的WRRMMap是怎樣實(shí)現的：我們將一個(gè)Map對象與一個(gè)Mutex對象結合起來(lái)，像這樣：
// WRRMMap的一個(gè)基于鎖的實(shí)現
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;
}
};
為了避免所有權問(wèn)題以及無(wú)效引用問(wèn)題（這兩個(gè)問(wèn)題后面會(huì )給我們帶來(lái)大麻煩），Lookup按值返回其結果。這一做法雖說(shuō)穩妥但有代價(jià)。每次查找都會(huì )導致對Mutex加鎖/解鎖，而實(shí)際上一是平行的查找并不需要相互加鎖，二是Update比Lookup發(fā)生的頻率要小得多。那么，現在就讓我們來(lái)實(shí)現一個(gè)更好的WRRMMap吧。
垃圾收集，你在何方？
對實(shí)現一個(gè)鎖無(wú)關(guān)的WRRMMap的第一番嘗試停在下面這幾個(gè)問(wèn)題上：
// WRRMMap的首個(gè)鎖無(wú)關(guān)的實(shí)現
// 只有當你有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)當中，Update()例程對整個(gè)map作了一份拷貝，并往該副本中加入了一個(gè)新項，最后再?lài)L試交換新舊兩個(gè)map的指針。這里，最后一步，一定要使用CAS原語(yǔ)而不是簡(jiǎn)單的賦值，這很關(guān)鍵，否則像下面這樣的一個(gè)執行序列將會(huì )破壞該map：
而通過(guò)CAS，一切都能夠優(yōu)雅地完成，因為每個(gè)線(xiàn)程都相當于作了如下的陳述：“假設該map自從我上次觀(guān)察它以來(lái)并沒(méi)有任何更動(dòng)，那么就進(jìn)行CAS（寫(xiě)回改動(dòng)后的新map）。否則一切從頭來(lái)過(guò)。”
根據定義，這就使得Update成了一個(gè)鎖無(wú)關(guān)的算法，但它并不是等待無(wú)關(guān)的。例如，如果若干線(xiàn)程同時(shí)調用Update，那么它們每一個(gè)都可能會(huì )循環(huán)嘗試不確定的次數，然而總會(huì )有某個(gè)線(xiàn)程能夠確保成功更新該map，因而整體上的進(jìn)度總是在繼續的。另外，幸運的是，Lookup是等待無(wú)關(guān)的。
在一個(gè)擁有垃圾收集的環(huán)境中，我們的工作就算完成了，而這篇文章也將在一片歡欣鼓舞中結束。然而，事實(shí)是我們并沒(méi)有垃圾收集，因而只得面對麻煩了。麻煩就是，我們不能簡(jiǎn)單地就將舊的pMap_扔掉（意即delete——譯注），如果正當你試圖delete它的時(shí)候一幫其它線(xiàn)程沖上來(lái)想要訪(fǎng)問(wèn)它里面的數據（Lookup）該怎么辦呢？你是知道的，垃圾收集器可以訪(fǎng)問(wèn)所有線(xiàn)程的數據及私有棧，所以它對于“哪些pMap_所指的map不再被使用了”這個(gè)問(wèn)題有更清晰的認識，而且它也能夠優(yōu)雅地將這些不再被使用的map清理掉。而如果沒(méi)有垃圾收集器的幫助，事情可就沒(méi)那么簡(jiǎn)單了。實(shí)際上，是難得多！而且看起來(lái)確定性的內存歸還在鎖無(wú)關(guān)數據結構方面是個(gè)基礎問(wèn)題。
寫(xiě)鎖定(Write-Locked)的WRRM Map
為了弄清我們遇到的問(wèn)題有多棘手，讓我們先來(lái)試試用經(jīng)典的引用計數技術(shù)來(lái)實(shí)現WRRMMap，看看這有何不可。那么，考慮將一個(gè)引用計數器跟map的指針綁定在一起，并讓WRRMMap保存一個(gè)指向如此構造出的數據結構的指針。
template <class K, class V>
class WRRMMap {
typedef std::pair<Map<K, V>*,
unsigned> Data;
Data* pData_;
...
};
嗯，看上去不賴(lài)?，F在，Lookup會(huì )先遞增pData_->second，然后在map中進(jìn)行查找，最后再遞減pData_->second。當pData_->second計數器的值下降到0的時(shí)候，pData_->first就可以被delete掉了，接著(zhù)pData_自己也就可以被delete掉了?？雌饋?lái)簡(jiǎn)單穩妥是不是，只不過(guò)…只不過(guò)它是幼稚的。試想下面這種情況，正當某個(gè)線(xiàn)程注意到引用計數器的值下降到0并著(zhù)手delete pData_時(shí)，另一個(gè)線(xiàn)程或另一堆線(xiàn)程插進(jìn)來(lái)拽住了垂死的pData_并準備從它進(jìn)行讀??！不管你怎么聰明地安排你的策略，你都逃不開(kāi)一個(gè)基本的問(wèn)題：即要想讀取數據的指針，你得先遞增引用計數，但引用計數又必須得是你要讀取的數據的一部分，因此倘不先讀取那個(gè)指針你就無(wú)法訪(fǎng)問(wèn)到該引用計數。這就好比一個(gè)將開(kāi)關(guān)安放在其頂端的帶電鐵絲網(wǎng)：要想安全的爬上去你就得先將開(kāi)關(guān)關(guān)掉，但要想將開(kāi)關(guān)關(guān)掉你就得先安全地爬上去??！
那么，就讓我們來(lái)看看有沒(méi)有其它方法能夠正確地delete舊的map。一個(gè)方案是等待然后delete?？紤]到隨著(zhù)處理器時(shí)間（毫秒計）的推移，舊的pMap_對象會(huì )被越來(lái)越少的線(xiàn)程所訪(fǎng)問(wèn)（這是因為新的訪(fǎng)問(wèn)是對新的map進(jìn)行的），于是一旦那些在CAS操作之前開(kāi)始的Lookup操作結束了，對應的（舊）pMap_也就可以去見(jiàn)閻王了。因此，我們的一個(gè)解決方案就是將舊的pMap_推入一個(gè)隊列，并由一個(gè)專(zhuān)門(mén)的清理線(xiàn)程，每隔，比如說(shuō)200毫秒，醒來(lái)一次，delete掉隊列中待得最久的一個(gè)pMap_。
但這并非一個(gè)理論上安全的方案（盡管從實(shí)際上來(lái)說(shuō)它可能絕大多數情況下都不會(huì )出什么意外）。比如說(shuō)，由于某種原因一個(gè)進(jìn)行Lookup的線(xiàn)程被延遲了，那么清理線(xiàn)程就會(huì )在該線(xiàn)程的眼皮子底下delete掉它正在訪(fǎng)問(wèn)的map。這可以通過(guò)總是給清理線(xiàn)程賦予一個(gè)比任何線(xiàn)程低的優(yōu)先級來(lái)予以避免，然而總的來(lái)說(shuō)，這個(gè)方案骨子里的劣根性是難以清除的。如果你也同意對于這樣一個(gè)技術(shù)我們沒(méi)法為其作任何正兒八經(jīng)的辯護的話(huà)，我們就繼續往下。
其它的方案[4]則依賴(lài)于一個(gè)擴展的DCAS原子操作，該操作能夠compare-and-swap內存中的兩個(gè)不必連續的字：
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è)字當然是指map的指針以及引用計數器。DCAS已經(jīng)由摩托羅拉68040處理器（非常低效地）實(shí)現了，然而其它處理器并沒(méi)有實(shí)現它。因此，基于DCAS的解決方案主要是被當成理想方案來(lái)考慮的。
那么，在確定性析構的大背景下，我們對于該問(wèn)題的嘗試首先是求助于不像DCAS那么要求苛刻的CAS2操作。再次說(shuō)明，許多32位的機器都實(shí)現了64位的CAS操作，被稱(chēng)為CAS2（CAS2僅操作連續的字，所以它的能力顯然不及DCAS強大）。作為開(kāi)始，讓我們將引用計數跟它所“保衛”的map指針緊挨著(zhù)存放在內存中：
template <class K, class V>
class WRRMMap {
typedef std::pair<Map<K, V>*,
unsigned> Data;
Data data_;
...
};
（注意，這一次，引用計數與它所保護的指針緊挨在一起了，這就消除了我們前面提到的“帶電鐵絲網(wǎng)-開(kāi)關(guān)”的尷尬問(wèn)題。待會(huì )你就會(huì )看到這樣做的代價(jià)。）
那么，讓我們修改Lookup從而使其能夠在訪(fǎng)問(wèn)map之前先遞增引用計數，并在訪(fǎng)問(wèn)結束之后將其遞減回去。在下面的代碼片斷中，為了簡(jiǎn)潔起見(jiàn)，我并沒(méi)有考慮異常安全問(wèn)題（這個(gè)問(wèn)題可以用標準技術(shù)來(lái)解決）。
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負責將該map替換為一個(gè)新的——僅當其引用計數為1的時(shí)候。
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è)變量（我們現在應該非常熟悉這兩個(gè)變量了）。只不過(guò)這次old.second并非由data_.second賦值而來(lái)，而是始終為1。這意味著(zhù)，Update會(huì )一直循環(huán)直到它等到data_.first指針的引用計數變成1（此時(shí)沒(méi)有任何線(xiàn)程在讀），并將其替換為另一個(gè)引用計數為1的新map的指針。說(shuō)白了這相當于如下的陳述：“我將會(huì )把舊的map替換成一個(gè)更新過(guò)的，而且我會(huì )留神其它對于該map的更新，不過(guò)，僅當現有map的引用計數為1的時(shí)候我才會(huì )進(jìn)行替換。”變量last及其相關(guān)代碼只不過(guò)是個(gè)優(yōu)化技巧：當舊map并沒(méi)有被改動(dòng)，而只是其引用技術(shù)被改動(dòng)的時(shí)候，last可以幫助避免我們重建同一個(gè)map。
挺漂亮的手法，對不對？只可惜事實(shí)并非如此。Update現在實(shí)際上是基于鎖的：它得等待所有Lookup結束之后才能去更新該map。而鎖無(wú)關(guān)數據結構的好處就在于一切都能夠如行云流水般進(jìn)行。特別地，在這種實(shí)現下，Update很容易就可以被餓死：你只需足夠頻繁地進(jìn)行Lookup就行了，讓它的引用計數永不降為1?？偠灾?，到目前為止我們得到的并非一個(gè)WRRM Map，而是一個(gè)WRRMBNTM（Write-Rarely-Read-Many-But-Not-Too-Many） Map。
結論
鎖無(wú)關(guān)數據結構是大有前途的技術(shù)。它在線(xiàn)程中止、優(yōu)先級倒置以及信號安全等方面都有著(zhù)良好的表現。它們永遠不會(huì )死鎖或活鎖。在測試當中，最近的鎖無(wú)關(guān)數據結構遠遠超越了它們的基于鎖的版本[9]。然而，鎖無(wú)關(guān)編程的技巧性要求較高，特別是當涉及到內存釋放的時(shí)候。一個(gè)垃圾收集環(huán)境對此是大有裨益的，因為它能夠暫停并檢視所有線(xiàn)程。不過(guò)，如果你想要確定性析構的話(huà)，你就需要來(lái)自硬件或內存分配器的特殊支持了。在下期的Generic<Programming>專(zhuān)欄中，我們將會(huì )考察優(yōu)化WRRMMap的途徑，使其在確定性析構的基礎上實(shí)現鎖無(wú)關(guān)。
如果本期的垃圾收集map和WRRMBNTM Map并沒(méi)能滿(mǎn)足你的胃口的話(huà)，下面是個(gè)省錢(qián)小訣竅：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
DavidB. Held, Michael Maged, Larry Evans, and Scott Meyers provided veryhelpful feedback. Also, Michael graciously agreed to coauthor the next"Generic<Programming>" installment, which will greatly improve onour 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.
聯(lián)系客服
