無鎖編程的探索與研究

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

0 前言

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

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

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

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

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

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

2 基于鎖的傳統(tǒng)編程技術(shù)的缺點(diǎn)

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

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

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

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

Lock-free這個(gè)單詞和基于鎖(lock-base)相對應(yīng)，中文翻譯的話，lock-free可以翻譯成為“無鎖編程”或者“鎖無關(guān)”，當(dāng)然，國外的研究也經(jīng)常使用low-lock這個(gè)單詞。這是因?yàn)檎嬲耐耆盁o鎖”幾乎是不可能的，所以，lock-free更多的是強(qiáng)調(diào)減少鎖的使用。

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

圖1 死鎖層級(jí)圖

4 無鎖編程技術(shù)的優(yōu)缺點(diǎn)

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

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

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

（3）線程間通訊變得極其便利，因?yàn)椴恍杩紤]共享數(shù)據(jù)的訪問是否會(huì)被block掉。

當(dāng)然，帶來的缺點(diǎn)也是顯而易見的，對于我們這些習(xí)慣于基于鎖技術(shù)處理多線程共享數(shù)據(jù)問題的程序員來說，lock-free編程帶來的難度很大，很多程序員幾乎無法在第一次就將一個(gè)lock-free程序?qū)懻_。

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

5 無鎖編程技術(shù)與其他鎖概念的比較

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

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

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

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

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

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

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

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

6 總結(jié)

在開發(fā)過程中注重?zé)o鎖編程，減少多線程程序的死鎖情況，開發(fā)出更加優(yōu)雅的多線程程序，需要不斷地進(jìn)行學(xué)習(xí)、訓(xùn)練。隨著多核處理器的發(fā)展，多核多線程程序?qū)⒏嗟氖艿饺藗兊淖放?，而無鎖編程作為多核多線程中的熱點(diǎn)話題，也將越來越受到程序員的重視。

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

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

[3]周偉明.多核計(jì)算與程序設(shè)計(jì).華中科技大學(xué)出版社.2009.

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

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

[6](美)休斯著，周良忠譯. C++面向?qū)ο蠖嗑€程編程.人民郵電出版社.2003.