C++ 11 Atomic

引入的原子指令

SSE2 extensions introduce two new fence instructions (LFENCE and MFENCE) as companions to the SFENCE instruction introduced with SSE extensions. The LFENCE instruction establishes a memory fence for loads. It guarantees ordering between two loads and prevents speculative loads from passing the load fence (that is, no speculative loads are allowed until all loads specified before the load fence have been carried out). The MFENCE instruction establishes a memory fence for both loads and stores. The processor ensures that no load or store after MFENCE will become globally visible until all loads and stores before MFENCE are globally visible.1 Note that the sequences LFENCE;SFENCE and SFENCE;LFENCE are not equivalent to MFENCE because neither ensures that older stores are globally observed prior to younger loads.

C++ 封装

我们都知道多核编程常用锁避免多个线程在修改同一个数据时产生race condition。当锁成为性能瓶颈时，我们又总想试着绕开它，而不可避免地接触了原子指令。但在实践中，用原子指令写出正确的代码是一件非常困难的事，琢磨不透的race condition、ABA problem、memory fence很烧脑，这篇文章试图通过介绍SMP架构下的原子指令帮助大家入门。C++11正式引入了原子指令，我们就以其语法描述。

顾名思义，原子指令是对软件不可再分的指令，比如x.fetch_add(n)指原子地给x加上n，这个指令对软件要么没做，要么完成，不会观察到中间状态。常见的原子指令有：

原子指令	作用
x.load()	返回x的值。
x.store(n)	把x设为n，什么都不返回。
x.exchange(n)	把x设为n，返回设定之前的值。
x.compare_exchange_strong(expected_ref, desired)	若x等于expected_ref，则设为desired，返回成功；否则把最新值写入expected_ref，返回失败。
x.compare_exchange_weak(expected_ref, desired)	相比compare_exchange_strong可能有spurious wakeup。
x.fetch_add(n), x.fetch_sub(n)	原子地做x += n, x-= n，返回修改之前的值。

你已经可以用这些指令做原子计数，比如多个线程同时累加一个原子变量，以统计这些线程对一些资源的操作次数。但是，这可能会有两个问题：

• 这个操作没有你想象地快。
• 如果你尝试通过看似简单的原子操作控制对一些资源的访问，你的程序有很大几率会crash。

Cacheline

没有任何竞争或只被一个线程访问的原子操作是比较快的，“竞争”指的是多个线程同时访问同一个cacheline。现代CPU为了以低价格获得高性能，大量使用了cache，并把cache分了多级。百度内常见的Intel E5-2620拥有32K的L1 dcache和icache，256K的L2 cache和15M的L3 cache。其中L1和L2 cache为每个核心独有，L3则所有核心共享。一个核心写入自己的L1 cache是极快的(4 cycles, ~2ns)，但当另一个核心读或写同一处内存时，它得确认看到其他核心中对应的cacheline。对于软件来说，这个过程是原子的，不能在中间穿插其他代码，只能等待CPU完成一致性同步，这个复杂的硬件算法使得原子操作会变得很慢，在E5-2620上竞争激烈时fetch_add会耗费700纳秒左右。访问被多个线程频繁共享的内存往往是比较慢的。比如像一些场景临界区看着很小，但保护它的spinlock性能不佳，因为spinlock使用的exchange, fetch_add等指令必须等待最新的cacheline，看上去只有几条指令，花费若干微秒并不奇怪。

要提高性能，就要避免让CPU频繁同步cacheline。这不单和原子指令本身的性能有关，还会影响到程序的整体性能。最有效的解决方法很直白：尽量避免共享。

Memory fence

仅靠原子技术实现不了对资源的访问控制，即使简单如spinlock或引用计数，看上去正确的代码也可能会crash。这里的关键在于重排指令导致了读写顺序的变化。只要没有依赖，代码中在后面的指令就可能跑到前面去，编译器和CPU都会这么做。

这么做的动机非常自然，CPU要尽量塞满每个cycle，在单位时间内运行尽量多的指令。如上节中提到的，访存指令在等待cacheline同步时要花费数百纳秒，最高效地自然是同时同步多个cacheline，而不是一个个做。一个线程在代码中对多个变量的依次修改，可能会以不同的次序同步到另一个线程所在的核心上。不同线程对数据的需求不同，按需同步也会导致cacheline的读序和写序不同。

如果其中第一个变量扮演了开关的作用，控制对后续变量的访问。那么当这些变量被一起同步到其他核心时，更新顺序可能变了，第一个变量未必是第一个更新的，然而其他线程还认为它代表着其他变量有效，去访问了实际已被删除的变量，从而导致未定义的行为。比如下面的代码片段：

// Thread 1
// ready was initialized to false
p.init();
ready =true;

// Thread2
if(ready){
    p.bar();
}

从人的角度，这是对的，因为线程2在ready为true时才会访问p，按线程1的逻辑，此时p应该初始化好了。但对多核机器而言，这段代码可能难以正常运行：

• 线程1中的ready = true可能会被编译器或cpu重排到p.init()之前，从而使线程2看到ready为true时，p仍然未初始化。这种情况同样也会在线程2中发生，p.bar()中的一些代码可能被重排到检查ready之前。

• 即使没有重排，ready和p的值也会独立地同步到线程2所在核心的cache，线程2仍然可能在看到ready为true时看到未初始化的p。

通过这个简单例子，你可以窥见原子指令编程的复杂性了吧。为了解决这个问题，CPU和编译器提供了memory fence，让用户可以声明访存指令间的可见性(visibility)关系，boost和C++11对memory fence做了抽象，总结为如下几种memory order.

header 1	header 2
row 1 col 1	row 1 col 2
row 2 col 1	row 2 col 2

memory order	作用
memory_order_relaxed	没有fencing作用
memory_order_consume	后面依赖此原子变量的访存指令勿重排至此条指令之前
memory_order_acquire	后面访存指令勿重排至此条指令之前
memory_order_release	前面访存指令勿重排至此条指令之后。当此条指令的结果对其他线程可见后，之前的所有指令都可见
memory_order_acq_rel	acquire + release语意
memory_order_seq_cst	acq_rel语意外加所有使用seq_cst的指令有严格地全序关系

有了memory order，上面的例子可以这么更正：

// Thread1
// ready was initialized to false
p.init();
ready.store(true, std::memory_order_release);

// Thread2
if(ready.load(std::memory_order_acquire)){
    p.bar();
}

线程2中的acquire和线程1的release配对，确保线程2在看到ready==true时能看到线程1 release之前所有的访存操作。

注意，memory fence不等于可见性，即使线程2恰好在线程1在把ready设置为true后读取了ready也不意味着它能看到true，因为同步cache是有延时的。memory fence保证的是可见性的顺序：“假如我看到了a的最新值，那么我一定也得看到b的最新值”。

一个相关问题是：如何知道看到的值是新还是旧？一般分两种情况：

值是特殊的。比如在上面的例子中，ready=true是个特殊值，只要线程2看到ready为true就意味着更新了。只要设定了特殊值，读到或没有读到特殊值都代表了一种含义。
总是累加。一些场景下没有特殊值，那我们就用fetch_add之类的指令累加一个变量，只要变量的值域足够大，在很长一段时间内，新值和之前所有的旧值都会不相同，我们就能区分彼此了。
原子指令的例子可以看boost.atomic的Example，atomic的官方描述可以看这里 https://zh.cppreference.com/w/cpp/atomic/memory_order。

wait-free & lock-free

原子指令能为我们的服务赋予两个重要属性：wait-free和lock-free。前者指不管OS如何调度线程，每个线程都始终在做有用的事；后者比前者弱一些，指不管OS如何调度线程，至少有一个线程在做有用的事。如果我们的服务中使用了锁，那么OS可能把一个刚获得锁的线程切换出去，这时候所有依赖这个锁的线程都在等待，而没有做有用的事，所以用了锁就不是lock-free，更不会是wait-free。为了确保一件事情总在确定时间内完成，实时系统的关键代码至少是lock-free的。在百度广泛又多样的在线服务中，对时效性也有着严苛的要求，如果RPC中最关键的部分满足wait-free或lock-free，就可以提供更稳定的服务质量。

值得提醒的是，常见想法是lock-free或wait-free的算法会更快，但事实可能相反，因为：

• lock-free和wait-free必须处理更多更复杂的race condition和ABA problem，完成相同目的的代码比用锁更复杂。代码越多，耗时就越长。

• 使用mutex的算法变相带“后退”效果。后退(backoff)指出现竞争时尝试另一个途径以临时避免竞争，mutex出现竞争时会使调用者睡眠，使拿到锁的那个线程可以很快地独占完成一系列流程，总体吞吐可能反而高了。

mutex导致低性能往往是因为临界区过大（限制了并发度），或竞争过于激烈（上下文切换开销变得突出）。lock-free/wait-free算法的价值在于其保证了一个或所有线程始终在做有用的事，而不是绝对的高性能。但在一种情况下lock-free和wait-free算法的性能多半更高：就是算法本身可以用少量原子指令实现。实现锁也是要用原子指令的，当算法本身用一两条指令就能完成的时候，相比额外用锁肯定是更快了。

理解C++的原子操作

事实上，Sequentially-consistent ordering是目前绝大多数编译器的缺省设置。如果按照高赞回答的意思，那么多线程如果使用了atom操作，貌似就几乎变成了单线程（或者回合制）？真的吗？

既然是多线程，那么线程之间的执行顺序就一定不是确定性的（你只能在某些点同步它们，但是在任何其它的地方是没有办法保证执行顺序的）。C++11所规定的这6种模式，其实并不是限制（或者规定）两个线程该怎样同步执行，而是在规定一个线程内的指令该怎样执行。是的，我知道这部分的文档（规定）以及给出的例子里面，满屏都是多线程。但是其实讨论的是单线程的问题。更为准确地说，是在讨论单线程内的指令执行顺序对于多线程的影响的问题。

首先，什么是原子操作？原子操作就是对一个内存上变量（或者叫左值）的读取-变更-存储（load-add-store）作为一个整体一次完成。让我们考察一下普通的非原子操作：x++这个表达式如果编译成汇编，对应的是3条指令：mov（从内存到寄存器），add，mov（从寄存器到内存）那么在多线程环境下，就存在这样的可能：当线程A刚刚执行完第二条指令的时候，线程B开始执行第一条指令。那么就会导致线程B没有看到线程A执行的结果。如果这个变量初始值是0，那么线程A和线程B的结果都是1。如果我们想要避免这种情况，就可以使用原子操作。使用了原子操作之后，你可以认为这3条指令变成了一个整体，从而别的线程无法在其执行的期间当中访问x。也就是起到了锁的作用。所以，atom本身就是一种锁。它自己就已经完成了线程间同步的问题。这里并没有那6个memory order的什么事情。

问题在于以这个原子操作为中心，其前后的代码。这些代码并不一定需要是原子操作，只是普通的代码就行。什么问题？比如还有另外一个变量y，在我们这个原子操作代码的附近，有一个y++那么现在的问题是，这个y++到底会在我们的x++之前执行，还是之后？注意这完全是单线程当中指令的执行顺序问题，与多线程风马牛不相及。但是，这个问题会导致多线程执行结果的不同。

理解了这个，就理解了那6种memory order。为啥？因为我们对x进行原子操作的地方，锁定了线程间的关系，是一个同步点。那么，以这个点为基准，我们就可以得出两个线程当中其它指令执行先后顺序关系。比如，A线程先对x进行了自增操作。因为对x的访问是原子的，所以B线程执行该行代码（假设代码当中对x的访问只有这一处）的时间点必然在A完成之后。那么，如果在A线程当中，y++是在x++之前执行的，那么我们就可以肯定，对于B线程来说，在x++（同步点）之后所有对y的参照，必定能看到A线程执行了y++之后的值（注意对y的访问并非原子）但是有个问题。如果在程序当中y++紧靠x++，那么其实它到底是会先于x++执行（完毕），还是晚于x++执行（完毕），这个是没准儿的。为啥呢？首先编译器对代码可能进行指令重排。

也就是说，编译器编译之后（特别是开了优化之后）的代码执行顺序，是不一定严格按照你写代码的顺序的。但是如果仅仅如此，也只是二进制（机器码）的顺序与源代码不同，还不至于导致A和B当中的指令执行顺序不同（因为A和B执行的是相同的机器码程序）。但是实际上，在非常微观的层面上，A和B也是可能不同的，甚至于，A每次执行到这里顺序都不见得一样。啥？…还真的是这样。原因在于当代CPU内部也有指令重排。也就是说，CPU执行指令的顺序，也不见得是完全严格按照机器码的顺序。特别是，当代CPU的IPC（每时钟执行指令数）一般都远大于1，也就是所谓的多发射，很多命令都是同时执行的。

比如，当代CPU当中（一个核心）一般会有2套以上的整数ALU（加法器），2套以上的浮点ALU（加法器），往往还有独立的乘法器，以及，独立的Load和Store执行器。Load和Store模块往往还有8个以上的队列，也就是可以同时进行8个以上内存地址（cache line）的读写交换。是不是有些晕？

简单来说，你可以理解当代CPU不仅是多核心，而且每个核心还是多任务（多指令）并行的。计算机课本上的那种一个时钟一条指令的，早就是老黄历了 （当然，宏观来看基本原理并没有改变）看到这里还没有晕的话，那么恭喜你，你快要理解什么是memory order了。所谓的memory order，其实就是限制编译器以及CPU对单线程当中的指令执行顺序进行重排的程度（此外还包括对cache的控制方法）。

这种限制，决定了以atom操作为基准点（边界），对其之前的内存访问命令，以及之后的内存访问命令，能够在多大的范围内自由重排（或者反过来，需要施加多大的保序限制）。

从而形成了6种模式。它本身与多线程无关，是限制的单一线程当中指令执行顺序。但是（合理的）指令执行顺序的重排在单线程环境下不会造成逻辑错误而在多线程环境下会，所以这个问题的目的是为了解决多线程环境下出现的问题。

引用

• brpc文档
• https://www.zhihu.com/question/24301047/answer/1193956492
• https://stackoverflow.com/questions/27595595/when-are-x86-lfence-sfence-and-mfence-instructions-required