来自一篇墙外的文章,要了解如何使用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,标示当前的状态。
modified状态:该cache-line包含修改过的数据,内存中的数据不会出现在其他CPU-cache中,此时该CPU的cache中包含的数据是最新的 exclusive状态:与modified类似,但是数据没有修改,表示内存中的数据是最新的。如果此时要从cache中剔除数据项,不需要将数据写回内存 shared状态:数据项可能在其他CPU中有重复,CPU必须在查询了其他CPU之后才可以向该cache-line写数据 invalid状态:表示该cache-line空 |
MESI使用消息传递的方式在上述几种状态之间切换,具体转换过程参见[1]。如果CPU使用共享BUS,下面的消息足够:
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写回内存,为其他数据腾出空间 |
引用[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中。如果按照下面流程执行这段代码:
1 CPU0执行a=1;
2 因为a在CPU1-cache中,所以CPU0发送一个read invalidate消息来占有数据
3 CPU0将a存入store buffer
4 CPU1接收到read invalidate消息,于是它传递cache-line,并从自己的cache中移出该cache-line
5 CPU0开始执行b=a+1;
6 CPU0接收到了CPU1传递来的cache-line,即“a=0”
7 CPU0从cache中读取a的值,即“0”
8 CPU0更新cache-line,将store buffer中的数据写入,即“a=1”
9 CPU0使用读取到的a的值“0”,执行加1操作,并将结果“1”写入b(b在CPU0-cache中,所以直接进行)
10 CPU0执行assert(b == 2); 失败 |
出现问题的原因是我们有两份”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(),程序执行的顺序如下:
1 CPU0执行 a = 1; 因为a不在CPU0-cache中,所以CPU0将a的值放到store-buffer里,然后发送read invalidate消息
2 CPU1执行while(b == 0) continue; 但是因为b不再CPU1-cache中,所以它会发送一个read消息
3 CPU0执行 b = 1;因为b在CPU0-cache中,所以直接存储b的值到store-buffer中
4 CPU0收到 read 消息,于是它将更新过的b的cache-line传递给CPU1,并标记为shared
5 CPU1接收到包含b的cache-line,并安装到自己的cache中
6 CPU1现在可以继续执行while(b == 0) continue;了,因为b=1所以循环结束
7 CPU1执行assert(a == 1);因为a本来就在CPU1-cache中,而且值为0,所以断言为假
8 CPU1收到read invalidate消息,将并将包含a的cache-line传递给CPU0,然后标记cache-line为invalid。但是已经太晚了 |
就是说,可能出现这类情况,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()。执行操作如下:
1 CPU0执行a=1。因为cache-line是shared状态,所以新值放到store-buffer里,并传递invalidate消息来通知CPU1
2 CPU1执行 while(b==0) continue;但是b不再CPU1-cache中,所以发送read消息
3 CPU1接受到CPU0的invalidate消息,将其排队,然后返回ACK消息
4 CPU0接收到来自CPU1的ACK消息,然后执行smp_mb(),将a从store-buffer移到cache-line中
5 CPU0执行b=1;因为已经包含了该cache-line,所以将b的新值写入cache-line
6 CPU0接收到了read消息,于是传递包含b新值的cache-line给CPU1,并标记为shared状态
7 CPU1接收到包含b的cache-line
8 CPU1继续执行while(b==0) continue;因为为假所以进行下一个语句
9 CPU1执行assert(a==1),因为a的旧值依然在CPU1-cache中,断言失败
10 尽管断言失败了,但是CPU1还是处理了队列中的invalidate消息,并真的invalidate了包含a的cache-line,但是为时已晚 |
可以看出出现问题的原因是,当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
-
分享到:
相关推荐
内存屏障分析,内存屏障分析,内存屏障分析,内存屏障分析,内存屏障分析
Linux内存屏障知识讲解,彻底了解内存屏障
内核同步机制-优化屏障和内存屏障,linux内核。
内存屏障浅析,多线程编程,由于编译器的优化和缓存的使用,导致对内存的写入操作不能及时的反应出来,也就是说当完成对内存的写入操作之后,读取出来的可能是旧的内容
内存屏障是为应付内存访问操作的乱序执行而生的. 那么, 内存访问为什么会乱序呢? 这里先简要介绍一下: 现在的CPU一般采用流水线来执行指令. 一个指令的执行被分成: 取指, 译码, 访存, 执行,写回, 等若干个阶段. ...
主要为大家讲解JVM内存模型|内存结构|内存屏障,他们的概念,有什么关联以及各种的功能
国外的文章,比较详细的介绍了各种cpu的内存访问顺序问题
中国Linux内核开发者大会十周年演讲稿(中兴通讯谢宝友)-Linux内存屏障
乱序执行和内存屏障
其java内存模型中更重要的,应该是内存屏障,memoryfence较粗犷,代价也提到内存屏障,先应该说到重排序,这强调下,重排序只对于那些在当前线程没有依赖关
linux内核文档<<LINUX KERNEL MEMORY BARRIERS>>的中文翻译及译注.
Linux内存屏障,CSDN 2015开发者大会上的优秀演讲
java内存屏障与JVM并发详解实用.pdf
volatile是JVM提供的一种最轻量级的同步机制,因为Java内存模型为volatile定义特殊的访问规则,使其可以实现Java内存模型中的两大特性...这篇文章主要介绍了Java多线程之volatile关键字及内存屏障,需要的朋友可以参考下
3. CPU 0 执行 b = 1,它已经在缓存行中有“b”的值了 (换句话说,缓存行已 4. CPU 0 接收到“读”消息,并且发送缓存行中的最新的“b”的值
Memory Barriers: a Hardware View for Software Hackers 讲解内存屏障的好论文,推荐!
写屏障:强制将写缓冲器中的内容写入到高速缓存中,或者将屏障之后的指令全部写到写缓冲器直到之前写缓冲器中的内容全部被刷回缓存中,也就是处理 0 必须等到所有的 i
处理器重排序与内存屏障指令 happens-before 重排序 数据依赖性 as-if-serial 语义 程序顺序规则 重排序对多线程的影响 顺序一致性 数据竞争与顺序一致性保证 顺序一致性内存模型 同步程序的顺序一致性效果 未同步...
一文读懂原子操作、内存屏障、锁(偏向锁、轻量级锁、重量级锁、自旋锁)、Disruptor、Go Context之上半部分.doc
处理器重排序与内存屏障指令 7 happens-before 10 重排序 13 数据依赖性 13 as-if-serial 语义 13 程序顺序规则 15 重排序对多线程的影响 15 顺序一致性 19 数据竞争与顺序一致性保证 19 顺序一致性内存模型...