技術分享：Linux多核并行編程關鍵技術
發(fā)布時間：2018-09-20 11:28:00
多核并行編程的背景
在摩爾定律失效之前，提升處理器性能通過主頻提升、硬件超線程等技術就能滿足應用需要。隨著主頻提升慢慢接近撞上光速這道墻，摩爾定律開始逐漸失效，多核集成為處理器性能提升的主流手段?，F(xiàn)在市面上已經(jīng)很難看到單核的處理器，就是這一發(fā)展趨勢的佐證。要充分發(fā)揮多核豐富的計算資源優(yōu)勢，多核下的并行編程就不可避免，Linux kernel就是一典型的多核并行編程場景。但多核下的并行編程卻挑戰(zhàn)多多。
多核并行編程的挑戰(zhàn)
目前主流的計算機都是馮諾依曼架構，即共享內存的計算模型，這種過程計算模型對并行計算并不友好。下圖是一種典型的計算機硬件體系架構。
這種架構中，有如下設計特點：
·多個CPU核改善處理器的計算處理能力;
·多級cache改善CPU訪問主存的效率;
·各個CPU都有本地內存(NUMA(非一致性內存訪問))，進一步改善CPU訪問主存的效率;
·store buffer模塊改善cache write由于應答延遲而造成的寫停頓問題;
·invalidate queue模塊改善使無效應答的時延，把使無效命令放入queue后就立即發(fā)送應答;
外設DMA支持直接訪問主存，改善CPU使用效率;
這些硬件體系設計特點也引入很多問題，最大的問題就是cache一致性問題和亂序執(zhí)行問題。
cache一致性問題由cache一致性協(xié)議MESI解決，MESI由硬件保證，對軟件來說是透明的。MESI協(xié)議保證所有CPU對單個cache line中單個變量修改的順序保持一致，但不保證不同變量的修改在所有CPU上看到的是相同順序。這就造成了亂序。不僅如此，亂序的原因還有很多：
·store buffer引起的延遲處理，會造成亂序;
·invalidate queue引起的延遲處理，會造成亂序;
·編譯優(yōu)化，會造成亂序;
·分支預測、多流水線等CPU硬件優(yōu)化技術，會造成亂序;
·外設DMA，會造成數(shù)據(jù)亂序;
這種情況造成，就連簡單的++運算操作的原子性都無法保證。這些問題必須采用多核并行編程新的技術手段來解決。
多核并行編程關鍵技術
鎖技術
Linux kernel提供了多種鎖機制，如自旋鎖、信號量、互斥量、讀寫鎖、順序鎖等。各種鎖的簡單比較如下，具體實現(xiàn)和使用細節(jié)這里就不展開了，可以參考《Linux內核設計與實現(xiàn)》等書的相關章節(jié)。
·自旋鎖，不休眠，無進程上下文切換開銷，可以用在中斷上下文和臨界區(qū)小的場合;
·信號量，會休眠，支持同時多個并發(fā)體進入臨界區(qū)，可以用在可能休眠或者長的臨界區(qū)的場合;
·互斥量，類似與信號量，但只支持同時只有一個并發(fā)體進入臨界區(qū);
·讀寫鎖，支持讀并發(fā)，寫寫/讀寫間互斥，讀會延遲寫，對讀友好，適用讀側重場合;
·順序鎖，支持讀并發(fā)，寫寫/讀寫間互斥，寫會延遲讀，對寫友好，適用寫側重場合;
鎖技術雖然能有效地提供并行執(zhí)行下的競態(tài)保護，但鎖的并行可擴展性很差，無法充分發(fā)揮多核的性能優(yōu)勢。鎖的粒度太粗會限制擴展性，粒度太細會導致巨大的系統(tǒng)開銷，而且設計難度大，容易造成死鎖。除了并發(fā)可擴展性差和死鎖外，鎖還會引入很多其他問題，如鎖驚群、活鎖、饑餓、不公平鎖、優(yōu)先級反轉等。不過也有一些技術手段或指導原則能解決或減輕這些問題的風險。
·按統(tǒng)一的順序使用鎖(鎖的層次)，解決死鎖問題;
·指數(shù)后退，解決活鎖/饑餓問題;
·范圍鎖(樹狀鎖)，解決鎖驚群問題;
·優(yōu)先級繼承，解決優(yōu)先級反轉問題 ;
原子技術
原子技術主要是解決cache不一致性和亂序執(zhí)行對原子訪問的破壞問題。主要的原子原語有：
ACCESS_ONECE()：只限制編譯器對內存訪問的優(yōu)化;
barrier()：只限制編譯器的亂序優(yōu)化;
smb_wmb()：寫內存屏障，刷新store buffer，同時限制編譯器和CPU的亂序優(yōu)化;
smb_rmb()：讀內存屏障，刷新invalidate queue，同時限制編譯器和CPU的亂序優(yōu)化;
smb_mb()：讀寫內存屏障，同時刷新store buffer和invalidate queue，同時限制編譯器和CPU的亂序優(yōu)化;
atomic_inc()/atomic_read()等：整型原子操作;
多提一句的是，atomic_inc()原語為了保證原子性，需要對cache進行刷新，而緩存行在多核體系下傳播相當耗時，其多核下的并行可擴展性差。
無鎖技術
上一小節(jié)中所提到的原子技術，是無鎖技術中的一種，除此之外，無鎖技術還包括RCU、Hazard pointer等。值得一提的是，這些無鎖技術都基于內存屏障實現(xiàn)的。
Hazard pointer主要用于對象的生命周期管理，類似引用計數(shù)，但比引用計數(shù)有更好的并行可擴展性;
RCU適用的場景很多，其可以替代：讀寫鎖、引用計數(shù)、垃圾回收器、等待事物結束等，而且有更好的并行擴展性。但RCU也有一些不適用的場景，如寫側重;臨界區(qū)長;臨界區(qū)內休眠等場景。
不過，所有的無鎖原語也只能解決讀端的并行可擴展性問題，寫端的并行可擴展性只能通過數(shù)據(jù)分割技術來解決。
數(shù)據(jù)分割技術
分割數(shù)據(jù)結構，減少共享數(shù)據(jù)，是解決并行可擴展性的根本辦法。對分割友好(即并行友好)的數(shù)據(jù)結構有：
·數(shù)組
·哈希表
·基樹(Radix Tree)/稀疏數(shù)組
·跳躍列表(skip list)
使用這些便于分割的數(shù)據(jù)結構，有利于我們通過數(shù)據(jù)分割來改善并行可擴展性。
除了使用合適的數(shù)據(jù)結構外，合理的分割指導規(guī)則也很重要：
·讀寫分割：以讀為主的數(shù)據(jù)與以寫為主的數(shù)據(jù)分開;
·路徑分割：按獨立的代碼執(zhí)行路徑來分割數(shù)據(jù);
·專項分割：把經(jīng)常更新的數(shù)據(jù)綁定到指定的CPU/線程中;
·所有權分割：按CPU/線程個數(shù)對數(shù)據(jù)結構進行分割，把數(shù)據(jù)分割到per-cpu/per-thread中;
4種分割規(guī)則中，所有權分割是分割最徹底的。
以上這些多核并行編程內容基本上涵蓋了Linux kernel中所有的并發(fā)編程關鍵技術。當然并行編程還有很多其他技術沒有應用到Linux kernel中的，如無副作用的并行函數(shù)式編程技術(Erlang/Go等)、消息傳遞、MapReduce等等。
本文為轉載