CPU 緩存一致性：從理論到實戰

01 存儲體系結構

速度快的存儲硬件成本高、容量小，速度慢的成本低、容量大。爲了權衡成本和速度，計算機存儲分了很多層次，揚長避短，有寄存器、L1 cache、L2 cache、L3 cache、主存（內存）和硬盤等。圖 1 展示了現代存儲體系結構。

根據程序的空間局部性和時間局部性原理，緩存命中率可以達到 70～90% 。因此，增加緩存可以讓整個存儲系統的性能接近寄存器，並且每字節的成本都接近內存，甚至是磁盤。

所以緩存是存儲體系結構的靈魂。

02 緩存原理

2.1 緩存的工作原理

cache line（緩存行） 是緩存進行管理的最小存儲單元，也叫緩存塊，每個 cache line 包含 Flag、Tag 和 Data ，通常 Data 大小是 64 字節，但不同型號 CPU 的 Flag 和 Tag 可能不相同。從內存向緩存加載數據是按整個緩存行加載的，一個緩存行和一個相同大小的 內存塊 對應。

圖 2 中，緩存是按照矩陣方式排列 (M × N)，橫向是組 (Set)，縱向是路 (Way)。每一個元素是緩存行 (cache line)。

那麼給定一個虛擬地址 addr 如何在緩存中定位它呢？首先把它所在的組號找到，即：

//左移6位是因爲 Block Offset 佔 addr 的低 6 位，Data 爲 64 字節
Set Index = (addr >> 6) % M;

然後遍歷該組所有的路，找到 cache line 中的 Tag 與 addr 中 Tag 相等爲止，所有路都沒有匹配成功，那麼緩存未命中。

整個緩存容量 = 組數 × 路數 × 緩存行大小

我電腦的 CPU 信息：

我電腦的緩存信息：

通過緩存行大小和路數可以倒推出緩存的組數，即：

緩存組數 = 整個緩存容量 ÷ 路數 ÷ 緩存行大小

2.2 緩存行替換策略

目前最常用的緩存替換策略是最近最少使用算法（Least Recently Used ，LRU）或者是類似 LRU 的算法。

LRU 算法比較簡單，如圖 3，緩存有 4 路，並且訪問的地址都哈希到了同一組，訪問順序是 D1、D2、D3、D4 和 D5，那麼 D1 會被 D5 替換掉。算法的實現方式有很多種，最簡單的實現方式是位矩陣。

首先，定義一個行、列都與緩存路數相同的矩陣。當訪問某個路對應的緩存行時，先將該路對應的所有行置爲 1，然後再將該路對應的所有列置爲 0。

最近最少使用的緩存行所對應的矩陣行中 1 的個數最少，最先被替換出去。

2.3 緩存缺失

緩存缺失就是緩存未命中，需要把內存中數據加載到緩存，所以運行速度會變慢。

就拿我的電腦來測試，L1d 的緩存大小是 32KB（32768B），8 路，緩存行大小 64B，那麼

緩存組數 = 32 × 1024 ÷ 8 ÷ 64 = 64

運行下面的代碼

char *a = new char(64 * 64 * 8); //32768B
for(int i = 0; i < 20000000; i++) 
    for(int j = 0; j < 32768; j += 4096) 
        a[j]++;

結果：循環 160000000 次，耗時 301 ms。除了第一次未命中緩存，後面每次讀寫數據都能命中緩存。

調整上面的代碼，並運行

char *a = new char(64 * 64 * 8 * 2); //65536B
for(int i = 0; i < 10000000; i++)
    for(int j = 0; j < 65536; j += 4096)
        a[j]++;

結果：循環 160000000 次，耗時 959 ms。每一次讀寫數據都沒有命中緩存，所以耗時增加了 2 倍。

2.4 程序局部性

程序局部性就是讀寫內存數據時讀寫連續的內存空間，目的是讓緩存可以命中，減少緩存缺失導致替換的開銷。

我電腦上運行下面代碼

int M = 10000, N = 10000;
char (*a)[N] = (char(*)[N])calloc(M * N, sizeof(char));
for(int i = 0; i < M; i++)
    for(int j = 0; j < N; j++)
        a[i][j]++;

結果：循環 100000000 次，耗時 314 ms。利用了程序局部性原理，緩存命中率高。

修改上面的代碼如下，並運行

int M = 10000, N = 10000;
char (*a)[N] = (char(*)[N])calloc(M * N, sizeof(char));
for(int j = 0; j < N; j++)
    for(int i = 0; i < M; i++)
        a[i][j]++;

結果：循環 100000000 次，耗時 1187 ms。沒有利用程序局部性原理，緩存命中率低，所以耗時增加了 2 倍。

2.5 僞共享（false-sharing）

當兩個線程同時各自修改兩個相鄰的變量，由於緩存是按緩存行來整體組織的，當一個線程對緩存行中數據執行寫操作時，必須通知其他線程該緩存行失效，導致另一個線程從緩存中讀取其想修改的數據失敗，必須從內存重新加載，導致性能下降。

我電腦運行下面代碼

struct S {
    long long a;
    long long b;
} s;
std::thread t1([&]() {
    for(int i = 0; i < 100000000; i++)
        s.a++;
});
std::thread t2([&]() {
    for(int i = 0; i < 100000000; i++)
        s.b++;
});

結果：耗時 512 ms，原因上面提到了，就是兩個線程互相影響，使對方的緩存行失效，導致直接從內存讀取數據。

解決辦法是對上面代碼做如下修改：

struct S {
    long long a;
    long long noop[8];
    long long b;
} s;

結果：耗時 181 ms，原因是通過 long long noop[8] 把兩個數據（a 和 b）劃分到兩個不同的緩存行中，不再互相使對方的緩存失效，所以速度變快了。

本小節的測試代碼都沒有開啓編譯器優化，即編譯選項爲 -O0 。 

03 緩存一致性協議

在單核時代，增加緩存可以大大提高讀寫速度，但是到了多核時代，卻引入了緩存一致性問題，如果有一個核心修改了緩存行中的某個值，那麼必須有一種機制保證其他核心能夠觀察到這個修改。

3.1 緩存寫策略

從緩存和內存的更新關係來看，分爲：

從寫緩存時 CPU 之間的更新策略來看，分爲：

從寫緩存時數據是否被加載來看，分爲：

3.2 MESI 協議

MESI 協議是⼀個基於 失效 的緩存⼀致性協議，是⽀持 寫回（write-back） 緩存的最常⽤協議。也稱作伊利諾伊協議 (Illinois protocol，因爲是在伊利諾伊⼤學厄巴納 - ⾹檳分校被髮明的)。

爲了解決多個核心之間的數據傳播問題，提出了總線嗅探（Bus Snooping）策略。本質上就是把所有的讀寫請求都通過總線（Bus）廣播給所有的核心，然後讓各個核心去嗅探這些請求，再根據本地的狀態進行響應。

3.2.1 狀態

這些狀態信息實際上存儲在緩存行（cache line）的 Flag 裏。

3.2.2 事件

3.2.3 狀態機

表 1 是對狀態機圖 4 的詳解講解（選讀）

FkhNbU

3.2.4 動畫演示

各家 CPU 廠商沒有都完全按照 MESI 實現緩存一致性協議，導致 MESI 有很多變種，例如：Intel 採用的 MESIF 和 AMD 採用的 MOESI，ARM 大部分採用的是 MESI，少部分使用的是 MOESI 。

3.3 MOESI 協議（選讀）

MOESI 是一個完整的緩存一致性協議，它包含了其他協議中常用的所有可能狀態。除了四種常見的 MESI 協議狀態之外，還有第五種 Owned 狀態，表示修改和共享的數據。

這就避免了在共享數據之前將修改過的數據寫回主存的需要。雖然數據最終仍然必須寫回，但寫回可能是延遲的。

3.4 MESIF 協議（選讀）

MESIF 是一個 緩存一致性 和 記憶連貫 協議，該協議由五個狀態組成：已修改（M），互斥（E），共享（S），無效（I） 和 轉發（F）。

M，E，S 和 I 狀態與 MESI 協議一致。F 狀態是 S 狀態的一種特殊形式，當系統中有多個 S 時，必須選取一個轉換爲 F，只有 F 狀態的負責應答。通常是最後持有該副本的轉換爲 F，注意 F 是乾淨的數據。

該協議與 MOESI 協議有較大的不同，也遠比 MOESI 協議複雜。該協議由 Intel 的 快速通道互聯 QPI（QuickPath Interconnect）技術引入，其主要目的是解決 “基於點到點互聯的非一致性內存訪問（Non-uniform memory access，NUMA）處理器系統” 的緩存一致性問題，而不是 “基於共享總線的一致性內存訪問（Uniform Memory Access，UMA）處理器系統” 的緩存一致性問題。

04 內存屏障（Memory Barriers）

編譯器和處理器都必須遵守重排序規則。在單處理器的情況下，不需要任何額外的操作便能保持正確的順序。但是對於多處理器來說，保證一致性通常需要增加內存屏障指令。即使編譯器可以優化掉字段的訪問（例如因爲未使用加載到的值），編譯器仍然需要生成內存屏障，就好像字段訪問仍然存在一樣（可以單獨將內存屏障優化掉）。

內存屏障只與內存模型中的高級概念（例如 acquire 和 release）間接相關。內存屏障指令只直接控制 CPU 與其緩存的交互，以及它的寫緩衝區（持有等待刷新到內存的數據的存儲）和它的用於等待加載或推測執行指令的緩衝。這些影響可能導致緩存、主內存和其他處理器之間的進一步交互。

幾乎所有的處理器都至少支持一個粗粒度的屏障指令（通常稱爲 Fence，也叫全屏障），它保證了嚴格的有序性：在 Fence 之前的所有讀操作（load）和寫操作（store）先於在 Fence 之後的所有讀操作（load）和寫操作（store）執行完。對於任何的處理器來說，這通常都是最耗時的指令之一（它的開銷通常接近甚至超過原子操作指令）。大多數處理器還支持更細粒度的屏障指令。

表 2 是各處理器支持的內存屏障和原子操作

4.1 寫緩衝與寫屏障

嚴格按照 MESI 協議，核心 0 在修改本地緩存之前，需要向其他核心發送 Invalid 消息，其他核心收到消息後，使他們本地對應的緩存行失效，並返回 Invalid acknowledgement 消息，核心 0 收到後修改緩存行。這裏核心 0 等待其他核心返回確認消息的時間對核心來說是漫長的。

爲了解決這個問題，引入了 Store Buffer ，當核心想修改緩存時，直接寫入 Store uffer ，無需等待，繼續處理其他事情，由 Store Buffer 完成後續工作。

這樣一來寫的速度加快了，但是引來了新問題，下面代碼的 bar 函數中的斷言可能會失敗。

int a = 0, b = 0;
// CPU0
void foo() {
    a = 1;
    b = 1;
}
// CPU1
void bar() {
    while (b == 0) continue;
    assert(a == 1);
}

第一種情況：CPU 爲了提升運行效率和提高緩存命中率，採用了亂序執行；

第二種情況：Store Buffer 在寫入時，b 所對應的緩存行是 E 狀態，a 所對應的緩存行是 S 狀態，因爲對 b 的修改不需要核心間同步，但是修改 a 則需要，也就是 b 會先寫入緩存。與之對應 CPU1 中 a 是 S 狀態，b 是 I 狀態，由於 b 所對應的緩存區域是 I 狀態，它就會向總線發出 BusRd 請求，那麼 CPU1 就會先把 b 的最新值讀到本地，完成變量 b 值的更新，但是從緩存直接讀取 a 值是 0 。

舉一個更極端的例子

// CPU0
void foo() {
    a = 1;
    b = a;
}

第一種情況不會發生了，原因是代碼有依賴，不會亂序執行。但由於 Store Buffer 的存在，第二種情況仍然可能發生，原因同上。這會讓人感到更加匪夷所思。

爲了解決上面問題，引入了內存屏障，屏障的作用是前邊的讀寫操作未完成的情況下，後面的讀寫操作不能發生。這就是 Arm 上 dmb 指令的由來，它是數據內存屏障（Data Memory Barrier）的縮寫。

int a = 0, b = 0; 
// CPU0
void foo() {
    a = 1;
    smp_mb(); //內存屏障，各CPU平臺實現不一樣
    b = 1;
}
// CPU1
void bar() {
    while (b == 0) continue;
    assert(a == 1);
}

加上內存屏障後，保證了 a 和 b 的寫入緩存順序。

總的來說，Store Buffer 提升了寫性能，但放棄了緩存的順序一致性，這種現象稱爲****弱緩存一致性。通常情況下，多個 CPU 一起操作同一個變量的情況是比較少的，所以 Store Buffer 可以大幅提升程序的性能。但在需要核間同步的情況下，還是需要通過手動添加內存屏障來保證緩存一致性。

上面解決了核間同步的寫問題，但是核間同步還有一個瓶頸，那就是讀。

4.2 失效隊列與讀屏障

前面引入 Store Buffer 提升了寫入速度，那麼 invalid 消息確認速度相比起來就慢了，帶來了速度不匹配，很容易導致 Store Buffer 的內容還沒及時寫到緩存裏，自己就滿了，從而失去了加速的作用。

爲了解決這個問題，又引入了 Invalid Queue。收到 Invalid 消息的核心立刻返回 Invalid acknowledgement 消息，然後把 Invalid 消息加入 Invalid Queue ，等到空閒的時候再去處理 Invalid 消息。

運行上面增加內存屏障的代碼，第 11 行的斷言又可能失敗了。

核心 0 中 a 所對應的緩存行是 S 狀態，b 所對應的緩存行是 E 狀態；核心 1 中 a  所對應的緩存行是 S 狀態，b   所對應的緩存行是 I 狀態；

引入 Invalid Queue 後，對核心 1 來說看到的 a 和 b 的寫入又出現亂序了。

解決辦法是繼續加內存屏障，核心 1 想越過屏障必須清空 Invalid Queue，及時處理了對 a 的無效，然後讀取到新的 a 值，如下代碼：

int a = 0, b = 0;
// CPU0
void foo() {
    a = 1;
    smp_mb();
    b = 1;
}
// CPU1
void bar() {
    while (b == 0) continue;
    smp_mb(); //繼續加內存屏障
    assert(a == 1);
}

這裏使用的內存屏障是全屏障，包括讀寫屏障，過於嚴格了，會導致性能下降，所以有了細粒度的讀屏障和寫屏障。

4.3 讀寫屏障分離

**分離的寫屏障和讀屏障的出現，是爲了更加精細地控制 Store Buffer 和 Invalid Queue 的順序。

優化前面的代碼如下

int a = 0, b = 0;
// CPU0
void foo() {
  a = 1;
  smp_wmb(); //寫屏障
  b = 1;
}
// CPU1
void bar() {
  while (b == 0) continue;
  smp_rmb(); //讀屏障
  assert(a == 1);
}

這種修改只有在區分讀寫屏障的體系結構裏纔會有作用，比如 alpha 結構。在 x86 和 Arm 中是沒有作用的，因爲 x86 採用了 TSO 模型，後面會詳細介紹，而 Arm 採用了單向屏障。

4.4 單向屏障

單向屏障 (half-way barrier) 也是一種內存屏障，但它不是以讀寫來區分的，而是像單行道一樣，只允許單向通行，例如 ARM 中的 stlr 和 ldar 指令就是這樣。

理論普及的差不多了，接下單獨來說說服務端同學工作中最常用的 x86 內存模型，填一下 4.3 中留下的坑。

05 x86-TSO

x86-TSO（Total Store Order）採用的是圖 10 模型。

x86-TSO 有下面幾個特點：

下面的代碼是 Linux 在 x86 下的內存屏障定義

06 基準測試

6.1 關於 Store Buffer 的測試

6.1.1 測試核心內是否存在 Store Buffer

6.1.2 測試核心間是否共享 Store Buffer

6.1.3 測試 Store Forwarding （轉發）是否生效

6.2 測試 CPU 是否亂序執行

6.2.1 測試：StoreStore 亂序

6.2.2 測試：LoadStore 亂序

6.3 測試 n5 / n4b：兩個核心同時修改同一個變量

6.3.1 測試：n5

6.3.2 測試：n4b

6.4  測試：寫操作的可見性是否傳遞（如果 A 能看到 B 的動作，B 能看到 C 的動作，那麼 A 是否能看到 C 的動作）

07 CAS 原理

比較並交換 (compare and swap, CAS)，是原子操作的一種，可用於在多線程編程中實現不被打斷的數據交換操作，從而避免多線程同時改寫某一數據時由於執行順序不確定性以及中斷的不可預知性產生的數據不一致問題。該操作通過將內存中的值與指定數據進行比較，當數值一樣時將內存中的數據替換爲新的值。

下面代碼是使用 CAS 的一個例子（無鎖隊列 Pop 函數）

template <typename T>
bool AtomQueue<T>::Pop(T& v)
{
    uint64_t tail = tail_;
    if (tail == head_ || !valid_[tail])
        return false;
    if (!__sync_bool_compare_and_swap(&tail_, tail, (tail + 1) & mod_)) 
        return false;
    v = std::move(data_[tail]);
    valid_[tail] = 0;
    return true;
}

在使用上，通常會記錄下某塊內存中的 舊值，通過對 舊值 進行一系列的操作後得到 新值，然後通過 CAS 操作將 新值 與 舊值 進行交換。

如果這塊內存的值在這期間內沒被修改過，則 舊值 會與內存中的數據相同，這時 CAS 操作將會成功執行，使內存中的數據變爲 新值。

如果內存中的值在這期間內被修改過，則一般來說 _舊值 _ 會與內存中的數據不同，這時 CAS 操作將會失敗，新值 將不會被寫入內存。

7.1 應用

在應用中 CAS 可以用於實現 無鎖數據結構，常見的有 無鎖隊列（先入先出）以及 無鎖棧（先入後出）。對於可在任意位置插入數據的 鏈表以及雙向鏈表，實現無鎖操作的 難度較大。

7.2 ABA 問題

ABA 問題是無鎖結構實現中常見的一種問題，可基本表述爲：

  1. 線程 P1 讀取了一個數值 A；

  2. P1 被掛起 (時間片耗盡、中斷等)，線程 P2 開始執行；

  3. P2 修改數值 A 爲數值 B，然後又修改回 A；

  4. P1 被喚醒，比較後發現數值 A 沒有變化，程序繼續執行。

對於 P1 來說，數值 A 未發生過改變，但實際上 A 已經被變化過了，繼續使用可能會出現問題。在 CAS 操作中，由於比較的多是指針，這個問題將會變得更加嚴重。試想如下情況：

有一個棧 (先入後出) 中有 top 和 NodeA，NodeA 目前位於棧頂，top 指針指向 A。現在有一個線程 P1 想要 pop 一個節點，因此按照如下無鎖操作進行

pop()
{
  do{
    ptr = top;            // ptr = top = NodeA
    next_ptr = top->next; // next_ptr = NodeX
  } while(CAS(top, ptr, next_ptr) != true);
  return ptr;   
}

而線程 P2 在 P1 執行 CAS 操作之前把它打斷了，並對棧進行了一系列的 pop 和 push 操作，使棧變爲如下結構：

線程 P2 首先 pop 出 NodeA，之後又 push 了兩個 NodeB 和 C，由於內存管理機制中廣泛使用的內存重用機制，導致 NodeC 的地址與之前的 NodeA 一致。

這時 P1 又開始繼續運行，在執行 CAS 操作時，由於 top 依舊指向的是 NodeA 的地址 (實際上已經變爲 NodeC)，因此將 top 的值修改爲了 NodeX，這時棧結構如下：

經過 CAS 操作後，top 指針錯誤地指向了 NodeX 而不是 NodeB。

簡單的解決辦法是採用 DCAS（雙長度 CAS），一個 CAS 長度 保存原始有效數據，另一個 CAS 長度 保存累計變化的次數，第一個 CAS 可能出現 ABA 問題，但是第二個 CAS 極難出現 ABA 問題。

7.3 實現

CAS 操作基於 CPU 提供的原子操作指令實現。對於 Intel X86 處理器，可通過在彙編指令前增加 lock 前綴來鎖定系統總線，使系統總線在彙編指令執行時無法訪問相應的內存地址。而各個編譯器根據這個特點實現了各自的原子操作函數。

08 原子操作

程序代碼最終都會被翻譯爲 CPU 指令，一條最簡單的加減法語句都會被翻譯成幾條指令執行；爲了避免語句在 CPU 這一層級上的指令交叉帶來的不可預知行爲，在多線程程序設計時必須通過一些方式來進行規範，最常見的做法就是引入互斥鎖，但互斥鎖是操作系統這一層級的，最終映射到 CPU 上也是一堆指令，是指令就必然會帶來額外的開銷。

既然 CPU 指令是多線程不可再分的最小單元，那我們如果有辦法將代碼語句和指令對應起來，不就不需要引入互斥鎖從而提高性能了嗎? 而這個對應關係就是所謂的原子操作；在 C++11 的 atomic 中有兩種做法:

可以通過 is_lock_free 函數，判斷一個 atomic 是否是 lock-free 類型。

原子操作有三類：

8.1 自旋鎖

使用原子操作模擬互斥鎖的行爲就是自旋鎖，互斥鎖狀態是由操作系統控制的，自旋鎖的狀態是程序員自己控制的，常用的自旋鎖模型有：

LOCK 時自旋鎖是自己輪詢狀態，如果不引入中斷機制，會有大量計算資源浪費到輪詢本身上；常用的做法是使用 yield 切換到其他線程執行，或直接使用 sleep 暫停當前線程.

8.2 C++ 內存模型

C++11 原子操作的很多函數都有個 std::memory_order 參數，這個參數就是這裏所說的內存模型，對應緩存一致性模型，其作用是對同一時間的讀寫操作進行排序，一共定義了 6 種類型如下：

在不同的 CPU 架構上，這些模型的具體實現方式可能不同，但是 C++11 幫你屏蔽了內部細節，不用考慮內存屏障，只要符合上面的使用規則，就能得到想要的效果。可能有時使用的模型粒度比較大，會損耗性能，當然還是使用各平臺底層的內存屏障粒度更準確，效率也會更高，對程序員的功底要求也高。

8.3 C++ volatile

這個關鍵字僅僅保證數據只在內存中讀寫，直接操作它既不能保證操作是原子的，也不能通用地達到內存同步的效果；

由於 volatile 不能在多處理器的環境下確保多個線程能看到同樣順序的數據變化，在今天的通用應用程序中，不應該再看到 volatile 的出現。

09 無鎖隊列

本節是 CPU 緩存一致性的實戰部分，通過運用前面的理論知識實現一個 無鎖隊列，達到學以致用的目的。

下面是我採用 CAS 實現了一個多生產者多消費者無鎖隊列，設計參考 Disruptor ，最高可達 660 萬 QPS（單生產者單消費者）和 160 萬 QPS（10 個生產者 10 個消費者）。

9.1 設計思路

1、如圖 15，使用 2 個環形數組，數組元素均非原子變量，一個存儲 T 範型數據（一般爲指針），另一個是可用性檢查數組（uint8_t）。Head 是所有生產者的競爭標記，Tail 是所有消費者的競爭標記。紅色區表示待生產位置，綠色區表示待消費位置。 

2、生產者們通過 CAS 來競爭和移動 Head，搶到 Head 的生產者，先將 Head 加 1，再生產原 Head 位置的數據；同樣的消費者們通過 CAS 來競爭和移動 Tail，搶到 Tail 的消費者，先將 Tail 加 1，再消費原 Tail 位置的數據 。

9.2 實現細節

下面多生產者多消費者無鎖隊列的代碼是在 x86-64（x86-TSO） 平臺上編寫和測試的。

Talk is cheap. Show me the code.

9.2.1 AtomQueue 類模板定義

template <typename T>
class AtomQueue
{
public:
    AtomQueue(uint64_t size);
    ~AtomQueue();
    bool Push(const T& v);
    bool Pop(T& v);
private:
    uint64_t    P0[8];  //頻繁變化數據, 避免僞共享, 採用Padding
    uint64_t    head_;  //生產者標記, 表示生產到這個位置，但還沒有生產該位置
    uint64_t    P1[8];
    uint64_t    tail_;  //消費者標記, 表示消費到這個位置，但還沒有消費該位置
    uint64_t    P2[8];
    uint64_t    size_;  //數組最大容量, 必須滿足2^N
    int         mod_;   //取模 % -> & 減少2ns
    T*          data_;  //環形數據數組
    uint8_t*    valid_; //環形可用數組，與數據數組大小一致
};

細心的你會看到 **head_** 和 **tail_** 還有後面的變量中加添加了無意義的字段 **P0**、**P1** 和 **P2** ，因爲 **head_** 和 **tail_** 頻繁變化，目的是防止出現前面講過的 **僞共享** 導致性能下降問題。

9.2.2 構造函數與析構函數

template <typename T> 
AtomQueue<T>::AtomQueue(uint64_t size) : size_(size << 1), head_(0), tail_(0) 
{
    if ((size_ & (size_ - 1))) 
    {
        printf("AtomQueue::size_ must be 2^N !!!\n");
        exit(0);
    }
    mod_    = size_ - 1;
    data_   = new T[size_];
    valid_  = new uint8_t[size_];
    std::memset(valid_, 0, sizeof(valid_));
}
template <typename T>
AtomQueue<T>::~AtomQueue()
{
    delete[] data_;
    delete[] valid_; 
}

構造函數中強制傳入的隊列大小（size）必須爲 2 的冪數，目的是想用 & 而不是 % 取模，因爲 & 比 % 快 2ns，最求極致性能。

9.2.3 生產者調用的 Push 函數 和 消費者調用的 Pop 函數

template <typename T>
bool AtomQueue<T>::Push(const T& v)
{
    uint64_t head = head_, tail = tail_;
    if (tail <= head ? tail + size_ <= head + 1 : tail <= head + 1)
        return false;
    if (valid_[head])
        return false;
    if (!__sync_bool_compare_and_swap(&head_, head, (head + 1) & mod_))
        return false;
    data_[head] = v;
    valid_[head] = 1;
    return true;
}
template <typename T>
bool AtomQueue<T>::Pop(T& v)
{
    uint64_t tail = tail_;
    if (tail == head_ || !valid_[tail])
        return false;
    if (!__sync_bool_compare_and_swap(&tail_, tail, (tail + 1) & mod_)) 
        return false;
    v = std::move(data_[tail]);
    valid_[tail] = 0;
    return true;
}

分析一下上述 Push 和 Pop 函數中讀寫操作是否需要增加內存屏障，讀寫操作可以抽象描述如下表格：

在讀寫操作亂序的 CPU 上可以出現上述情況，會導出線 Bug，解釋一下：

解決辦法是添加讀寫屏障（LoadStore barrier），如下表格：

在 Arm 等亂序執行的平臺上可以解決問題；幸好 x86-TSO 平臺上讀操作不能延後，也就不需要讀寫屏障，手動加了也是空操作（no-op）。

通過執行反彙編命令（objdump -S a.out）得到 Push 中下面代碼的彙編代碼。

if (!__sync_bool_compare_and_swap(&tail_, tail, (tail + 1) & mod_)) 
400a61:  48 8b 45 f8            mov    -0x8(%rbp),%rax
400a65:  48 8d 50 01            lea    0x1(%rax),%rdx
400a69:  48 8b 45 e8            mov    -0x18(%rbp),%rax
400a6d:  8b 80 d8 00 00 00      mov    0xd8(%rax),%eax
400a73:  48 98                  cltq   
400a75:  48 89 d1               mov    %rdx,%rcx
400a78:  48 21 c1               and    %rax,%rcx
400a7b:  48 8b 45 e8            mov    -0x18(%rbp),%rax
400a7f:  48 8d 90 88 00 00 00   lea    0x88(%rax),%rdx
400a86:  48 8b 45 f8            mov    -0x8(%rbp),%rax
400a8a:  f0 48 0f b1 0a         lock cmpxchg %rcx,(%rdx)
400a8f:  0f 94 c0               sete   %al
400a92:  83 f0 01               xor    $0x1,%eax
400a95:  84 c0                  test   %al,%al
400a97:  74 07                  je     400aa0 <_ZN9AtomQueueIiE3PopERi+0x8c>
return false;
400a99:  b8 00 00 00 00         mov    $0x0,%eax
400a9e:  eb 40                  jmp    400ae0 <_ZN9AtomQueueIiE3PopERi+0xcc>

發現 __sync_bool_compare_and_swap 函數對應的彙編代碼爲：

400a8a:  f0 48 0f b1 0a         lock cmpxchg %rcx,(%rdx)

是帶 lock 前綴的命令，前面講過，在 x86-TSO 上，帶有 lock 前綴的命令具有刷新 Store Buffer 的功能，也就是 **head_** 和 **tail_** 的修改都能及時被其他核心觀察到，可以做到及時生產和消費。

10 參考資料

結束語

OMG，竟然寫了這麼多，頭一次！終於把 CPU 緩存、內存屏障、原子操作以及無鎖隊列一口氣梳理完了。期間查閱大量資料，這裏特地感謝一下參考資料中的作者，讓我學到了很多知識；期間也寫了很多測試代碼來驗證理論，避免誤人子弟，儘量做到有理有據。由於作者水平有限，本文錯漏缺點在所難免，希望讀者批評指正。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/kJF_ezR2TdPnYlfPCjwdKQ

猜你喜歡