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

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

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

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

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

清單4。spinlock實(shí)現(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;

}

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

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

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

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

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

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

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

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

清單6。2。6。10seqlock實(shí)現(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();