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

作者：時(shí)間：2012-05-21 來(lái)源：網(wǎng)絡(luò)

加入技術(shù)交流群
- 掃碼加入
  和技術(shù)大咖面對(duì)面交流
  海量資料庫(kù)查詢

}

voiddo_gettimeofday(structtimeval*tv)

{

unsignedlongseq;

unsignedlongusec，sec;

unsignedlongmax_ntp_tick;

……

do{

unsignedlonglost;

seq=read_seqbegin(xtime_lock);

……

sec=xtime。tv_sec;

usec+=(xtime。tv_nsec/1000);

}while(read_seqretry(xtime_lock，seq));

……

tv->tv_sec=sec;

tv->tv_usec=usec;

}

intdo_settimeofday(structtimespec*tv)

{

……

write_seqlock_irq(xtime_lock);

……

write_sequnlock_irq(xtime_lock);

clock_was_set();

return0;

}

Seqlock實(shí)現(xiàn)原理是依賴一個(gè)序列計(jì)數(shù)器，當(dāng)寫者寫入數(shù)據(jù)時(shí)，會(huì)得到一把鎖，并且將序列值加1。當(dāng)讀者讀取數(shù)據(jù)之前和之后，該序列號(hào)都會(huì)被讀取，如果讀取的序列號(hào)值都相同，則表明寫沒(méi)有發(fā)生。反之，表明發(fā)生過(guò)寫事件，則放棄已進(jìn)行的操作，重新循環(huán)一次，直至成功。不難看出，do_gettimeofday函數(shù)里面的while循環(huán)和接下來(lái)的兩行賦值操作就是CAS操作。

采用順序鎖seqlock好處就是寫者永遠(yuǎn)不會(huì)等待，缺點(diǎn)就是有些時(shí)候讀者不得不反復(fù)多次讀相同的數(shù)據(jù)直到它獲得有效的副本。當(dāng)要保護(hù)的臨界區(qū)很小，很簡(jiǎn)單，頻繁讀取而寫入很少發(fā)生（WRRM---WriteRarelyReadMostly）且必須快速時(shí)，就可以使用seqlock。但seqlock不能保護(hù)包含有指針的數(shù)據(jù)結(jié)構(gòu)，因?yàn)楫?dāng)寫者修改數(shù)據(jù)結(jié)構(gòu)時(shí)，讀者可能會(huì)訪問(wèn)一個(gè)無(wú)效的指針。

3。Lock-free應(yīng)用場(chǎng)景三——RCU

在2。6內(nèi)核中，開(kāi)發(fā)者還引入了一種新的無(wú)鎖機(jī)制-RCU(Read-Copy-Update)，允許多個(gè)讀者和寫者并發(fā)執(zhí)行。RCU技術(shù)的核心是寫操作分為寫和更新兩步，允許讀操作在任何時(shí)候無(wú)阻礙的運(yùn)行，換句話說(shuō)，就是通過(guò)延遲寫來(lái)提高同步性能。RCU主要應(yīng)用于WRRM場(chǎng)景，但它對(duì)可保護(hù)的數(shù)據(jù)結(jié)構(gòu)做了一些限定：RCU只保護(hù)被動(dòng)態(tài)分配并通過(guò)指針引用的數(shù)據(jù)結(jié)構(gòu)，同時(shí)讀寫控制路徑不能有睡眠。以下數(shù)組動(dòng)態(tài)增長(zhǎng)代碼摘自2。4。34內(nèi)核：

清單7。2。4。34RCU實(shí)現(xiàn)代碼

其中ipc_lock是讀者，grow_ary是寫者，不論是讀或者寫，都需要加spinlock對(duì)被保護(hù)的數(shù)據(jù)結(jié)構(gòu)進(jìn)行訪問(wèn)。改變數(shù)組大小是小概率事件，而讀取是大概率事件，同時(shí)被保護(hù)的數(shù)據(jù)結(jié)構(gòu)是指針，滿足RCU運(yùn)用場(chǎng)景。以下代碼摘自2。6。10內(nèi)核：

清單8。2。6。10RCU實(shí)現(xiàn)代碼

#definercu_read_lock()preempt_disable()

#definercu_read_unlock()preempt_enable()

#definercu_assign_pointer(p，v)({

smp_wmb();

(p)=(v);

})

structkern_ipc_perm*ipc_lock(structipc_ids*ids，intid)

{

……

rcu_read_lock();

entries=rcu_dereference(ids->entries);

if(lid>=entries->size){

rcu_read_unlock();

returnNULL;

}

out=entries->p[lid];

if(out==NULL){

rcu_read_unlock();

returnNULL;

}

……

returnout;

}

staticintgrow_ary(structipc_ids*ids，intnewsize)

{

structipc_id_ary*new;

structipc_id_ary*old;

……

new=ipc_rcu_alloc(sizeof(structkern_ipc_perm*)*newsize+

sizeof(structipc_id_ary));

if(new==NULL)

returnsize;

new->size=newsize;

memcpy(new->p，ids->entries->p，sizeof(structkern_ipc_perm*)*size

+sizeof(structipc_id_ary));

for(i=size;inew->p[i]=NULL;

}

old=ids->entries;

*Usercu_assign_pointer()tomakesurethememcpyedcontents

*ofthenewarrayarevisiblebeforethenewarraybecomesvisible。

rcu_assign_pointer(ids->entries，new);

ipc_rcu_putref(old);

returnnewsize;

}

縱觀整個(gè)流程，寫者除內(nèi)核屏障外，幾乎沒(méi)有一把鎖。當(dāng)寫者需要更新數(shù)據(jù)結(jié)構(gòu)時(shí)，首先復(fù)制該數(shù)據(jù)結(jié)構(gòu)，申請(qǐng)new內(nèi)存，然后對(duì)副本進(jìn)行修改，調(diào)用memcpy將原數(shù)組的內(nèi)容拷貝到new中，同時(shí)對(duì)擴(kuò)大的那部分賦新值，修改完畢后，寫者調(diào)用rcu_assign_pointer修改相關(guān)數(shù)據(jù)結(jié)構(gòu)的指針，使之指向被修改后的新副本，整個(gè)寫操作一氣呵成，其中修改指針值的操作屬于原子操作。在數(shù)據(jù)結(jié)構(gòu)被寫者修改后，需要調(diào)用內(nèi)存屏障smp_wmb，讓其他CPU知曉已更新的指針值，否則會(huì)導(dǎo)致SMP環(huán)境下的bug。當(dāng)所有潛在的讀者都執(zhí)行完成后，調(diào)用call_rcu釋放舊副本。同Spinlock一樣，RCU同步技術(shù)主要適用于SMP環(huán)境。

環(huán)形緩沖區(qū)是生產(chǎn)者和消費(fèi)者模型中常用的數(shù)據(jù)結(jié)構(gòu)。生產(chǎn)者將數(shù)據(jù)放入數(shù)組的尾端，而消費(fèi)者從數(shù)組的另一端移走數(shù)據(jù)，當(dāng)達(dá)到數(shù)組的尾部時(shí)，生產(chǎn)者繞回到數(shù)組的頭部。

如果只有一個(gè)生產(chǎn)者和一個(gè)消費(fèi)者，那么就可以做到免鎖訪問(wèn)環(huán)形緩沖區(qū)（RingBuffer）。寫入索引只允許生產(chǎn)者訪問(wèn)并修改，只要寫入者在更新索引之前將新的值保存到緩沖區(qū)中，則讀者將始終看到一致的數(shù)據(jù)結(jié)構(gòu)。同理，讀取索引也只允許消費(fèi)者訪問(wèn)并修改。