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

 

 

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

 

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

 

1.  // Thread1  

2.  // ready was initialized to false  

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，編譯器層面的屏障，可以防止編譯器在將原始碼轉換成機器碼的過程中重排。簡單的例子如下：

 

  int a, b;    int main()    {        a = b + 1;        // asm volatile("":::"memory");        b = 0;        return 0;    } 

 

對於以上程式碼，使用 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 -S main.cpp    $ cat main.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 -S main.cpp    $ cat main.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。

 

後續的技術部落格會繼續深入介紹 C++ 11 中的 Memory Order，敬請期待。