关于乱序

首先需要明确一个很普遍，但却未必人人都注意到的事实：程序并不总是按照源码中的顺序被执行的，此谓之乱序，乱序产生的原因可能有好几种：

1. 编译器出于优化的目的，在编译阶段将源码的顺序进行交换。
2. 程序执行期间，指令流水被 cpu 乱序执行。
3. cache 的分层及刷新策略使得有时候某些写，读操作的顺序被重排。

以上乱序现象虽然来源不同，但从源码的角度，对上层程序来说，他们的效果其实是一样的：写出来的代码与最后被执行的代码是不一致的。这个事实可能会让人很惊讶：有这样严重的问题，还怎么写得出正确的代码？ 这担忧是多虑了，乱序的现象虽然普遍存在，但它们都有很重要的一条共同点：在单线程执行的情况下，乱序执行与不乱序执行，最后都会得出相同的结果(both end up with the same observable result), 这是乱序被允许出现所需要遵循的首要原则，也是为什么乱序虽然一直存在但却大部分程序员都感觉不到的原因。

乱序的出现说到底是编译器，CPU 等为了让你程序跑得更快而作出的无限努力的结果，程序员们应该为它们的良苦用心抹一把泪。

从乱序的种类来看，乱序主要可以分为如下4种：

1. 写写乱序(store store), 前面的写操作被放到了后面的操作之后，比如：

   a = 3;
   b = 4;
   被乱序为：
   b = 4;
   a = 3;
   

2. 写读乱序(store load)，前面的写操作被放到了后面的读操作之后，比如：

   a = 3;
   load(b);
   被乱序为
   load(b);
   a = 3;
   

3. 读读乱序(load load)， 前面的读操作被放到了后一个读操作之后，比如：

   load(a);
   load(b);
   被乱序为：
   load(b);
   load(a);
   

4. 读写乱序(load store), 前面的读操作被放到了后一个写操作之后，比如：

   load(a);
   b = 4;
   被乱序为：
   b = 4;
   load(a);
   

程序的乱序在单线程的世界里没有引起太多引人注意的问题，但在多线程时，这些乱序就制造了特别的麻烦，究其原因，最主要的有2个：

1. 不能保证修改共享变量的原子性，这会导致常说的 race condition，各个线程同时修改某块内存，因此像 mutex，各种 lock 之类的东西在写多线程时被频繁地使用。
2. 变量被修改后，该修改未必能被另一个线程及时观察到，因此需要“同步”。

解决同步问题就需要确定内存模型，也就是需要确定线程间应该怎么通过共享内存来进行交互(查看维基百科).

内存模型

内存模型所要表达的内容主要是怎么描述：一个内存操作的效果，在各个线程间的可见性的问题。 我们知道，对计算机来说，通常内存的写操作相对于读操作是昂贵很多很多的，因此对写操作的优化是提升性能的关键，而这些对写操作的种种优化，导致了一个很普遍的现象出现：写操作通常会在 CPU 内部的 cache 中缓存起来。 这就导致了在一个 CPU 里执行一个写操作之后，该操作导致的内存变化却不会马上就被另一个 CPU 所看到。

cpu1 执行如下：
a = 3;
cpu2 执行如下：
load(a);

对如上代码，假设 a 的初始值是 0, 然后 cpu1 先执行，之后 cpu2 再执行，那么最后 cpu2 如果读到 a = 0 也其实不是什么奇怪事情。很显然，这种在某个线程里修改全局变量，居然在另一个线程里看不到效果的后果是很严重的。

因此必须要有必要的手段对这种修改公共变量的行为进行同步。

c++11 的 atomic library 中定义了以下6种语义来对内存操作进行约定，这些语义分别表示了不同的操作行为在其它线程中的可见性的问题：

enum memory_order {
    memory_order_relaxed,
    memory_order_consume,
    memory_order_acquire,
    memory_order_release,
    memory_order_acq_rel,
    memory_order_seq_cst
};

我们主要讨论其中的几个：relaxed, acquire, release, seq_cst(sequential consistency).

relaxed 语义

首先是 relaxed，这表示一种最宽松的内存操作约定，该约定其实就是是不进行约定，以这种方式修改内存时，不需要保证该修改会不会及时被其它线程看到，也不对乱序做任何要求。 因此当对公共变量以 relaxed 方式进行读写时，编译器，cpu 等是被允许按照任意它们认为合适的方式来处理的。

release-acquire 语义

如果你曾经去看过别的介绍内存模型相关的文章，你一定会发现 release 总是和 acquire 放到一起来讲，这不是偶然。 事实上，release 和 acquire 是相辅相承的，它们必须配合起来使用，这俩是一个 package deal， 分开使用则完全没有意义。

具体到其中， release 用于进行写操作，acquire 则用于进行读操作，它们结合起来表示这样一个约定：

如果一个线程A对一块内存 m 以 release 的方式进行修改，那在线程 A 中，所有在该 release 操作之前进行的写操作，都在另一个线程 B 对内存 m 以 acquire 的方式进行读取之后，变得可见。

举个粟子，假设线程 A 执行如下指令：

a.store(3);
b.store(4);
m.store(5, release);

线程 B 执行如下:

e.load();
f.load();
m.load(acquire);
g.load();
h.load();

如上，假设线程 A 先执行，线程 B 后执行, 因为线程 A 中对 m 以 release 的方式进行修改， 而线程 B 中以 acquire 的方式对 m 进行读取，所以当线程 B 执行完 m.load(release) 之后， 线程 B 必须已经能看到 a == 3, b == 4.

以上死板的描述事实上还传达了额外的不那么明显的信息：

1. release 和 acquire 是相对两个线程来说的，它约定的是两个线程间的相对行为：如果其中一个线程 A 以 release 的方式修改公共变量 m， 另一个线程 B 以 acquire 的方式时读取该 m 时，要有什么样的后果，但它并不保证，此时如果还有另一个线程 C 以非 acquire 的方式来读取 m 时，会有什么后果。

2. 一定程度阻止了乱序的发生，因为要求 release 操作之前的所有操作都在另一个线程 acquire 之后可见，那么：

   1. release 操作之前的 store 操作不允许被乱序到 release 之后。
   2. acquire 操作之前的 load 操作不允许被乱序到 acquire 之前。

在对它们的使用上，有几点是特别需要注意的：

1. release 和 acquire 是配合使用的，单独使用时没有意义的。
2. release 只对写操作(store) 有效，对读(load)是没意义的。
3. acquire 则只对读操作有效，对写操作是无意义的。

现代的处理器通常都支持一些 read-modify-write 之类的指令，对这种指令，有时我们可能既想对该操作 release 又要对该操作进行 acquire，因此 c++11 中还定义了 memory_order_acq_rel，该类型的操作就是 release 与 acquire 的结合，除前面提到的作用外，还起到了 memory barrier 的功能。

sequential consistency

sequential consistency 相当于 release + acquire 之外，还加上了一个全局顺序的问题，这是什么意思呢？

简单来说就是，对任意内存操作，不管它们是不是分散在不同的 cpu 中同时进行，这些操作所产生的效果最终都要求有一个全局的顺序，而且这个顺序在各个线程看起来是一致的。

举个粟子,假设 a, b 的初始值都是0：

线程 A 执行：

a.store(3, seq_cst);

线程 B 执行：

b.store(4, seq_cst);

如上虽然对于 a 与 b 的修改分别在两个线程里同时进行，但是这多个动作毕竟是非原子的，因此它们的进行在全局上必须要有一个先后顺序：

1. 先修改a, 后修改b，或
2. 先修改b, 把整个a。

而且这个顺序是固定的，必须在其它任意线程看起来都是一样，因此 a == 0 && b == 4 与 a == 3 && b == 0 不允许同时成立。

后话

这篇随笔躺在我的草稿箱里已经半年多时间了，半年多来我不断地整理在这方面的知识，也在不断理清自己的思路，最后还是觉得关于内存模型有太多可以说却不是一下子能说得清楚的东西了，因此这儿只能把想说的东西一减再减，把范围缩小到 c++11 语言层面上作简单介绍，纯粹算是做个总结，有兴趣深入了解更多细节的读者，我强烈推荐去看一下 Herb Sutter 在这方面做的一个 talk, 内存模型方面的知识是很难理解，更难以正确使用的，在大多数情况下使用它而得到的些少性能优势，已经完全不值得为此而带来的代码复杂性可读性方面的损失，如果你还在犹豫是否要用这些低层的东西的时候，就不要用它，犹豫就说明还有其它选择，不到没得选择，都不要亲自实现 lock free 相关的东西。

【引用】

http://bartoszmilewski.com/2008/11/11/who-ordered-sequential-consistency/

http://bartoszmilewski.com/2008/11/05/who-ordered-memory-fences-on-an-x86/

http://bartoszmilewski.com/2008/12/01/c-atomics-and-memory-ordering/

http://en.cppreference.com/w/cpp/atomic/memory_order

http://preshing.com