在避免死鎖的同時確定線程繼續

C/C++ Users Journal October, 2004

鎖無關的（Lock-Free）資料結構

在避免死鎖的同時確定線程繼續

Andrei Alexandrescu

劉未鵬 譯

Andrei Alexandrescu是華盛頓大學計算機科學系的在讀研究所學生，也是《Modern C++ Design》一書的作者。他的郵箱是 [email protected]。

在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），這也是我一直使用的原語：

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對象結合起來，像這樣：

// 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。

// 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儲存一個指向如此構造出的資料結構的指針。

template <class K, class V>

class WRRMMap {

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

      unsigned> Data;

   Data* pData_;

   ...

};

嗯，看上去不賴。現在，Lookup會先遞增pData_->second，然後在map中進行查找，最後再遞減pData_->second。當pData_->second計數器的值下降到0的時候，pData_->first就可以被delete掉了，接着pData_自己也就可以被delete掉了。看起來簡單穩妥是不是，隻不過…隻不過它是幼稚的。試想下面這種情況，正當某個線程注意到引用計數器的值下降到0并着手delete pData_時，另一個線程或另一堆線程插進來拽住了垂死的pData_并 準備從它進行讀取！不管你怎麼聰明地安排你的政策，你都逃不開一個基本的問題：即要想讀取資料的指針，你得先遞增引用計數，但引用計數又必須得是你要讀取 的資料的一部分，是以倘不先讀取那個指針你就無法通路到該引用計數。這就好比一個将開關安放在其頂端的帶電鐵絲網：要想安全的爬上去你就得先将開關關掉， 但要想将開關關掉你就得先安全地爬上去啊！

那麼，就讓我們來看看有沒有其它方法能夠正确地delete舊的map。一個方案是等待然後delete。考慮到随着處理器時間（毫秒計）的推移，舊的pMap_對象會被越來越少的線程所通路（這是因為新的通路是對新的map進行的），于是一旦那些在CAS操作之前開始的Lookup操作結束了，對應的（舊）pMap_也就可以去見閻王了。是以，我們的一個解決方案就是将舊的pMap_推入一個隊列，并由一個專門的清理線程，每隔，比如說200毫秒，醒來一次，delete掉隊列中待得最久的一個pMap_。

但這并非一個理論上安全的方案（盡管從實際上來說它可能絕大多數情況下都不會出什麼意外）。比如說，由于某種原因一個進行Lookup的線程被延遲了，那麼清理線程就會在該線程的眼皮子底下delete掉它正在通路的map。這可以通過總是給清理線程賦予一個比任何線程低的優先級來予以避免，然而總的來說，這個方案骨子裡的劣根性是難以清除的。如果你也同意對于這樣一個技術我們沒法為其作任何正兒八經的辯護的話，我們就繼續往下。

其它的方案[4]則依賴于一個擴充的DCAS原子操作，該操作能夠compare-and-swap記憶體中的兩個不必連續的字：

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指針緊挨着存放在記憶體中：

template <class K, class V>

class WRRMMap {

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

      unsigned> Data;

   Data data_;

   ...

};

（注意，這一次，引用計數與它所保護的指針緊挨在一起了，這就消除了我們前面提到的“帶電鐵絲網-開關”的尴尬問題。待會你就會看到這樣做的代價。）

那麼，讓我們修改Lookup進而使其能夠在通路map之前先遞增引用計數，并在通路結束之後将其遞減回去。在下面的代碼片斷中，為了簡潔起見，我并沒有考慮異常安全問題（這個問題可以用标準技術來解決）。

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的時候。

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.