并行程序設(shè)計中最重要的鎖-RCU鎖

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

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

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

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

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

先有阻塞型同步

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

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

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

再有非阻塞型同步

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

Wait-free（無等待）

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

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

Lock-free（無鎖）

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

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

Obstruction-free（無障礙）

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

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

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

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

主流無鎖技術(shù)

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

● test-and-set （TSR）

● compare-and-swap （CAS）

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

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

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

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

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

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

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

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

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

原始的RCU思想

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

優(yōu)缺點

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

好處

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

沒有死鎖問題

沒有優(yōu)先級倒置問題（優(yōu)先級倒置和優(yōu)先級繼承）

無限制延遲沒有問題

無內(nèi)存泄漏風險問題

缺點

使用起來有點復(fù)雜

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

適用場景

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

（Quiescent State-Based Reclamation）

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

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

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

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

基本架構(gòu)

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

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

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

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

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

RCU 模型

Removal：在寫端臨界區(qū)部分，讀?。≧ead（）），進行復(fù)制（Copy），并執(zhí)行更改（Update）操作；

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

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

三個重要概念

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

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

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

三個主要的角色

讀者reader：

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

負責標識進出臨界區(qū)；

寫者updater：

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

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

回收者reclaimer：

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

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

三個重要機制

發(fā)布/訂閱機制

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

延遲回收機制：

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

多版本機制：

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

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

讀者無鎖訪問數(shù)據(jù)，標記進出臨界區(qū)；

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

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

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

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

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

檢查當前CPU是否度過QS；

QS report（匯報寬限期度過）；

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

rcu callbacks處理；

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

擴展閱讀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