深入理解 RCU 核心原理

hi，大家好，今天給大家分享並行程序設計中最重要的鎖 -RCU 鎖，RCU 鎖本質是用空間換時間，是對讀寫鎖的一種優化加強，但不僅僅是這樣簡單，RCU 體現出來的垃圾回收思想，也是值得我們學習和借鑑，各個語言 C, C++,Java, go 等都有 RCU 鎖實現，同時內核精巧的實現也是學習代碼設計好素材，深入理解 RCU 分爲兩個部分，第一部分主要是講核心原理，理解其核心設計思想，對 RCU 會有個宏觀的理解；第二部分會分析源碼實現（本來準備放在一起，由於實現相當精巧，篇幅會很多，就單獨成一篇），希望大家喜歡。

並行程序設計演進

如何正確有效的保護共享數據是編寫並行程序必須面臨的一個難題，通常的手段就是同步。同步可分爲阻塞型同步（Blocking Synchronization）和非阻塞型同步（ Non-blocking Synchronization）。

阻塞型同步是指當一個線程到達臨界區時，因另外一個線程已經持有訪問該共享數據的鎖，從而不能獲取鎖資源而阻塞（睡眠），直到另外一個線程釋放鎖。常見的同步原語有 mutex、semaphore 等。如果同步方案採用不當，就會造成死鎖（deadlock），活鎖（livelock）和優先級反轉（priority inversion），以及效率低下等現象。

爲了降低風險程度和提高程序運行效率，業界提出了不採用鎖的同步方案，依照這種設計思路設計的算法稱爲非阻塞型同步，其本質就是停止一個線程的執行不會阻礙系統中其他執行實體的運行。

先有阻塞型同步

互斥鎖（英語：Mutual exclusion，縮寫 Mutex）是一種用於多線程編程中，防止兩條線程同時對同一公共資源進行讀寫的機制。該目的通過將代碼切片成一個一個的臨界區域（critical section）達成。臨界區域指的是一塊對公共資源進行存取的代碼。

信號量 (Semaphore)，是在多線程環境下使用的一種設施，是可以用來保證兩個或多個關鍵代碼段不被併發調用，可以認爲 mutex 是 0-1 信號量；

讀寫鎖是計算機程序的併發控制的一種同步機制，它把對共享資源的訪問者劃分成讀者和寫者，讀者只對共享資源進行讀訪問，寫者則需要對共享資源進行寫操作，讀操作可併發重入，寫操作是互斥的。

再有非阻塞型同步

當今比較流行的非阻塞型同步實現方案有三種：

1. Wait-free（無等待）

   **Wait-free **是指任意線程的任何操作都可以在有限步之內結束，而不用關心其它線程的執行速度。Wait-free 是基於 per-thread 的，可以認爲是 starvation-free 的。非常遺憾的是實際情況並非如此，採用 Wait-free 的程序並不能保證 starvation-free，同時內存消耗也隨線程數量而線性增長。目前只有極少數的非阻塞算法實現了這一點。

   簡單理解：任意時刻所有的線程都在幹活；

2. Lock-free（無鎖）

   Lock-Free 是指能夠確保執行它的所有線程中至少有一個能夠繼續往下執行。由於每個線程不是 starvation-free 的，即有些線程可能會被任意地延遲，然而在每一步都至少有一個線程能夠往下執行，因此係統作爲一個整體是在持續執行的，可以認爲是 system-wide 的。所有 Wait-free 的算法都是 Lock-Free 的。

   **簡單理解：**任意時刻至少一個線程在幹活；

3. Obstruction-free（無障礙）

   Obstruction-free 是指在任何時間點，一個孤立運行線程的每一個操作可以在有限步之內結束。只要沒有競爭，線程就可以持續運行。一旦共享數據被修改，Obstruction-free 要求中止已經完成的部分操作，並進行回滾。所有 Lock-Free 的算法都是 Obstruction-free 的。

   **簡單理解：**只要數據有修改，就會重新獲取，並且把已經完成操作回滾重來；

綜上所述，不難得出 Obstruction-free 是 Non-blocking synchronization 中性能最差的，而 Wait-free 性能是最好的，但實現難度也是最大的，因此 Lock-free 算法開始被重視，並廣泛運用於各種程序設計中，這裏主要介紹 Lock_free 算法。

**lock-free（無鎖）**往往可以提供更好的性能和伸縮性保證，但實際上其優點不止於此。早期這些概念首先是在操作系統上應用的，因爲一個不依賴於鎖的算法，可以應用於各種場景下，而無需考慮各種錯誤，故障，失敗等情形。比如死鎖，中斷，甚至 CPU 失效。

主流無鎖技術

**Atomic operation（原子操作），**在單一、不間斷的步驟中讀取和更改數據的操作。需要處理器指令支持原子操作：

● test-and-set (TSR)

● compare-and-swap (CAS)

● load-link/store-conditional (ll/sc)

**Spin Lock（自旋鎖）**是一種輕量級的同步方法，一種非阻塞鎖。當 lock 操作被阻塞時，並不是把自己掛到一個等待隊列，而是死循環 CPU 空轉等待其他線程釋放鎖。

**Seqlock (順序鎖) **是 Linux 2.6 內核中引入一種新型鎖，它與 spin lock 讀寫鎖非常相似，只是它爲寫者賦予了較高的優先級。也就是說，即使讀者正在讀的時候也允許寫者繼續運行，讀者會檢查數據是否有更新，如果數據有更新就會重試，因爲 seqlock 對寫者更有利，只要沒有其他寫者，寫鎖總能獲取成功。

**RCU(Read-Copy Update)，**顧名思義就是讀 - 拷貝修改，它是基於其原理命名的。對於被 RCU 保護的共享數據結構，讀者不需要獲得任何鎖就可以訪問它，但寫者在訪問它時首先拷貝一個副本，然後對副本進行修改，最後使用一個回調（callback）機制在適當的時機把指向原來數據的指針替換爲新的被修改的數據。這個時機就是所有引用該數據的 CPU 都退出對共享數據的訪問。

本文主要講解 RCU 的核心原理。

歷史背景

高性能並行程序中，數據一致性訪問是一個非常重要的部分，一般都是採用鎖機制（semaphore、spinlock、rwlock 等）進行保護共享數據，根本的思想就是在訪問臨界資源時，首先訪問一個全局的變量（鎖），通過全局變量的狀態來控制線程對臨界資源的訪問。但是，這種思想是需要硬件支持的，硬件需要配合實現全局變量（鎖）的讀 - 修改 - 寫，現代 CPU 都會提供這樣的原子化指令。

採用鎖機制實現數據訪問的一致性存在如下兩個問題：

• 效率問題。鎖機制的實現需要對內存的原子化訪問，這種訪問操作會破壞流水線操作，降低了流水線效率，這是影響性能的一個因素。另外，在採用讀寫鎖機制的情況下，寫鎖是排他鎖，無法實現寫鎖與讀鎖的併發操作，在某些應用下會降低性能。

• 擴展性問題。例如，當系統中 CPU 數量增多的時候，採用鎖機制實現數據的同步訪問效率偏低。並且隨着 CPU 數量的增多，效率降低，由此可見鎖機制實現的數據一致性訪問擴展性差。

原始的 RCU 思想

在多線程場景下，經常我們需要併發訪問一個數據結構，爲了保證線程安全我們會考慮使用互斥設施來進行同步，更進一步我們會根據對這個數據結構的讀寫比例而選用讀寫鎖進行優化。但是讀寫鎖不是唯一的方式，我們可以藉助於 COW 技術來做到寫操作不需要加鎖，也就是在讀的時候正常讀，寫的時候，先加鎖拷貝一份，然後進行寫，寫完就原子的更新回去，使用 COW 實現避免了頻繁加讀寫鎖本身的性能開銷。

優缺點

由於 RCU 旨在最小化讀取端開銷，因此僅在以更高速率使用同步邏輯進行讀取操作時才使用它。如果更新操作超過 10%，性能反而會變差，所以應該選擇另一種同步方式而不是 RCU。

• 好處

• 幾乎沒有讀取端開銷。零等待，零開銷

• 沒有死鎖問題

• 沒有優先級倒置問題（優先級倒置和優先級繼承）

• 無限制延遲沒有問題

• 無內存泄漏風險問題

• 缺點

• 使用起來有點複雜

• 對於寫操作，它比其他同步技術稍慢

• 適用場景

核心原理

**理論基礎 -**QSBR 算法

(Quiescent State-Based Reclamation)

這個算法的核心思想就是識別出線程的不活動 (quiescent) 狀態，那麼什麼時候纔算是不活動的狀態呢？這個狀態和臨界區狀態是相對的，線程離開臨界區就是不活動的狀態了。識別出不活動狀態了，還需要把狀態通知出去，讓其他線程知道，這整個過程可以用下面的圖來描述:

上面有四個線程，線程 1 執行完更新操作後添加了釋放內存的 callback，此時線程 2,3,4 都讀取的是之前的內容，等他們執行完成後分別回去調用 onQuiescentState 來表明自己已經不不活動了，等到最後一個線程調用 onQuiescentState 的時候就可以去調用註冊的 callback 了。要實現上面這個過程其要點就是選擇適合的位置執行 onQuiescentState，還有就是如何知道誰是最後一個執行 onQuiescentState 的線程。

批量回收，如果更新的次數比較多的話，但是每次只回調一個 callback，釋放一次內存就會導致內存釋放跟不上回收的速度，爲此需要進行批量回收，每次更新都會註冊新的 callback，當第一次所有的線程都進入不活動狀態的時候就把當前的所有 callback 保存起來，等待下一次所有線程進入不活動的狀態的時候就回調前一次所有的 callback。

基本架構

Linux 內核 RCU 參考 QSBR 算法設計一套無鎖同步機制。

• 多個讀者可以併發訪問共享數據，而不需要加鎖；

• 寫者更新共享數據時候，需要先 copy 副本，在副本上修改，最終，讀者只訪問原始數據，因此他們可以安全地訪問數據，多個寫者之間是需要用鎖互斥訪問的（比如用自旋鎖）；

• 修改資源後，需要更新共享資源，讓後面讀者可以訪問最新的數據；

• 等舊資源上所有的讀者都訪問完畢後，就可以回收舊資源了；

RCU 模型

• Removal：在寫端臨界區部分，讀取（Read()），進行復制（Copy），並執行更改（Update）操作；

• Grace Period：這是一個等待期，以確保所有與執行刪除的數據相關的 reader 訪問完畢；

• Reclamation：回收舊數據；

三個重要概念

**靜止狀態 QS(Quiescent State): **CPU 發生了上下文切換稱爲經歷一個 quiescent state；

**寬限期 GP(Grace Period): **grace period 就是所有 CPU 都經歷一次 quiescent state 所需要的等待的時間，也即系統中所有的讀者完成對共享臨界區的訪問；

**GP 原理
**

**讀側臨界部分 RCS(Read-Side Critical Section): **保護禁止其他 CPU 修改的代碼區域，但允許多個 CPU 同時讀；

三個主要的角色

讀者 reader：

• 安全訪問臨界區資源；

• 負責標識進出臨界區；

寫者 updater：

• 複製一份數據，然後更新數據；

• 用新數據覆蓋舊數據，然後進入 grace period；

回收者 reclaimer：

• 等待在 grace period 之前的讀者退出臨界區；

• 在寬限期結束後，負責回收舊資源；

三個重要機制

發佈 / 訂閱機制

• 主要用於更新數據，即使在數據被同時修改時線程也能安全瀏覽數據。RCU 通過發佈 - 訂閱機制（Publish-Subscribe Mechanism）實現這種併發的插入操作能力；

延遲迴收機制：

• 實現檢查舊數據上所有 RCU 讀者完成，用於安全刪除舊數據；

多版本機制：

• 維護最近更新對象的多個版本，用於允許讀者容忍併發的插入和刪除新對象的多個版本；

最後總結

最後，總結一下 RCU 鎖的核心思想：

• 讀者無鎖訪問數據，標記進出臨界區；

• 寫者讀取，複製，更新；

• 舊數據延遲迴收；

RCU 核心思想就三句話，產品經理都說簡單，但 Linux 內核實現卻不是這麼簡單。除了要實現基本功能，需要考慮很多複雜情況：

內核的 RCU 系統可以說是內核最複雜系統之一，爲了高性能和多核擴展性，設計了非常精巧的數據結構：

同時巧妙實現了很多核心流程：

• 檢查當前 CPU 是否度過 QS；

• QS report(彙報寬限期度過)；

• 寬限期的發起與完成；

• rcu callbacks 處理；

其中很多實現都可以說是非常精巧，結合了預處理，批量處理，延後（異步）處理，多核併發，原子操作，異常處理，多場景精細優化等多種技術，性能好，可擴展性強，穩定性強，有一定的學習和參考價值，即使你的工作不是內核編程，裏面體現很多編程思想和代碼設計思想，也是值得大家學習的。

預知後事如何，且聽下回分解，下次會帶大家領悟 RCU 源碼實現的美妙。

擴展閱讀

http://csng.cs.toronto.edu/publication_files/0000/0159/jpdc07.pdf

http://www.rdrop.com/users/paulmck/rclock/RCUdissertation.2004.07.14e1.pdf

https://lwn.net/Articles/262464/

http://www.wowotech.net/kernel_synchronization/461.html

http://concurrencyfreaks.blogspot.com/2013/05/lock-free-and-wait-free-definition-and.html

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/6T_h-ZY23H9GUUK1tYofjQ