透過Linux內(nèi)核看無鎖編程

多核多線程已經(jīng)成為當下一個時髦的話題，而無鎖編程更是這個時髦話題中的熱點話題。Linux內(nèi)核可能是當今最大最復雜的并行程序之一，為我們分析多核多線程提供了絕佳的范例。內(nèi)核設計者已經(jīng)將最新的無鎖編程技術(shù)帶進了2。6系統(tǒng)內(nèi)核中，本文以2。6。10版本為藍本，帶領(lǐng)您領(lǐng)略多核多線程編程的真諦，窺探無鎖編程的奧秘，體味大師們的高雅設計！

非阻塞型同步(Non-blockingSynchronization)簡介

如何正確有效的保護共享數(shù)據(jù)是編寫并行程序必須面臨的一個難題，通常的手段就是同步。同步可分為阻塞型同步（BlockingSynchronization）和非阻塞型同步（Non-blockingSynchronization）。

阻塞型同步是指當一個線程到達臨界區(qū)時，因另外一個線程已經(jīng)持有訪問該共享數(shù)據(jù)的鎖，從而不能獲取鎖資源而阻塞，直到另外一個線程釋放鎖。常見的同步原語有mutex、semaphore等。如果同步方案采用不當，就會造成死鎖（deadlock），活鎖（livelock）和優(yōu)先級反轉(zhuǎn)（priorityinversion），以及效率低下等現(xiàn)象。

為了降低風險程度和提高程序運行效率，業(yè)界提出了不采用鎖的同步方案，依照這種設計思路設計的算法稱為非阻塞型算法，其本質(zhì)特征就是停止一個線程的執(zhí)行不會阻礙系統(tǒng)中其他執(zhí)行實體的運行。

當今比較流行的Non-blockingSynchronization實現(xiàn)方案有三種：

Wait-free

Wait-free是指任意線程的任何操作都可以在有限步之內(nèi)結(jié)束，而不用關(guān)心其它線程的執(zhí)行速度。Wait-free是基于per-thread的，可以認為是starvation-free的。非常遺憾的是實際情況并非如此，采用Wait-free的程序并不能保證starvation-free，同時內(nèi)存消耗也隨線程數(shù)量而線性增長。目前只有極少數(shù)的非阻塞算法實現(xiàn)了這一點。

Lock-free

Lock-Free是指能夠確保執(zhí)行它的所有線程中至少有一個能夠繼續(xù)往下執(zhí)行。由于每個線程不是starvation-free的，即有些線程可能會被任意地延遲，然而在每一步都至少有一個線程能夠往下執(zhí)行，因此系統(tǒng)作為一個整體是在持續(xù)執(zhí)行的，可以認為是system-wide的。所有Wait-free的算法都是Lock-Free的。

Obstruction-free

Obstruction-free是指在任何時間點，一個孤立運行線程的每一個操作可以在有限步之內(nèi)結(jié)束。只要沒有競爭，線程就可以持續(xù)運行。一旦共享數(shù)據(jù)被修改，Obstruction-free要求中止已經(jīng)完成的部分操作，并進行回滾。所有Lock-Free的算法都是Obstruction-free的。

綜上所述，不難得出Obstruction-free是Non-blockingsynchronization中性能最差的，而Wait-free性能是最好的，但實現(xiàn)難度也是最大的，因此Lock-free算法開始被重視，并廣泛運用于當今正在運行的程序中，比如linux內(nèi)核。

一般采用原子級的read-modify-write原語來實現(xiàn)Lock-Free算法，其中LL和SC是Lock-Free理論研究領(lǐng)域的理想原語，但實現(xiàn)這些原語需要CPU指令的支持，非常遺憾的是目前沒有任何CPU直接實現(xiàn)了SC原語。根據(jù)此理論，業(yè)界在原子操作的基礎(chǔ)上提出了著名的CAS（Compare-And-Swap）操作來實現(xiàn)Lock-Free算法，Intel實現(xiàn)了一條類似該操作的指令：cmpxchg8。

CAS原語負責將某處內(nèi)存地址的值（1個字節(jié)）與一個期望值進行比較，如果相等，則將該內(nèi)存地址處的值替換為新值，CAS操作偽碼描述如下：

清單1。CAS偽碼

BoolCAS(T*addr，Texpected，TnewValue)

{

if(*addr==expected)

{

*addr=newValue;

returntrue;

}

else

returnfalse;

}

在實際開發(fā)過程中，利用CAS進行同步，代碼如下所示：

清單2。CAS實際操作

do{

備份舊數(shù)據(jù)；

基于舊數(shù)據(jù)構(gòu)造新數(shù)據(jù)；

}while(！CAS(內(nèi)存地址，備份的舊數(shù)據(jù)，新數(shù)據(jù)))

就是指當兩者進行比較時，如果相等，則證明共享數(shù)據(jù)沒有被修改，替換成新值，然后繼續(xù)往下運行；如果不相等，說明共享數(shù)據(jù)已經(jīng)被修改，放棄已經(jīng)所做的操作，然后重新執(zhí)行剛才的操作。容易看出CAS操作是基于共享數(shù)據(jù)不會被修改的假設，采用了類似于數(shù)據(jù)庫的commit-retry的模式。當同步?jīng)_突出現(xiàn)的機會很少時，這種假設能帶來較大的性能提升。

加鎖的層級

根據(jù)復雜程度、加鎖粒度及運行速度，可以得出如下圖所示的鎖層級：

圖1。加鎖層級

其中標注為紅色字體的方案為Blockingsynchronization，黑色字體為Non-blockingsynchronization。Lock-based和Lockless-based兩者之間的區(qū)別僅僅是加鎖粒度的不同。圖中最底層的方案就是大家經(jīng)常使用的mutex和semaphore等方案，代碼復雜度低，但運行效率也最低。

Linux內(nèi)核中的無鎖分析

Linux內(nèi)核可能是當今最大最復雜的并行程序之一，它的并行主要來至于中斷、內(nèi)核搶占及SMP等。內(nèi)核設計者們?yōu)榱瞬粩嗵岣週inux內(nèi)核的效率，從全局著眼，逐步廢棄了大內(nèi)核鎖來降低鎖的粒度；從細處下手，不斷對局部代碼進行優(yōu)化，用無鎖編程替代基于鎖的方案，如seqlock及RCU等；不斷減少鎖沖突程度、降低等待時間，如Double-checkedlocking和原子鎖等。

無論什么時候當臨界區(qū)中的代碼僅僅需要加鎖一次，同時當其獲取鎖的時候必須是線程安全的，此時就可以利用Double-checkedLocking模式來減少鎖競爭和加鎖載荷。目前Double-checkedLocking已經(jīng)廣泛應用于單例(Singleton)模式中。內(nèi)核設計者基于此思想，巧妙的將Double-checkedLocking方法運用于內(nèi)核代碼中。

當一個進程已經(jīng)僵死，即進程處于TASK_ZOMBIE狀態(tài)，如果父進程調(diào)用waitpid()系統(tǒng)調(diào)用時，父進程需要為子進程做一些清理性的工作，代碼如下所示：

清單3。少鎖操作

984staticintwait_task_zombie(task_t*p，intnoreap，

985structsiginfo__user*infop，

986int__user*stat_addr，structrusage__user*ru)

987{

……

1103if(p->real_parent！=p->parent){

1104write_lock_irq(tasklist_lock);