多核架构下的内存模型
一
走进多核编程
CPU 发展早期阶段，性能的提升主要来自于主频的提升和架构的优化，当这条优化途径出现瓶颈后，多核 CPU 开始流行起来。多核心同时执行任务极大地提高了系统整体性能，但也对硬件架构和软件编写提出了更大的挑战。各个核心都有自己的 Cache，以及不同层级的 Cache，彼此共享内存。一个典型的多核 CUP 架构如下图所示：
利用多核心的优势在各个核之间互相配合完成任务，如何进行各个核心间的数据同步（各个核心所属 L1 Cache/L2 Cache 数据的同步）是问题的关键所在。虽然发展出多种数据同步方式，以及流水线乱序执行的模式，但数据在各个核之间的一致性和可见性并不是那么理想；再加上编译器也会做优化，最终导致各个核的指令执行顺序和各个变量值的可见性变得不确定。
这种现象可以通称为重排，即原本应该有全序的内存读写操作被打乱。不过无论产生什么样的重排，都会保证对于单线程内部的执行结果不会有任何区别。下面是一个简单例子：
1. // Thread1
2. // ready was initialized to false
3. p.init();
4. ready = true;
1. // thread2
2. if(ready){
3. p.bar();
4. } 对于 Thread 1 内部，p 和 ready 没有关联，完全可以被重排而不影响正确性，而 Thread 2 依赖 ready 做标识位，一旦重排，Thread 2 在看到 ready 为 true 的时候 p 都可能没有 init，显然这是有问题的。
二
多核编程中临界区保护
利用多线程做并发的任务中通常都会有公共的临界区，比如最常用的一种数据结构：并发队列，生产者和消费者需要访问队列的公共内存进行写入和读取。目前对于临界区的保护方式通常可以分为三个级别：互斥、Lock-free 和 Wait-free。
1、 互 斥
互斥，顾名思义每个线程访问临界区之前都需要获得互斥锁，如果被别的线程占用了就阻塞等待。当进入临界区的线程发生阻塞，或被操作系统换出时，会出现全局阻塞，因为获得锁的线程被换出无法执行操作，而未获得锁的线程也只能一同等待，出现了阻塞传播。如果另一个线程先进入临界区，有可能反而可以更快的顺利完成。因为存在全局阻塞的可能性，采用互斥技术进行临界区保护的算法有着最低的阻塞容忍能力。
2、 Lock-free
Lock-free 允许单个线程阻塞，但是会保证系统整体层面上的吞吐。如果当程序线程运行足够长时间的情况下，至少有一个线程取得了进展，那么就可以说这个算法是 Lock-free 的。如果一个线程被挂起，那么 Lock-free 算法保证剩余的线程仍然可以进行。
使用锁的代码一定不是 Lock-free 的，因为一个线程加锁后如果被系统切出去了，其他所有线程都处于等待中。但是没用锁也不一定是 Lock-free，因为普通的代码逻辑也可能会导致一个线程夯住另一个线程。锁之所以在高并发的时候表现很差，主要原因是加锁的线程会夯住其他等待加锁的线程，Lock-free 可以很好地解决这一问题。
在实现上一般先假设临界区不存在竞争，各个线程直接开始在临界区的执行，执行过程中通过良好的程序设计，让这段预先的执行是无冲突并且是可回滚的。最终有一个需要同步的提交操作，一般基于原子变量 CAS 操作，或者版本校验等机制完成。在提交阶段如果发生冲突，那么被仲裁为失败的各方需要对临界区预执行进行回滚，并重新发起一轮尝试。
注意，并不是说 Lock-free 的算法就一定比加锁的算法好，Lock-free 需要处理更多更复杂的 race condition 移机 ABA 等问题，编写出合理的 Lock-free 代码也需要更深厚的技术功底，需要对底层有更多地了解，完成相同目的的代码会比用锁更复杂，执行时间可能更长，代码也更难理解。
很多场景下合理地使用锁就能很好的胜任，Lock-free 和锁之间在应用场景上更多的是一种互补的关系。Lock-free 算法的价值在于其保证了一个或所有线程始终在做有用的事，而不是绝对的高性能。但 Lock-free 相较于锁在并发度高（竞争激烈导致上下文切换开销变得突出）的某些场景下会有很大的性能优势，比如实现一个多线程的 Lock-free queue。总的来说，在多核环境下，Lock-free 是很有意义的。
3、 Wait-free
Lock-free 技术主要解决了临界区内的阻塞传播问题，但是本质上，依然是多个线程排队顺序经过临界区。而 Wait-free 和 Lock-free 的主要区别也就体现在系统吞吐上。在无全局停顿的基础上，Wait-free 进一步保障了执行任意算法的线程，都应该在有限的步骤内完成。不只是整体算法时时刻刻都存在有效计算，每个线程依然是需要持续进行有效的计算。这就要求多线程在临界区内不能被细粒度地串行起来，而必须是同时都能进行有效计算。虽然理论角度存在不少有 Wait-free 的算法，但大多并不具备工业使用的价值。
4、相关技术
Lock-free 和 Wait-free 编程中最重要的两个相关技术就是原子操作和控制 Memory Order。
CPU 保证没有线程能观察到原子操作的中间态，也就是说一个原子操作对于所有的线程来说要么做了要么没做。原子操作主要包括赋值原子操作、Read-Modify-Write（比如C++ 11里的fetch_add）、Compare-And-Swap（比如 C++ 11 里的 Compare_exchange_strong）等操作。原子操作保证了各线程在进行共享内存的存取的时候能读到完整的值。
Memory Order 即内存排序，指 CPU 访问主存的顺序。可以是编译器在编译时产生，也可以是 CPU 在运行时产生。为了充分利用不用内存的总线带宽，现代处理器大多是乱序执行的。无锁算法没有显式的锁，将会直接观察到这些和代码顺序不一致的重排，C++ 11 引入的 Memory Order 给使用者提供了一种跨平台的通用方法来限制上述两种重排。
三
Memory Order
Memory Model 内存模型，定义了特定处理器上或者工具链上的重排情况。某个处理器或者工具链对代码的重排会严格遵循对应的 Memory Model。这里讨论的重排只是针对单个线程内部在单个核内的指令的执行顺序问题。可以理解为指定 Memory order，就是通过限制重排来保证共享数据的可见性和正确同步。
1、Reorder 类型和 Memory Order 的强弱
对内存的操作可以概括为读和写，可以表示为 Load 和 store 操作，因此 Reorder 也就可以整体上分为以下四种类型：
- Load-load reorder：两个读操作之间重排；
- Load-store reorder：原来在写操作之前的读操作重排到之后；
- Store-load reorder：原来在读操作之前的写操作重排到之后；
- Store-store reorder：两个写操作之间重排。
Memory Model 既有软件层面的 Software Memory Model，又有硬件平台的 Hardware Memory Model，下图中是几种 CPU 架构下的 Hardware Memory Model。
- DEC Alpha 架构下，上述四种 Reorder 都有可能发生，只保证不改变单线程内部的执行正确性。
- ARM 架构下的 CPU 也允许四种 Reorder 的发生，额外保证了数据依赖顺序。
- X86/X64 平台属于强 Memory Model 的范畴，只可能发生 Store-load reorder。
- C++ 11 中原子操作的内存序属于 Software Memory Model 的范畴，在软件层面进行相关限制，让 CPU 实现相应操作的效果。
2、Compiler Barrier 与 Runtime Memory Barrier
无论是哪种 Memory Model 中涉及的重排，都是指的在没有其他限制的情况。为了能够保证程序的正确性，CPU 和编译器（语言）的设计者都预留了手方法来改变这些重排，这类方法可以抽象成一个统一的概念 Barrier：屏障。需要使用者用代码来限制编译阶段和运行阶段的重排，因此可以分为 Compiler Barrier 和 Runtime Memory Barrier。
Compiler Barrier，编译器层面的屏障，可以防止编译器在将源码转换成机器码的过程中重排。简单的例子如下：
int a, b;
int main() {
a = b + 1;
// asm volatile("":::"memory");
b = 0;
return 0;
} 对于以上代码，使用 gcc 4.9.4 整体不开启优化进行编译，得到汇编代码如下：
$ gcc -S main.cpp
$ cat main.s
...
movl _b(%rip), %eax
addl $1, %eax
movl %eax, _a(%rip)
movl $0, _b(%rip)
movl $0, %eax
popq %rbp
... 同样使用 gcc 4.9.4 整体开启优化进行编译，得到汇编代码如下：
$ gcc –O2 -S main.cpp
$ cat main.s
...
movl _b(%rip), %eax
movl $0, _b(%rip)
addl $1, %eax
movl %eax, _a(%rip)
xorl %eax, %eax
... 如果想要整体开启优化，但是对于部分代码不想要重排，那么就可以使用 Compiler Barrier，在 gcc 里，asm volatile(“” ::: “memory”)就是这么一个 Compiler Barrier。在使用 Compiler Barrier 后，使用使用 gcc 4.9.4 整体开启优化进行编译，得到汇编代码如下：
$ gcc -O2 -S main.cpp
$ cat main.s
...
movl _b(%rip), %eax
addl $1, %eax
movl %eax, _a(%rip)
movl $0, _b(%rip)
xorl %eax, %eax
... 可以看到和未开启编译优化时的结果保持一致。
Compiler Barrier 只能保证编译阶段不重排。在多核系统里，光做到这一点还不够，因为它没法对 CPU 核心运行时的重排做出限制。因此，在多核编程中，通常需要同时对编译重排和运行时重排做出限制，需要使用到 Runtime Memory Barrier。
下面这篇讲的应该就是Runtime Memory Barrier
要了解如何使用memory barrier，最好的方法是明白它为什么存在。CPU硬件设计为了提高指令的执行速度，增设了两个缓冲区（store buffer, invalidate queue）。这个两个缓冲区可以避免CPU在某些情况下进行不必要的等待，从而提高速度，但是这两个缓冲区的存在也同时带来了新的问题。下面我们一步步来分析说明
cache一致性问题
Cache 一致性问题出现的原因是在一个多处理器系统中，每个处理器核心都有独占的Cache 系统（比如一级 Cache 和二级 Cache），而导致一个内存块在系统中同时可能有多个备份，从而引起访问时的不一致性问题。
Cache 一致性问题的根源是因为存在多个处理器独占的 Cache，而不是多个处理器。它的限制条件比较多：多核，独占 Cache，Cache 写策略。当其中任一个条件不满足时便不存在cache一致性问题。
为了保证在多处理器的环境下cache一致性，需要通过某种手段来保证cache的一致性。
解决 Cache 一致性问题的机制有两种：基于目录的协议（Directory-based protocol）和总线窥探协议（Bus snooping protocol）。 目前被多个厂家广泛使用的协议是MESI协议。它是从总线窥探协议中衍生而来的一种协议。
cache一致性协议：MESI
MESI 协议是 Cache line 四种状态的首字母的缩写，分别是修改（Modified）态、独占（Exclusive）态、共享（Shared）态和失效（Invalid）态。 Cache 中缓存的每个 Cache Line 都必须是这四种状态中的一种。
- 修改态（Modified），如果该 Cache Line 在多个 Cache 中都有备份，那么只有一个备份能处于这种状态，并且“dirty”标志位被置上。拥有修改态 Cache Line 的 Cache 需要在某个合适的时候把该 Cache Line 写回到内存中。但是在写回之前，任何处理器对该 Cache Line在内存中相对应的内存块都不能进行读操作。 Cache Line 被写回到内存中之后，其状态就由修改态变为共享态。
- 独占态（Exclusive），和修改状态一样，如果该 Cache Line 在多个 Cache 中都有备份，那么只有一个备份能处于这种状态，但是“dirty”标志位没有置上，因为它是和主内存内容保持一致的一份拷贝。如果产生一个读请求，它就可以在任何时候变成共享态。相应地，如果产生了一个写请求，它就可以在任何时候变成修改态。
- 共享态（Shared），意味着该 Cache Line 可能在多个 Cache 中都有备份，并且是相同的状态，它是和内存内容保持一致的一份拷贝，而且可以在任何时候都变成其他三种状态。
- 失效态（Invalid），该 Cache Line 要么已经不在 Cache 中，要么它的内容已经过时。一旦某个Cache Line 被标记为失效，那它就被当作从来没被加载到 Cache 中
MESI使用消息传递的方式在上述几种状态之间切换，具体转换过程参见[1]。常见的消息类型：
read: 包含要读取的CACHE-LINE的物理地址
read response: 包含READ请求的数据，要么由内存满足要么由cache满足
invalidate: 包含要invalidate的cache-line的物理地址，所有其他cache必须移除相应的数据项
invalidate ack: 回复消息
read invalidate: 包含要读取的cache-line的物理地址，同时使其他cache移除该数据。需要read response和invalidate ack消息
writeback：包含要写回的数据和地址，该状态将处于modified状态的lines写回内存，为其他数据腾出空间Store buffer的引入
虽然该MESI协议可以保证数据的一致性，但是在某种情况下并不高效。举例来说，如果CPU0要更新一个处于CPU1-cache中的数据，那么它必须等待 cache-line从CPU1-cache传递到CPU0-cache，然后再执行写操作。cache之间的传递需要花费大量的时间，比执行一个简单的 操作寄存器的指令高出几个数量级。而事实上，花费这个时间根本毫无意义，因为不论从CPU1-cache传递过来的数据是什么，CPU0都会覆盖它。为了 解决这个问题，硬件设计者引入了store buffer，该缓冲区位于CPU和cache之间，当进行写操作时，CPU直接将数据写入store buffer，而不再等待另一个CPU的消息。但是这个设计会导致一个很明显的错误情况。
引入store buffer后出现的问题1
试考虑如下代码：
a = 1;
b = a + 1;
assert(b == 2);假设初始时a和b的值都是0，a处于CPU1-cache中，b处于CPU0-cache中。如果按照下面流程执行这段代码：
CPU 0 starts executing the a = 1
CPU 0 looks “a” up in the cache, and finds that it is missing
CPU 0 therefore sends a “read invalidate” message in order to get exclusive ownership of the cache line containing “a”.
CPU 0 records the store to “a” in its store buffer.
CPU 1 receives the “read invalidate” message, and responds by transmitting the cache line and removing that cacheline from its cache.
CPU 0 starts executing the b = a + 1.
CPU 0 receives the cache line from CPU 1, which still has a value of zero for “a”.
CPU 0 loads “a” from its cache, finding the value zero.
CPU 0 applies the entry from its store buffer to the newly arrived cache line, setting the value of “a” in its cache to one.
CPU 0 adds one to the value zero loaded for “a” above, and stores it into the cache line containing “b” (which we will assume is already owned by CPU 0).
CPU 0 executes assert(b == 2), which fails.
出现问题的原因是我们有两份”a”的拷贝，一份在cache-line中，一份在store buffer中。硬件设计师的解决办法是“store forwarding”，当执行load操作时，会同时从cache和store buffer里读取。也就是说，当进行一次load操作，如果store-buffer里有该数据，则CPU会从store-buffer里直接取出数 据，而不经过cache。因为“store forwarding”是硬件实现，我们并不需要太关心。
引入store buffer后出现的问题2
请看下面的代码：
void foo(void)
{
a = 1;
b = 1;
}
void bar(void)
{
while (b == 0) continue;
assert(a == 1);
}假设变量a在CPU1-cache中，b在CPU0-cache中。CPU0执行foo()，CPU1执行bar()。
程序执行的顺序如下：
CPU 0 执行a = 1。缓存行不在CPU0的缓存中，因此CPU0将“a”的新值放到存储缓冲区，并发送一个“读使无效”消息
CPU 1 执行while (b == 0) continue，但是包含“b”的缓存行不在缓存中，它发送一个“读”消息。
CPU 0 执行b = 1，它已经在缓存行中有“b”的值了(换句话说，缓存行已经处于“modified”或者“exclusive”状态)，因此它存储新的“b”值在它的缓存行中。
CPU 0 接收到“读”消息，并且发送缓存行中的最新的“b”的值到CPU1，同时将缓存行设置为“shared”状态
CPU 1 接收到包含“b”值的缓存行，并将其值写到它的缓存行中
CPU 1 现在结束执行while (b == 0) continue，因为它发现“b”的值是1，它开始处理下一条语句。
CPU 1 执行assert(a == 1)，并且，由于CPU 1 工作在旧的“a”的值，因此验证失败。
CPU 1 接收到“读使无效”消息, 并且发送包含“a”的缓存行到CPU0，同时使它的缓存行变成无效。但是已经太迟了。
CPU 0 接收到包含“a”的缓存行，将且将存储缓冲区的数据保存到缓存行中，这使得CPU1验证失败。
就是说，可能出现这类情况，b已经赋值了，但是a还没有，所以出现了b = 1, a = 0的情况。对于这类问题，硬件设计者也爱莫能助，因为CPU无法知道变量之间的关联关系。所以硬件设计者提供了memory barrier指令，让软件来告诉CPU这类关系。解决办法是：使用硬件设计者提供的“内存屏障”来修改代码：
void foo(void)
{
a = 1;
smp_mb();
b = 1;
}Linux内核提供的内存屏障API函数说明如下表。内存屏障可用于多处理器和单处理器系统，如果仅用于多处理器系统，就使用smp_xxx函数，在单处理器系统上，它们什么都不要。
内存屏障API函数说明 内存屏障的宏定义功能说明
mb() 适用于多处理器和单处理器的内存屏障。
rmb() 适用于多处理器和单处理器的读内存屏障。
wmb() 适用于多处理器和单处理器的写内存屏障。
smp_mb() 适用于多处理器的内存屏障。
smp_rmb() 适用于多处理器的读内存屏障。
smp_wmb() 适用于多处理器的写内存屏障。smp_mb()指令可以迫使CPU在进行后续store操作前刷新store-buffer。以上面的程序为例，增加memory barrier之后，就可以保证在执行b=1的时候CPU0-store-buffer中的a已经刷新到cache中了，此时CPU1-cache中的a 必然已经标记为invalid。对于CPU1中执行的代码，则可以保证当b==0为假时，a已经不在CPU1-cache中，从而必须从CPU0- cache传递，得到新值“1”
Invalidation Queue的引入
store buffer一般很小，所以CPU执行几个store操作就会填满, 这时候CPU必须等待invalidation ACK消息（得到invalidation ACK消息后会将storebuffer中的数据存储到cache中，然后将其从store buffer中移除），来释放store buffer缓冲区空间。
“Invalidation ACK”消息需要如此长的时间，其原因之一是它们必须确保相应的缓存行实际变成无效了。如果缓存比较忙的话，这个使无效操作可能被延迟。例如，如果CPU密集的装载或者存储数据，并且这些数据都在缓存中。另外，如果在一个较短的时间内，大量的“使无效”消息到达，一个特定的CPU会忙于处理它们。这会使得其他CPU陷于停顿。但是，在发送应答前，CPU 不必真正的使无效缓存行。它可以将使无效消息排队。并且它明白，在发送更多的关于该缓存行的消息前，需要处理这个消息。
一个带Invalidation Queue的CPU可以迅速应答一个Invalidation Ack消息，而不必等待相应的行真正变成无效状态。于是乎出现了下面的组织架构：
但是，此种方法也存在如下问题：
void foo(void)
{
a = 1;
smp_mb();
b = 1;
}
void bar(void)
{
while (b == 0) continue;
assert(a == 1);
}CPU0执行a=1。因为cache-line是shared状态，所以新值放到store-buffer里，并传递invalidate消息来通知CPU1
CPU1执行 while(b==0) continue;但是b不再CPU1-cache中，所以发送read消息
CPU1接受到CPU0的invalidate消息，将其排队，然后返回ACK消息
CPU0接收到来自CPU1的ACK消息，然后执行smp_mb()，将a从store-buffer移到cache-line中。（内存屏蔽在此处生效了）
CPU0执行b=1;因为已经包含了该cache-line，所以将b的新值写入cache-line
CPU0接收到了read消息，于是传递包含b新值的cache-line给CPU1，并标记为shared状态
CPU1接收到包含b的cache-line
CPU1继续执行while(b==0) continue;因为为假所以进行下一个语句
CPU1执行assert(a==1)，因为a的旧值依然在CPU1-cache中，断言失败
尽管断言失败了，但是CPU1还是处理了队列中的invalidate消息，并真的invalidate了包含a的cache-line，但是为时已晚
出现问题的原因是，当CPU排队某个invalidate消息后，并做错了应答Invalidate Ack, 但是在它还没有处理这个消息之前，就再次读取了位于cache中的数据，该数据此时本应该已经失效，但由于未处理invalidate消息导致使用错误。
解决方法是在bar()中也增加一个memory barrier：
void bar(void)
{
while (b == 0) continue;
smp_mb();
assert(a == 1);
}此处smp_mb()的作用是处理“Invalidate Queues”中的消息，于是在执行assert(a==1)时，CPU1中的包含a的cache-line已经无效了，新的值要重新从CPU0-cache中读取
从这两个例子可以看出：
smp_mb();既可以用来处理storebuffer中的数据，也可以用来处理Invalidation Queue中的Invalid消息。实际上，memory barrier确实可以细分为“write memory barrier(wmb)”和“read memory barrier(rmb)”。rmb只处理Invalidate Queues，wmb只处理store buffer。
上述例子完整的代码变为：
void foo(void)
{
a = 1;
smp_wmb();/*CPU1要使用该值，因此需要及时更新处理store buffer中的数据*/
b = 1;
}
void bar(void)
{
while (b == 0) continue;
smp_rmb();/*由于CPU0修改了a值，使用此值时及时处理Invalidation Queue中的消息*/
assert(a == 1);
}