透過Linux內(nèi)核看無鎖編程
}
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ù)結(jié)構(gòu),因為當寫者修改數(shù)據(jù)結(jié)構(gòu)時,讀者可能會訪問一個無效的指針。
3。Lock-free應(yīng)用場景三——RCU
在2。6內(nèi)核中,開發(fā)者還引入了一種新的無鎖機制-RCU(Read-Copy-Update),允許多個讀者和寫者并發(fā)執(zhí)行。RCU技術(shù)的核心是寫操作分為寫和更新兩步,允許讀操作在任何時候無阻礙的運行,換句話說,就是通過延遲寫來提高同步性能。RCU主要應(yīng)用于WRRM場景,但它對可保護的數(shù)據(jù)結(jié)構(gòu)做了一些限定:RCU只保護被動態(tài)分配并通過指針引用的數(shù)據(jù)結(jié)構(gòu),同時讀寫控制路徑不能有睡眠。以下數(shù)組動態(tài)增長代碼摘自2。4。34內(nèi)核:
清單7。2。4。34RCU實現(xiàn)代碼
其中ipc_lock是讀者,grow_ary是寫者,不論是讀或者寫,都需要加spinlock對被保護的數(shù)據(jù)結(jié)構(gòu)進行訪問。改變數(shù)組大小是小概率事件,而讀取是大概率事件,同時被保護的數(shù)據(jù)結(jié)構(gòu)是指針,滿足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ù)結(jié)構(gòu)時,首先復制該數(shù)據(jù)結(jié)構(gòu),申請new內(nèi)存,然后對副本進行修改,調(diào)用memcpy將原數(shù)組的內(nèi)容拷貝到new中,同時對擴大的那部分賦新值,修改完畢后,寫者調(diào)用rcu_assign_pointer修改相關(guān)數(shù)據(jù)結(jié)構(gòu)的指針,使之指向被修改后的新副本,整個寫操作一氣呵成,其中修改指針值的操作屬于原子操作。在數(shù)據(jù)結(jié)構(gòu)被寫者修改后,需要調(diào)用內(nèi)存屏障smp_wmb,讓其他CPU知曉已更新的指針值,否則會導致SMP環(huán)境下的bug。當所有潛在的讀者都執(zhí)行完成后,調(diào)用call_rcu釋放舊副本。同Spinlock一樣,RCU同步技術(shù)主要適用于SMP環(huán)境。
環(huán)形緩沖區(qū)是生產(chǎn)者和消費者模型中常用的數(shù)據(jù)結(jié)構(gòu)。生產(chǎn)者將數(shù)據(jù)放入數(shù)組的尾端,而消費者從數(shù)組的另一端移走數(shù)據(jù),當達到數(shù)組的尾部時,生產(chǎn)者繞回到數(shù)組的頭部。
如果只有一個生產(chǎn)者和一個消費者,那么就可以做到免鎖訪問環(huán)形緩沖區(qū)(RingBuffer)。寫入索引只允許生產(chǎn)者訪問并修改,只要寫入者在更新索引之前將新的值保存到緩沖區(qū)中,則讀者將始終看到一致的數(shù)據(jù)結(jié)構(gòu)。同理,讀取索引也只允許消費者訪問并修改。
圖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。
linux操作系統(tǒng)文章專題:linux操作系統(tǒng)詳解(linux不再難懂)linux相關(guān)文章:linux教程
評論