透過Linux內核看無鎖編程

1105/*Double-checkwithlockheld。*/

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

1107__ptrace_unlink(p);

1108//TODO：isthissafe？

1109p->exit_state=EXIT_ZOMBIE;

……

1120}

1121write_unlock_irq(tasklist_lock);

1122}

……

1127}

如果將write_lock_irq放置于1103行之前，鎖的范圍過大，鎖的負載也會加重，影響效率；如果將加鎖的代碼放到判斷里面，且沒有1106行的代碼，程序會正確嗎？在單核情況下是正確的，但在雙核情況下問題就出現了。一個非主進程在一個CPU上運行，正準備調用exit退出，此時主進程在另外一個CPU上運行，在子進程調用release_task函數之前調用上述代碼。子進程在exit_notify函數中，先持有讀寫鎖tasklist_lock，調用forget_original_parent。主進程運行到1104處，由于此時子進程先持有該鎖，所以父進程只好等待。在forget_original_parent函數中，如果該子進程還有子進程，則會調用reparent_thread()，將執行p->parent=p->real_parent;語句，導致兩者相等，等非主進程釋放讀寫鎖tasklist_lock時，另外一個CPU上的主進程被喚醒，一旦開始執行，繼續運行將會導致bug。

嚴格的說，Double-checkedlocking不屬于無鎖編程的范疇，但由原來的每次加鎖訪問到大多數情況下無須加鎖，就是一個巨大的進步。同時從這里也可以看出一點端倪，內核開發者為了降低鎖沖突率，減少等待時間，提高運行效率，一直在持續不斷的進行改進。

原子操作可以保證指令以原子的方式執行——執行過程不被打斷。內核提供了兩組原子操作接口：一組針對于整數進行操作，另外一組針對于單獨的位進行操作。內核中的原子操作通常是內聯函數，一般是通過內嵌匯編指令來完成。對于一些簡單的需求，例如全局統計、引用計數等等，可以歸結為是對整數的原子計算。

1。Lock-free應用場景一——SpinLock

SpinLock是一種輕量級的同步方法，一種非阻塞鎖。當lock操作被阻塞時，并不是把自己掛到一個等待隊列，而是死循環CPU空轉等待其他線程釋放鎖。Spinlock鎖實現代碼如下：

清單4。spinlock實現代碼

staticinlinevoid__preempt_spin_lock(spinlock_t*lock)

{

……

do{

preempt_enable();

while(spin_is_locked(lock))

cpu_relax();

preempt_disable();

}while(！_raw_spin_trylock(lock));

}

staticinlineint_raw_spin_trylock(spinlock_t*lock)

{

charoldval;

__asm____volatile__(

xchgb%b0，%1

：=q(oldval)，=m(lock->lock)

：0(0)：memory);

returnoldval>0;

}

匯編語言指令xchgb原子性的交換8位oldval(存0)和lock->lock的值，如果oldval為1(lock初始值為1)，則獲取鎖成功，反之，則繼續循環，接著relax休息一會兒，然后繼續周而復始，直到成功。

對于應用程序來說，希望任何時候都能獲取到鎖，也就是期望lock->lock為1，那么用CAS原語來描述_raw_spin_trylock(lock)就是CAS(lock->lock，1，0);

如果同步操作總是能在數條指令內完成，那么使用SpinLock會比傳統的mutexlock快一個數量級。SpinLock多用于多核系統中，適合于鎖持有時間小于將一個線程阻塞和喚醒所需時間的場合。

pthread庫已經提供了對spinlock的支持，所以用戶態程序也能很方便的使用spinlock了，需要包含pthread。h。在某些場景下，pthread_spin_lock效率是pthread_mutex_lock效率的一倍多。美中不足的是，內核實現了讀寫spinlock鎖，但pthread未能實現。

2。Lock-free應用場景二——Seqlock

手表最主要最常用的功能是讀時間，而不是校正時間，一旦后者成了最常用的功能，消費者肯定不會買賬。計算機的時鐘也是這個功能，修改時間是小概率事件，而讀時間是經常發生的行為。以下代碼摘自2。4。34內核：

清單5。2。4。34seqlock實現代碼

443voiddo_gettimeofday(structtimeval*tv)

444{

……

448read_lock_irqsave(xtime_lock，flags);

……

455sec=xtime。tv_sec;

456usec+=xtime。tv_usec;

457read_unlock_irqrestore(xtime_lock，flags);

……

466}

468voiddo_settimeofday(structtimeval*tv)

469{

470write_lock_irq(xtime_lock);

……

490write_unlock_irq(xtime_lock);

491}

不難發現獲取時間和修改時間采用的是spinlock讀寫鎖，讀鎖和寫鎖具有相同的優先級，只要讀持有鎖，寫鎖就必須等待，反之亦然。

Linux2。6內核中引入一種新型鎖——順序鎖(seqlock)，它與spinlock讀寫鎖非常相似，只是它為寫者賦予了較高的優先級。也就是說，即使讀者正在讀的時候也允許寫者繼續運行。當存在多個讀者和少數寫者共享一把鎖時，seqlock便有了用武之地，因為seqlock對寫者更有利，只要沒有其他寫者，寫鎖總能獲取成功。根據lock-free和時鐘功能的思想，內核開發者在2。6內核中，將上述讀寫鎖修改成了順序鎖seqlock，代碼如下：

清單6。2。6。10seqlock實現代碼

staticinlineunsignedread_seqbegin(constseqlock_t*sl)

{

unsignedret=sl->sequence;

smp_rmb();

returnret;

}

staticinlineintread_seqretry(constseqlock_t*sl，unsignediv)

{

smp_rmb();

return(iv1)|(sl->sequence^iv);

}

staticinlinevoidwrite_seqlock(seqlock_t*sl)

{

spin_lock(sl->lock);

++sl->sequence;

smp_wmb();