本文詳細地介紹了 Linux 2.6 內核中新的鎖機制 RCU(Read-Copy Update) 的實現機制，使用要求與典型應用。
眾所周知，為了保護共享數據,需要一些同步機制,如自旋鎖(spinlock)，讀寫鎖(rwlock)，它們使用起來非常簡單,而且是一種很有效的同步機制，在UNIX系統和Linux系統中得到了廣泛的使用。但是隨著計算機硬件的快速發展，獲得這種鎖的開銷相對於CPU的速度在成倍地增加，原因很簡單，CPU的速度與訪問內存的速度差距越來越大，而這種鎖使用了原子操作指令，它需要原子地訪問內存，也就說獲得鎖的開銷與訪存速度相關，另外在大部分非x86架構上獲取鎖使用了內存柵(Memory Barrier)，這會導致處理器流水線停滯或刷新，因此它的開銷相對於CPU速度而言就越來越大。表1數據證明了這一點。
表1是在700MHz的奔騰III機器上的基本操作的開銷，在該機器上一個時鐘周期能夠執行兩條整數指令。在1.8GHz的奔騰4機器上, 原子加1指令的開銷要比700MHz的奔騰III機器慢75納秒(ns)，盡管CPU速度快兩倍多。
這種鎖機制的另一個問題在於其可擴展性，在多處理器系統上，可擴展性非常重要，否則根本無法發揮其性能。圖1表明了Linux上各種鎖的擴展性。
注：refcnt表示自旋鎖與引用記數一起使用。
讀寫鎖rwlock在兩個CPU的情況下性能反倒比一個CPU的差，在四個CPU的情況下，refcnt的性能要高於rwlock，refcnt大約是理論性能的45%，而rwlock是理論性能的39%,自旋縮spinlock的性能明顯好於refcnt和rwlock，但它也只達到了理性性能的57%，brlock（Big Reader Lock）性能可以線性擴展。Brlock是由RedHat的Ingo Molnar實現的一個高性能的rwlock，它適用於讀特多而寫特少的情況，讀者獲得brlock的開銷很低，但寫者獲得鎖的開銷非常大，而且它只預定義了幾個鎖，用戶無法隨便定義並使用這種鎖，它也需要為每個CPU定義一個鎖狀態數組，因此這種鎖並沒有被作為rwlock的替代方案廣泛使用，只是在一些特別的地方使用到。
正是在這種背景下，一個高性能的鎖機制RCU呼之欲出，它克服了以上鎖的缺點，具有很好的擴展性，但是這種鎖機制的使用范圍比較窄，它只適用於讀多寫少的情況，如網絡路由表的查詢更新、設備狀態表的維護、數據結構的延遲釋放以及多徑I/O設備的維護等。
RCU並不是新的鎖機制，它只是對Linux內核而言是新的。早在二十世紀八十年代就有了這種機制，而且在生產系
統中使用了這種機制，但這種早期的實現並不太好，在二十世紀九十年代出現了一個比較高效的實現，而在linux中是在開發內核2.5.43中引入該技術的並正式包含在2.6內核中。
RCU(Read-Copy Update)，顧名思義就是讀-拷貝修改，它是基於其原理命名的。對於被RCU保護的共享數據結構，讀者不需要獲得任何鎖就可以訪問它，但寫者在訪問它時首先拷貝一個副本，然後對副本進行修改，最後使用一個回調（callback）機制在適當的時機把指向原來數據的指針重新指向新的被修改的數據。這個時機就是所有引用該數據的CPU都退出對共享數據的操作。
因此RCU實際上是一種改進的rwlock，讀者幾乎沒有什麼同步開銷，它不需要鎖，不使用原子指令，而且在除alpha的所有架構上也不需要內存柵（Memory Barrier），因此不會導致鎖競爭，內存延遲以及流水線停滯。不需要鎖也使得使用更容易，因為死鎖問題就不需要考慮了。寫者的同步開銷比較大，它需要延遲數據結構的釋放，復制被修改的數據結構，它也必須使用某種鎖機制同步並行的其它寫者的修改操作。讀者必須提供一個信號給寫者以便寫者能夠確定數據可以被安全地釋放或修改的時機。有一個專門的垃圾收集器來探測讀者的信號，一旦所有的讀者都已經發送信號告知它們都不在使用被RCU保護的數據結構，垃圾收集器就調用回調函數完成最後的數據釋放或修改操作。 RCU與rwlock的不同之處是：它既允許多個讀者同時訪問被保護的數據，又允許多個讀者和多個寫者同時訪問被保護的數據（注意：是否可以有多個寫者並行訪問取決於寫者之間使用的同步機制），讀者沒有任何同步開銷，而寫者的同步開銷則取決於使用的寫者間同步機制。但RCU不能替代rwlock，因為如果寫比較多時，對讀者的性能提高不能彌補寫者導致的損失。
讀者在訪問被RCU保護的共享數據期間不能被阻塞，這是RCU機制得以實現的一個基本前提，也就說當讀者在引用被RCU保護的共享數據期間，讀者所在的CPU不能發生上下文切換，spinlock和rwlock都需要這樣的前提。寫者在訪問被RCU保護的共享數據時不需要和讀者競爭任何鎖，只有在有多於一個寫者的情況下需要獲得某種鎖以與其他寫者同步。寫者修改數據前首先拷貝一個被修改元素的副本，然後在副本上進行修改，修改完畢後它向垃圾回收器注冊一個回調函數以便在適當的時機執行真正的修改操作。等待適當時機的這一時期稱為grace period，而CPU發生了上下文切換稱為經歷一個quiescent state，grace period就是所有CPU都經歷一次quiescent state所需要的等待的時間。垃圾收集器就是在grace period之後調用寫者注冊的回調函數來完成真正的數據修改或數據釋放操作的。
以下以鏈表元素刪除為例詳細說明這一過程。
寫者要從鏈表中刪除元素 B，它首先遍歷該鏈表得到指向元素 B 的指針，然後修改元素 B 的前一個元素的 next 指針指向元素 B 的 next 指針指向的元素C，修改元素 B 的 next 指針指向的元素 C 的 prep 指針指向元素 B 的 prep指針指向的元素 A,在這期間可能有讀者訪問該鏈表，修改指針指向的操作是原子的，所以不需要同步，而元素 B 的指針並沒有去修改，因為讀者可能正在使用 B 元素來得到下一個或前一個元素。寫者完成這些操作後注冊一個回調函數以便在 grace period 之後刪除元素 B，然後就認為已經完成刪除操作。垃圾收集器在檢測到所有的CPU不在引用該鏈表後，即所有的 CPU 已經經歷了 quiescent state,grace period 已經過去後，就調用剛才寫者注冊的回調函數刪除了元素 B。
更多詳情見請繼續閱讀下一頁的精彩內容： http://www.linuxidc.com/Linux/2015-02/112909p2.htm
