早在C++11就在STL中引入了原子操作支持了。大部分時候，我使用C++11的atomic僅僅是為了原子地操作特定的一個變數，比如`load`、`store`、`fetch_add`等等。然而實際上，C++11的原子操作帶著的memory order還能起到memory barrier的作用。本文會... ...

早在C++11就在STL中引入了原子操作支持了。大部分時候，我使用C++11的atomic僅僅是為了原子地操作特定的一個變數，比如load、store、fetch_add等等。然而實際上，C++11的原子操作帶著的memory order還能起到memory barrier的作用。本文會從頭介紹C++11原子變數的用法，使用的註意事項以及一些原理，原理部分會涉及少量的電腦體繫結構的知識，主要與CPU的緩存相關。

原子操作

原子性

原子操作指的是要麼處於已完成的狀態，要麼處於初始狀態，而不存在中間狀態的操作。例如，假設下麵的函數滿足原子性（它實際上不滿足原子性，但我們假設它滿足）：

int value = 0;
void atomic_function() {
    for (int i = 0; i < 100; ++i)
        value += 1;
}

我們線上程A調用atomic_function()，然後我們線上程B觀察value。因為它滿足原子性，所以我們線上程B觀察到的value要麼是0（atomic_function()沒有執行，value的初始狀態），要麼是100（atomic_function()執行完畢），而不會觀察到1，2，50等中間狀態。

原子性這個性質並不僅僅限定於針對記憶體的操作，比如關係型資料庫的事務也是滿足原子性的（~~這裡點名批評MySQL~~）。

數據競爭

多線程訪問同一個變數時會出現數據競爭（data race），數據競爭會導致結果變得不確定：

int value = 0;
void modify_value() {
    value += 1;
}

假設我們在A和B兩個線程同時執行modify_value()，那麼可能會出現這樣的執行順序：

+----------------------------+----------------------------+
|          thread A          |          thread B          |
+----------------------------+----------------------------+
| int tmp = value; // 0      | int tmp = value; // 0      |
| tmp += 1;        // 1      | tmp += 1;        // 1      |
| value = tmp;     // 1      | value = tmp;     // 1      |
+----------------------------+----------------------------+

如果以這樣的順序執行，那麼value最終的結果就是1。之所以會出現這種情況，是因為CPU並不會在每次訪問變數時都去訪問記憶體，而是優先訪問寄存器與高速緩存。對於具有多個核心的CPU來說，CPU的每個核心通常都有獨立的寄存器以、L1緩存和L2緩存，L3緩存通常是多個核心共用的。當變數存在與CPU核心的寄存器或L1、L2緩存中時，就可能出現這種情況。

而如果兩個線程按照這樣的順序執行：

+----------------------------+----------------------------+
|          thread A          |          thread B          |
+----------------------------+----------------------------+
| int tmp = value; // 0      |                            |
| tmp += 1;        // 1      |                            |
| value = tmp;     // 1      |                            |
|                            | int tmp = value; // 1      |
|                            | tmp += 1;        // 2      |
|                            | value = tmp;     // 2      |
+----------------------------+----------------------------+

那麼value最終的結果就是2，也就是正確的執行結果。原子操作能夠保證多個線程不會同時操作同一個變數。

std::atomic

C++11提供了一個模板類std::atomic<T>，同時還預定義了一些常用的類型，比如std::atomic_int等。這個模板類提供了各種原子訪問操作，比如load()、store()等存取操作、compare_exchange等CAS操作、fetch_add等加減和位運算。這些方法的使用本身很簡單，本文不再詳述。這裡想要討論的是以下幾個問題：

既然std::atomic<T>是個模板類型，那麼是否所有的類型都可以被原子地訪問？
std::atomic<T>支持哪些原子操作？它的所有操作都滿足原子性嗎？
atomic是否等價於無鎖？

類型限制

正如上文所述，std::atomic<T>的原子操作依賴CPU的指令來實現。因此不難想到，std::atomic<T>的原子操作只能用於純粹的數據。“純粹的數據”指的是類型T必須可平凡拷貝（trivially copyable），即滿足

static_assert(std::is_trivially_copyable<T>::value, "T is not trivially copyable.");

“可平凡拷貝”這個說法比較抽象。基本上，只要一個類型滿足這幾個條件，它就可平凡拷貝：

可以用memcpy拷貝
沒有虛函數
構造函數noexcept

比如，這些都是典型的可平凡拷貝的類型：

int i;                       // trivially copyable.
double d;                    // trivially copyable.
struct { long a; int b; } s; // trivially copyable.
char c[256];                 // trivially copyable.

這些是典型的不可平凡拷貝的類型：

std::string s;      // not trivially copyable.
std::vector<int> v; // not trivially copyable.

C語言的各種類型，即Plain Old Data（POD）就是典型的可平凡拷貝類型（C++標準已經棄用POD的說法，改用平凡類型等更具體的名稱）。

原子操作

從cppreference.com可以很容易地歸納出std::atomic<T>支持的各種原子操作，比如加減法、位運算等。需要註意的是，以下幾種運算是不支持原子操作的：

（有符號和無符號）整型的乘除法
浮點數的加減乘除運算

原子變數在使用的時候有各種陷阱，比如以下代碼：

std::atomic_int x{1};
x = 2 * x;

這段代碼能夠正常地編譯通過，但它可能並不會像你預期的那樣工作。你可能期望它能夠原子地完成乘法與賦值，但這段代碼實際上是這樣工作的：

std::atomic_int x{1};
int tmp = x.load();
tmp = tmp * 2;
x.store(tmp);

它並不是一次完成的，而是分成了一次原子讀取、一次乘法以及一次原子寫入。std::atomic的數學運算有很多類似的陷阱，原因與剛剛所述的類似：

std::atomic_int x{1};
x += 1;    // atomic operation.
x = x + 1; // not atomic!

正因如此，我個人更建議使用std::atomic提供的函數，而不是數學運算符。比如使用x.fetch_add(1)來代替x += 1，因為一次方法調用很明確地就是一次原子操作。

atomic與無鎖

std::atomic<T>一定是無鎖的嗎？其實只要你花一點時間去翻一下cppreference.com就能得到答案：“不！”，因為std::atomic<T>提供了一個方法叫is_lock_free。

考慮以下幾個結構體：

struct A { long x; };
struct B { long x; long y; };
struct C { char s[1024]; };

A應當是無鎖的，因為它顯然等價於long。C應該不是無鎖的，因為它實在是太大了，目前沒有寄存器能存下它。至於B我們就很難直接推斷出來了。

對於x86架構的CPU，結構體B應當是無鎖的，它剛剛好可以原子地使用MMX寄存器（64bit）處理。但如果它再大一點（比如塞一個int進去），它就不能無鎖地處理了。

原子操作究竟是否無鎖與CPU的關係很大。如果CPU提供了豐富的用於無鎖處理的指令與寄存器，則能夠無鎖執行的操作就會多一些，反之則少一些。除此之外，原子操作能否無鎖地執行還與記憶體對齊有關。正因如此，is_lock_free()才會是一個運行時方法，而沒有被標記為constexpr。

記憶體屏障與memory order

在C++11之前，C++沒有提供統一的跨平臺的記憶體屏障。而從C++11開始，std::atomic的memory order就能夠起到記憶體屏障的作用了。在介紹memory order之前，首先介紹以下CPU亂序執行：

CPU亂序執行

為了節省時間並提高程式執行的效率，CPU在執行程式的時候可能會打亂指令執行順序。比如，考慮下麵這一段彙編指令：

1   mov (%r10), %r11
2   add %r11,   %rdx
3   mov %rcx,   %rax

這段彙編指令所做的事情很簡單。指令1從寄存器%r10指向的地址取出數據，存入寄存器%r11；指令2使%r11與%rdx進行整數加法，加法的結果存入%rdx；指令3將寄存器%rcx的值拷貝一份放入寄存器%rax。使用類似C語言的寫法就是

r11 = *r10;
rdx += r11;
rax = rcx;

指令1需要從記憶體取數據。相比於CPU的運算速度，從記憶體讀取數據是很慢的，而第二條指令又依賴於第一條指令的結果，因此這段指令的執行順序可能會被CPU重排為1 -> 3 -> 2。

Memory Order

C++11提供了6中memory order，分別是relaxed、consume、acquire、release、acq_rel、seq_cst。我們首先介紹relaxed、acqure與release這三種，另外三種可以在這三種的基礎上進行推廣。

std::memory_order_relaxed是約束力最低的memory order，它只保證對std::atomic<T>變數本身的訪問是原子的，並不能起到記憶體屏障的作用。值得一提的是，由於x86架構下普通訪存操作本身就滿足std::memory_order_relaxed，因此有很多人發現使用volatile也具有原子操作的特性，這種用法是錯誤的。volatile僅能夠保證編譯器不會打亂記憶體讀寫相關指令的順序，而不能約束CPU的訪存行為，也不能約束CPU的亂序執行。

std::memory_order_acquire通常與std::memory_order_release成對使用。它除了保證原子訪存之外，還保證排在原子操作之後的讀寫指令不會由於CPU亂序執行而在原子操作之前被執行。以下麵的偽指令為例：

load A
store B
inst C
atomic operation
store D
load E
load F

指令D、E、F不會由於CPU亂序執行而在atomic operation之前被執行，但允許A、B、C被放到atomic operation之後執行。

std::memory_order_release與std::memory_order_acquire剛好相反。它保證排在原子操作之前的讀寫指令不會被排到原子操作之後執行。還是以上面的偽指令為例，指令A、B不會被排到atomic operation之後執行，但允許D、E、F被排到atomic operation之前執行。

通常，我們會使用release store配合acquire load來實現記憶體屏障的功能。比如：

+----------------------------+----------------------------+
|          thread A          |          thread B          |
+----------------------------+----------------------------+
| store A                    |                            |
| inst B                     |                            |
| release store X            |                            |
| store D                    | acquire load X             |
|                            | load A // valid            |
|                            | load D // maybe invalid    |
+----------------------------+----------------------------+

由於線上程A中，store A一定會在release store X之前完成，而線上程B中，load A一定在acquire load X之後才會執行，因此Acquire-Release在這裡能夠起到記憶體屏障的作用，從而保證線程A的寫入對於線程B可見。

需要註意的是，Acquire-Release只對於使用release store和acquire load操作的兩個線程起到記憶體屏障的作用。如果需要記憶體屏障對所有線程起作用，則應當使用std::memory_order_seq_cst，std::memory_order_seq_cst保證會刷新所有CPU核心的cache line。

std::memory_order_acq_rel相當於std::memory_order_acquire + std::memory_order_release，即同時保證原子操作前面的訪存指令不會被重排到後面，也保證原子操作之後的訪存指令不會被重排到前面。

std::memory_order_consume與std::memory_order_acquire類似，但它的約束比std::memory_order_acquire要小。std::memory_order_acquire保證atomic load之後的所有訪存操作都不會被排到atomic load之前，但std::memory_order_consume只保證與原子變數存在依賴關係的訪存操作不會被排到atomic load之前。

性能

CPU Cache Line

CPU的緩存是存在“行”的，即CPU每次會將一段連續的數據載入到緩存中。要訪問記憶體時，CPU會首先查找要訪問的記憶體所在的這一行是否已經被載入到緩存中，如果命中則直接從緩存中的這一行取出對應的數據。更詳細的內容請參考電腦組成原理，這裡我們只需要知道CPU的緩存會以“行”為單位進行載入和釋放即可。

Cache line會對原子操作的性能產生影響，具體表現為同時原子訪問同一個Cache Line中的元素時，二者並不會同時進行，其中某一個訪存會等待另一個原子訪存完成。詳細的內容請參考CppCon2017 C++ atomics, from basic to advanced。

演算法

通常我們使用無鎖數據結構時，是因為它快。但實際上演算法的影響往往要大得多。來看一下CppCon2017給出的例子：

std::atomic_size_t a{0};
void do_work(std::size_t n) {
    for (std::size_t i = 0; i < n; ++i)
        a.fetch_add(1, std::memory_order_relaxed);
}

std::size_t b{0};
std::mutex m;
void do_work2(std::size_t n) {
    std::size_t result = 0;
    for (std::size_t i = 0; i < n; ++i)
        result += 1;
    std::lock_guard<std::mutex> lock(m);
    b += result;
}

隨著線程數量的增加，do_work2相對於do_work1的優勢越來越明顯。顯然，減少線程之間的競爭要比採用無鎖操作要快得多。

結語

本文是對C++11引入的原子操作的使用簡介，同時也是我觀看CppCon2017 C++ atomics, from basic to advanced的一篇筆記。在本文中我略去了compare_exchange相關的內容，因為。。。我懶得寫了，實際上compare_exchange_strong與compare_exchange_weak有不少值得記錄的內容。compare_exchange_weak的“假失敗”與CPU的設計有關，如果好奇的話就去看CppCon的演講吧。

淺析C++ atomic

原子操作

原子性

數據競爭

std::atomic

類型限制

原子操作

atomic與無鎖

記憶體屏障與memory order

CPU亂序執行

Memory Order

性能

CPU Cache Line

演算法

結語

參考資料