1. 问题的引入
1.1. 多线程带来的三个问题
在多线程编程下，程序的运行结果可能并不如我们所预料的一致。这主要是由以下三种原因导致的：
1.1.1. 非原子操作
原子操作(atomic operation)指不会被线程调度机制中断的一个或一系列操作。从汇编的角度去思考，我们会发现C/C++中有不少常见语句在编译成汇编语言后，往往被转换成了多条汇编语句，此时该操作的原子性就无法得到保证。
举个最常见的非原子操作例子，经典的i++。其汇编代码为：
mov eax, dword ptr[i]
inc eax
mov dword ptr[i], eax显然，在这三行语句执行期间可以发生上下文切换，所以i++的原子性是不能保证的。
此外，对于一个简单的赋值语句，例如a = b;，一般也不是原子操作。例如X86汇编语言中的MOV就不支持从主存到主存的数据传输，此时其汇编代码为：
mov eax, dword ptr [b]
mov dword ptr [a], eax 如果使用C/C++的基础语法，那么多线程场景下对同一块内存的并发读写都不是原子的。而当基础的读写原子性都无法保证，那么业务代码中常见的RMW操作(read-modify-write，读取值、在读取值的基础上进行计算、将计算结果写回)的原子性更是无法保证。综上所述，我们需要设法实现原子操作型的读、写和RMW。
1.1.2. 指令重排和CPU乱序执行
指令重排是现代编译器在编译优化过程中的一个重要步骤，编译器会调整语句的执行顺序以提高运行性能。而现代的CPU也有乱序执行的机制，CPU会分析指令之间的数据依赖，而后于程序运行期间修改指令序列的执行顺序，将不与流水线中正在执行的指令存在依赖关系的指令提前执行。例如序列中有两条相邻的指令AB，指令B需要用到指令A的运算结果，则B必须在A完成写回后才能开始进入执行阶段，此时没有乱序执行机制的CPU就只能在指令AB之间填充数个气泡，而有乱序执行机制的CPU可以从后继指令里选出数条不与AB存在数据依赖的指令，将这些指令提前到A之后执行，避免了气泡带来的性能下降。
对于单线程的程序，编译器在进行编译优化时，都会遵循“如同规则”(as-if rule)，即语句顺序修改不会导致程序运行的结果发生变化。从程序员的角度上看，对于一个遵循as-if rule规则进行重排的单线程程序，其运行结果就好像未经过任何优化一样。同理，CPU的乱序执行受到指令间数据依赖关系的限制，能确保运行结果和没有乱序执行机制时相同。但是在多线程场景下，编译器很可能无法发现跨线程的数据竞争问题，此时如同规则的限制不足以避免问题的发生。
这里给出一个例子：
#include <iostream>
#include <thread>
int x = 0, y = 0;
void func1() {
x = 100;
y = 200;
}
void func2() {
while(y != 200)
;
std::cout << x;
}
int main() {
std::thread thread1(func1);
std::thread thread2(func2);
thread1.join();
thread2.join();
return 0;
}根据直觉，输出的值应当永远是100。但实际上，当func1和func2由两个不同的std::thread分线程执行时，编译器并不能分析出指令重排的后果；此外，对于执行这两个线程的物理CPU核心，它们从单个线程的角度去分析，也会认为不存在数据依赖，进而允许乱序执行。无论这二者谁是“凶手”，运行时一旦func1、func2中的代码顺序被调换，这个程序就可能输出0。
1.1.3. 多核CPU缓存一致性
现代多核CPU的架构中，缓存分为L1 L2 L3三个层次，随着层级的提高缓存大小增大但是访问性能下降。问题在于，每个物理核心有自己的L1 L2级cache，这便涉及到了经典的缓存一致性问题。例如这样一个场景：某一数据被多个物理核的cache缓存，某一时刻其中一个物理核更新了该数据，而更新后的值首先会被写入该核心自有的cache，此时需要通知其他缓存了该数据的核心，告知他们缓存的值已经失效。否则，就可能导致程序的运行结果与预期不符。
1.2. volatile并不是好的解决方案
C/C++的volatile关键字是一种类型修饰符，其作用是告知编译器此变量可以被某些编译器未知的因素更改，从而令编译器对修饰的变量不再进行优化；此外，在最后生成的汇编/机器指令中，对该变量的每次读取都从内存重新读取，而不是从CPU cache或是寄存器中读取已有的该变量的旧值。
volatile关键字能够一定程度上解决多线程场景下错误的编译优化和多核CPU缓存问题，但是存在其局限性。首先，简单粗暴地关闭对该变量的优化等于放弃了高速的寄存器和缓存，会导致更广泛场景下的性能问题；其次，volatile仍然没能解决CPU乱序执行带来的错误结果。所以，volatile并不是解决上述三个问题的最佳方案。
1.3. 引入
可以发现上述三个问题都是由于硬件进入多核时代而产生的，本质是硬件问题。随着技术的发展，一系列硬件层面的技术被开发出来用于解决上述三个问题。C++11引入的原子变量和内存序就是使用这些硬件技术实现的，学会使用他们可以写出健壮的多线程程序，还能尽量减少互斥锁的使用，从而提高多线程运行性能。接下来，本文将介其定义与性质，并简单解释其硬件层面的实现原理。
2. C++11原子变量std::atomic 和内存序std::memory_order
2.1. 简介
C++11引入了原子变量std::atomic和内存序std::memory_order，二者均包含于头文件<atomic>中。内存序用于控制原子变量的线程间同步行为，这里暂时只简单定义其作用，将在第三节详述。
原子变量是一个模板类，包含成员函数load和store，用于对其进行读操作和写操作。即使是在最低的同步等级下，也能保证多线程并行场景中对原子变量的读写是原子操作。这样就解决了问题1.1中读写操作的原子性问题。
2.2. 解决1.1中RMW操作的原子性问题
当我们拥有了原子操作版本的读和写，我们便可以通过CAS(Compare And Swap)思想来实现原子性的RMW操作。CAS的伪码如下：
bool CAS( int * pAddr, int nExpected, int nNew ) {
atomically {
if ( *pAddr == nExpected ) {
*pAddr = nNew ;
return true ;
}
else
return false ;
}
}std::atomic的成员函数compare_exchange_weak()就是一个基础的CAS，其返回值为bool，至少接受两个参数，第一个称为expected，第二个称为desired，可以接受更多的std::memory_order作为第三、第四参数来控制同步行为。如果*this和expected按位相等，那么则将desired中的值赋给*this，并返回true；否则，将*this中的实际值加载进expected，并返回false。利用这个失败时会将当前值赋给expected的机制，我们可以用一行while语句写出CAS。
例如，一个线程安全的双端链表中的push_front操作：
p->next = head;
while (!head.compare_exchange_weak(p->next, p))
{}再例如，一个线程安全的RMW乘法函数
int fetch_multiply(std::atomic<int>& shared, int multiplier)
{
int oldValue = shared.load();
while (!shared.compare_exchange_weak(oldValue, oldValue * multiplier))
{}
return oldValue;
}std::atomic对于一些常见的基础类型（例如int等整数类型和float等浮点类型）做了特化，它们具有额外的特性，例如具有一系列额外的原子操作型成员函数，其中包括类似+=运算符的fetch_add成员函数、++/--/+=/-=运算符等。显然，提到的这几种操作都是RMW操作，而它们的原子性正是通过CAS机制来保证的。
2.3. CAS与ABA问题
CAS机制容易遇到ABA问题，可以用三个线程来解释次问题，此处借用稀土掘金社区的一篇博客中的简明例子：
小明在提款机，提取了50元，因为提款机问题，有两个线程，同时把余额从100变为50
线程1（提款机）：获取当前值100，期望更新为50，
线程2（提款机）：获取当前值100，期望更新为50，
线程1成功执行，线程2某种原因block了，这时，某人给小明汇款50
线程3（默认）：获取当前值50，期望更新为100，
这时候线程3成功执行，余额变为100，
线程2从Block中恢复，获取到的也是100，compare之后，继续更新余额为50！！！
此时可以看到，实际余额应该为100（100-50+50），但是实际上变为了50（100-50+50-50）这就是ABA问题带来的成功提交。一个简单的解决思路是加唯一且递增的版本号。
2.4. 原子操作的底层实现原理
无论是原子性的读写，还是原子性的CAS机制，都是由硬件实现的。
首先被开发出来的原子操作实现方式是CPU锁总线。CPU芯片上有一条引线#HLOCK pin，如果汇编语言的程序中在一条指令前面加上前缀"LOCK"，经过汇编以后的机器代码就使物理核在执行这条指令的时候把#HLOCK pin的电位拉低，持续到这条指令结束时放开，从而把总线锁住，这样同一总线上别的物理核就暂时不能通过总线访问内存了，保证了这条指令在多核环境中的原子性。总线锁会导致其他几个核在一定时钟周期内无法访问内存，虽然会影响其他核的性能，但比起操作系统级别的锁，已经足够轻量。
随着技术发展，锁缓存技术被开发出来，即当某个物理核对缓存中的数据做出修改后，会通过缓存一致性协议使得其他物理核缓存中的数据失效，其他的物理核再次需要访问该数据时需要重新从内存读取。这里涉及了缓存一致性协议，将在第4节详述。当代CPU一般是优先锁缓存，但在一些特殊情况下也会使用锁总线，例如访问对象的数据跨多个缓存行或是尚未被缓存时。
在X86汇编语言中有一条专门的指令CMPXCHG提供CAS功能。实际使用的时候，一般用法也需要加LOCK前缀进行总线锁或是缓存锁的施加，例如JDK实现中就有出现LOCK CMPXCHG。
https://zhuanlan.zhihu.com/p/375706879
3. 内存序和内存模型
3.1. 各内存模型涉及到的内存序
用于描述线程间同步行为的内存模型(Memory Model)可以被分为以下几种类型：
- Relaxed Ordering，宽松顺序 (涉及内存序参数
memory_order_relaxed) - Release-Acquire Ordering，释放-获得顺序 (涉及内存序参数
memory_order_release,memory_order_acquire,memory_order_acq_rel) - Release-Consume Ordering，释放-消费顺序（涉及内存序参数
memory_order_consume和之前出现的memory_order_release） - Sequentially Consistent Ordering，序列一致顺序 (涉及内存序参数
memory_order_seq_cst)
接下来详细介绍各个内存模型。
3.2. Relaxed Ordering，宽松顺序
3.2.1. 性质
Relaxed Ordering只保证最最最最基础的同步，即原子操作本身的性质：对目标原子变量的load和store操作是原子性的。
3.2.2. 使用方法
若要使用宽松顺序，则对std::atomic的load()和store()都要带上memory_order_relaxed参数，例如：
std::atomic<int> x = 0;
r1 = x.load(memory_order_relaxed);
x.store(r1, memory_order_relaxed); 3.2.3. 适用场景
Relaxed Ordering仅保证读写操作的原子性，故只适用于最基础的同步场景，例如多线程操作同一个计数器。
3.3. Release-acquire Ordering，释放-获得顺序
3.3.1. 参数的作用
首先我们需要介绍所使用的两个参数的作用：
memory_order_acquire用于限制load操作，受此限制的读操作被称为Acquire操作，即获得操作。在此load之后的内存读写操作不能被指令重排到此load之前。此外，当load操作成功获得其他线程释放的值后，在该释放操作之前的所有内存写入都对本load所在线程可见。
memory_order_release用于限制store操作，受此限制的写操作被称为release操作，即释放操作。在此store之前的内存读写操作不能被指令重排到此store之后。当前线程的所有内存写入，可见于获得该同一原子变量的其他线程。
额外强调：根据cppreference上的描述，此处被禁止重排和保证可见的内存操作是所有内存操作，即不局限于对原子变量的读写。
3.3.2. 性质
释放-获得顺序提供了更高等级的线程同步。首先，和基础的relax ordering一样，它能保证对目标原子变量的读写操作是原子性的；其次，也是最重要的，这个atomic变量会在程序中引入多个内存屏障(memory barrier / memory fence，或译内存栅栏)，从GCC的拓展汇编指令的角度去解释，这些内存屏障既是complier fence又是CPU fence。
引入内存屏障后，首先编译器的指令重排将受到限制，不允许将load后、store前的指令重排到另一侧；此外，还能限制CPU的乱序执行，保证屏障之前的写指令全部执行完后才能执行屏障之后的读语句。这样一来，就以内存屏障为同步点实现了多线程的同步，保证一个load操作成功获得其他线程释放的值后，在该释放操作之前的所有内存写入都对本load所在线程可见，这被称为“可见副效应”。
在这个等级的内存序下，我们利用内存屏障解决了问题1.2.
https://zhuanlan.zhihu.com/p/413889872
https://gcc.gnu.org/onlinedocs/gcc/Extended-Asm.html#Clobbers-and-Scratch-Registers
3.3.3. 使用方法
store()使用memory_order_release参数，而load()使用memory_order_acquire。
3.3.4. 适用场景
能保证一定的并行性能，并且提供较高等级的同步。互斥锁std::mutex就是释放-获得同步的一个经典例子，其lock()就是获得操作，unlock()就是释放操作。在互斥锁被线程A释放再被线程B获得后，A在释放该锁之前所做的所有写入操作都能被B看到。
3.3.5. 其他
还有一个参数memory_order_acq_rel，顾名思义是release和acquire的结合体，同时具有二者的功能并可以同时作为store和load的参数。带此参数的读写操作既是获得操作又是释放操作。当前线程的读或写内存不能被重排到此store/load之前或之后。所有释放同一原子变量的线程的写入可见于修改之前，而且修改可见于其他获得同一原子变量的线程。此参数下，提供的同步和内存屏障限制更强。
3.4. Release-Consume，释放消费顺序
3.4.1. 性质
注意，C++17起释放消费顺序的规范正在修订中，暂时不鼓励使用memory_order_consume。C++标准委员会尚在讨论研究如何将此机制设计得能被编译器实现。相当长一段时间以来，大多数编译器将consume操作视为acquire的同义操作。
Release-Consume可以被视为一种理想的优化版Release-Acquire顺序。后者的问题在于其可见负效应带来的同步约束过强，即使是不存在数据竞争的内存操作也被进行了同步，导致指令重排布受到较大的限制，进而导致并行性能的下降。针对这个问题，Release-Consume顺序被提出，只对存在数据依赖的内存操作进行限制。
memory_order_acquire用于限制load操作，受此限制的读操作被称为Consume操作，即消费操作。当前线程中，依赖于此load获取值的读或者写操作不能被指令重排到此load之前。当一个load操作成功消费其他线程释放的值后，在该释放操作之前的所有内存写入都对本load所在线程中使用从该消费操作获得的值的运算符和函数可见。
3.4.2. 使用方法
store()使用memory_order_release参数，而load()使用memory_order_consume。
3.4.3. 适用场景
暂不建议。
3.5. Sequentially Consistent Ordering 序列一致顺序
3.5.1. 性质
序列一致顺序提供了最严格的线程同步。此顺序也包含了所有更低等级的内存序所拥有的同步机制，即可以保证操作的原子性，也拥有可见副效应。在此基础上，序列一致顺序保证了内存操作的全局序列性，即所有线程看到的内存读写操作的顺序都应当是一致的，并且所有的读操作都能获得最新的写入值。这样一来，在序列一致顺序下，多个线程的内存操作表现为(appears)类似单线程执行的全局串行化。
3.5.2. 使用方法
Load()和store()都使用参数memory_order_seq_cst，或不带内存参数而采用默认参数。这是由于序列一致顺序的强约束能使得程序运行的结果符合编程人员的直觉，故被设置为了load和store的默认参数。
3.5.3. 使用场景
不追求极致多线程性能的场景。
4. TODO: 缓存一致性协议和内存屏障的硬件实现原理
4.1. MESI协议
MESI 协议是最经典的缓存一致性协议(cache coherence protocols)。
4.2. X86平台内存屏障实现原理
X86平台从硬件层面提供了多种内存屏障，对应的X86汇编指令有mfence/sfence/lfence。在2.3节提到LOCK前缀指令虽然不是内存屏障，但是一定程度上也提供了类似的效果。详细的硬件解释待补全。
https://zhuanlan.zhihu.com/p/125549632
http://www.puppetmastertrading.com/images/hwViewForSwHackers.pdf
5. wait-free与lock-free
原子指令能为多线程高性能编程引入两个重要的概念：wait-free和lock-free（无锁编程）。wait-free指不管OS如何调度线程，每个线程都始终在做有用的事；lock-free则比前者弱一些，指不管OS如何调度线程，至少有一个线程在做有用的事。
如果一个多线程程序中使用了互斥锁，那么OS进行线程调度时可能把一个刚获得锁的线程切换为就绪态，此时所有依赖于该锁的线程都在阻塞或自旋等待，而没有做有用的事，所以用到了锁就不是lock-free，更不会是wait-free。为了确保一个任务总在确定时间内完成，实时系统的关键代码应当至少是lock-free的。
在使用原子变量的无锁编程中，也存在着锁总线/锁缓存/执行缓存一致性协议等影响性能的机制，其中某些操作实际上也“锁”住了（或者说延缓了）其他线程在物理核上的运行，但是相对于直接使用互斥锁而导致的OS线程调度的成本，这个性能损失可以算是相当小的。参考linux内核的线程调度代码，一次线程调度可能会牵扯到几十乃至几百行C代码的执行，汇编成机器指令后这个数值只会更夸张。此外，无锁编程也能尽可能减少死锁等问题的发生。总的来说，无锁编程可以大幅度地提高多线程程序的性能。
6. 参考
cppreference上的内存序文档
http://senlinzhan.github.io/2017/12/04/cpp-memory-order/
https://github.com/apache/incubator-brpc/blob/master/docs/cn/atomic_instructions.md
https://blog.csdn.net/smilejiasmile/article/details/114188217
https://monkeysayhi.github.io/2017/12/28/%E4%B8%80%E6%96%87%E8%A7%A3%E5%86%B3%E5%86%85%E5%AD%98%E5%B1%8F%E9%9A%9C/
