转自：http://blog.csdn.net/chen19870707/article/details/39896655

• Author：Echo Chen（陈斌）

• Email：chenb19870707@gmail.com

• Blog：Blog.csdn.net/chen19870707

• Date：September 30th, 2014

         来自一篇墙外的文章，要了解如何使用memory barrier，最好的方法是明白它为什么存在。CPU硬件设计为了提高指令的执行速度，增设了两个缓冲区（store buffer, invalidate queue）。这个两个缓冲区可以避免CPU在某些情况下进行不必要的等待，从而提高速度，但是这两个缓冲区的存在也同时带来了新的问题。

要仔细分析这个问题需要先了解cache的工作方式。

        目前CPU的cache的工作方式很像软件编程所使用的hash表，书上说“N路组相联（N-way set associative）”，其中的“组”就是hash表的模值，即hash链的个数，而常说的“N路”，就是每个链表的最大长度。链表的表项叫做 cache-line，是一段固定大小的内存块。读操作很直接，不再赘述。如果某个CPU要写数据项，必须先将该数据项从其他CPU的cache中移出， 这个操作叫做invalidation。当invalidation结束，CPU就可以安全的修改数据了。如果数据项在该CPU的cache中，但是是只 读的，这个过程叫做”write miss”。一旦CPU将数据从其他CPU的cache中移除，它就可以重复的读写该数据项了。如果此时其他CPU试图访问这个数据项，将产生一 次”cache miss”，这是因为第一个CPU已经使数据项无效了。这种类型的cache-miss叫做”communication miss”，因为产生这种miss的数据项通常是做在CPU之间沟通之用，比如锁就是这样一种数据项。

       为了保证在多处理器的环境下cache仍然一致，需要一种协议来防止数据不一致和丢失。目前常用的协议是MESI协议。MESI是 Modified,Exclusive, Shared, Invalid这四种状态的首字母的组合。使用该协议的cache，会在每个cache-line前加一个2位的tag，标示当前的状态。

MESI使用消息传递的方式在上述几种状态之间切换，具体转换过程参见[1]。如果CPU使用共享BUS，下面的消息足够：

引用[1]中的话：

Interestingly enough, a shared-memory multiprocessor system really is a message-passing computer under the covers. This means that clusters of SMP machines that use distributed shared memory are using message passing to implement shared memory at two different levels of the system architecture.

      虽然该协议可以保证数据的一致性，但是在某种情况下并不高效。举例来说，如果CPU0要更新一个处于CPU1-cache中的数据，那么它必须等待 cache-line从CPU1-cache传递到CPU0-cache，然后再执行写操作。cache之间的传递需要花费大量的时间，比执行一个简单的 操作寄存器的指令高出几个数量级。而事实上，花费这个时间根本毫无意义，因为不论从CPU1-cache传递过来的数据是什么，CPU0都会覆盖它。为了 解决这个问题，硬件设计者引入了store buffer，该缓冲区位于CPU和cache之间，当进行写操作时，CPU直接将数据写入store buffer，而不再等待另一个CPU的消息。但是这个设计会导致一个很明显的错误情况。

试考虑如下代码：

   1: a = 1;

   2: b = a + 1;

   3: assert(b == 2);

假设初始时a和b的值都是0，a处于CPU1-cache中，b处于CPU0-cache中。如果按照下面流程执行这段代码：

出现问题的原因是我们有两份”a”的拷贝，一份在cache-line中，一份在store buffer中。硬件设计师的解决办法是“store forwarding”，当执行load操作时，会同时从cache和store buffer里读取。也就是说，当进行一次load操作，如果store-buffer里有该数据，则CPU会从store-buffer里直接取出数 据，而不经过cache。因为“store forwarding”是硬件实现，我们并不需要太关心。

还有一中错误情况，考虑下面的代码：

   1: void foo(void)

   2: {

   3: a = 1;

   4: b = 1;

   5: }

   6:  

   7: void bar(void)

   8: {

   9: while (b == 0) continue;

  10: assert(a == 1);

  11: }

假设变量a在CPU1-cache中，b在CPU0-cache中。CPU0执行foo()，CPU1执行bar()，程序执行的顺序如下：

就是说，可能出现这类情况，b已经赋值了，但是a还没有，所以出现了b = 1, a = 0的情况。对于这类问题，硬件设计者也爱莫能助，因为CPU无法知道变量之间的关联关系。所以硬件设计者提供了memory barrier指令，让软件来告诉CPU这类关系。解决方法是修改代码如下：

   1: void foo(void)

   2: {

   3: a = 1;

   4: smp_mb();

   5: b = 1;

   6: }

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”。具体过程见[1]。

上面的例子是使用memory barrier的一种环境，另一种环境涉及到另一个缓冲区，确切的说是一个队列——“Invalidate Queues”。

store buffer一般很小，所以CPU执行几个store操作就会填满。这时候CPU必须等待invalidation ACK消息，来释放缓冲区空间——得到invalidation ACK消息的记录会同步到cache中，并从store buffer中移除。同样的情形发生在memory barrier执行以后，这时候所有后续的store操作都必须等待invalidation完成，不论这些操作是否导致cache-miss。解决办法 很简单，即使用“Invalidate Queues”将invalidate消息排队，然后马上返回invalidate ACK消息。不过这种方法有问题。

考虑下面的情况：

   1: void foo(void)

   2: {

   3: a = 1;

   4: smp_mb();

   5: b = 1;

   6: }

   7:  

   8: void bar(void)

   9: {

  10: while (b == 0) continue;

  11: assert(a == 1);

  12: }

a处于shared状态，b在CPU0-cache内。CPU0执行foo()，CPU1执行函数bar()。执行操作如下：

可以看出出现问题的原因是，当CPU排队某个invalidate消息后，在它还没有处理这个消息之前，就再次读取该消息对应的数据了，该数据此时本应该已经失效的。

解决方法是在bar()中也增加一个memory barrier：

   1: void bar(void)

   2: {

   3: while (b == 0) continue;

   4: smp_mb();

   5: assert(a == 1);

   6: }

此处smp_mb()的作用是处理“Invalidate Queues”中的消息，于是在执行assert(a==1)时，CPU1中的包含a的cache-line已经无效了，新的值要重新从CPU0-cache中读取。

memory bariier还可以细分为“write memory barrier(wmb)”和“read memory barrier(rmb)”。rmb只处理Invalidate Queues，wmb只处理store buffer。

可以使用rmb和wmb重写上面的例子：

   1: void foo(void)

   2: {

   3: a = 1;

   4: smp_wmb();

   5: b = 1;

   6: }

   7:  

   8: void bar(void)

   9: {

  10: while (b == 0) continue;

  11: smp_rmb();

  12: assert(a == 1);

  13: }

最后提一下x86的mb。x86CPU会自动处理store顺序，所以smp_wmb()原语什么也不做，但是load有可能乱序，smp_rmb()和smp_mb()展开为lock;addl。

       [1] http://www.rdrop.com/users/paulmck/scalability/paper/whymb.2010.06.07c.pdf 
       [2] http://en.wikipedia.org/wiki/Memory_barrier 
       [3] http://www.mjmwired.net/kernel/Documentation/memory-barriers.txt

       [4]http://sstompkins.wordpress.com/2011/04/12/why-memory-barrier%EF%BC%9F/

-

Echo Chen：Blog.csdn.net/chen19870707

为什么需要内存屏障【转】