}

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

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

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

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

清單7。2。4。34RCU實現代碼

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

清單8。2。6。10RCU實現代碼

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

}

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

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

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

圖2。環形緩沖區實現原理圖

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

清單9。2。6。10環形緩沖區實現代碼

/*

*__kfifo_put-putssomedataintotheFIFO，nolockingversion

*Notethatwithonlyoneconcurrentreaderandoneconcurrent

*writer，youdon'tneedextralockingtousethesefunctions。