}

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

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

3。Lock-free應用場景三——RCU

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

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

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

清單8。2。6。10RCU實現(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;

}

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

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

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

圖2。環(huán)形緩沖區(qū)實現(xiàn)原理圖

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

清單9。2。6。10環(huán)形緩沖區(qū)實現(xiàn)代碼

/*

*__kfifo_put-putssomedataintotheFIFO，nolockingversion

*Notethatwithonlyoneconcurrentreaderandoneconcurrent

*writer，youdon'tneedextralockingtousethesefunctions。