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

}

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

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

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

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

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

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

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

#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;

}

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

環(huán)形緩沖區是生產(chǎn)者和消費者模型中常用的數據結構。生產(chǎn)者將數據放入數組的尾端，而消費者從數組的另一端移走數據，當達到數組的尾部時(shí)，生產(chǎn)者繞回到數組的頭部。

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

圖2。環(huán)形緩沖區實(shí)現原理圖

如圖所示，當讀者和寫(xiě)者指針相等時(shí)，表明緩沖區是空的，而只要寫(xiě)入指針在讀取指針后面時(shí)，表明緩沖區已滿(mǎn)。

清單9。2。6。10環(huán)形緩沖區實(shí)現代碼

/*

*__kfifo_put-putssomedataintotheFIFO，nolockingversion

*Notethatwithonlyoneconcurrentreaderandoneconcurrent

*writer，youdon'tneedextralockingtousethesefunctions。