hi，大家好，今天給大家分享并行程序設(shè)計(jì)中最重要的鎖-RCU鎖，RCU鎖本質(zhì)是用空間換時(shí)間，是對(duì)讀寫鎖的一種優(yōu)化加強(qiáng)，但不僅僅是這樣簡(jiǎn)單，RCU體現(xiàn)出來(lái)的垃圾回收思想，也是值得我們學(xué)習(xí)和借鑒，。

各個(gè)語(yǔ)言C， C++，Java， go等都有RCU鎖實(shí)現(xiàn)，同時(shí)內(nèi)核精巧的實(shí)現(xiàn)也是學(xué)習(xí)代碼設(shè)計(jì)好素材，深入理解RCU分為兩個(gè)部分，第一部分主要是講核心原理，理解其核心設(shè)計(jì)思想，對(duì)RCU會(huì)有個(gè)宏觀的理解；第二部分會(huì)分析源碼實(shí)現(xiàn)（本來(lái)準(zhǔn)備放在一起，由于實(shí)現(xiàn)相當(dāng)精巧，篇幅會(huì)很多，就單獨(dú)成一篇），希望大家喜歡。

并行程序設(shè)計(jì)演進(jìn)如何正確有效的保護(hù)共享數(shù)據(jù)是編寫并行程序必須面臨的一個(gè)難題，通常的手段就是同步。同步可分為阻塞型同步（Blocking Synchronization）和非阻塞型同步（ Non-blocking Synchronization）。

阻塞型同步是指當(dāng)一個(gè)線程到達(dá)臨界區(qū)時(shí)，因另外一個(gè)線程已經(jīng)持有訪問(wèn)該共享數(shù)據(jù)的鎖，從而不能獲取鎖資源而阻塞（睡眠），直到另外一個(gè)線程釋放鎖。常見(jiàn)的同步原語(yǔ)有 mutex、semaphore 等。如果同步方案采用不當(dāng)，就會(huì)造成死鎖（deadlock），活鎖（livelock）和優(yōu)先級(jí)反轉(zhuǎn)（priority inversion），以及效率低下等現(xiàn)象。

為了降低風(fēng)險(xiǎn)程度和提高程序運(yùn)行效率，業(yè)界提出了不采用鎖的同步方案，依照這種設(shè)計(jì)思路設(shè)計(jì)的算法稱為非阻塞型同步，其本質(zhì)就是停止一個(gè)線程的執(zhí)行不會(huì)阻礙系統(tǒng)中其他執(zhí)行實(shí)體的運(yùn)行。

先有阻塞型同步

互斥鎖（英語(yǔ)：Mutual exclusion，縮寫Mutex）是一種用于多線程編程中，防止兩條線程同時(shí)對(duì)同一公共資源進(jìn)行讀寫的機(jī)制。該目的通過(guò)將代碼切片成一個(gè)一個(gè)的臨界區(qū)域（critical section）達(dá)成。臨界區(qū)域指的是一塊對(duì)公共資源進(jìn)行存取的代碼。

信號(hào)量（Semaphore），是在多線程環(huán)境下使用的一種設(shè)施，是可以用來(lái)保證兩個(gè)或多個(gè)關(guān)鍵代碼段不被并發(fā)調(diào)用，可以認(rèn)為mutex是0-1信號(hào)量；

讀寫鎖是計(jì)算機(jī)程序的并發(fā)控制的一種同步機(jī)制，它把對(duì)共享資源的訪問(wèn)者劃分成讀者和寫者，讀者只對(duì)共享資源進(jìn)行讀訪問(wèn)，寫者則需要對(duì)共享資源進(jìn)行寫操作，讀操作可并發(fā)重入，寫操作是互斥的。

再有非阻塞型同步

當(dāng)今比較流行的非阻塞型同步實(shí)現(xiàn)方案有三種：

Wait-free（無(wú)等待）

Wait-free 是指任意線程的任何操作都可以在有限步之內(nèi)結(jié)束，而不用關(guān)心其它線程的執(zhí)行速度。Wait-free 是基于 per-thread 的，可以認(rèn)為是 starvation-free 的。非常遺憾的是實(shí)際情況并非如此，采用 Wait-free 的程序并不能保證 starvation-free，同時(shí)內(nèi)存消耗也隨線程數(shù)量而線性增長(zhǎng)。目前只有極少數(shù)的非阻塞算法實(shí)現(xiàn)了這一點(diǎn)。

簡(jiǎn)單理解：任意時(shí)刻所有的線程都在干活；

Lock-free（無(wú)鎖）

Lock-Free是指能夠確保執(zhí)行它的所有線程中至少有一個(gè)能夠繼續(xù)往下執(zhí)行。由于每個(gè)線程不是 starvation-free 的，即有些線程可能會(huì)被任意地延遲，然而在每一步都至少有一個(gè)線程能夠往下執(zhí)行，因此系統(tǒng)作為一個(gè)整體是在持續(xù)執(zhí)行的，可以認(rèn)為是 system-wide 的。所有 Wait-free 的算法都是 Lock-Free 的。

簡(jiǎn)單理解：任意時(shí)刻至少一個(gè)線程在干活；

Obstruction-free（無(wú)障礙）

Obstruction-free 是指在任何時(shí)間點(diǎn)，一個(gè)孤立運(yùn)行線程的每一個(gè)操作可以在有限步之內(nèi)結(jié)束。只要沒(méi)有競(jìng)爭(zhēng)，線程就可以持續(xù)運(yùn)行。一旦共享數(shù)據(jù)被修改，Obstruction-free 要求中止已經(jīng)完成的部分操作，并進(jìn)行回滾。所有 Lock-Free 的算法都是 Obstruction-free 的。

簡(jiǎn)單理解：只要數(shù)據(jù)有修改，就會(huì)重新獲取，并且把已經(jīng)完成操作回滾重來(lái)；

綜上所述，不難得出 Obstruction-free 是 Non-blocking synchronization 中性能最差的，而 Wait-free 性能是最好的，但實(shí)現(xiàn)難度也是最大的，因此 Lock-free 算法開(kāi)始被重視，并廣泛運(yùn)用于各種程序設(shè)計(jì)中，這里主要介紹Lock_free算法。

lock-free（無(wú)鎖）往往可以提供更好的性能和伸縮性保證，但實(shí)際上其優(yōu)點(diǎn)不止于此。早期這些概念首先是在操作系統(tǒng)上應(yīng)用的，因?yàn)橐粋€(gè)不依賴于鎖的算法，可以應(yīng)用于各種場(chǎng)景下，而無(wú)需考慮各種錯(cuò)誤，故障，失敗等情形。比如死鎖，中斷，甚至CPU失效。

主流無(wú)鎖技術(shù)

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

● test-and-set （TSR）

● compare-and-swap （CAS）

● load-link/store-conditional （ll/sc）

Spin Lock（自旋鎖）是一種輕量級(jí)的同步方法，一種非阻塞鎖。當(dāng) lock 操作被阻塞時(shí)，并不是把自己掛到一個(gè)等待隊(duì)列，而是死循環(huán) CPU 空轉(zhuǎn)等待其他線程釋放鎖。

Seqlock （順序鎖） 是Linux 2.6 內(nèi)核中引入一種新型鎖，它與 spin lock 讀寫鎖非常相似，只是它為寫者賦予了較高的優(yōu)先級(jí)。也就是說(shuō)，即使讀者正在讀的時(shí)候也允許寫者繼續(xù)運(yùn)行，讀者會(huì)檢查數(shù)據(jù)是否有更新，如果數(shù)據(jù)有更新就會(huì)重試，因?yàn)?seqlock 對(duì)寫者更有利，只要沒(méi)有其他寫者，寫鎖總能獲取成功。

RCU（Read-Copy Update），顧名思義就是讀-拷貝修改，它是基于其原理命名的。對(duì)于被RCU保護(hù)的共享數(shù)據(jù)結(jié)構(gòu)，讀者不需要獲得任何鎖就可以訪問(wèn)它，但寫者在訪問(wèn)它時(shí)首先拷貝一個(gè)副本，然后對(duì)副本進(jìn)行修改，最后使用一個(gè)回調(diào)（callback）機(jī)制在適當(dāng)?shù)臅r(shí)機(jī)把指向原來(lái)數(shù)據(jù)的指針替換為新的被修改的數(shù)據(jù)。這個(gè)時(shí)機(jī)就是所有引用該數(shù)據(jù)的CPU都退出對(duì)共享數(shù)據(jù)的訪問(wèn)。

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

歷史背景高性能并行程序中，數(shù)據(jù)一致性訪問(wèn)是一個(gè)非常重要的部分，一般都是采用鎖機(jī)制（semaphore、spinlock、rwlock等）進(jìn)行保護(hù)共享數(shù)據(jù)，根本的思想就是在訪問(wèn)臨界資源時(shí)，首先訪問(wèn)一個(gè)全局的變量（鎖），通過(guò)全局變量的狀態(tài)來(lái)控制線程對(duì)臨界資源的訪問(wèn)。但是，這種思想是需要硬件支持的，硬件需要配合實(shí)現(xiàn)全局變量（鎖）的讀-修改-寫，現(xiàn)代CPU都會(huì)提供這樣的原子化指令。

采用鎖機(jī)制實(shí)現(xiàn)數(shù)據(jù)訪問(wèn)的一致性存在如下兩個(gè)問(wèn)題：

效率問(wèn)題。鎖機(jī)制的實(shí)現(xiàn)需要對(duì)內(nèi)存的原子化訪問(wèn)，這種訪問(wèn)操作會(huì)破壞流水線操作，降低了流水線效率，這是影響性能的一個(gè)因素。另外，在采用讀寫鎖機(jī)制的情況下，寫鎖是排他鎖，無(wú)法實(shí)現(xiàn)寫鎖與讀鎖的并發(fā)操作，在某些應(yīng)用下會(huì)降低性能。

擴(kuò)展性問(wèn)題。例如，當(dāng)系統(tǒng)中CPU數(shù)量增多的時(shí)候，采用鎖機(jī)制實(shí)現(xiàn)數(shù)據(jù)的同步訪問(wèn)效率偏低。并且隨著CPU數(shù)量的增多，效率降低，由此可見(jiàn)鎖機(jī)制實(shí)現(xiàn)的數(shù)據(jù)一致性訪問(wèn)擴(kuò)展性差。

原始的RCU思想

在多線程場(chǎng)景下，經(jīng)常我們需要并發(fā)訪問(wèn)一個(gè)數(shù)據(jù)結(jié)構(gòu)，為了保證線程安全我們會(huì)考慮使用互斥設(shè)施來(lái)進(jìn)行同步，更進(jìn)一步我們會(huì)根據(jù)對(duì)這個(gè)數(shù)據(jù)結(jié)構(gòu)的讀寫比例而選用讀寫鎖進(jìn)行優(yōu)化。但是讀寫鎖不是唯一的方式，我們可以借助于COW技術(shù)來(lái)做到寫操作不需要加鎖，也就是在讀的時(shí)候正常讀，寫的時(shí)候，先加鎖拷貝一份，然后進(jìn)行寫，寫完就原子的更新回去，使用COW實(shí)現(xiàn)避免了頻繁加讀寫鎖本身的性能開(kāi)銷。

優(yōu)缺點(diǎn)

由于 RCU 旨在最小化讀取端開(kāi)銷，因此僅在以更高速率使用同步邏輯進(jìn)行讀取操作時(shí)才使用它。如果更新操作超過(guò)10%，性能反而會(huì)變差，所以應(yīng)該選擇另一種同步方式而不是RCU。

好處

幾乎沒(méi)有讀取端開(kāi)銷。零等待，零開(kāi)銷

沒(méi)有死鎖問(wèn)題

沒(méi)有優(yōu)先級(jí)倒置問(wèn)題（優(yōu)先級(jí)倒置和優(yōu)先級(jí)繼承）

無(wú)限制延遲沒(méi)有問(wèn)題

無(wú)內(nèi)存泄漏風(fēng)險(xiǎn)問(wèn)題

缺點(diǎn)

使用起來(lái)有點(diǎn)復(fù)雜

對(duì)于寫操作，它比其他同步技術(shù)稍慢

適用場(chǎng)景

核心原理理論基礎(chǔ)-QSBR算法

（Quiescent State-Based Reclamation）

這個(gè)算法的核心思想就是識(shí)別出線程的不活動(dòng)（quiescent）狀態(tài)，那么什么時(shí)候才算是不活動(dòng)的狀態(tài)呢？這個(gè)狀態(tài)和臨界區(qū)狀態(tài)是相對(duì)的，線程離開(kāi)臨界區(qū)就是不活動(dòng)的狀態(tài)了。識(shí)別出不活動(dòng)狀態(tài)了，還需要把狀態(tài)通知出去，讓其他線程知道，這整個(gè)過(guò)程可以用下面的圖來(lái)描述：

上面有四個(gè)線程，線程1執(zhí)行完更新操作后添加了釋放內(nèi)存的callback，此時(shí)線程2，3，4都讀取的是之前的內(nèi)容，等他們執(zhí)行完成后分別回去調(diào)用onQuiescentState來(lái)表明自己已經(jīng)不不活動(dòng)了，等到最后一個(gè)線程調(diào)用onQuiescentState的時(shí)候就可以去調(diào)用注冊(cè)的callback了。

要實(shí)現(xiàn)上面這個(gè)過(guò)程其要點(diǎn)就是選擇適合的位置執(zhí)行onQuiescentState，還有就是如何知道誰(shuí)是最后一個(gè)執(zhí)行onQuiescentState的線程。

批量回收，如果更新的次數(shù)比較多的話，但是每次只回調(diào)一個(gè)callback，釋放一次內(nèi)存就會(huì)導(dǎo)致內(nèi)存釋放跟不上回收的速度，為此需要進(jìn)行批量回收，每次更新都會(huì)注冊(cè)新的callback，當(dāng)?shù)谝淮嗡械木€程都進(jìn)入不活動(dòng)狀態(tài)的時(shí)候就把當(dāng)前的所有callback保存起來(lái)，等待下一次所有線程進(jìn)入不活動(dòng)的狀態(tài)的時(shí)候就回調(diào)前一次所有的callback。

基本架構(gòu)

Linux 內(nèi)核RCU 參考QSBR算法設(shè)計(jì)一套無(wú)鎖同步機(jī)制。

多個(gè)讀者可以并發(fā)訪問(wèn)共享數(shù)據(jù)，而不需要加鎖；

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

修改資源后，需要更新共享資源，讓后面讀者可以訪問(wèn)最新的數(shù)據(jù)；

等舊資源上所有的讀者都訪問(wèn)完畢后，就可以回收舊資源了；

RCU 模型

Removal：在寫端臨界區(qū)部分，讀取（Read（）），進(jìn)行復(fù)制（Copy），并執(zhí)行更改（Update）操作；

Grace Period：這是一個(gè)等待期，以確保所有與執(zhí)行刪除的數(shù)據(jù)相關(guān)的reader訪問(wèn)完畢；

Reclamation：回收舊數(shù)據(jù)；

三個(gè)重要概念

靜止?fàn)顟B(tài)QS（Quiescent State）： CPU發(fā)生了上下文切換稱為經(jīng)歷一個(gè)quiescent state；

寬限期GP（Grace Period）： grace period就是所有CPU都經(jīng)歷一次quiescent state所需要的等待的時(shí)間，也即系統(tǒng)中所有的讀者完成對(duì)共享臨界區(qū)的訪問(wèn)；

讀側(cè)臨界部分RCS（Read-Side Critical Section）： 保護(hù)禁止其他CPU修改的代碼區(qū)域，但允許多個(gè)CPU同時(shí)讀；

三個(gè)主要的角色

讀者reader：

安全訪問(wèn)臨界區(qū)資源；

負(fù)責(zé)標(biāo)識(shí)進(jìn)出臨界區(qū)；

寫者updater：

復(fù)制一份數(shù)據(jù)，然后更新數(shù)據(jù)；

用新數(shù)據(jù)覆蓋舊數(shù)據(jù)，然后進(jìn)入grace period；

回收者reclaimer：

等待在grace period之前的讀者退出臨界區(qū)；

在寬限期結(jié)束后，負(fù)責(zé)回收舊資源；

三個(gè)重要機(jī)制

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

主要用于更新數(shù)據(jù)，即使在數(shù)據(jù)被同時(shí)修改時(shí)線程也能安全瀏覽數(shù)據(jù)。RCU通過(guò)發(fā)布-訂閱機(jī)制（Publish-Subscribe Mechanism）實(shí)現(xiàn)這種并發(fā)的插入操作能力；

延遲回收機(jī)制：

實(shí)現(xiàn)檢查舊數(shù)據(jù)上所有RCU讀者完成，用于安全刪除舊數(shù)據(jù)；

多版本機(jī)制：

維護(hù)最近更新對(duì)象的多個(gè)版本，用于允許讀者容忍并發(fā)的插入和刪除新對(duì)象的多個(gè)版本；

最后總結(jié)最后，總結(jié)一下RCU鎖的核心思想：

讀者無(wú)鎖訪問(wèn)數(shù)據(jù)，標(biāo)記進(jìn)出臨界區(qū)；

寫者讀取，復(fù)制，更新；

舊數(shù)據(jù)延遲回收；

RCU核心思想就三句話，產(chǎn)品經(jīng)理都說(shuō)簡(jiǎn)單，但Linux內(nèi)核實(shí)現(xiàn)卻不是這么簡(jiǎn)單。除了要實(shí)現(xiàn)基本功能，需要考慮很多復(fù)雜情況：

內(nèi)核的RCU系統(tǒng)可以說(shuō)是內(nèi)核最復(fù)雜系統(tǒng)之一，為了高性能和多核擴(kuò)展性，設(shè)計(jì)了非常精巧的數(shù)據(jù)結(jié)構(gòu)：

同時(shí)巧妙實(shí)現(xiàn)了很多核心流程：

檢查當(dāng)前CPU是否度過(guò)QS；

QS report（匯報(bào)寬限期度過(guò)）；

寬限期的發(fā)起與完成；

rcu callbacks處理；

其中很多實(shí)現(xiàn)都可以說(shuō)是非常精巧，結(jié)合了預(yù)處理，批量處理，延后（異步）處理，多核并發(fā)，原子操作，異常處理，多場(chǎng)景精細(xì)優(yōu)化等多種技術(shù)，性能好，可擴(kuò)展性強(qiáng)，穩(wěn)定性強(qiáng)，有一定的學(xué)習(xí)和參考價(jià)值，即使你的工作不是內(nèi)核編程，里面體現(xiàn)很多編程思想和代碼設(shè)計(jì)思想，也是值得大家學(xué)習(xí)的。

擴(kuò)展閱讀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

編輯：jq