linux經(jīng)典的rcu如何實(shí)現(xiàn)？

一、RCU有什么用？

RCU主要用于對(duì)性能要求苛刻的并行實(shí)時(shí)計(jì)算。例如：天氣預(yù)報(bào)、模擬核爆炸計(jì)算、內(nèi)核同步等等。

假設(shè)你正在編寫(xiě)一個(gè)并行實(shí)時(shí)程序，該程序需要訪問(wèn)隨時(shí)變化的數(shù)據(jù)。這些數(shù)據(jù)可能是隨著溫度、濕度的變化而逐漸變化的大氣壓。這個(gè)程序的實(shí)時(shí)響應(yīng)要求是如此嚴(yán)格，需要處理的數(shù)據(jù)量如此巨大，以至于不允許任何自旋或者阻塞，因此不能使用任何鎖。

幸運(yùn)的是，溫度和壓力的范圍通常變化不大，因此使用默認(rèn)的數(shù)據(jù)集也是可行的。當(dāng)溫度、濕度和壓力抖動(dòng)時(shí)，有必要使用實(shí)時(shí)數(shù)據(jù)。但是溫度、濕度和壓力是逐漸變化的，我們可以在幾分鐘內(nèi)更新數(shù)據(jù)，但沒(méi)必要實(shí)時(shí)更新值。

在這種情況下，可以使用一個(gè)全局指針，即gptr，通常為NULL，表示要使用默認(rèn)值。偶爾也可以將gptr指向假設(shè)命名為a、b和c的變量，以反映氣壓的變化。

傳統(tǒng)的軟件可以使用自旋鎖這樣的同步機(jī)制，來(lái)保護(hù)gptr指針的讀寫(xiě)。一旦舊的值不被使用，就可以將舊指針指向的數(shù)據(jù)釋放。這種簡(jiǎn)單的方法有一個(gè)最大的問(wèn)題：它會(huì)使軟件效率下降數(shù)個(gè)數(shù)量級(jí)（注意，不是下降數(shù)倍而是下降數(shù)個(gè)數(shù)量級(jí)）。

在現(xiàn)代計(jì)算系統(tǒng)中，向gptr寫(xiě)入a、b、c這樣的值，并發(fā)的讀者要么看到一個(gè)NULL指針要么看到指向新結(jié)構(gòu)gptr的指針，不會(huì)看到中間結(jié)果。也就是說(shuō)，對(duì)于指針賦值來(lái)說(shuō)，某種意義上這種賦值是原子的。讀者不會(huì)看到a、b、c之外的其他結(jié)果。并且，更好的一點(diǎn)，也是更重要的一點(diǎn)是：讀者不需要使用任何代價(jià)高昂的同步原語(yǔ)，因此這種方法非常適合于實(shí)時(shí)使用。

真正的難點(diǎn)在于：在讀者獲得gptr的引用時(shí)，它可能看到a、b、c這三個(gè)值中任意一個(gè)值，寫(xiě)者何時(shí)才能安全的釋放a、b、c所指向的內(nèi)存數(shù)據(jù)結(jié)構(gòu)？

引用計(jì)數(shù)的方案很有誘惑力，但正如鎖和順序鎖一樣，引用計(jì)數(shù)可能消耗掉數(shù)百個(gè)CPU指令周期，更致命的是，它會(huì)引用緩存行在CPU之間的來(lái)回顛簸，破壞各個(gè)CPU的緩存，引起系統(tǒng)整體性能的下降。很明顯，這種選擇不是我們所期望的。

想要理解Linux經(jīng)典RCU實(shí)現(xiàn)的讀者，應(yīng)當(dāng)認(rèn)真閱讀下面這段話：

一種實(shí)現(xiàn)方法是，寫(xiě)者完全不知道有哪些讀者存在。這種方法顯然讓讀者的性能最佳，但留給寫(xiě)者的問(wèn)題是：如何才能確定所有的老讀者已經(jīng)完成。

最簡(jiǎn)單的實(shí)現(xiàn)是：讓線程不會(huì)被搶占，或者說(shuō)，讀者在讀RCU數(shù)據(jù)期間不能被搶占。在這種不可搶占的環(huán)境中，每個(gè)線程將一直運(yùn)行，直到它明確地和自愿地阻塞自己（現(xiàn)實(shí)世界確實(shí)有這樣的操作系統(tǒng)，它由線程自己決定何時(shí)釋放CPU。例如大名鼎鼎的Solaris操作系統(tǒng)）。這要求一個(gè)不能阻塞的無(wú)限循環(huán)將使該CPU在循環(huán)開(kāi)始后無(wú)法用于任何其他目的，還要求還要求線程在持有自旋鎖時(shí)禁止阻塞。否則會(huì)形成死鎖。

這種方法的示意圖下所示，圖中的時(shí)間從頂部推移到底部，CPU 1的list_del()操作是RCU寫(xiě)者操作，CPU2、CPU3在讀端讀取list節(jié)點(diǎn)。

Linux經(jīng)典RCU的概念即是如此。雖然這種方法在生產(chǎn)環(huán)境上的實(shí)現(xiàn)可能相當(dāng)復(fù)雜，但是玩具實(shí)現(xiàn)卻非常簡(jiǎn)單。

1 for_each_online_cpu(cpu)

2 run_on(cpu);

for_each_online_cpu()原語(yǔ)遍歷所有CPU，run_on()函數(shù)導(dǎo)致當(dāng)前線程在指定的CPU上執(zhí)行，這會(huì)強(qiáng)制目標(biāo)CPU執(zhí)行上下文切換。因此，一旦for_each_online_cpu()完成，每個(gè)CPU都執(zhí)行了一次上下文切換，這又保證了所有之前存在的讀線程已經(jīng)完成。

請(qǐng)注意，這個(gè)方法不能用于生產(chǎn)環(huán)境。正確處理各種邊界條件和對(duì)性能優(yōu)化的強(qiáng)烈要求意味著用于生產(chǎn)環(huán)境的代碼實(shí)現(xiàn)將十分復(fù)雜。此外，可搶占環(huán)境的RCU實(shí)現(xiàn)需要讀者實(shí)際做點(diǎn)什么事情（也就是在讀臨界區(qū)內(nèi)，禁止搶占。這是Linux經(jīng)典RCU讀鎖的實(shí)現(xiàn)）。不過(guò)，這種簡(jiǎn)單的不可搶占的方法在概念上是完整的，有助于我們理解RCU的基本原理。

二、RCU是什么？

RCU是read-copy-update的簡(jiǎn)稱，翻譯為中文有點(diǎn)別扭“讀-復(fù)制-更新”。它是是一種同步機(jī)制，有三種角色或者操作：讀者、寫(xiě)者和復(fù)制操作，我理解其中的復(fù)制操作就是不同CPU上的讀者復(fù)制了不同的數(shù)據(jù)值，或者說(shuō)擁有同一個(gè)指針的不同拷貝值，也可以理解為：在讀者讀取值的時(shí)候，寫(xiě)者復(fù)制并替換其內(nèi)容（后一種理解來(lái)自于RCU作者的解釋）。它于2002年10月引入Linux內(nèi)核。

RCU允許讀操作可以與更新操作并發(fā)執(zhí)行，這一點(diǎn)提升了程序的可擴(kuò)展性。常規(guī)的互斥鎖讓并發(fā)線程互斥執(zhí)行，并不關(guān)心該線程是讀者還是寫(xiě)者，而讀/寫(xiě)鎖在沒(méi)有寫(xiě)者時(shí)允許并發(fā)的讀者，相比于這些常規(guī)鎖操作，RCU在維護(hù)對(duì)象的多個(gè)版本時(shí)確保讀操作保持一致，同時(shí)保證只有所有當(dāng)前讀端臨界區(qū)都執(zhí)行完畢后才釋放對(duì)象。RCU定義并使用了高效并且易于擴(kuò)展的機(jī)制，用來(lái)發(fā)布和讀取對(duì)象的新版本，還用于延后舊版本對(duì)象的垃圾收集工作。這些機(jī)制恰當(dāng)?shù)卦谧x端和更新端并行工作，使得讀端特別快速。在某些場(chǎng)合下（比如非搶占式內(nèi)核里），RCU讀端的函數(shù)完全是零開(kāi)銷(xiāo)。

Seqlock也可以讓讀者和寫(xiě)者并發(fā)執(zhí)行，但是二者有什么區(qū)別？

首先是二者的目的不一樣。Seqlock是為了保證讀端在讀取值的時(shí)候，寫(xiě)者沒(méi)有對(duì)它進(jìn)行修改，而RCU是為了多核擴(kuò)展性。

其次是保護(hù)的數(shù)據(jù)結(jié)構(gòu)大小不一樣。Seqlock可以保護(hù)一組相關(guān)聯(lián)的數(shù)據(jù)，而RCU只能保護(hù)指針這樣的unsigned long類型的數(shù)據(jù)。

最重要的區(qū)別還在于效率，Seqlock本質(zhì)上是與自旋鎖同等重量級(jí)的原語(yǔ)，其效率與RCU不在同一個(gè)數(shù)量級(jí)上面。

下面從三個(gè)基礎(chǔ)機(jī)制來(lái)闡述RCU究竟是什么？

RCU由三種基礎(chǔ)機(jī)制構(gòu)成，第一個(gè)機(jī)制用于插入，第二個(gè)用于刪除，第三個(gè)用于讓讀者可以不受并發(fā)的插入和刪除干擾。分別是：

發(fā)布/訂閱機(jī)制，用于插入。

等待已有的RCU讀者完成的機(jī)制，用于刪除。

維護(hù)對(duì)象多個(gè)版本的機(jī)制，以允許并發(fā)的插入和刪除操作。

1、發(fā)布/訂閱機(jī)制

RCU的一個(gè)關(guān)鍵特性是可以安全的讀取數(shù)據(jù)，即使數(shù)據(jù)此時(shí)正被修改。RCU通過(guò)一種發(fā)布/訂閱機(jī)制達(dá)成了并發(fā)的數(shù)據(jù)插入。舉個(gè)例子，假設(shè)初始值為NULL的全局指針gp現(xiàn)在被賦值指向一個(gè)剛分配并初始化的數(shù)據(jù)結(jié)構(gòu)。如下所示的代碼片段：

1 structfoo {

2 inta;

3 intb;

4 intc;

5 };

6 structfoo *gp =NULL;

7

8 /*. . . */

9

10 p= kmalloc(sizeof(*p), GFP_KERNEL);

11 p->a= 1;

12 p->b= 2;

13 p->c= 3;

14 gp = p;

“發(fā)布”數(shù)據(jù)結(jié)構(gòu)（不安全）

不幸的是，這塊代碼無(wú)法保證編譯器和CPU會(huì)按照編程順序執(zhí)行最后4條賦值語(yǔ)句。如果對(duì)gp的賦值發(fā)生在初始化p的各字段之前，那么并發(fā)的讀者會(huì)讀到未初始化的值。這里需要內(nèi)存屏障來(lái)保證事情按順序發(fā)生，可是內(nèi)存屏障又向來(lái)以難用而聞名。所以這里我們用一句rcu_assign_ pointer()原語(yǔ)將內(nèi)存屏障封裝起來(lái)，讓其擁有發(fā)布的語(yǔ)義。最后4行代碼如下。

1 p->a= 1;

2 p->b= 2;

3 p->c= 3;

4 rcu_assign_pointer(gp, p);

rcu_assign_pointer()“發(fā)布”一個(gè)新結(jié)構(gòu)，強(qiáng)制讓編譯器和CPU在為p的各字段賦值后再去為gp賦值。

不過(guò)，只保證更新者的執(zhí)行順序并不夠，因?yàn)樽x者也需要保證讀取順序。請(qǐng)看下面這個(gè)例子中的代碼。

1 p= gp;

2 if(p != NULL){

3 do_something_with(p->a, p->b,p->c);

4 }

這塊代碼看起來(lái)好像不會(huì)受到亂序執(zhí)行的影響，可惜事與愿違，在DEC Alpha CPU機(jī)器上，還有啟用編譯器值猜測(cè)（value-speculation）優(yōu)化時(shí)，會(huì)讓p->a，p->b和p->c的值在p賦值之前被讀取。

也許在啟動(dòng)編譯器的值猜測(cè)優(yōu)化時(shí)比較容易觀察到這一情形，此時(shí)編譯器會(huì)先猜測(cè)p->a、p->b、p->c的值，然后再去讀取p的實(shí)際值來(lái)檢查編譯器的猜測(cè)是否正確。這種類型的優(yōu)化十分激進(jìn)，甚至有點(diǎn)瘋狂，但是這確實(shí)發(fā)生在剖析驅(qū)動(dòng)（profile-driven）優(yōu)化的上下文中。

然而讀者可能會(huì)說(shuō)，我們一般不會(huì)使用編譯器猜測(cè)優(yōu)化。那么我們可以考慮DEC Alpha CPU這樣的極端弱序的CPU。在這個(gè)CPU上面，引起問(wèn)題的根源在于：在同一個(gè)CPU內(nèi)部，使用了不止一個(gè)緩存來(lái)緩存CPU數(shù)據(jù)。這樣可能使用p和p->a被分布不同一個(gè)CPU的不同緩存中，造成緩存一致性方面的問(wèn)題。

顯然，我們必須在編譯器和CPU層面阻止這種危險(xiǎn)的優(yōu)化。rcu_dereference()原語(yǔ)用了各種內(nèi)存屏障指令和編譯器指令來(lái)達(dá)到這一目的。

1 rcu_read_lock();

2 p= rcu_dereference(gp);

3 if(p != NULL){

4 do_something_with(p->a, p->b,p->c);

5 }

6 rcu_read_unlock();

其中rcu_read_ lock()和rcu_read_unlock()這對(duì)原語(yǔ)定義了RCU讀端的臨界區(qū)。事實(shí)上，在沒(méi)有配置CONFIG_PREEMPT的內(nèi)核里，這對(duì)原語(yǔ)就是空函數(shù)。在可搶占內(nèi)核中，這這對(duì)原語(yǔ)就是關(guān)閉/打開(kāi)搶占。

rcu_dereference()原語(yǔ)用一種“訂閱”的辦法獲取指定指針的值。保證后續(xù)的解引用操作可以看見(jiàn)在對(duì)應(yīng)的“發(fā)布”操作（rcu_assign_pointer()）前進(jìn)行的初始化，即：在看到p的新值之前，能夠看到p->a、p->b、p->c的新值。請(qǐng)注意，rcu_assign_pointer()和rcu_dereference()這對(duì)原語(yǔ)既不會(huì)自旋或者阻塞，也不會(huì)阻止list_add_ rcu()的并發(fā)執(zhí)行。

雖然理論上rcu_assign_pointer()和rcu_derederence()可以用于構(gòu)造任何能想象到的受RCU保護(hù)的數(shù)據(jù)結(jié)構(gòu)，但是實(shí)踐中常常只用于構(gòu)建更上層的原語(yǔ)。例如，將rcu_assign_pointer()和rcu_dereference()原語(yǔ)嵌入在Linux鏈表的RCU變體中。Linux有兩種雙鏈表的變體，循環(huán)鏈表struct list_head和哈希表structhlist_head/struct hlist_node。前一種如下圖所示。

對(duì)鏈表采用指針發(fā)布的例子如下：

1 struct foo {

2struct list_head *list;

3 int a;

4 int b;

5 int c;

6 };

7LIST_HEAD(head);

8

9 /* .. . */

10

11 p =kmalloc(sizeof(*p), GFP_KERNEL);

12p->a = 1;

13p->b = 2;

14p->c = 3;

15list_add_rcu(&p->list,&head);

RCU發(fā)布鏈表

第15行必須用某些同步機(jī)制（最常見(jiàn)的是各種鎖）來(lái)保護(hù)，防止多核list_add()實(shí)例并發(fā)執(zhí)行。不過(guò)，同步并不能阻止list_add()的實(shí)例與RCU的讀者并發(fā)執(zhí)行。

訂閱一個(gè)受RCU保護(hù)的鏈表的代碼非常直接。

1 rcu_read_lock();

2 list_for_each_entry_rcu(p, head,list) {

3 do_something_with(p->a, p->b,p->c);

4 }

5 rcu_read_unlock();

list_add_rcu()原語(yǔ)向指定的鏈表發(fā)布了一項(xiàng)條目，保證對(duì)應(yīng)的list_for_each_ entry_rcu()可以訂閱到同一項(xiàng)條目。

Linux的其他鏈表、哈希表都是線性鏈表，這意味著它的頭結(jié)點(diǎn)只需要一個(gè)指針，而不是象循環(huán)鏈表那樣需要兩個(gè)。因此哈希表的使用可以減少哈希表的hash bucket數(shù)組一半的內(nèi)存消耗。

向受RCU保護(hù)的哈希表發(fā)布新元素和向循環(huán)鏈表的操作十分類似，如下所示。

1 struct foo {

2struct hlist_node *list;

3 int a;

4 int b;

5 int c;

6 };

7HLIST_HEAD(head);

8

9 /* .. . */

10

11 p =kmalloc(sizeof(*p), GFP_KERNEL);

12p->a = 1;

13p->b = 2;

14p->c = 3;

15hlist_add_head_rcu(&p->list,&head);

和之前一樣，第15行必須用某種同步機(jī)制，比如鎖來(lái)保護(hù)。

訂閱受RCU保護(hù)的哈希表和訂閱循環(huán)鏈表沒(méi)什么區(qū)別。

1rcu_read_lock();

2hlist_for_each_entry_rcu(p,q, head, list){

3do_something_with(p->a,p->b, p->c);

4 }

5 rcu_read_unlock();

表9.2是RCU的發(fā)布和訂閱原語(yǔ)，另外還有一個(gè)刪除發(fā)布原語(yǔ)。

請(qǐng)注意，list_replace_rcu()、list_del_rcu()、hlist_replace_rcu()和hlist_ del_rcu()這些API引入了一點(diǎn)復(fù)雜性。何時(shí)才能安全地釋放剛被替換或者刪除的數(shù)據(jù)元素？我們?cè)趺茨苤篮螘r(shí)所有讀者釋放了他們對(duì)數(shù)據(jù)元素的引用？

2、等待已有的RCU讀者執(zhí)行完畢

從最基本的角度來(lái)說(shuō)，RCU就是一種等待事物結(jié)束的方式。當(dāng)然，有很多其他的方式可以用來(lái)等待事物結(jié)束，比如引用計(jì)數(shù)、讀/寫(xiě)鎖、事件等等。RCU的最偉大之處在于它可以等待（比如）20,000種不同的事物，而無(wú)需顯式地去跟蹤它們中的每一個(gè)，也無(wú)需去擔(dān)心對(duì)性能的影響，對(duì)擴(kuò)展性的限制，復(fù)雜的死鎖場(chǎng)景，還有內(nèi)存泄漏帶來(lái)的危害等等使用顯式跟蹤手段會(huì)出現(xiàn)的問(wèn)題。

在RCU的例子中，被等待的事物稱為“RCU讀端臨界區(qū)”。RCU讀端臨界區(qū)從rcu_read_lock()原語(yǔ)開(kāi)始，到對(duì)應(yīng)的rcu_read_unlock()原語(yǔ)結(jié)束。RCU讀端臨界區(qū)可以嵌套，也可以包含一大塊代碼，只要這其中的代碼不會(huì)阻塞或者睡眠（先不考慮可睡眠RCU）。如果你遵守這些約定，就可以使用RCU去等待任何代碼的完成。

RCU通過(guò)間接地確定這些事物何時(shí)完成，才完成了這樣的壯舉。

如上圖所示，RCU是一種等待已有的RCU讀端臨界區(qū)執(zhí)行完畢的方法，這里的執(zhí)行完畢也包括在臨界區(qū)里執(zhí)行的內(nèi)存操作。不過(guò)請(qǐng)注意，在某個(gè)寬限期開(kāi)始后才啟動(dòng)的RCU讀端臨界區(qū)會(huì)擴(kuò)展到該寬限期的結(jié)尾處。

下列偽代碼展示了寫(xiě)者使用RCU等待讀者的基本方法。

1．作出改變，比如替換鏈表中的一個(gè)元素。

2．等待所有已有的RCU讀端臨界區(qū)執(zhí)行完畢（比如使用synchronize_rcu()原語(yǔ)）。這里要注意的是后續(xù)的RCU讀端臨界區(qū)無(wú)法獲取剛剛刪除元素的引用。

3．清理，比如釋放剛才被替換的元素。

下圖所示的代碼片段演示了這個(gè)過(guò)程，其中字段a是搜索關(guān)鍵字。

1 struct foo {

2struct list_head *list;

3 int a;

4 int b;

5 int c;

6 };

7LIST_HEAD(head);

8

9 /* .. . */

10

11 p =search(head, key);

12 if (p== NULL) {

13 /* Takeappropriate action, unlock,and

return.*/

14 }

15 q =kmalloc(sizeof(*p), GFP_KERNEL);

16 *q = *p;

17q->b = 2;

18q->c = 3;

19list_replace_rcu(&p->list,&q->list);

20synchronize_rcu();

21 kfree(p);

標(biāo)準(zhǔn)RCU替換示例

第19、20和21行實(shí)現(xiàn)了剛才提到的三個(gè)步驟。第16至19行正如RCU其名（讀-復(fù)制-更新），在允許并發(fā)讀的同時(shí)，第16行復(fù)制，第17到19行更新。

synchronize_rcu()原語(yǔ)可以相當(dāng)簡(jiǎn)單。然而，想要達(dá)到產(chǎn)品質(zhì)量，代碼實(shí)現(xiàn)必須處理一些困難的邊界情況，并且還要進(jìn)行大量?jī)?yōu)化，這兩者都將導(dǎo)致明顯的復(fù)雜性。理解RCU的難點(diǎn)，主要在于synchronize_rcu()的實(shí)現(xiàn)。

3、維護(hù)最近被更新對(duì)象的多個(gè)版本

下面展示RCU如何維護(hù)鏈表的多個(gè)版本，供并發(fā)的讀者訪問(wèn)。通過(guò)兩個(gè)例子來(lái)說(shuō)明在讀者還處于RCU讀端臨界區(qū)時(shí)，被讀者引用的數(shù)據(jù)元素如何保持完整性。第一個(gè)例子展示了鏈表元素的刪除，第二個(gè)例子展示了鏈表元素的替換。

例子1：在刪除過(guò)程中維護(hù)多個(gè)版本

1 p= search(head, key);

2 if(p != NULL){

3 list_del_rcu(&p->list);

4 synchronize_rcu();

5 kfree(p);

6 }

如下圖，每個(gè)元素中的三個(gè)數(shù)字分別代表字段a、b、c的值。紅色的元素表示RCU讀者此時(shí)正持有該元素的引用。請(qǐng)注意，我們?yōu)榱俗寛D更清楚，忽略了后向指針和從尾指向頭的指針。

等第3行的list_del_rcu()執(zhí)行完畢后，“5、6、7”元素從鏈表中被刪除。因?yàn)樽x者不直接與更新者同步，所以讀者可能還在并發(fā)地掃描鏈表。這些并發(fā)的讀者有可能看見(jiàn)，也有可能看不見(jiàn)剛剛被刪除的元素，這取決于掃描的時(shí)機(jī)。不過(guò)，剛好在取出指向被刪除元素指針后被延遲的讀者（比如，由于中斷、ECC內(nèi)存錯(cuò)誤），就有可能在刪除后還看見(jiàn)鏈表元素的舊值。因此，我們此時(shí)有兩個(gè)版本的鏈表，一個(gè)有元素“5、6、7”，另一個(gè)沒(méi)有。元素“5、6、7”用黃色標(biāo)注，表明老讀者可能還在引用它，但是新讀者已經(jīng)無(wú)法獲得它的引用。

請(qǐng)注意，讀者不允許在退出RCU讀端臨界區(qū)后還維護(hù)元素“5、6、7”的引用。因此，一旦第4行的synchronize_rcu()執(zhí)行完畢，所有已有的讀者都要保證已經(jīng)執(zhí)行完，不能再有讀者引用該元素。這樣我們又回到了唯一版本的鏈表。

此時(shí)，元素“5、6、7”可以安全被釋放了。這樣我們就完成了元素“5、6、7”的刪除。

例子2：在替換過(guò)程中維護(hù)多個(gè)版本

1 q= kmalloc(sizeof(*p), GFP_KERNEL);

2 *q = *p;

3 q->b = 2;

4 q->c = 3;

5list_replace_rcu(&p->list,&q->list);

6synchronize_rcu();

7 kfree(p);

鏈表的初始狀態(tài)包括指針p都和“刪除”例子中一樣。

RCU從鏈表中替換元素

和前面一樣，每個(gè)元素中的三個(gè)數(shù)字分別代表字段a、b、c。紅色的元素表示讀者可能正在引用，并且因?yàn)樽x者不直接與更新者同步，所以讀者有可能與整個(gè)替換過(guò)程并發(fā)執(zhí)行。請(qǐng)注意我們?yōu)榱藞D表的清晰，再一次忽略了后向指針和從尾指向頭的指針。

下面描述了元素“5、2、3”如何替換元素“5、6、7”的過(guò)程，任何特定讀者可能看見(jiàn)這兩個(gè)值其中一個(gè)。

第1行用kmalloc()分配了要替換的元素。此時(shí)，沒(méi)有讀者持有剛分配的元素的引用（用綠色表示），并且該元素是未初始化的（用問(wèn)號(hào)表示）。

第2行將舊元素復(fù)制給新元素。新元素此時(shí)還不能被讀者訪問(wèn)，但是已經(jīng)初始化了。

第3行將q->b的值更新為2，第4行將q->c的值更新為3。

現(xiàn)在，第5行開(kāi)始替換，這樣新元素終于對(duì)讀者可見(jiàn)了，因此顏色也變成了紅色。此時(shí)，鏈表就有兩個(gè)版本了。已經(jīng)存在的老讀者可能看到元素“5、6、7”（現(xiàn)在顏色是黃色的），而新讀者將會(huì)看見(jiàn)元素“5、2、3”。不過(guò)這里可以保證任何讀者都能看到一個(gè)完好的鏈表。

隨著第6行synchronize_rcu()的返回，寬限期結(jié)束，所有在list_replace_rcu()之前開(kāi)始的讀者都已經(jīng)完成。特別是任何可能持有元素“5、6、7”引用的讀者保證已經(jīng)退出了它們的RCU讀端臨界區(qū)，不能繼續(xù)持有引用。因此，不再有任何讀者持有舊數(shù)據(jù)的引用,，如第6排綠色部分所示。這樣我們又回到了單一版本的鏈表，只是用新元素替換了舊元素。

等第7行的kfree()完成后，鏈表就成了最后一排的樣子。

不過(guò)盡管RCU是因替換的例子而得名的，但是RCU在內(nèi)核中的主要用途還是用于簡(jiǎn)單的刪除。