S.l.e!ep.￠%

新一篇:?鎖無(wú)關(guān)的數(shù)據(jù)結(jié)構(gòu)與Hazard指針——操縱有限的資源?|?舊一篇:?C++中的求值|副作用|序列點(diǎn)所導(dǎo)致的模糊語(yǔ)義

C/C++ Users Journal October, 2004

鎖無(wú)關(guān)的（ Lock-Free ）數(shù)據(jù)結(jié)構(gòu)

在避免死鎖的同時(shí)確保線程繼續(xù)

?

Andrei Alexandrescu

劉未鵬 譯

Andrei Alexandrescu 是華盛頓大學(xué)計(jì)算機(jī)科學(xué)系的在讀研究生，也是《 Modern C++ Design 》 一書(shū)的作者。他的郵箱是 andrei@metalanguage.com 。

在 Generic<Programming> 沉默了一期之后 ( 研究生的學(xué)業(yè)總是使人不得不投入百分之百的精力 ), 這一期文章的可寫(xiě)內(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)建不完全類(lèi)型的容器 ( 例如 list 、 vector 或 map) （順便再回顧一下 Yanslander 技術(shù) [2] ），這一任務(wù)可以借助于一些有趣的技巧來(lái)完成（當(dāng)下的標(biāo)準(zhǔn)庫(kù)容器并不能保證可存放不完全類(lèi)型的對(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)行的：讀、改、寫(xiě)（回），而這顯然不是原子的。

簡(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)題。例如，你可以在鎖期間讀鍵盤(pá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ā)表的開(kāi)創(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)突然變得一錢(qián)不值，同時(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)閹в性?/span> 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ǔ)：

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)代碼要么是匯編寫(xiě)的，要么得在 C++ 代碼中到處插入所謂的 “ 內(nèi)存屏障 ” （ “ 內(nèi)存屏障 ” 是一種處理器相關(guān)的機(jī)制，它能夠強(qiáng)制內(nèi)存讀寫(xiě)的順序性）。為了不失討論重點(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è) “ 順序一致 ” 的模型，其中讀和寫(xiě)操作的執(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è)線程都試圖去避開(kāi)另一個(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

寫(xiě)專欄文章的好處之一就是你可以定義自己的縮寫(xiě)，所以就讓我們來(lái)定義 WRRM （ Write Rarely Read Many ）這一縮寫(xiě)，一個(gè) WRRM Map 是一個(gè)被讀比被寫(xiě)的次數(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)，像這樣：

?

// 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ū)嶋H Map 的指針，而不是一個(gè) Map 。

?

// 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 用其改寫(xiě)后的副本替換原有 map ，這里，線程 A 的改寫(xiě)后的副本中沒(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 （寫(xiě)回改動(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)題。

寫(xiě)鎖定 (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)的指針。

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)行讀取！不管你怎么聰明地安排你的策略，你都逃不開(kāi)一個(gè)基本的問(wèn)題：即要想讀取數(shù)據(jù)的指針，你得先遞增引用計(jì)數(shù)，但引用計(jì)數(shù)又必須得是你要讀取的數(shù)據(jù)的一部分，因此倘不先讀取那個(gè)指針你就無(wú)法訪問(wèn)到該引用計(jì)數(shù)。這就好比一個(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 。考慮到隨著處理器時(shí)間（毫秒計(jì)）的推移，舊的 pMap_ 對(duì)象會(huì)被越來(lái)越少的線程所訪問(wèn)（這是因?yàn)樾碌脑L問(wèn)是對(duì)新的 map 進(jìn)行的），于是一旦那些在 CAS 操作之前開(kāi)始的 Lookup 操作結(jié)束了，對(duì)應(yīng)的（舊） pMap_ 也就可以去見(jiàn)閻王了。因此，我們的一個(gè)解決方案就是將舊的 pMap_ 推入一個(gè)隊(duì)列，并由一個(gè)專門(mén)的清理線程，每隔，比如說(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ù)的字：

?

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)大）。作為開(kāi)始，讓我們將引用計(jì)數(shù)跟它所 “ 保衛(wèi) ” 的 map 指針緊挨著存放在內(nèi)存中：

?

template <class K, class V>

class WRRMMap {

?? typedef std::pair<Map<K, V>*,

????? unsigned> Data;

?? Data data_;

?? ...

};

?

（注意，這一次，引用計(jì)數(shù)與它所保護(hù)的指針緊挨在一起了，這就消除了我們前面提到的 “ 帶電鐵絲網(wǎng) - 開(kāi)關(guān) ” 的尷尬問(wèn)題。待會(huì)你就會(huì)看到這樣做的代價(jià)。）

那么，讓我們修改 Lookup 從而使其能夠在訪問(wèn) map 之前先遞增引用計(jì)數(shù)，并在訪問(wèn)結(jié)束之后將其遞減回去。在下面的代碼片斷中，為了簡(jiǎn)潔起見(jiàn)，我并沒(méi)有考慮異常安全問(wèn)題（這個(gè)問(wèn)題可以用標(biāo)準(zhǔ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 負(fù)責(zé)將該 map 替換為一個(gè)新的 —— 僅當(dāng)其引用計(jì)數(shù)為 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è)變量（我們現(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è)省錢(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

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.

?

發(fā)表于 @ 2006年01月26日 01:15:00|評(píng)論(7 )|編輯

新一篇:?鎖無(wú)關(guān)的數(shù)據(jù)結(jié)構(gòu)與Hazard指針——操縱有限的資源?|?舊一篇:?C++中的求值|副作用|序列點(diǎn)所導(dǎo)致的模糊語(yǔ)義