一

走進多核編程

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

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

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

1. //Thread1

2. //readywasinitializedtofalse

3. p.init();

4. ready=true;

1. //thread2

2. if(ready){

3. p.bar();

4. }

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

二

多核編程中臨界區保護

利用多線程做并發的任務中通常都會有公共的臨界區，比如最常用的一種數據結構：并發隊列，生產者和消費者需要訪問隊列的公共內存進行寫入和讀取。目前對于臨界區的保護方式通常可以分為三個級別：互斥、Lock-free 和 Wait-free。

1、互斥

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

2、Lock-free

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

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

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

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

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

3、Wait-free

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

4、相關技術

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

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

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

三

Memory Order

Memory Model 內存模型，定義了特定處理器上或者工具鏈上的重排情況。某個處理器或者工具鏈對代碼的重排會嚴格遵循對應的 Memory Model。這里討論的重排只是針對單個線程內部在單個核內的指令的執行順序問題。可以理解為指定 Memory order，就是通過限制重排來保證共享數據的可見性和正確同步。

1、Reorder 類型和 Memory Order 的強弱

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

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

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

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

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

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

DEC Alpha 架構下，上述四種 Reorder 都有可能發生，只保證不改變單線程內部的執行正確性。

ARM 架構下的 CPU 也允許四種 Reorder 的發生，額外保證了數據依賴順序。

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

C++ 11 中原子操作的內存序屬于 Software Memory Model 的范疇，在軟件層面進行相關限制，讓 CPU 實現相應操作的效果。

2、Compiler Barrier 與 Runtime Memory Barrier

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

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

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

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

  $ 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 整體開啟優化進行編譯，得到匯編代碼如下：

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

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

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

可以看到和未開啟編譯優化時的結果保持一致。

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

審核編輯：劉清