Linux核心RCU(Read Copy Update)鎖簡析-前傳

如果你用Linux perf tool的top命令做熱點糾察時，你會發現，前10名嫌疑犯裡面肯定有好幾個都是鎖！

在進行並行多處理時，不可避免地會遇到鎖的問題，這是不可避免的，因為這一直以來也許是保護共用資料的唯一方式，被保護的區域就是臨界區。而我們知道，鎖的開銷是巨大的，因為它不可避免地要麼等待，要麼讓別人等待，然而這並不是開銷的本質，開銷的本質在於很多鎖都採用了“原子操作”這麼一個技術，如此一個原子操作會對匯流排或者cache一致性造成很大的影響，比如要對一個變數進行原子加1，不要認為它很簡單，其實背後會有很多不希望的操作，在某架構的處理器上，首先要LOCK匯流排，這意味著LOCK不解除期間，其它處理器不能訪存(起碼是記憶體的某些區域)，可能還要涉及到刷cache，或者觸發cache一致性操作...這還不算最猛的打擊，在某些架構上，存在記憶體柵欄，它會刷掉CPU的流水線，刷掉cache，幾乎所有的為優化而設計的方案全部失效，當然，這是代價，收益就是你保護了臨界區。

你要保護臨界區，你要付出代價，這個代價如果用複雜的鎖來支付的話，未免有點大。非要這樣子嗎？也許是你的資料結構設計地不好，也許是你的程式碼流設計地不好，比如多個執行緒同時讀共用資料，兩個執行緒一個讀一個寫，能否採用環形緩衝區來減輕競爭呢？事實上很多諸如網絡卡，硬碟等共用外設驅動程式都是這麼玩的，程式碼只要保證讀指標和寫指標不相互超越即可，這樣可以最小化鎖的使用，當然這只是一個非常簡單的例子。

設計好的資料結構和程式碼流程是一方面，但是這個層次不夠抽象，更好的方式就是設計一種更加優化的鎖。讀寫鎖這種不對稱的鎖應對讀者多寫者少的情景是一種優化的鎖，它對讀者的優待就是無需等待，只要沒有寫者就可以直接讀，否則才等待。而對於寫者，它需要等待所有讀者的完成。這種讀寫的實現可以依賴於另一種叫做自旋鎖的機制實現，我的一個實現如下所示：

typedef struct { 
 
    spinlock_t *spinlock; 
 
    atomic_t readers; 
 
}rwlock_t; 
static inline void rdlock(rwlock_t *lock) 
{ 
    spinlock_t *lck = lock->spinlock; 
    if (likely(!lock->readers++)) 
        spin_lock(lck); 
} 
 
static inline void rdunlock(rwlock_t *lock) 
{ 
    spinlock_t *lck = lock->spinlock; 
    if (likely(!--lock->readers)) 
        spin_unlock(lck); 
} 
 
static inline void wrlock(rwlock_t *lock) 
{ 
    spin_lock(lock->spinlock); 
} 
 
static inline void wrunlock(rwlock_t *lock) 
{ 
    spin_unlock(lock->spinlock); 
} 

很OK，不是嗎？但是最好的方案就是徹底拋棄鎖，徹底不用鎖。

我曾經在設計我的轉發表的時候，為了降低lock開銷，我為每個CPU複製了一個區域性的本地轉發表，這些轉發表是一致的，由路由表生成，心想這就可以避免競爭，然而，這些轉發表總要面臨更新問題，如何更新它們？？我最初採用的方式是採用IPI(處理器間中斷)，在處理常式中，停掉處理執行緒，然後更新資料，最後開啟執行緒，這樣可以在處理期間避免lock。十分合理，不是嗎？可是我想複雜了。

仔細看看讀寫鎖的寫鎖，它魯莽地進行了標準鎖定操作，而讀鎖也是在第一個讀者進來的時候採用了鎖定動作。這些鎖定操作導致的等待可以避免嗎？看看我原始的IPI方案，停掉執行緒是為了防止讀者讀到錯誤的資料，實際上是將主動將執行流讓位給了寫者，寫者先來，然後再看看讀寫鎖中的寫者，發現有讀者存在時，沒有主動地讓位，而只是被動地等待，這種等待很無聊！

能否將我的方式和讀寫鎖的方式結合呢？

怎麼結合？按照剛剛的思路，無非就是為寫者是被動等待還是搶先讀者做一個決策！但是它還有一個別的選擇，那就是先按照自己的流程寫資料，不是寫原始資料，而是寫原始資料的一份拷貝(偉大的寫時拷貝)，然後將這件事掛在一個未竟事務連結串列上直接走人，等待系統發現所有的讀者都完成時用連結串列上的資料逐個覆蓋原始資料。這是個多麼好的結合，這就是偉大的RCU鎖。讀者的代價就是簡單地標示一下有人讀即可，而寫者也無需等待持鎖，直接寫副本，寫完走人，後來的事就交給系統了....

本文永久更新連結地址：http://www.linuxidc.com/Linux/2015-07/120041.htm