淺析從同步到RCU的引入

一、從同步開始

1.1 同步的產(chǎn)生

在閱讀或者編寫內(nèi)核代碼的時候，總是需要帶著一個默認(rèn)的前提條件：任意的一條執(zhí)行流，都可能在任意一條指令之后被中斷執(zhí)行，然后在并不確定的時間后再次回來執(zhí)行。

因此，常常需要考慮一個問題：指令在被中斷到回到斷點繼續(xù)執(zhí)行的這個過程中，原本所依賴的執(zhí)行環(huán)境是不是會發(fā)生變化，對應(yīng)的問題是，指令執(zhí)行所依賴的環(huán)境是獨享的還是共享的。如果它的獨享的，那就是安全的，而如果是共享的，那就可能存在被意外修改的問題，由此引發(fā)一些同步問題。處理同步問題，通常是通過原子變量、加鎖這些同步機制來解決。

而大部分工程師對于是否使用同步機制的判斷基于一個樸素的觀念：全局變量的操作需要加鎖，而局部變量并不需要。

在絕大多數(shù)的情況下，這句話是適用的。之所以我將全局和局部替換為共享與獨享，是因為在特定情況下，局部變量并不等于獨享資源，而全局變量也同樣如此，是否要引入同步機制這個問題也并不是一成不變的，比如下面的幾種情況：

(1) 需要注意的一個問題是，我們通常毫不思索地把返回指向棧上資源的指針這種行為視為絕對的 bug，但是卻忽略了這個 bug 產(chǎn)生的原因：函數(shù)返回之后棧上的數(shù)據(jù)會被覆蓋。但是如果函數(shù)沒有返回呢？內(nèi)核中能看到這樣的代碼：在棧上初始化一些資源，然后將其鏈接到全局鏈表上，隨后陷入睡眠，棧上數(shù)據(jù)的生命周期也就保持到了被喚醒之后。既然棧上的數(shù)據(jù)可以導(dǎo)出到其它地方，自然也就由獨享變成了共享，也就需要考慮同步問題。

(2) 當(dāng)我們把視線全部聚焦在數(shù)據(jù)上時，或者像第一點提到的理所當(dāng)然地認(rèn)為棧就應(yīng)該是獨占的時候，其實我們忽略了它們本身存在的形式：不論是指令、亦或者是數(shù)據(jù)，棧區(qū)也好，堆區(qū)也罷，它們都是存在于內(nèi)存當(dāng)中，而內(nèi)存本身的硬件屬性是可讀可寫的。而諸如代碼段只讀，棧獨立于每個進(jìn)程只是操作系統(tǒng)賦予它們的屬性，如果我們只是操作系統(tǒng)的使用者，自然可以默認(rèn)這些規(guī)律，但是如果我們是開發(fā)者，是不是存在修改代碼段或者其它非數(shù)據(jù)部分的需求？而這些修改又會不會存在同步問題呢？所以有時候同步問題并不僅僅局限于數(shù)據(jù)。

(3) 有些全局變量的定義可能僅僅是為了擴大訪問范圍，或者雖然它是共享資源，但是在特定場景下并沒有并發(fā)產(chǎn)生，(比如 per-task 的變量，percpu 變量)。因此，對于產(chǎn)生同步問題來說，共享只是其中一個必要條件，它還有另一個必要條件：同時操作。也就是多條執(zhí)行流同時訪問同一個共享資源。

同時操作中的同時如何理解？時間刻度下的同一時刻？如果是這樣判定，那從來就不存在真正意義上的同時，我們所定義的同時是在 A 還沒完成某項工作的情況下，B 也參與進(jìn)來，這種情況就視為 A 與 B 同時做這項工作。

比如，在單核環(huán)境下并不存在代碼執(zhí)行的同時，所有代碼都是串行執(zhí)行的，但是依舊會產(chǎn)生同步問題，比如 i++。這是因為，C 語言的最小粒度并非指令執(zhí)行的最小粒度，一個 i++ 操作實際上由 load/modified/store 指令組成，如果在執(zhí)行 load 指令完成之后被打斷，在其它執(zhí)行流再操作 i，從 C 語言的執(zhí)行角度來說，i++ 是沒有被執(zhí)行完的，由此而帶來的一種”同時”。而這樣的概念同樣可以引申到復(fù)合結(jié)構(gòu)。

(4)多個執(zhí)行流對共享的數(shù)據(jù)進(jìn)行同時操作，當(dāng)這個場景出現(xiàn)時，許多工程師會毫不猶豫地增加同步機制來避免出現(xiàn)問題。不知道各位盆友有沒有想過，如果不加鎖，是不是一定會造成程序上的 bug？要弄清楚這個問題，我們需要知道 CPU 在執(zhí)行時的一些行為。

首先就是要區(qū)分讀和寫，通常我們所說的問題其實就是執(zhí)行讀操作時讀取到不符合預(yù)料之中的值，隨后的邏輯判斷或者隨后的寫操作就會出現(xiàn)邏輯問題，而這種問題就是同時寫共享資源帶來的。

另一方面，程序在執(zhí)行時如果不做同步，會遇到幾種亂序：

編譯器會對程序執(zhí)行優(yōu)化操作，編譯器會假定所編譯的程序都是在單執(zhí)行流環(huán)境下運行的，在此基礎(chǔ)上進(jìn)行優(yōu)化，比如將代碼亂序，將計算結(jié)果使用寄存器緩存而不寫回內(nèi)存等等，自然地，如果你不希望編譯器這么做，就需要通過 volatile 來禁用激進(jìn)的優(yōu)化項，對于內(nèi)核而言，通常是使用 WRITE_ONCE/READ_ONCE 接口，或者試用 barrie 屏障防止特定代碼段的亂序行為。

為了進(jìn)一步提高并發(fā)性能，CPU 也會對代碼進(jìn)行亂序排列，通常 CPU 只會保證有邏輯依賴的指令按照順序執(zhí)行，比如一條指令依賴于上一條指令的執(zhí)行結(jié)果，就會按照順序執(zhí)行。而對于其它不存在邏輯依賴的指令，則不能保證順序，至于會怎么亂序，這個并不能做任何假設(shè)，而在多線程多核環(huán)境下，這種亂序會帶來問題，可以通過 CPU 的屏障來禁止這種行為。

現(xiàn)代 CPU 弱序的內(nèi)存模型，這和處理器架構(gòu)相關(guān)，在較弱的內(nèi)存模型中，寫操作并不會按照執(zhí)行順序提交到內(nèi)存，一個 CPU 寫完之后，另一個 CPU 在下次訪問時并不一定能立刻訪問到新值，而且另一個 CPU 的看到寫的順序也是不一定的，只有通過數(shù)據(jù)屏障或者特定內(nèi)存屏障來禁止這種行為。

因此，當(dāng)我們了解了程序在不使用同步機制會帶來什么問題的情況下，就可以具體問題具體分析，即使是針對同一共享數(shù)據(jù)的同時操作，比如出現(xiàn)下面的情況，即使不加鎖也不會出現(xiàn)問題：

針對共享數(shù)據(jù)的只讀

即使存在同時讀寫，也不一定會產(chǎn)生 bug，最常見的例子是對 /proc/ 目錄下的某些節(jié)點進(jìn)行設(shè)置操作，該設(shè)置對應(yīng)一個全局變量，而內(nèi)核代碼中只會讀取該變量，這種情況不加同步措施(或者只加編譯器屏障)，通常也只會造成非常短的時間周期內(nèi)讀者讀到舊值，通常不會產(chǎn)生邏輯問題。

而對于同時的寫，在特定應(yīng)用場景下也可以不加鎖。參考下圖：

A 線程和 B 線程同時操作變量 cnt，盡管 A 和 B 都執(zhí)行了 cnt++ 操作，但是 B 的操作被覆蓋了，兩次 ++ 操作最終只有一次產(chǎn)生了效果，看起來這肯定是有問題的。但是在諸如網(wǎng)絡(luò)數(shù)據(jù)包統(tǒng)計的時候，這種情況發(fā)生的概率非常低，和所有路徑加鎖帶來巨大的性能損失相比，統(tǒng)計值稍微有一點點誤差也不是不能接受，這種情況下我們可以只加一個 WRITE_ONCE 來限制編譯器優(yōu)化。因此，當(dāng)我們了解了不同的同步措施所帶來的性能損失以及它實際能解決什么問題的時候，更多的是做性能與準(zhǔn)確性(也可以是吞吐量、功耗之類的指標(biāo))之間的權(quán)衡，而并不是不由分說地加鎖。

1.2 同步機制

聊到同步問題，那自然就離不開它的解決方案：同步機制，當(dāng)然，我們討論最多的同步機制就是鎖。既然同步問題產(chǎn)生的必要條件是 "共享" 和 "同時"，那只需要破壞其中的某一個條件，就可以解決同步問題。

最簡單也是最經(jīng)典的方案就是 spinlock 和 mutex，只要接觸過 linux，對這兩者基本上就不會陌生，這兩者所實現(xiàn)的邏輯就是建立一個臨界區(qū)來保護(hù)某一個共享資源的操作，一次只允許一個訪問者進(jìn)入，等該訪問者退出的時候，下一個再進(jìn)來，破壞了 "同時" 這個條件，也就能解決同步問題。

spinlock 在無法獲取鎖的時候會選擇自旋等待，而 mutex 無法獲取鎖的時候會選擇睡眠，它們應(yīng)用在不同的場景，對于一個操作系統(tǒng)而言，這兩者是必要的。但是很多朋友在看待它們之間的差異的時候，往往只注意到嘗試持鎖但失敗這個場景下的不同，而忽略了持鎖之后的差異：

(1) spinlock 持鎖是關(guān)搶占的，但是并不一定關(guān)中斷，也就是說在 spinlock 臨界區(qū)中，不會出現(xiàn)調(diào)度，但是可能出現(xiàn)進(jìn)程環(huán)境的切換，比如中斷、軟中斷，這在某些場景下是需要考慮的。

(2) 而 mutex 是不能應(yīng)用在中斷環(huán)境下的，所以可以不用考慮進(jìn)程運行環(huán)境的切換，但是 mutex 并不關(guān)搶占，所以 mutex 也會帶來嵌套持鎖的復(fù)雜問題。

如果要深入研究代碼實現(xiàn)甚至對它們進(jìn)行優(yōu)化，這兩個問題是無法回避的。而如果只是使用 spinlock、mutex 作為同步措施保護(hù)特定全局?jǐn)?shù)據(jù)，這兩個問題并不需要過多考慮，而且如果沒有其它方面諸如性能的需求，你只需要知道 mutex 和 spinlock 這兩個簡單的接口就能應(yīng)付工作。

當(dāng)然，如果你是一個對事物本源有好奇心的朋友，可以再深入思考 spinlock(mutex) 的實現(xiàn)原理，就會發(fā)現(xiàn)一個矛盾點：spinlock 的作用是對全局?jǐn)?shù)據(jù)的同時操作做互斥保護(hù)，讓一個訪問者進(jìn)入而其它訪問者等待，而讓一個訪問者進(jìn)入而其它訪問者等待，做這件事本身就需要線程之間的通信。

換句話說，在 spinlock 的實現(xiàn)中，等待線程要知道鎖已經(jīng)被占用，而占用者在嘗試持鎖之初要知道自己已經(jīng)占用鎖，它們也必須通過訪問某個全局的資源才能獲得這個信息，這是不是又產(chǎn)生了對某一個共享資源的同時訪問？那誰又來保護(hù) spinlock 本身的實現(xiàn)呢？

軟件無法解決，那就需要借助硬件來實現(xiàn)，因此每個不同的硬件架構(gòu)都至少需要實現(xiàn)對單字長變量的原子操作指令，比如 64 位平臺下，硬件必須支持一類或一組指令，該指令保證對一個 long 型變量執(zhí)行諸如 ++ 操作時，保證它的原子性。

借助于這個原子性的硬件操作，spinlock 就可以這樣實現(xiàn)：先請求鎖的，就可以通過原子操作獲取到某個全局變量的所有權(quán)，而后請求鎖的，必須等待之前的 owner 釋放其所有權(quán)，也就是 unlock，而上面說到的某個全局變量，就是鎖變量。

因此可以看到，對共享的全局?jǐn)?shù)據(jù)的操作，變成了對鎖的競爭，而對鎖的競爭實際上就是對鎖變量的競爭，本質(zhì)上就是將復(fù)合數(shù)據(jù)的保護(hù)收斂成單字長變量的保護(hù)，然后使用硬件的原子指令來解決這個問題。

舉個例子，多個執(zhí)行流對某個 struct foo 結(jié)構(gòu)實例有讀寫操作，為了防止同步問題，這些執(zhí)行流從競爭 struct foo 變成競爭 foo->spinlock，而 spinlock 是基于鎖變量lock->val實現(xiàn)的，所以，實際上所有執(zhí)行流競爭的是鎖變量?；诖耍浑y發(fā)現(xiàn)，鎖的實現(xiàn)并非消除了競爭，它只是將競爭縮小到單變量的范圍。

而在隨后的發(fā)展中，因為需要平衡延遲、吞吐量、功耗等因素，漸漸地對鎖又加入了更多的邏輯，比如 mutex 最開始實現(xiàn)了排隊機制，后續(xù)為了減少上下文切換引入樂觀自旋，又為了解決樂觀自旋帶來的公平性問題引入 handoff 機制。而它的表兄弟 rwsem 在 mutex 的基礎(chǔ)上進(jìn)一步區(qū)分讀寫，實現(xiàn)則更加復(fù)雜。

俗話說，是藥三分毒，鎖是解決同步問題的一劑猛藥，但是它帶來的問題也不容小覷：

死鎖、餓死這些常見且直接導(dǎo)致系統(tǒng)死機。

鎖只是緩解競爭，而不是根治，所以競爭依舊存在，在激烈條件下開銷依舊不小。

鎖實現(xiàn)越來越趨于復(fù)雜，也會消耗指令周期和 cache 空間，而且這種復(fù)雜度讓量化分析變得越來越難。

具體的鎖有具體的問題，比如spinlock 機制會帶來 cpu 的空轉(zhuǎn)，在某些競爭激烈的場景下，8 個 cpu 同時競爭同一個 spinlock 鎖，因為關(guān)搶占的原因，這 8 個 CPU 上除了處理中斷，再也做不了任何事，只是空轉(zhuǎn)浪費 CPU 資源。而 mutex 所帶來的無效喚醒以及本身的進(jìn)程切換也是有不小的開銷，比如 mutex 的環(huán)境下，當(dāng)多個 cpu 在競爭同一把鎖時，不良的鎖使用或者不合時宜的設(shè)計會導(dǎo)致很多的無效喚醒，也就是很多進(jìn)程被喚醒之后卻無法獲取鎖，只能再次睡下，而這些開銷都是一種資源的浪費，在重載環(huán)境下這種浪費程度是非常大的.

這些都是鎖本身的實現(xiàn)問題，來自于性能、公平性、吞吐量之間不可調(diào)和的矛盾，而鎖競爭所花費的時間完全是產(chǎn)生不了任何效益的。

當(dāng)解決方案本身成為最大的問題，當(dāng)屠龍的少年即將成為新的惡龍，我們不得不轉(zhuǎn)而去尋找更合適的同步方案。

1.3 其它同步解決方案

當(dāng)通用的鎖方案無法更進(jìn)一步時，另一個方向是拆分使用場景，尋找特定場景下的針對性解決方案。

一種想法是繼續(xù)沿用鎖的形式，但是區(qū)分讀寫，因為讀寫的性質(zhì)是完全不一樣的。

在上面的描述中，對共享資源進(jìn)行操作的角色我們統(tǒng)稱為訪問者，但是從實際的硬件角度出發(fā)，發(fā)現(xiàn)讀和寫對于共享數(shù)據(jù)的操作有根本性的不同，而寫操作通常才是帶來同步問題的罪魁禍?zhǔn)?，針對多讀少寫的場景，在 spinlock、mutex 的基礎(chǔ)上衍生出了 rwlock、rwsem(rwsem 其實并沒有信號量的語義，它更像是睡眠版的 rwlock)。

另一種是無鎖設(shè)計，無鎖設(shè)計也分成很多種類型，第一種是干脆不使用同步機制，或者最小化使用同步機制，因為某些場景下，全局?jǐn)?shù)據(jù)的不同步是可以接受的。這一點在上面已經(jīng)論證過了。

另外的較常見的無鎖方案，通過結(jié)合應(yīng)用場景采用更細(xì)化的設(shè)計，只使用硬件提供的原子操作，而不引入諸如 spinlock 這一類復(fù)雜的鎖邏輯，從而避免在鎖上消耗太多 CPU 資源。

除此之外，一種二次確認(rèn)的機制也比較常用，因為某些共享數(shù)據(jù)的操作可能會帶來同步問題，如果產(chǎn)生并發(fā)條件的概率足夠低，直接采用鎖有時候并沒有必要，我們大可以直接使用無鎖下的操作，然后對操作結(jié)果進(jìn)行檢查，如果結(jié)果不符合我們的預(yù)期，那就重新執(zhí)行一遍操作，以保證數(shù)據(jù)被正常更新。

還有很多的無鎖方案都是針對”共享”的條件來做的，比如使用額外的內(nèi)存來避免競爭的產(chǎn)生，其中使用最多的就是內(nèi)核中的 percpu 機制，盡管大多數(shù)工程師通常并不會將它看成是一種同步的解決方案，但是它卻實際上地解決了同步問題產(chǎn)生的"共享"這個條件，也就是將原本 cpu 之間共享的全局?jǐn)?shù)據(jù)分散到每個 cpu 一份，這樣雖然依舊存在進(jìn)程環(huán)境與中斷環(huán)境的同步問題，但是卻極大地降低了多 cpu 之間的同步問題，從多核收斂到單核的環(huán)境。

同時，針對一些特定的場景還涌現(xiàn)出一些無鎖方案，最常見的是在特定場景下存在冷熱路徑，通過增大冷路徑下的開銷這種設(shè)計來實現(xiàn)熱路徑下的無鎖方案，而冷熱路徑的定義完全是取決于應(yīng)用場景的，因此這些優(yōu)化都不能作為通用方案，因為它們的實現(xiàn)是一些特殊情況下的權(quán)衡。

而我們今天要聊到的，RCU，也正是在特定場景下的一種無鎖方案。

二、RCU 是什么？

2.1 RCU 的基本概念

RCU，read-copy-update，也就是讀-拷貝-更新，其基本思想在于，當(dāng)我們需要對一個共享數(shù)據(jù)進(jìn)行操作的時候，我們可以先復(fù)制一份原有的數(shù)據(jù) B，將需要更新的部分在 B 上實現(xiàn)，然后再使用 B 替換掉 A，這也是 RCU 最典型的使用場景。

很顯然，這種無鎖方案所針對的是 "共享" 這個特性，畢竟并不直接對目標(biāo)數(shù)據(jù)進(jìn)行操作。

從這個理念出發(fā)，其實我們可以非常直觀地感受到 RCU 的第一個特點：RCU 是針對多讀少寫的使用場景的，畢竟這種形式的實現(xiàn)明顯加大了寫端的開銷。

RCU 的設(shè)計理念簡單到任何人在第一次聽到時就能夠理解它，但是當(dāng)我們嘗試像 spinlock 那樣通過它的 lock/unlock 接口來閱讀它的代碼實現(xiàn)時，居然驚奇地發(fā)現(xiàn)它的 lock/unlock 實現(xiàn)僅僅只是開關(guān)一下?lián)屨迹诙啻未_認(rèn)內(nèi)核配置沒有問題之后，發(fā)現(xiàn)事實確實是如此，從而產(chǎn)生一種很荒謬的感覺：僅僅通過開關(guān)搶占是怎么實現(xiàn)讀-拷貝-更新的？

2.2 RCU 實現(xiàn)的核心問題是什么？

很多對 RCU 感興趣的朋友其實在網(wǎng)上也看過不少 RCU 相關(guān)的文章，知道了 RCU 的操作形式：讀-拷貝-更新，并自然而然地覺得這是個很好的想法，而且它好像確實不需要鎖來實現(xiàn)，因為更新操作和原本讀者讀到的是不同的數(shù)據(jù)，不滿足共享的條件，隨后再執(zhí)行替換就好了。而且，這三個操作步驟完全就可以由使用者自己完成，實在是想不到有什么地方需要操作系統(tǒng)來插手的。

如果一個問題想不明白，那么我們就代入到真實的場景下來考慮這個問題：假設(shè)現(xiàn)在有 3 個讀者和 1 個更新者需要對共享數(shù)據(jù)進(jìn)行訪問，讀者不間斷地對數(shù)據(jù)發(fā)起讀操作，而更新者需要更新時，拷貝出一份新的數(shù)據(jù)，操作完之后然后再替換舊的數(shù)據(jù)，這樣就完成了數(shù)據(jù)的更新，而讀者就可以讀到新的數(shù)據(jù)。

看起來非常合理，效率也很高，但是這里有一個最大的問題在于，我們默認(rèn)了一個并不存在的前提條件：新數(shù)據(jù)的替換立馬就對所有的讀者生效，替換之后就可以立刻刪除舊數(shù)據(jù)，而讀者也可以立刻讀到新的數(shù)據(jù)。

我們可以通過上圖來了解這個流程，其中存在三個讀者，讀者的兩個箭頭標(biāo)定讀操作的開始點和結(jié)束點，中間的表示共享數(shù)據(jù)。

從圖中可以看到，writer 先是從 D1 copy 出一份 D2，接著對D2 執(zhí)行修改，緊接著將 D2 更新為新的共享數(shù)據(jù)，這個過程就可以理解為一次 Read-Copy-Update 操作。

而在整個過程中，reader1 始終讀到 D1 數(shù)據(jù)，而reader3 始終讀到 D2 的新數(shù)據(jù)，但是 reader2 就比較麻煩了，它的讀操作跨越了 D1 到 D2 的更新過程，那么它讀到的是 D1 還是 D2，又或者說讀到一半 D1 的數(shù)據(jù)和另一半 D2 的數(shù)據(jù)？

按照傳統(tǒng)的同步鎖做法，這時候需要寫者等所有舊讀者退出，然后讀者等待寫者更新完，才繼續(xù)進(jìn)讀臨界區(qū)，對應(yīng)上圖就是 writer 必須等 reader2 先讀完再執(zhí)行更新。你有沒有意識到，寫者等讀者退出，讀者再等寫者更新完，這個操作實際上就是 rwlock 的實現(xiàn)，難道 RCU 操作要基于 rwlock 來實現(xiàn)？那為什么我不直接使用 rwlock 呢？顯然讓替換立刻生效來實現(xiàn) RCU 的方式，只能說你創(chuàng)造了一個新的同步機制，但它永遠(yuǎn)也不會有人用。

那么為了能超過 rwlock 的性能，一方面不能做讀者與寫者之間的鎖同步，從而讓 RCU 能在特定場景下有性能優(yōu)勢，另一方面，如果不做鎖同步，那就意味著讀者不知道寫者什么時候更新，寫者也不知道更新時是否存在讀者，唯一的方案是：即使 writer 在更新完之后，reader2 讀取的依舊是 D1 的舊數(shù)據(jù)(因為 reader2 不知道數(shù)據(jù)有更新)，而更新完之后新來的讀者讀到的自然是新數(shù)據(jù)。

在這種情況下，也就意味著 RCU 不能像普通鎖一樣保護(hù)復(fù)合結(jié)構(gòu)的實例，而只能是針對指向動態(tài)資源的數(shù)據(jù)指針，稍微深入地想一想，就能發(fā)現(xiàn)，如果D1 和 D2是同一個結(jié)構(gòu)實例，D2 會覆蓋掉 D1 的數(shù)據(jù)，就會產(chǎn)生reader2 讀到一半D1，更新后讀到另一半D2的錯誤結(jié)果。而如果在更新完之后reader2依舊需要能夠讀取到 D1，那D1和D2必須是獨立的兩片內(nèi)存。

之前的問題是如何處理跨越更新點的讀者，在確定這類讀者依舊讀取舊數(shù)據(jù)之后，現(xiàn)在剩下的問題變成了：判斷什么時候這些讀者讀完了舊數(shù)據(jù)，從而可以回收舊數(shù)據(jù)的資源？

這就是內(nèi)核中 RCU 實現(xiàn)所需要解決的問題：如何低成本地實現(xiàn)等待依舊正在訪問舊數(shù)據(jù)的讀者退出？而讀-拷貝-更新操作，完全可以留給用戶自己做，所以，RCU 在內(nèi)核中的實現(xiàn)實際上并不是 Read-Copy-Update 操作，而是實現(xiàn)一種等待讀者退出臨界區(qū)的機制。

同時，由于通常情況下，RCU 等待所有舊讀者退出之后，主要的操作就是釋放舊數(shù)據(jù)，所以它的實現(xiàn)也很像一種垃圾回收機制。

結(jié)合上面的兩點問題，也就引出 RCU 的另外幾個特點：

即使是在寫者更新完之后，依舊允許讀者讀到舊數(shù)據(jù)。而內(nèi)核的 RCU 實現(xiàn)需要保證所有能讀到舊數(shù)據(jù)的 RCU 退出，才刪除舊數(shù)據(jù)。

RCU 同步機制所保護(hù)的對象不能直接是復(fù)合結(jié)構(gòu)，只能保護(hù)動態(tài)分配數(shù)據(jù)對應(yīng)的指針

追求讀端的極限性能，這是 RCU 在內(nèi)核中的立足之本。

2.3 RCU 的實現(xiàn)討論

如果我上一小節(jié)已經(jīng)將 RCU 在內(nèi)核中實現(xiàn)的邏輯表達(dá)清楚，且你也已經(jīng)看明白，那下一步需要討論的就是：如何低成本地實現(xiàn)等待舊的讀者退出臨界區(qū)。也就是從現(xiàn)在開始，我們才真正進(jìn)入到 RCU 的實現(xiàn)中。

等待一件事情結(jié)束，最常用的也是容易想到的解決方案就是在開始的時候做一個標(biāo)記，憑票入場，出場退票，這樣只需要通過判斷出入的記錄是否成對就能判斷是否還存在沒有退出者，當(dāng)然，這個想法在上面已經(jīng)被證實效率過低，記錄讀端的起始意味著需要執(zhí)行全局的寫操作，而讀端臨界區(qū)一旦需要執(zhí)行全局的寫操作，在多核上并發(fā)時就會產(chǎn)生同步問題，這并不好解決，而且開銷并不小，當(dāng)然這個全局寫操作可以換成 percpu 類型的，從而減少一些性能的損失，不過這種方式總歸是治標(biāo)不治本，而我們的理想狀態(tài)是讀端沒有同步開銷，也就是不記錄讀臨界區(qū)的進(jìn)入。

另一個思路是，我們是否可以借用其它的事件來完成這個等待操作？也就是說是否能通過一些既有事件來判斷我們需要等待的條件已經(jīng)滿足，而不需要進(jìn)行針對該事件直接的記錄行為。

在內(nèi)核中，RCU 的實現(xiàn)就使用了一種非常巧妙的方式：簡單地通過關(guān)-開搶占來實現(xiàn)一個讀臨界區(qū)，讀者進(jìn)入臨界區(qū)將會關(guān)搶占，而退出臨界區(qū)時再將搶占打開，而進(jìn)程的調(diào)度只會在搶占開的時候發(fā)生，因此，寫者等待之前所有的讀者退出，只需要等待所有 cpu 上都執(zhí)行完一次調(diào)度就行了。

這里有必要進(jìn)一步解釋一下，上一段文字中非常重要的幾個字是：之前所有的讀者。

參考上圖，在writer更新之前，reader1 和 reader2 依舊引用的是 D1 數(shù)據(jù)，而 reader3 已經(jīng)讀取到新的數(shù)據(jù)了，所以只需要等待 reader1 和 reader2 完成讀操作，就可以釋放 D1 了。

而在 reader1 整個讀的過程中，是處于關(guān)搶占的狀態(tài)，如果 reader1 運行在 cpu0 上，那 writer 更新完之后，只需要判斷 cpu0 上一旦發(fā)生了調(diào)度，就能判斷 reader1 已經(jīng)退出臨界區(qū)，畢竟發(fā)生調(diào)度的前提是 cpu0 上開了搶占，也就意味著 reader1 已經(jīng)讀完了。

而更新者更新完數(shù)據(jù)之后，等待所有讀者退出臨界區(qū)這個過程，被命名為寬限期(grance period)，也就是寬限期一過，也就意味著數(shù)據(jù)的更新以及所有讀者退出這個過程已經(jīng)完成，這時候就可以釋放舊數(shù)據(jù)了，如果是單純的 add 操作，那自然就不需要刪除舊數(shù)據(jù)，只需要確認(rèn)更新已經(jīng)完成就好。

當(dāng)然，等待所有之前的讀者退出臨界區(qū)這個過程可能會比較長，甚至到幾十毫秒。因此，在決定是否使用 RCU 作為同步之前需要考慮到這一點。

這也就引出 RCU 的另外兩個特點：

Linux 實現(xiàn)下的RCU 讀端臨界區(qū)就是通過關(guān)-開搶占來實現(xiàn)的，性能以及多核擴展性非常好，但是很明顯讀端臨界區(qū)不支持搶占和睡眠。

寫端具有一定的延遲。讀端在一定的時間周期內(nèi)會獲取到新或者舊數(shù)據(jù)。

上圖是一個簡單的示例，更新端在 CPU1 上對 gptr 執(zhí)行了置 NULL 操作，然后調(diào)用 synchronize_rcu 阻塞等待所有之前的讀者退出臨界區(qū)，synchronize_rcu 會立刻觸發(fā)一次調(diào)度，接著 CPU2 上在執(zhí)行完淺藍(lán)長條對應(yīng)的讀端臨界區(qū)之后，執(zhí)行了一次調(diào)度，同時也意味著 CPU2 已經(jīng)渡過了臨界區(qū)，而在 CPU3 上，實際上經(jīng)歷了三次進(jìn)入-退出讀臨界區(qū)的階段，但是因為沒有觸發(fā)進(jìn)程切換，RCU core 是無法判斷 CPU3 渡過了臨界區(qū)的，直到最后 CPU3 執(zhí)行了一次調(diào)度，整個系統(tǒng)也就渡過了一個完整的寬限期，CPU1 上阻塞的 task 得以繼續(xù)運行，free 對應(yīng)的內(nèi)存。

同時，再整體總結(jié)一下 RCU 的特點：

RCU 是針對多讀少寫的使用場景

寫端具有一定的延遲。讀端在一定的時間周期內(nèi)會獲取到新或者舊數(shù)據(jù)

即使是在寫者更新完之后，依舊允許讀者讀到舊數(shù)據(jù)。而內(nèi)核的 RCU 實現(xiàn)需要保證所有能讀到舊數(shù)據(jù)的讀者退出，才刪除舊數(shù)據(jù)

RCU 同步機制所保護(hù)的對象不能直接是復(fù)合結(jié)構(gòu)，只能是指針

RCU 追求讀端的極限性能，這是 RCU 在內(nèi)核中的立足之本

Linux 實現(xiàn)下的經(jīng)典RCU 讀端臨界區(qū)就是通過關(guān)-開搶占來實現(xiàn)的，性能以及多核擴展性非常好，但是很明顯讀端臨界區(qū)不支持搶占和睡眠

三、結(jié)語

其實對于 RCU ，還有很多東西要講，包括RCU的使用、實現(xiàn)、RCU的變種、RCU的發(fā)展以及源代碼分析之類的，整個 RCU 是一個非常龐大的體系。

按照我以往的經(jīng)驗，這種大段的文字且沒有什么趣味性的東西，篇幅還是不宜過長，如果各位對 RCU 真的感興趣，下次咱們再一起走進(jìn) RCU 的使用和實現(xiàn)。

審核編輯：劉清