無鎖編程的探索與研究

郭加盛 李健北京工業大學計算機學院 北京 100124

0 前言

在計算機多核技術迅速發展的時代，線程的優勢越來越明顯，多線程的學習成為每個程序員必備的基礎。但在實際開發過程中，越來越多的異常，越來越多的死鎖現象讓每個程序員崩潰不已，線程與鎖的問題凸顯在每個程序員的面前。

線程和進程的區別在于，子進程和父進程有不同的代碼和數據空間，而多個線程則共享數據空間，每個線程有自己的執行堆棧和程序計數器為其執行上下文。多線程主要是為了節約CPU時間，發揮利用，根據具體情況而定。線程的運行中需要使用計算機的內存資源和CPU。

在多道程序設計的環境下，多個進程競爭同一資源的現象時有發生。當進程申請的資源被其他進程占用時，就有可能發生死鎖。死鎖的概念比較抽象，簡單理解，每個汽車都是一個資源，他們都在申請路口這個資源，錯誤！未找到引用源。就生動的描述了死鎖的現象。

1 基于鎖的傳統編程技術

作為一個程序員，我們對基于鎖的多線程解決方案并不陌生。經典基于鎖的多數據操作必須以原子操作的形式出現，這樣才能保證在本線程執行的過程中沒有其它線程來破壞相應數據的一致性，即便像“++count”這樣的簡單操作也得加鎖，因為增量操作實際上是分三步進行的：讀、改、寫(回)，而這顯然不是原子的。

簡而言之，在基于鎖的多線程編程中，你需要確保任何針對共享數據的、且有可能導致競爭條件的操作都被做成了原子操作(通過對一個 mutex或 lock進行加鎖解鎖，參見Semaphore與Mutex的關系)。從好的一面來說，只要mutex是在鎖狀態，你就可以放心地進行任何操作，不用擔心其它線程會闖進來破壞你共享數據的一致性。

2 基于鎖的傳統編程技術的缺點

正是這種在mutex的鎖狀態下可以隨心所欲操作內存的情況帶來了問題。例如，你可以在鎖期間讀鍵盤或進行某些耗時較長的I/O操作，這便意味著其他需要某些共享資源的“互斥”的線程只能被block掉。當然，死鎖的問題也很嚴重，嚴重到我們甚至無法在很短的篇幅中描述它的危害。

基于鎖編程的另一個缺點是，在多處理器、多內存通道的環境中，CPU計算和內存讀取都并非必須是串行化的。因此，基于鎖編程的強行串行化極大影響了這些程序在并行環境中的性能表現，因為內存控制器根本無法將這種程序自動處理成為并行的。

3 無鎖編程(lock-free)技術

對于線程加鎖一般分為四個級別，根據龐雜程度、加鎖力度、運行速度等進行劃分，結構如圖1死鎖層級圖。我們可以看到lock-free技術復雜度較高。

Lock-free這個單詞和基于鎖(lock-base)相對應，中文翻譯的話，lock-free可以翻譯成為“無鎖編程”或者“鎖無關”，當然，國外的研究也經常使用low-lock這個單詞。這是因為真正的完全“無鎖”幾乎是不可能的，所以，lock-free更多的是強調減少鎖的使用。

既然是減少鎖的使用，那么少到什么程度呢？事實上，在實現良好的lock-free系統中，只有極少的系統級組件才不得不使用鎖，而用戶級的組件，則使用不同的算法和邏輯抽象，將鎖的數量減少到零。

圖1 死鎖層級圖

4 無鎖編程技術的優缺點

在鎖無關的多線程編程中，幾乎任何操作都是無法原子地完成的。這帶來了很多好處。

（1）對于并行環境極其有利，不需要過多的改進就能夠在并行環境中得到很好的性能提升；

（2）基本消除了死鎖帶來的問題；

（3）線程間通訊變得極其便利，因為不需考慮共享數據的訪問是否會被block掉。

當然，帶來的缺點也是顯而易見的，對于我們這些習慣于基于鎖技術處理多線程共享數據問題的程序員來說，lock-free編程帶來的難度很大，很多程序員幾乎無法在第一次就將一個lock-free程序寫正確。

另一個問題是，在系統級組件中，終究需要一些原子操作，那么，多大的一個操作閉包才是滿足lock-free編程的最小集呢？對于這個問題，Maurice Herlihy在1991年發表了論文“Wait-Free Synchronization”提出了CAS原語操作，當然這些問題超出了本文的范疇。

5 無鎖編程技術與其他鎖概念的比較

這樣一些概念常見于編程中：等待無關(wait-free)、鎖無關(lock-free)與基于鎖(lock-base)。

一個“等待無關”的程序可以在有限步之內結束，而不管其它線程的相對速度如何。

一個“鎖無關”的程序能夠確保執行它的所有線程中至少有一個能夠繼續往下執行。這便意味著有些線程可能會被任意地延遲，然而在每一步都至少有一個線程能夠往下執行。因此這個系統作為一個整體總是在“前進”的，盡管有些線程的進度可能不如其它線程來得快。

一個“基于鎖”的程序則無法提供上述的任何保證。一旦任何線程持有了某個mutex并處于等待狀態，那么其它任何想要獲取同一mutex的線程就必須block；一般來說，基于鎖的算法無法擺脫死鎖的可能，因此，除去程序員自己保證不發生死鎖以及系統內核態部分加入死鎖檢測外，對于死鎖沒有其他任何處置的方法。

等待無關和鎖無關算法的定義意味著它們有更多的優點：

（1）線程終止免疫：一般情況下，殺掉系統中的任何線程都不會導致其它線程被延遲；

（2）信號免疫：C和C++標準禁止在信號或異步中斷中調用某些系統例程(如 malloc)。如果中斷與某個被中斷線程同時調用malloc的話，結果就會導致死鎖。而鎖無關例程則沒有這一問題：線程可以自由地互相穿插執行；

（3）優先級倒置免疫：所謂“優先級倒置”就是指一個低優先級線程持有了一個高優先級線程所需要的互斥體。這種微妙的沖突必須由OS內核來解決。而等待無關和鎖無關算法則對此免疫。

6 總結

在開發過程中注重無鎖編程，減少多線程程序的死鎖情況，開發出更加優雅的多線程程序，需要不斷地進行學習、訓練。隨著多核處理器的發展，多核多線程程序將更多的受到人們的追捧，而無鎖編程作為多核多線程中的熱點話題，也將越來越受到程序員的重視。

[1](孟加拉)阿克特(Akhter，S.),(美)羅伯茨(Roberts，J.)著,李寶峰,富弘毅,李韜譯.多核程序設計技術——通過軟件多線程提升性能.電子工業出版社.2007.

[2](美)Abraham Silberschatz, Peter Baer Galvin 著,鄭扣根譯操作系統概念.2004.

[3]周偉明.多核計算與程序設計.華中科技大學出版社.2009.

[4](美)仁達敬(Reinders,J)著.聶雪軍等譯.Intel Threading Building Blocks編程指南.機械工業出版社.2009.

[5](美)瓦格納著,陳黎夫譯.More Effective C#中文版——改善C#程序的50個具體辦法人民郵電出版社.2010.

[6](美)休斯著，周良忠譯. C++面向對象多線程編程.人民郵電出版社.2003.