reordering：一个 CPU 执行了 write 的 operation，需要经过一段时间，operation 的 effect 对于其他 CPU 来说才是 visible 的。其他 CPU 观察到的 operation 的生效顺序可能和这个 CPU 的 operation 的提交顺序不同，这就叫做 reordering。

注：多线程编程中，只有在 data-race 时才需要考虑 reorder。（data-race：存在共享 data，且至少存在一个 store 的 memory operation）

内存一致性模型

Sequential Consistancy 模型

这是最简单的一种内存模型，在其他 CPU 看来，不存在任何的 reorder。
要实现这个内存一致性模型，需要满足以下两个要求：

  1. single main memory：例如不能有 store buffer
  2. 按照 program order 执行

该内存模型可以满足 coherence 的性质：对于同一个 memory location 的多个 write，在所有 CPU 看来，发生的顺序都是一致的。

在介绍 Total Store Ordering 模型之前，首先需要介绍一下 store buffer。

store buffer

store_buffer.svg

在 CPU 和 cache 之间有 store buffer，store buffer 是每个 CPU 私有的，是用来加速写入操作的。
假设存在如下的两个线程：

  1. // initial state
  2. a = b = 0;
  4. // thread A runs on CPU0
  5. a = 2;
  6. x = b;
  8. // thread B runs on CPU1
  9. b = 3;
  10. y = a;

最终的结果可能是 x == 0, y == 0。
因为可能存在这样一直情况：线程 A 的store(a, 2)位于 CPU0 的 store buffer 中，线程 B 的store(b, 3)位于 CPU1 的 store buffer 中。线程 A 读到了 b的 oldvalue，线程 B 读到了 a的 oldvalue。
在一个 CPU 看来，另一个 CPU 发生了 reordering。

注：MESI 硬件协议可以保证缓存一致，所有 CPU 都可以看到缓存的内存，缓存是透明的。

Total Store Ordering 模型

这种内存模型在 Sequntial Consistency 的基础上，允许 store buffer 的存在。

x86 就是这种内存模型。
x86 可以保证，只有进行先 store后load操作时，才可能发生 reordering。正如 store buffer 中的例子那样。而其他的读写顺序，load - load，load - store，store - store都不会发生 reordering。

注：ARM 架构的内存模型更加的弱（coherence 更弱），几乎允许所有有的 reordering。

同步

reordering 会给多线程程序的编写带来各种不便，因此硬件提供了一系列的工具来阻止 reordering。

barrier
这里以最强的 barrier 为例进行简单介绍。在其他 CPU 看来，「barrier 之前的 memory operation」 会在 「barrier 之后的 memory operation」 之前发生。

CAS 指令：campare and swap
这是一个原子操作，函数签名可以是：bool CAS(addr, expect, desire);
将 expect 的值和指定内存地址 addr 中的值进行比较，如果两者相同，就将 desire 值写入内存。

可以利用这个指令实现很多的 lock-free 的编程。

参考