透過(guò)Linux內核看無(wú)鎖編程

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

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

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

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

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

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

Wait-free

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

Lock-free

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

Obstruction-free

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

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

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

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

清單1。CAS偽碼

BoolCAS(T*addr，Texpected，TnewValue)

{

if(*addr==expected)

{

*addr=newValue;

returntrue;

}

else

returnfalse;

}

在實(shí)際開(kāi)發(fā)過(guò)程中，利用CAS進(jìn)行同步，代碼如下所示：

清單2。CAS實(shí)際操作

do{

備份舊數據；

基于舊數據構造新數據；

}while(！CAS(內存地址，備份的舊數據，新數據))

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

加鎖的層級

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

圖1。加鎖層級

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

Linux內核中的無(wú)鎖分析

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

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

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

清單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);