浅析C++ atomic

早在C++11就在STL中引入了原子操作支持了。大部分时候,我使用C++11的atomic仅仅是为了原子地操作特定的一个变量,比如loadstorefetch_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等加减和位运算。这些方法的使用本身很简单,本文不再详述。这里想要讨论的是以下几个问题:

  1. 既然std::atomic<T>是个模板类型,那么是否所有的类型都可以被原子地访问?
  2. std::atomic<T>支持哪些原子操作?它的所有操作都满足原子性吗?
  3. atomic是否等价于无锁?

类型限制

正如上文所述,std::atomic<T>的原子操作依赖CPU的指令来实现。因此不难想到,std::atomic<T>的原子操作只能用于纯粹的数据。“纯粹的数据”指的是类型T必须可平凡拷贝(trivially copyable),即满足

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

“可平凡拷贝”这个说法比较抽象。基本上,只要一个类型满足这几个条件,它就可平凡拷贝:

  1. 可以用memcpy拷贝
  2. 没有虚函数
  3. 构造函数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_releasestd::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_cststd::memory_order_seq_cst保证会刷新所有CPU核心的cache line。

std::memory_order_acq_rel相当于std::memory_order_acquire + std::memory_order_release,即同时保证原子操作前面的访存指令不会被重排到后面,也保证原子操作之后的访存指令不会被重排到前面。

std::memory_order_consumestd::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_strongcompare_exchange_weak有不少值得记录的内容。compare_exchange_weak的“假失败”与CPU的设计有关,如果好奇的话就去看CppCon的演讲吧。

参考资料

热门相关:盛世妖颜   紫府仙缘   我成了暴戾帝君的小娇包   重生成偏执霍少的小仙女   一等狂妃:邪王,请接招!