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