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

0 前言

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

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

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

1 基于鎖的傳統(tǒng)編程技術

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

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

2 基于鎖的傳統(tǒng)編程技術的缺點

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

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

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

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

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

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

圖1 死鎖層級圖

4 無鎖編程技術的優(yōu)缺點

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6 總結

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

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

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

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

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

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

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