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

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

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

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

1。Lock-free應用場(chǎng)景一——SpinLock

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

清單4。spinlock實(shí)現代碼

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;

}

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

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

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

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

2。Lock-free應用場(chǎng)景二——Seqlock

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

清單5。2。4。34seqlock實(shí)現代碼

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ā)現獲取時(shí)間和修改時(shí)間采用的是spinlock讀寫(xiě)鎖，讀鎖和寫(xiě)鎖具有相同的優(yōu)先級，只要讀持有鎖，寫(xiě)鎖就必須等待，反之亦然。

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

清單6。2。6。10seqlock實(shí)現代碼

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