浅谈运行期间cpu指令重排
上篇谈到了编译器会进行内存操作指令的重排，这篇来谈谈运行期间cpu进行内存操作指令重排。当且仅当lock-free技术采用时才会出现这个情况，换句话说在多线程之间没有任何互斥操作在操作同一块共享内存期间。不像编译期间内存操作指令重排一样，这种情况只有在多核的系统中才会发生。
我们可以使用memory barrier指令来保证内存操作次顺的一致性。下面列举了一些可以被当做屏障的指令：
- 显式的gcc的汇编指令 比如 asm volatile("lwsync" ::: "memory")
- 很多c++11的原子操作，比如load(std::memory_order_acquire)
- 互斥锁 比如pthread_mutex
确实有很多指令可以被充当成memory barrier，也有很多不同类型的memory barrier。确实，不同类型的操作产生不同类型的屏障指令。下面详细的谈谈这方面的内容。
我们假设一个多核系统的架构，有L1，L2两级缓存（实际上现在普遍都是3级），每个核心分布都有私有的32KB的L1缓存。1MB的L2缓存被两个核共享了，还有512MB的主存。
我们都用过代码仓库管理系统，多核系统的工作有点像一组程序员使用个代码仓库协作下工作。上述的双核系统有点像只有两个程序员。为了方便分别命名为Larry和Sergey。
右边我们有一个中心仓库，这个代表着L2和RAM。Larry和Sergey分别各自在自己机器上完成工作，本地仓库这个代表着每个核私有的L1缓存。两者还有一些scratch area记录着寄存器以及栈上的局部变量。两个程序员修改着他们的本地仓库以及scratch area。他们做的任何工作都是依赖于当前看到的数据，这个很类似一个线程在一个核上运行的场景。
随着Larry和Sergey不停的修改他们的本地仓库。pull和push到远程仓库在后台自动运行，并且在完全随机的时间里。一旦Larry修改了文件X，这个修改会push到远程仓库，但是不能保证何时push，可能立即push，也可能延迟push，可能他将会编辑其他文件Y，Z后在push。可能这些修改push到远程仓库比X更早。这种就类似stores操作重排。
同样的，在Sergey的机器中，也不能保证时间以及顺序，这些修改会pull到本地仓库。这种就类比于loads操作重排。
如果两个程序员分别使用两个独立的远程仓库开发，这些奇怪的push/pull操作并没有任何影响。这个就类比运行了2个独立的单线程程序。这种情况下，内存次序的基本规则是遵守的。
会议上篇中的例子。X和Y都是全局变量，而且分别被初始化为0。
假设X和Y是文件，存在于Larry和Sergey的本地仓库以及远程仓库中。在同一个时刻，Larry写入1到自己的本地仓库的X中，Sergey写入1到自己的本地仓库的Y。如果两者的修改都没有时间去push到远程和从远程pull。这个运行的结果就是r1=0 r2=0。这个好像挺违法直觉的，但是这个符合之前提到的代码控制策略。
内存屏障类型
幸运的是，Larry和Sergey并不是完全依赖不可预测随机的后台自动运行的pull和push的方式。他们还有一些特别的指令，被称为fence指令，这个就是内存屏障。在这个假设中，我们会有4种不同类型的内存屏障。每个类型的阻止不同类型的内存重排。根据命名规则就很容易理解。比如#storeLoad被设计着阻止一个store跟随一个load的内存重排。
大部分时候，真实的cpu指令一般都至少是上述屏障的组合或者附加了一些其他效果。但是一旦你理解了这4种类型的屏障，就很容易理解大多数cpu的屏障指令了或者高级语言中的屏障表达式了。
#LoadLoad
LoadLoad屏障保证了屏障前的Loads以及屏障后的Loads的顺序一致性。
值得注意的是，#LoadLoad操作并不能保证获取最新的远程仓库的内容。可能pull了一个比较旧一点的仓库，但是至少和本地的值是一样的新的。
这个听起来有点“弱保证”，但是这个也仍然是个很好的方式去阻止获取“脏数据”。考虑之前的例子，当Sergey检查共享标志时，查看Larry是否有数据push。如果flag为true，在读取push的值之前，会添加一个LoadLoad屏障。
if(IsPublished){
COMPILER_BARRIER();
return Value;
}
显然的，这个例子依赖于IsPublished，在Sergey的本地仓库中是否从远程pull了。什么时候pull并不重要，但是一旦IsPublished值被更新了，加入#LoadLoad就能保证，Value值的读取必须更晚于这个标记本身。
#StoreStore
StoreStore屏障会阻止Store和Store指令间的重排。
作为一个额外的转折，让我们假设#StoreStore指令都不是即时的。他们都是有延迟执行的，异步的方式。即使Larry执行了#StoreStore，我们也不能认为，他push的修改立马就可以到达远程仓库。
这种弱保障的方式确实有一些“疑惑”，但是这里仍然能很好的阻止Sergey pull任何脏数据（Larry push的）。Larry只是需要push数据到共享内存，添加#StoreStore屏障，然后把IsPubulished标记设置成true。
这个屏障的加上后，不能保证其他用户立即获取到最新的Value值，但是保证了，远程仓库中一旦IsPublished值更新后，Value的值也一定是更新后的值。这里指的脏数据的情况是“远程仓库中IsPubulished值更新了，但是Value还是个旧值”。
Value = x;
COMPILER_BARRIER();
IsPublished = 1;
同样的，我们观察IsPublished值从Larry的本地仓库流向Sergey的本地仓库。一旦Sergey看到了值修改了，他可以立马获取到一个正确的Value值。有趣的是，甚至Value的值都不需要是原子性的，甚至是一个结构体都可以。这个就可以理解“屏障的意思了”，结构体的store就是多条指令的store，意味着屏障不仅保障上下两条指令的顺序，而是保证“上半集合”和“下半集合”的顺序先后关系。集合内部的顺序并不保障。
#LoadStore
不像#LoadLoad和#StoreStore，#LoadStore并没有很好的假想场景在源码管理器中。最好的方式去理解#LoadStore，最好的方式去理解#LoadStore就是依据指令重排。
想象下，Larray有一堆指令去跟踪，一些指令是从本地仓库中load数据到寄存器中，一些是store寄存器数据到本地仓库中。Larry只有在特殊的情况下才有辨别这些指令的能力。有时他遇到了一个load，他接下来希望看到有一些stores接着后面，如果strore和load完全没有任何关系的时候，他就会被允许把store放到load前面去。这种情况下，存储一致性的基本准则还是遵循的，单线程下不修改其最后结果。
在真实的cpu中，一些指令会发生在load时cache Miss，而紧接着的Store cache Hit。这个也容易理解，cache Miss会多花几十倍的时钟周期去完成执行，cpu不可能等待着。但是就理解这个比喻而言，硬件细节并不重要。我们可以说Larry工作类了，在这仅有的时间内Larry会创造性的工作。何时以及到底会不会这么做都是不可预测的。幸运的是，这里有个相对低消耗的方式去阻止指令重排。当Larry遇到了#LoadStore时，他会克制重排，在屏障上下。
在我们的假设中，哪怕加入了#LoadLoad或者#StoreStore屏障，Larry还是会执行重排（因为没有加#LoadStore屏障）。然而，一个真实的cpu指令，一个有#LoadStore屏障功能的指令，至少含有上述两类屏障的功能。
#StoreLoad
StoreLoad屏障保障了，屏障前的store指令被执行后数据更新到其他处理器后，然后在进行load获取最新值。换句话说，这个有效阻止了屏障前的store操作和屏障后的load操作的重排。
` #StoreLoad很特殊，这个是仅有的方式去阻止r1=r2=0，在这个https://github.com/iamjokerjun/memReordering
这个时候可能会想到StoreLoad屏障和StoreStore屏障和LoadLoad屏障的组合有什么不同的。毕竟StoreStore屏障会push改变到远程仓库，而LoadLoad屏障会从远程仓库pull。然后仅有这两种屏障是不够的。记住push操作可能会延迟的。这个就是意味着PowerPC的lwsync指令-具有LoadLoad屏障，LoadStore屏障以及StoreStore屏障，但是没有StoreLoad屏障的功能，所以不足以阻止r1=r2=0.
就此类比而言，一个StoreLoad屏障push本地任何修改到远程仓库的，然后等到操作完成后，在拉领取相对来说最新的远程仓库的副本。在大多数处理器中，实现StoreLoad屏障相对来说会比其他类型屏障更消耗一些。
如果我们增加LoadStore屏障在上述操作中，也没什么大不了的，就意味着全内存屏障，4个屏障在一起。
