走進多核編程

CPU 發(fā)展早期階段，性能的提升主要來自于主頻的提升和架構(gòu)的優(yōu)化，當這條優(yōu)化途徑出現(xiàn)瓶頸后，多核 CPU 開始流行起來。多核心同時執(zhí)行任務極大地提高了系統(tǒng)整體性能，但也對硬件架構(gòu)和軟件編寫提出了更大的挑戰(zhàn)。各個核心都有自己的 Cache，以及不同層級的 Cache，彼此共享內(nèi)存。一個典型的多核 CUP 架構(gòu)如下圖所示：

利用多核心的優(yōu)勢在各個核之間互相配合完成任務，如何進行各個核心間的數(shù)據(jù)同步（各個核心所屬 L1 Cache/L2 Cache 數(shù)據(jù)的同步）是問題的關(guān)鍵所在。雖然發(fā)展出多種數(shù)據(jù)同步方式，以及流水線亂序執(zhí)行的模式，但數(shù)據(jù)在各個核之間的一致性和可見性并不是那么理想；再加上編譯器也會做優(yōu)化，最終導致各個核的指令執(zhí)行順序和各個變量值的可見性變得不確定。

這種現(xiàn)象可以通稱為重排，即原本應該有全序的內(nèi)存讀寫操作被打亂。不過無論產(chǎn)生什么樣的重排，都會保證對于單線程內(nèi)部的執(zhí)行結(jié)果不會有任何區(qū)別。下面是一個簡單例子：

1. //Thread1

2. //readywasinitializedtofalse

3. p.init();

4. ready=true;

1. //thread2

2. if(ready){

3. p.bar();

4. }

對于 Thread 1 內(nèi)部，p 和 ready 沒有關(guān)聯(lián)，完全可以被重排而不影響正確性，而 Thread 2 依賴 ready 做標識位，一旦重排，Thread 2 在看到 ready 為 true 的時候 p 都可能沒有 init，顯然這是有問題的。

二

多核編程中臨界區(qū)保護

利用多線程做并發(fā)的任務中通常都會有公共的臨界區(qū)，比如最常用的一種數(shù)據(jù)結(jié)構(gòu)：并發(fā)隊列，生產(chǎn)者和消費者需要訪問隊列的公共內(nèi)存進行寫入和讀取。目前對于臨界區(qū)的保護方式通?？梢苑譃槿齻€級別：互斥、Lock-free 和 Wait-free。

1、互斥

互斥，顧名思義每個線程訪問臨界區(qū)之前都需要獲得互斥鎖，如果被別的線程占用了就阻塞等待。當進入臨界區(qū)的線程發(fā)生阻塞，或被操作系統(tǒng)換出時，會出現(xiàn)全局阻塞，因為獲得鎖的線程被換出無法執(zhí)行操作，而未獲得鎖的線程也只能一同等待，出現(xiàn)了阻塞傳播。如果另一個線程先進入臨界區(qū)，有可能反而可以更快的順利完成。因為存在全局阻塞的可能性，采用互斥技術(shù)進行臨界區(qū)保護的算法有著最低的阻塞容忍能力。

2、Lock-free

Lock-free 允許單個線程阻塞，但是會保證系統(tǒng)整體層面上的吞吐。如果當程序線程運行足夠長時間的情況下，至少有一個線程取得了進展，那么就可以說這個算法是 Lock-free 的。如果一個線程被掛起，那么 Lock-free 算法保證剩余的線程仍然可以進行。

使用鎖的代碼一定不是 Lock-free 的，因為一個線程加鎖后如果被系統(tǒng)切出去了，其他所有線程都處于等待中。但是沒用鎖也不一定是 Lock-free，因為普通的代碼邏輯也可能會導致一個線程夯住另一個線程。鎖之所以在高并發(fā)的時候表現(xiàn)很差，主要原因是加鎖的線程會夯住其他等待加鎖的線程，Lock-free 可以很好地解決這一問題。

在實現(xiàn)上一般先假設臨界區(qū)不存在競爭，各個線程直接開始在臨界區(qū)的執(zhí)行，執(zhí)行過程中通過良好的程序設計，讓這段預先的執(zhí)行是無沖突并且是可回滾的。最終有一個需要同步的提交操作，一般基于原子變量 CAS 操作，或者版本校驗等機制完成。在提交階段如果發(fā)生沖突，那么被仲裁為失敗的各方需要對臨界區(qū)預執(zhí)行進行回滾，并重新發(fā)起一輪嘗試。

注意，并不是說 Lock-free 的算法就一定比加鎖的算法好，Lock-free 需要處理更多更復雜的 race condition 移機 ABA 等問題，編寫出合理的 Lock-free 代碼也需要更深厚的技術(shù)功底，需要對底層有更多地了解，完成相同目的的代碼會比用鎖更復雜，執(zhí)行時間可能更長，代碼也更難理解。

很多場景下合理地使用鎖就能很好的勝任，Lock-free 和鎖之間在應用場景上更多的是一種互補的關(guān)系。Lock-free 算法的價值在于其保證了一個或所有線程始終在做有用的事，而不是絕對的高性能。但 Lock-free 相較于鎖在并發(fā)度高（競爭激烈導致上下文切換開銷變得突出）的某些場景下會有很大的性能優(yōu)勢，比如實現(xiàn)一個多線程的 Lock-free queue?？偟膩碚f，在多核環(huán)境下，Lock-free 是很有意義的。

3、Wait-free

Lock-free 技術(shù)主要解決了臨界區(qū)內(nèi)的阻塞傳播問題，但是本質(zhì)上，依然是多個線程排隊順序經(jīng)過臨界區(qū)。而 Wait-free 和 Lock-free 的主要區(qū)別也就體現(xiàn)在系統(tǒng)吞吐上。在無全局停頓的基礎上，Wait-free 進一步保障了執(zhí)行任意算法的線程，都應該在有限的步驟內(nèi)完成。不只是整體算法時時刻刻都存在有效計算，每個線程依然是需要持續(xù)進行有效的計算。這就要求多線程在臨界區(qū)內(nèi)不能被細粒度地串行起來，而必須是同時都能進行有效計算。雖然理論角度存在不少有 Wait-free 的算法，但大多并不具備工業(yè)使用的價值。

4、相關(guān)技術(shù)

Lock-free 和 Wait-free 編程中最重要的兩個相關(guān)技術(shù)就是原子操作和控制 Memory Order。

CPU 保證沒有線程能觀察到原子操作的中間態(tài)，也就是說一個原子操作對于所有的線程來說要么做了要么沒做。原子操作主要包括賦值原子操作、Read-Modify-Write（比如C++ 11里的fetch_add）、Compare-And-Swap（比如 C++ 11 里的 Compare_exchange_strong）等操作。原子操作保證了各線程在進行共享內(nèi)存的存取的時候能讀到完整的值。

Memory Order 即內(nèi)存排序，指 CPU 訪問主存的順序?？梢允蔷幾g器在編譯時產(chǎn)生，也可以是 CPU 在運行時產(chǎn)生。為了充分利用不用內(nèi)存的總線帶寬，現(xiàn)代處理器大多是亂序執(zhí)行的。無鎖算法沒有顯式的鎖，將會直接觀察到這些和代碼順序不一致的重排，C++ 11 引入的 Memory Order 給使用者提供了一種跨平臺的通用方法來限制上述兩種重排。

三

Memory Order

Memory Model 內(nèi)存模型，定義了特定處理器上或者工具鏈上的重排情況。某個處理器或者工具鏈對代碼的重排會嚴格遵循對應的 Memory Model。這里討論的重排只是針對單個線程內(nèi)部在單個核內(nèi)的指令的執(zhí)行順序問題?？梢岳斫鉃橹付?Memory order，就是通過限制重排來保證共享數(shù)據(jù)的可見性和正確同步。

1、Reorder 類型和 Memory Order 的強弱

對內(nèi)存的操作可以概括為讀和寫，可以表示為 Load 和 store 操作，因此 Reorder 也就可以整體上分為以下四種類型：

• Load-load reorder：兩個讀操作之間重排；

• Load-store reorder：原來在寫操作之前的讀操作重排到之后；

• Store-load reorder：原來在讀操作之前的寫操作重排到之后；

• Store-store reorder：兩個寫操作之間重排。

Memory Model 既有軟件層面的 Software Memory Model，又有硬件平臺的 Hardware Memory Model，下圖中是幾種 CPU 架構(gòu)下的 Hardware Memory Model。

• DEC Alpha 架構(gòu)下，上述四種 Reorder 都有可能發(fā)生，只保證不改變單線程內(nèi)部的執(zhí)行正確性。

• ARM 架構(gòu)下的 CPU 也允許四種 Reorder 的發(fā)生，額外保證了數(shù)據(jù)依賴順序。

• X86/X64 平臺屬于強 Memory Model 的范疇，只可能發(fā)生 Store-load reorder。

• C++ 11 中原子操作的內(nèi)存序?qū)儆?Software Memory Model 的范疇，在軟件層面進行相關(guān)限制，讓 CPU 實現(xiàn)相應操作的效果。

2、Compiler Barrier 與 Runtime Memory Barrier

無論是哪種 Memory Model 中涉及的重排，都是指的在沒有其他限制的情況。為了能夠保證程序的正確性，CPU 和編譯器（語言）的設計者都預留了手方法來改變這些重排，這類方法可以抽象成一個統(tǒng)一的概念 Barrier：屏障。需要使用者用代碼來限制編譯階段和運行階段的重排，因此可以分為 Compiler Barrier 和 Runtime Memory Barrier。

Compiler Barrier，編譯器層面的屏障，可以防止編譯器在將源碼轉(zhuǎn)換成機器碼的過程中重排。簡單的例子如下：

inta,b;
intmain()
{
 a=b+1;
//asmvolatile("":::"memory");
b=0;
return0;
}

對于以上代碼，使用 gcc 4.9.4 整體不開啟優(yōu)化進行編譯，得到匯編代碼如下：

  $ gcc -S main.cpp  
  $ cat main.s  
...
movl_b(%rip),%eax
addl$1,%eax
movl%eax,_a(%rip)
movl$0,_b(%rip)
movl$0,%eax
popq%rbp
...

同樣使用 gcc 4.9.4 整體開啟優(yōu)化進行編譯，得到匯編代碼如下：

$gcc–O2-Smain.cpp
$catmain.s
...
movl_b(%rip),%eax
movl$0,_b(%rip)
addl$1,%eax
movl%eax,_a(%rip)
xorl%eax,%eax
...

如果想要整體開啟優(yōu)化，但是對于部分代碼不想要重排，那么就可以使用 Compiler Barrier，在 gcc 里，asm volatile("" ::: “memory”)就是這么一個 Compiler Barrier。在使用 Compiler Barrier 后，使用使用 gcc 4.9.4 整體開啟優(yōu)化進行編譯，得到匯編代碼如下：

$gcc-O2-Smain.cpp
$catmain.s
...
movl_b(%rip),%eax
addl$1,%eax
movl%eax,_a(%rip)
movl$0,_b(%rip)
xorl%eax,%eax
...

可以看到和未開啟編譯優(yōu)化時的結(jié)果保持一致。

Compiler Barrier 只能保證編譯階段不重排。在多核系統(tǒng)里，光做到這一點還不夠，因為它沒法對 CPU 核心運行時的重排做出限制。因此，在多核編程中，通常需要同時對編譯重排和運行時重排做出限制，需要使用到 Runtime Memory Barrier。

審核編輯 ：李倩