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

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行的代碼，程序會正確嗎？在單核情況下是正確的，但在雙核情況下問題就出現(xiàn)了。一個非主進程在一個CPU上運行，正準(zhǔn)備調(diào)用exit退出，此時主進程在另外一個CPU上運行，在子進程調(diào)用release_task函數(shù)之前調(diào)用上述代碼。子進程在exit_notify函數(shù)中，先持有讀寫鎖tasklist_lock，調(diào)用forget_original_parent。主進程運行到1104處，由于此時子進程先持有該鎖，所以父進程只好等待。在forget_original_parent函數(shù)中，如果該子進程還有子進程，則會調(diào)用reparent_thread()，將執(zhí)行p->parent=p->real_parent;語句，導(dǎo)致兩者相等，等非主進程釋放讀寫鎖tasklist_lock時，另外一個CPU上的主進程被喚醒，一旦開始執(zhí)行，繼續(xù)運行將會導(dǎo)致bug。

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

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

1。Lock-free應(yīng)用場景一——SpinLock

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

清單4。spinlock實現(xiàn)代碼

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)，則獲取鎖成功，反之，則繼續(xù)循環(huán)，接著relax休息一會兒，然后繼續(xù)周而復(fù)始，直到成功。

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

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

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

2。Lock-free應(yīng)用場景二——Seqlock

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

清單5。2。4。34seqlock實現(xiàn)代碼

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}

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

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

清單6。2。6。10seqlock實現(xiàn)代碼

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();