多核并行編程的背景

    在摩爾定律失效之前，提升處理器性能通過主頻提升、硬件超線程等技術(shù)就能滿足應(yīng)用需要。隨著主頻提升慢慢接近撞上光速這道墻，摩爾定律開始逐漸失效，多核集成為處理器性能提升的主流手段。現(xiàn)在市面上已經(jīng)很難看到單核的處理器，就是這一發(fā)展趨勢的佐證。要充分發(fā)揮多核豐富的計(jì)算資源優(yōu)勢，多核下的并行編程就不可避免，Linux kernel就是一典型的多核并行編程場景。但多核下的并行編程卻挑戰(zhàn)多多。

多核并行編程的挑戰(zhàn)

目前主流的計(jì)算機(jī)都是馮諾依曼架構(gòu)，即共享內(nèi)存的計(jì)算模型，這種過程計(jì)算模型對(duì)并行計(jì)算并不友好。下圖是一種典型的計(jì)算機(jī)硬件體系架構(gòu)。

    這種架構(gòu)中，有如下設(shè)計(jì)特點(diǎn)：

·多個(gè)CPU核改善處理器的計(jì)算處理能力;

·多級(jí)cache改善CPU訪問主存的效率;

·各個(gè)CPU都有本地內(nèi)存(NUMA(非一致性內(nèi)存訪問))，進(jìn)一步改善CPU訪問主存的效率;

·store buffer模塊改善cache write由于應(yīng)答延遲而造成的寫停頓問題;

·invalidate queue模塊改善使無效應(yīng)答的時(shí)延，把使無效命令放入queue后就立即發(fā)送應(yīng)答;

外設(shè)DMA支持直接訪問主存，改善CPU使用效率;

     這些硬件體系設(shè)計(jì)特點(diǎn)也引入很多問題，最大的問題就是cache一致性問題和亂序執(zhí)行問題。

     cache一致性問題由cache一致性協(xié)議MESI解決，MESI由硬件保證，對(duì)軟件來說是透明的。MESI協(xié)議保證所有CPU對(duì)單個(gè)cache line中單個(gè)變量修改的順序保持一致，但不保證不同變量的修改在所有CPU上看到的是相同順序。這就造成了亂序。不僅如此，亂序的原因還有很多：

·store buffer引起的延遲處理，會(huì)造成亂序;

·invalidate queue引起的延遲處理，會(huì)造成亂序;

·編譯優(yōu)化，會(huì)造成亂序;

·分支預(yù)測、多流水線等CPU硬件優(yōu)化技術(shù)，會(huì)造成亂序;

·外設(shè)DMA，會(huì)造成數(shù)據(jù)亂序;

     這種情況造成，就連簡單的++運(yùn)算操作的原子性都無法保證。這些問題必須采用多核并行編程新的技術(shù)手段來解決。

多核并行編程關(guān)鍵技術(shù)

     鎖技術(shù)

Linux kernel提供了多種鎖機(jī)制，如自旋鎖、信號(hào)量、互斥量、讀寫鎖、順序鎖等。各種鎖的簡單比較如下，具體實(shí)現(xiàn)和使用細(xì)節(jié)這里就不展開了，可以參考《Linux內(nèi)核設(shè)計(jì)與實(shí)現(xiàn)》等書的相關(guān)章節(jié)。

·自旋鎖，不休眠，無進(jìn)程上下文切換開銷，可以用在中斷上下文和臨界區(qū)小的場合;

·信號(hào)量，會(huì)休眠，支持同時(shí)多個(gè)并發(fā)體進(jìn)入臨界區(qū)，可以用在可能休眠或者長的臨界區(qū)的場合;

·互斥量，類似與信號(hào)量，但只支持同時(shí)只有一個(gè)并發(fā)體進(jìn)入臨界區(qū);

·讀寫鎖，支持讀并發(fā)，寫寫/讀寫間互斥，讀會(huì)延遲寫，對(duì)讀友好，適用讀側(cè)重場合;

·順序鎖，支持讀并發(fā)，寫寫/讀寫間互斥，寫會(huì)延遲讀，對(duì)寫友好，適用寫側(cè)重場合;

鎖技術(shù)雖然能有效地提供并行執(zhí)行下的競態(tài)保護(hù)，但鎖的并行可擴(kuò)展性很差，無法充分發(fā)揮多核的性能優(yōu)勢。鎖的粒度太粗會(huì)限制擴(kuò)展性，粒度太細(xì)會(huì)導(dǎo)致巨大的系統(tǒng)開銷，而且設(shè)計(jì)難度大，容易造成死鎖。除了并發(fā)可擴(kuò)展性差和死鎖外，鎖還會(huì)引入很多其他問題，如鎖驚群、活鎖、饑餓、不公平鎖、優(yōu)先級(jí)反轉(zhuǎn)等。不過也有一些技術(shù)手段或指導(dǎo)原則能解決或減輕這些問題的風(fēng)險(xiǎn)。

·按統(tǒng)一的順序使用鎖(鎖的層次)，解決死鎖問題;

·指數(shù)后退，解決活鎖/饑餓問題;

·范圍鎖(樹狀鎖)，解決鎖驚群問題;

·優(yōu)先級(jí)繼承，解決優(yōu)先級(jí)反轉(zhuǎn)問題 ;

    原子技術(shù)

    原子技術(shù)主要是解決cache不一致性和亂序執(zhí)行對(duì)原子訪問的破壞問題。主要的原子原語有：

ACCESS_ONECE()：只限制編譯器對(duì)內(nèi)存訪問的優(yōu)化;

barrier()：只限制編譯器的亂序優(yōu)化;

smb_wmb()：寫內(nèi)存屏障，刷新store buffer，同時(shí)限制編譯器和CPU的亂序優(yōu)化;

smb_rmb()：讀內(nèi)存屏障，刷新invalidate queue，同時(shí)限制編譯器和CPU的亂序優(yōu)化;

smb_mb()：讀寫內(nèi)存屏障，同時(shí)刷新store buffer和invalidate queue，同時(shí)限制編譯器和CPU的亂序優(yōu)化;

atomic_inc()/atomic_read()等：整型原子操作;

多提一句的是，atomic_inc()原語為了保證原子性，需要對(duì)cache進(jìn)行刷新，而緩存行在多核體系下傳播相當(dāng)耗時(shí)，其多核下的并行可擴(kuò)展性差。

無鎖技術(shù)

    上一小節(jié)中所提到的原子技術(shù)，是無鎖技術(shù)中的一種，除此之外，無鎖技術(shù)還包括RCU、Hazard pointer等。值得一提的是，這些無鎖技術(shù)都基于內(nèi)存屏障實(shí)現(xiàn)的。

Hazard pointer主要用于對(duì)象的生命周期管理，類似引用計(jì)數(shù)，但比引用計(jì)數(shù)有更好的并行可擴(kuò)展性;

RCU適用的場景很多，其可以替代：讀寫鎖、引用計(jì)數(shù)、垃圾回收器、等待事物結(jié)束等，而且有更好的并行擴(kuò)展性。但RCU也有一些不適用的場景，如寫側(cè)重;臨界區(qū)長;臨界區(qū)內(nèi)休眠等場景。

不過，所有的無鎖原語也只能解決讀端的并行可擴(kuò)展性問題，寫端的并行可擴(kuò)展性只能通過數(shù)據(jù)分割技術(shù)來解決。

數(shù)據(jù)分割技術(shù)

     分割數(shù)據(jù)結(jié)構(gòu)，減少共享數(shù)據(jù)，是解決并行可擴(kuò)展性的根本辦法。對(duì)分割友好(即并行友好)的數(shù)據(jù)結(jié)構(gòu)有：

·數(shù)組

·哈希表

·基樹(Radix Tree)/稀疏數(shù)組

·跳躍列表(skip list)

使用這些便于分割的數(shù)據(jù)結(jié)構(gòu)，有利于我們通過數(shù)據(jù)分割來改善并行可擴(kuò)展性。

除了使用合適的數(shù)據(jù)結(jié)構(gòu)外，合理的分割指導(dǎo)規(guī)則也很重要：

·讀寫分割：以讀為主的數(shù)據(jù)與以寫為主的數(shù)據(jù)分開;

·路徑分割：按獨(dú)立的代碼執(zhí)行路徑來分割數(shù)據(jù);

·專項(xiàng)分割：把經(jīng)常更新的數(shù)據(jù)綁定到指定的CPU/線程中;

·所有權(quán)分割：按CPU/線程個(gè)數(shù)對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行分割，把數(shù)據(jù)分割到per-cpu/per-thread中;

4種分割規(guī)則中，所有權(quán)分割是分割最徹底的。

     以上這些多核并行編程內(nèi)容基本上涵蓋了Linux kernel中所有的并發(fā)編程關(guān)鍵技術(shù)。當(dāng)然并行編程還有很多其他技術(shù)沒有應(yīng)用到Linux kernel中的，如無副作用的并行函數(shù)式編程技術(shù)(Erlang/Go等)、消息傳遞、MapReduce等等。

本文為轉(zhuǎn)載