并行程序設(shè)計演進
如何正確有效的保護共享數(shù)據(jù)是編寫并行程序必須面臨的一個難題,通常的手段就是同步。同步可分為阻塞型同步(Blocking Synchronization)和非阻塞型同步( Non-blocking Synchronization)。阻塞型同步是指當(dāng)一個線程到達臨界區(qū)時,因另外一個線程已經(jīng)持有訪問該共享數(shù)據(jù)的鎖,從而不能獲取鎖資源而阻塞(睡眠),直到另外一個線程釋放鎖。常見的同步原語有 mutex、semaphore 等。如果同步方案采用不當(dāng),就會造成死鎖(deadlock),活鎖(livelock)和優(yōu)先級反轉(zhuǎn)(priority inversion),以及效率低下等現(xiàn)象。
為了降低風(fēng)險程度和提高程序運行效率,業(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ā)重入,寫操作是互斥的。
再有非阻塞型同步
當(dāng)今比較流行的非阻塞型同步實現(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)完成操作回滾重來;
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(自旋鎖)是一種輕量級的同步方法,一種非阻塞鎖。當(dāng) 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)機制在適當(dāng)?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)用下會降低性能。
-
擴展性問題。例如,當(dāng)系統(tǒng)中CPU數(shù)量增多的時候,采用鎖機制實現(xiàn)數(shù)據(jù)的同步訪問效率偏低。并且隨著CPU數(shù)量的增多,效率降低,由此可見鎖機制實現(xiàn)的數(shù)據(jù)一致性訪問擴展性差。
在多線程場景下,經(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ēng)險問題
-
缺點
-
使用起來有點復(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,當(dāng)?shù)谝淮嗡械木€程都進入不活動狀態(tài)的時候就把當(dāng)前的所有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ū)的訪問;
GP原理
讀側(cè)臨界部分RCS(Read-Side Critical Section): 保護禁止其他CPU修改的代碼區(qū)域,但允許多個CPU同時讀;
三個主要的角色
讀者reader:
-
安全訪問臨界區(qū)資源;
-
負責(zé)標識進出臨界區(qū);
-
復(fù)制一份數(shù)據(jù),然后更新數(shù)據(jù);
-
用新數(shù)據(jù)覆蓋舊數(shù)據(jù),然后進入grace period;
-
等待在grace period之前的讀者退出臨界區(qū);
-
在寬限期結(jié)束后,負責(zé)回收舊資源;
發(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ù)延遲回收;
內(nèi)核的RCU系統(tǒng)可以說是內(nèi)核最復(fù)雜系統(tǒng)之一,為了高性能和多核擴展性,設(shè)計了非常精巧的數(shù)據(jù)結(jié)構(gòu):
同時巧妙實現(xiàn)了很多核心流程:
-
檢查當(dāng)前CPU是否度過QS;
-
QS report(匯報寬限期度過);
-
寬限期的發(fā)起與完成;
-
rcu callbacks處理;
擴展閱讀
http://csng.cs.toronto.edu/publication_files/0000/0159/jpdc07.pdfhttp://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
- EOF -