浅析C++ atomic

2023-10-07 11:12 由 icysky 发表于 #后端开发

早在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的演讲吧。

参考资料

CppCon2017 C++ atomics, from basic to advanced
cppreference.com