愿历尽千帆 归来仍少年

内存屏障

字数统计: 9,149阅读时长: 37 min
2020/06/20

本篇文章开始之前需要了解一些背景知识

Cache Memory

我们都知道程序是运行在 RAM之中,RAM 就是我们常说的DDR(例如 DDR3、DDR4等),我们称之为main memory(主存)当我们需要运行一个进程的时候,首先会从Flash设备(例如,eMMC、UFS等)中将可执行程序load到main memory中,然后开始执行。

在CPU内部存在一堆的通用寄存器(register),如果CPU需要将一个变量(假设地址是A)加1,一般分为以下3个步骤

  1. CPU 从主存中读取地址A的数据到内部通用寄存器 x0(ARM64架构的通用寄存器之一)
  2. 通用寄存器 x0 加1
  3. CPU 将通用寄存器 x0 的值写入主存

但是存在一个问题,CPU通用寄存器的速度和主存之间存在着太大的差异
从这个网址https://gist.github.com/jboner/2841832 摘了一段数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Latency Comparison Numbers (~2012)
----------------------------------
L1 cache reference 0.5 ns
Branch mispredict 5 ns
L2 cache reference 7 ns 14x L1 cache
Mutex lock/unlock 25 ns
Main memory reference 100 ns 20x L2 cache, 200x L1 cache
Compress 1K bytes with Zippy 3,000 ns 3 us
Send 1K bytes over 1 Gbps network 10,000 ns 10 us
Read 4K randomly from SSD* 150,000 ns 150 us ~1GB/sec SSD
Read 1 MB sequentially from memory 250,000 ns 250 us
Round trip within same datacenter 500,000 ns 500 us
Read 1 MB sequentially from SSD* 1,000,000 ns 1,000 us 1 ms ~1GB/sec SSD, 4X memory
Disk seek 10,000,000 ns 10,000 us 10 ms 20x datacenter roundtrip
Read 1 MB sequentially from disk 20,000,000 ns 20,000 us 20 ms 80x memory, 20X SSD
Send packet CA->Netherlands->CA 150,000,000 ns 150,000 us 150 ms

这里没有列出寄存器速度,看到L1 cache是0.5ns,可以肯定的是寄存器一定是低于1ns,Main memory是100ns,这里的数据仅供参考
所以上面的从主存读取数值三个步骤中的第一和第三步实际上速度很慢相对于寄存器而言

当CPU试图从主存中load/store 操作时,由于主存的速度限制,CPU不得不等待这漫长的65ns时间。如果我们可以提升主存的速度,那么系统将会获得很大的性能提升。如今的DDR存储设备,动不动就是几个GB,容量很大。如果我们采用更快材料制作更快速度的主存,并且拥有几乎差不多的容量。其成本将会大幅度上升。
我们试图提升主存的速度和容量,又期望其成本很低,这就有点难为人了。因此,我们有一种折中的方法,那就是制作一块速度极快但是容量极小的存储设备。那么其成本也不会太高。这块存储设备我们称之为cache memory。在硬件上,我们将cache放置在CPU和主存之间,作为主存数据的缓存。当CPU试图从主存中load/store数据的时候, CPU会首先从cache中查找对应地址的数据是否缓存在cache 中。如果其数据缓存在cache中,直接从cache中拿到数据并返回给CPU。
CPU和主存之间直接数据传输的方式转变成CPU和cache之间直接数据传输。cache负责和主存之间数据传输。

当存在cache的时候,以上程序如何运行的例子的流程将会变成如下:

cahe的速度在一定程度上同样影响着系统的性能。一般情况cache的速度可以达到1ns,几乎可以和CPU寄存器速度媲美。但是,这就满足人们对性能的追求了吗?并没有。当cache中没有缓存我们想要的数据的时候,依然需要漫长的等待从主存中load数据。为了进一步提升性能,引入多级cache。前面提到的cache,称之为L1 cache(第一级cache)。
我们在L1 cache 后面连接L2 cache,在L2 cache 和主存之间连接L3 cache。等级越高,速度越慢,容量越大。但是速度相比较主存而言,依然很快

多级cache不是本文重点,详细可参考如下两篇文章,写的比较详细
浅谈Cache Memory
高速缓存与一致性

Cacheline

本文后续会涉及到一个名词Cacheline,cache的大小称之为cahe size,代表cache可以缓存最大数据的大小。
我们将cache平均分成相等的很多块,每一个块大小称之为cache line,其大小是cache line size。例如一个64 Bytes大小的cache
如果我们将64 Bytes平均分成64块,那么cache line就是1字节,总共64行cache line。如果我们将64 Bytes平均分成8块,那么cache line就是8字节,总共8行cache line
有一点需要注意,cache line是cache和主存之间数据传输的最小单位。什么意思呢?当CPU试图load一个字节数据的时候,如果cache缺失,那么cache控制器会从主存中一次性的load cache line大小的数据到cache中。

例如,cache line大小是8字节。CPU即使读取一个byte,在cache缺失后,cache会从主存中load 8字节填充整个cache line,至于原因可以参见这篇文章:
浅谈Cache Memory

有了前面的基础知识的认知,不难理解下面这个极简的抽象CPU架构图

缓存一致性

考虑到多线程读写环境中,不免会有个疑问,如果一个数据是多个cpu都共享,其中一个修改了是不是要想办法使得其他cpu也能更新
一个cpu去读取一个数值时,怎么确定是最新的呢?说到底就是要保证在使用cache后如何确保各 CPU 看到的数据是一致的
这个就引出另外一个名词“cache-coherence protocol”即缓存一致性协议
其中,MESI protocol 是一个基本版,从 MESI protocol 可以了解 CPU 之间如何维持看到一致的资料,可以参见MESI的维基定义: MESI协议

这里摘取英文文档中的对于MESI拆解开来的四种状态的解释
A line in the “modified” state has been subject to a recent memory store from the corresponding CPU, and the corresponding memory is guaranteed not to appear in any other CPU’s cache. Cache lines in the “modified”state can thus be said to be “owned” by the CPU. Because this cache holds the only up-to-date copy of the data, this cache is ultimately responsible for either writing it back to memory or handing it off to some other cache, and must do so before reusing this line to hold other data.
处于modified状态的cacheline说明近期有过来自对应cpu的写操作,同时也说明该该数据不会存在其他cpu对应的cache中。因此,处于modified状态的cacheline也可以说是被该CPU独占。而又因为只有该CPU的cache保存了最新的数据(最终的memory中都没有更新),所以,该cache需要对该数据负责到底。例如根据请求,该cache将数据及其控制权传递到其他cache中,或者cache需要负责将数据写回到memory中,而这些操作都需要在reuse该cache line之前完成。
The “exclusive” state is very similar to the “modified”state, the single exception being that the cache line has not yet been modified by the corresponding CPU, which in turn means that the copy of the cache line’s data that resides in memory is up-to-date. However, since the CPU can store to this line at any time, without consulting other CPUs, a line in the “exclusive” state can still be said to be owned by the corresponding CPU. That said, because the corresponding value in memory is up to date, this cache can discard this data without writing it back to memory or handing it off to some other CPU.
exclusive状态和modified状态非常类似,唯一的区别是对应CPU还没有修改cacheline中的数据,也正因为还没有修改数据,因此memory中对应的data也是最新的。在exclusive状态下,cpu也可以不通知其他CPU cache而直接对cacheline进行操作,因此,exclusive状态也可以被认为是被该CPU独占。由于memory中的数据和cacheline中的数据都是最新的,因此,cpu不需对exclusive状态的cacheline执行写回的操作或者将数据以及归属权转交其他cpu cache,而直接reuse该cacheline(将cacheine中的数据丢弃,用作他用)
A line in the “shared” state might be replicated in at least one other CPU’s cache, so that this CPU is not permitted to store to the line without first consulting with other CPUs. As with the “exclusive” state, because the corresponding value in memory is up to date, this cache can discard this data without writing it back to memory or handing it off to some other CPU.
处于share状态的cacheline,其数据可能在一个或者多个CPU cache中,因此,处于这种状态的cache line,CPU不能直接修改cacheline的数据,而是需要首先和其他CPU cache进行沟通。和exclusive状态类似,处于share状态的cacheline对应的memory中的数据也是最新的,因此,cpu也可以直接丢弃cacheline中的数据而不必将其转交给其他CPU cache或者写回到memory中。
A line in the “invalid” state is empty, in other words, it holds no data. When new data enters the cache, it is placed into a cache line that was in the “invalid” state if possible. This approach is preferred because replacing a line in any other state could result in an expensive cache miss should the replaced line be referenced in the future.
处于invalid状态的cacheline是空的,没有数据。当新的数据要进入cache的时候,优选状态是invalid的cacheline,之所以如此是因为如果选中其他状态的cacheline,则说明需要替换cacheline数据,而未来如果再次访问这个被替换掉的cacheline数据的时候将遇到开销非常大的cache miss

个人理解:
1. 对于modified状态的cacheline,别的cpu如果需要其中的数据,必须要写回到memory或者转移
2. exclusive可以理解为是modified的轻量版,exclusive状态的cacheline数据此时还没有被cpu修改,也就是说它的数据和memory中是一致的,当别的cpu需要状态是exclusive的cacheline数据时,可以直接提供数据不需要写回到memory
3. share状态的cacheline不能直接被修改,如果一个cpu需要对这个cacheline进行修改了,需要先通知其他cpu让他们将各自对应的cacheline置为invalid,然后再切换cacheline的状态到exclusive,再然后就是M状态
4. invalid状态的cacheline之前可能是有数据的,比如之前是shared状态,后来其他cpu要修改这个cacheline了,就发通知过来了要求置为invalid的,不然读取出来的就是错误的

有一个MESI动画的网址,可以模拟各个cacheline的状态切换,比起文字描述来讲更好理解,可以不断的模拟测试,对理解MESI很有帮助
VivioJS - Interactive Reversible E-Learning Animations for the WWW

比如当前状态


个人理解添加
此时CPU0上a1数据对应的cacheline此时的状态是M状态,可以看到此时的数值是11,比memory要新,其他两个cpu1,cpu2上的a1对应的cacheline是invalid状态。如果此时cpu2上对a1进行写值加1,会是什么样子的呢?
根据上面的理论知识,此时应该会通过总线通知cpu0让其写入到memory中,然后cpu2才能读取到最新的值此时再进行修改此时数值应该是12并将状态置为E并且写回memory,此时CPU0上的a1对应cacheline状态理论上应该是invalid。

实际的cpu2对a1加1后效果图如下:

个人理解添加
此时如果对cpu2的cacheline进行写加1,cacheline状态会切换到M状态,如果一直写,数值一直增加一直是M状态,其他cpu无变化。因为此时M是最新的,只有其他cpu比如此时cpu1需要读取a1的值,这个时候cpu2会将这个值写回到memory并且此时cpu1和cpu2上a1对应的cacheline状态都是S。
如果这个时候,对cpu2的a1进行写操作呢?其状态会切换到E,其他cpu对应的a1-cacheline都切到invalid
介绍完MESI后,我们知道有了MESI protocol,任何一个CPU 要写入资料前,都要先确保其它CPU 已invalid 同一位置的cache 后(希望写入的CPU 广播invalidate,其它CPU 回invalidate ack), 才能写资料到自己的cache,并在稍后补写回memory。

这个设计确保资料的一致性,不用担心同一时间同一个位置的资料会有不同的值,但是代价是写入 cache 的速度会有点慢,让 CPU 闲置,下图中的stall就是cpu等待的时长


个人理解添加
想象一下这个场景:
CPU 0 打算写入值到位置 X,CPU 1 的 cache 有 X 的值。因为缓存一致性的缘故,这个时候CPU0给CPU1发送一个invalid的广播告知其需要将其对应数值置于无效 这个时候呢cpu0就开始傻乎乎的等 CPU 1 回 invalidate ack,但是此时CPU 1 的 cache 可能太忙而拖慢了回覆时间 (比方同时从 cache 大量的读写资料,或是短时间收到大量 invalidate ack)。
这样就导致了CPU0白白耗费时间在等待上,这对于宝贵的cpu资源是一种很大的浪费,其实没必要等待这么长的时间,毕竟物理CPU 1中的cacheline保存有什么样子的数据,其实都没有意义,这个值都会被CPU 0新写入的值覆盖的,所以能不能不等呢?这也就引出了另外一个名词StoreBuffer,还有另外一个名词对应刷新的Invalidate Queue

Store Buffer & Invalidate Queue

在CPU和cache之间增加store buffer这个HW block

个人理解添加
1. CPU 0 不等 invalidate ack:先写入 store buffer,然后继续作事。之后收到 invalidate ack 再更新 cache 的状态。因为最新的资料可能存在 store buffer,CPU 读资料的顺序变成 store buffer → cache → memory。
2. CPU 1 立即回 invalidate ack:收到 invalidate 时,记录到 invalidate queue 里,先回 invalidate ack,稍后再处理 invalidate。
3. 为啥有了store buffer后还会冒出来一个invalidate queue,因为 store buffer 很小,store buffer 满的时候,CPU 0 还是得等 invalidate ack,所以加上 invalidate queue,双管齐下减少 CPU 0 等待时间
这里还有一个细节后面会提到,如果有数据加了写内存屏障的话,加入storebuffer,其后面的写操作不管有没有写屏障都要加到storebuffer中,这就造成了storebuffer更容易满了,一旦满了又要开始等ack了,这就引入了
invalidate queue,后面还会继续讲它的作用
其实这里出现了一个重排序的“现象”,就是一旦某一条写指令放到storebuffer中了继续后面的指令操作,这就造成了下一条指令跑到这条指令前面执行的”假象”,这种重排序就是为了充分利用cpu的性能避免白白的浪费等待
CPU 为了提升效率而出现的这种”改指令”执行的顺序,只要最后結果和 single thread 预期的結果一样即可。这句话可以细品下,所以多线程的情况下需要我们研发人员自己控制

有了StoreBuffer以及Invalidate Queue之后的cpu cache架构如下

下面摘自perfbook文档关于StoreBuffer以及Invalidate Queue的解释

These store buffers are local to a given CPU or, on systems with hardware multithreading, local to a given core. Either way, a given CPU is permitted to access only the store buffer assigned to it. For example, in Figure C.5, CPU 0 cannot access CPU 1’s store buffer and vice versa. This restriction simplifies the hardware by separating concerns: The store buffer improves performance for consecutive writes, while the responsibility for communicating among CPUs (or cores, as the case may be) is fully shouldered by the cache-coherence protocol. However, even given this restriction, there are complications that must be addressed, which are covered in the next two sections.

这些store buffer对于cpu而言是local的,如果系统是硬件多线程, 那么每一个cpu core拥有自己私有的stroe buffer,一个cpu只能访问自己私有的那个store buffer。在上图中,cpu 0不能访问cpu1的store buffer,反之亦然。之所以做这样的限制是为了模块划分(各个cpu core模块关心自己的事情,让cache系统维护自己的操作),让硬件设计变得简单一些。store buffer增加了CPU连续写的性能,同时把各个CPU之间的通信的任务交给维护cache一致性的协议。即便给每个CPU分配私有的store buffer,仍然引入了一些复杂性,我们会在下面两个小节中描述。

Unfortunately, each store buffer must be relatively small, which means that a CPU executing a modest sequence of stores can fill its store buffer (for example, if all of them result in cache misses). At that point, the CPU must once again wait for invalidations to complete in order to drain its store buffer before it can continue executing. This same situation can arise immediately after a memory barrier, when all subsequent store instructions must wait for invalidations to complete, regardless of whether or not these stores result in cache misses.

不幸的是:每个cpu的store buffer不能实现的太大,其entry的数目不会太多。当cpu以中等的频率执行store操作的时候(假设所有的store操作导致了cache miss),store buffer会很快的被填满。在这种状况下,CPU只能又进入等待状态,直到cache line完成invalidation和ack的交互之后,可以将store buffer的entry写入cacheline,从而为新的store让出空间之后,CPU才可以继续执行。这种状况也可能发生在调用了memory barrier指令之后,因为一旦store buffer中的某个entry被标记了,那么随后的store都必须等待invalidation完成,因此不管是否cache miss,这些store都必须进入store buffer。

This situation can be improved by making invalidate acknowledge messages arrive more quickly. One way of accomplishing this is to use per-CPU queues of invalidate messages, or “invalidate queues”.

引入invalidate queues可以缓解这个状况。store buffer之所以很容易被填充满,主要是其他CPU回应invalidate acknowledge比较慢,如果能够加快这个过程,让store buffer尽快进入cacheline,那么也就不会那么容易填满了。

Invalidate Queues One reason that invalidate acknowledge messages can take so long is that they must ensure that the corresponding cache line is actually invalidated, and this invalidation can be delayed if the cache is busy, for example, if the CPU is intensively loading and storing data, all of which resides in the cache. In addition, if a large number of invalidate messages arrive in a short time period, a given CPU might fall behind in processing them, thus possibly stalling all the other CPUs.

invalidate acknowledge不能尽快回复的主要原因是invalidate cacheline的操作没有那么快完成,特别是cache比较繁忙的时候,这时,CPU往往进行密集的loading和storing的操作,而来自其他CPU的,对本CPU local cacheline的操作需要和本CPU的密集的cache操作进行竞争,只要完成了invalidate操作之后,本CPU才会发生invalidate acknowledge。此外,如果短时间内收到大量的invalidate消息,CPU有可能跟不上处理,从而导致其他CPU不断的等待。

However, the CPU need not actually invalidate the cache line before sending the acknowledgement. It could instead queue the invalidate message with the understanding that the message will be processed before the CPU sends any further messages regarding that cache line.

然而,CPU其实不需要完成invalidate操作就可以回送acknowledgement消息,这样,就不会阻止发生invalidate请求的那个CPU进入无聊的等待状态。CPU可以buffer这些invalidate message(放入Invalidate Queues),然后直接回应acknowledgement,表示自己已经收到请求,随后会慢慢处理。当然,再慢也要有一个度,例如对a变量cacheline的invalidate处理必须在该CPU发送任何关于a变量对应cacheline的操作到bus之前完成。

有了Invalidate Queue的CPU,在收到invalidate消息的时候首先把它放入Invalidate Queue,同时立刻回送acknowledge 消息,无需等到该cacheline被真正invalidate之后再回应。当然,如果本CPU想要针对某个cacheline向总线发送invalidate消息的时候,那么CPU必须首先去Invalidate Queue中看看是否有相关的cacheline,如果有,那么不能立刻发送,需要等到Invalidate Queue中的cacheline被处理完之后再发送。

Placing an entry into the invalidate queue is essentially a promise by the CPU to process that entry before transmitting any MESI protocol messages regarding that cache line. As long as the corresponding data structures are not highly contended, the CPU will rarely be inconvenienced by such a promise.

一旦将一个invalidate(例如针对变量a的cacheline)消息放入CPU的Invalidate Queue,实际上该CPU就等于作出这样的承诺:在处理完该invalidate消息之前,不会发送任何相关(即针对变量a的cacheline)的MESI协议消息。只要是对该cacheline的竞争不是那么剧烈,CPU还是对这样的承诺很有信心的

因为多了 store buffer 和 invalidate queue,cache 之间的资料就没有完全一致了

一个小案例

有了上面一连串理论知识的铺垫,下面看一个小例子,这个例子是老演员了,其实也是摘自perfbook中的,在查阅资料过程中发现很多博客都是用的这个图

1
2
3
4
5
6
7
8
9
10
11
12
int a = b = 0;
void foo(void)
{
a = 1;
b = 1;
}

void bar(void)
{
while (b == 0) continue;
assert(a == 1);
}

考虑 CPU 0 执行 foo(), CPU 1 执行 bar(),也就是我们常说的多线程环境,假设 cache 的状态如下:

1
2
3
4
        a       b
------------------------
CPU 0: Shared Modified
CPU 1: Shared Invalid

其实可以理解为假设 a,b 初始值为 0 ,a 被 CPU0 和 CPU1 共同持有,b 被 CPU0 独占

试想,即便在多线程环境下,foo 和 bar 如若严格按照理想的顺序执行,是无论如何都不会出现 assert failed 的情况的。但往往事与愿违,这种看似很诡异的且有一定几率发生的 assert failed ,结合上面所说的 Store Buffer 就一点都不难理解了
我们来还原 assert failed 的整个过程

  1. CPU0 处理 a=1 之前发送 Invalidate 消息给 CPU1 ,并将其放入 Store Buffer ,尚未及时刷入缓存,所以这时候 cache 里a的值仍是 0;
  2. CPU 0 转而处理 b=1 ,注意这里我们上面假设的是此时b 的状态已是 Modified,所以 b=1 直接被刷入缓存;
  3. CPU 1 发出 Read 消息读取 b 的值,CPU 1 从 CPU 0 的 cache 读到 b = 1 ,跳出 while 语句;
  4. CPU 1 发出 Read 消息读取 a 的值,发现 a 却为旧值 0,assert failed,然后收到 CPU 0 送来 “invalidate a” 的讯息,但已太迟了

上面这个还原过程摘自一个台湾人写的博客<從硬體觀點了解 memory barrier 的實作和效果>
个人感觉这个描述过程不完全准确,既然已经有了Invalidate Queue,这个时候cpu1理论上是立刻给cpu0发ack的,可能由于当前要回复的ack很多,导致发送给cpu0的ack并没有达到”立刻”的效果
所以出现上面描述的过程也是有可能的,但是其实还有一种可能,就是读取a的时候最新值Invalidate Queue中,详细在下面的个人理解环节中


个人理解如下
1. 大致流程是CPU0这个时候想要对a进行写值,发现a对应的cacheline对应的状态是S,也就是这里的cpu1上也有a的值,所以需要通知cpu1,通过总线发个消息告知cpu1进行invalid,因为有storebuffer这玩意所以直接放到storebuffer,又因为有invalidate queue的存在
2. 所以CPU1立刻回复了“已更新”的ack回去了,其实并没有实际更新,只是先放在了invalidate queue中待更改标记为invalid,CPU0收到这个ack后将数据回写到内存中
3. 此时CPU0开始了执行下一条对b写值,因为b是M状态也是说是cpu0独占的,所以直接写到缓存就完事了
4. 再来到cpu1这边看看,此时cpu1读取b的值,因为cpu1上没有对应的cacheline,cpu0上b对应的cacheline是M状态,所以此时cpu0会将b的值写回到memory,并且这个时候cpu1读取到的值是最新的和memory一样,此时cpu1和cpu0上b对于的cacheline状态变为S
5. 这个时候再看assert(a == 1); 此时CPU1读取到的数值a仍然是S状态,所以直接读取了,读取出来自然是0,因为此时并没有去invalidate queue看看有没有值,所以看到的值不是最新的,出现assert fail

如何解决这个问题呢?可以在foo函数a=1下面加一个写内存屏障,这样的话当a=1的值放到storebuffer中后,发现后面有一个写内存屏障指令,这个时候就会把后面的写指令都会顺序放到storebuffer中。另外在bar函数第二行读取a的时候需要看下invalidqueue中有没有值,有的话一定要将对应值得cacheline标记为无效,然后去读取最新值,这就引入了读内存屏障,强制标记队列中所有的值对应cacheline为无效

上面的这个程序在实际开发中也是有可能会遇到的,于是 CPU提供了write memory barrier 以及 read memory barrier,让软件有机会避免这个问题

write memory barrier

比如在上面的 foo 方法中,a 的赋值和 b 的赋值之间加上这个write memory barrier
会使得 CPU 在后续变量变更写入之前,把 Store Buffer 的变更写入 flush 到缓存;CPU 要么就等待 flush 完成后写入,要么就把后续的写入变更放到 Store Buffer 中,直到 Store Buffer 数据顺序刷到缓存。
write memory barrier 确保之前在 store buffer 里的资料会先更新到 cache,然后才能写入 barrier 之后的资料到 cache。

假设我们在 foo() 的 a=1 和 b=1 之间插一个 write memory barrier,过程变为

  1. write memory barrier 先设 store buffer 里的资料为 “marked” (即 a=1)
  2. 写入 b 的时候,因为发现 store buffer 里有 marked 的栏位,所以即使 b 已处于 Modified,仍需写入 b=1 到 store buffer,不过状态是 “unmarked”
  3. 待收到 a 的 invalidate ack 后,cache 中 a 的状态改为 Modified,然后先写入有 marked 栏位的值到 cache,再写入 unmarked 栏位的值到 cache。

这样其它 CPU 就会依序看到 a、b 更新的值了

read memory barrier

还是以上面的例子说明,假设 CPU 1 的 cache 里 a 处于 Shared。 CPU 0 已更新 a、b 到它的 cache,CPU 1 的 invalidate queue 里有 “invalidate a”,但还没处理。
这时 CPU 1 依序读 b、a 的值,会从 CPU 0 的 cache 读到 b=1,然后从自己的 cache 读到 a=0 (因为还没 invalidate a)。和上面的写入情况本质一样的,invalidate queue破坏了缓存一致性
invalidate queue是最新的,但是 a 处于 Shared,所以会从cache中直接拿,拿得是0,不是最新的
所以即便在foo函数给a,b分别赋值中间加上写栅栏,还是不能完全保证得到的结果是我们想要的,其实这个时候,可以猜到需要在assert之前也就是读取a之前加上一个读栅栏read memory barrier
目的很明确确保先清空 invalidate queue 再继续读资料。
在 assert(a==1) 之前插入 read memory barrier,执行顺序变成这样:

  1. CPU 1 执行 read memory barrier 时会设 invalidate queue 里的资料为 “marked”
  2. CPU 1 读 cache 里 a 的值时,发现 invalidate queue 里有标记 a,于是会先执行 invalidate a 再继续读 a 的值
  3. 执行 invalidate a 后,就不会读自己 cache 的值,而改从 CPU 0 的 cache 读到最新的值,达到「依序读 b、a 的值」的效果

第二个小案例

再摘一句perfbook的话,说的有点意思

Since the standard synchronization primitives preserve the illusion of ordering, your path of least resistance is to stop reading this section and simply use these primitives. However, if you need to implement the synchronization primitives themselves, or if you are simply interested in understanding how memory ordering and memory barriers work, read on!

你也许面对CPU的这种out of order的行为有本能的抵抗,没有关系,放轻松,你的抵抗之路可以到此结束,只要你愿意使用各种同步原语来保护你程序中的共享资源,因为透过这些标准的同步原语,你看到的是一个顺序执行的世界。当然,这会引入一些小小的遗憾:你不知道底层到底是如何把“乱序”变成“有序”的。不过,实现同步原语的那些软件工程师没有这个豁免权,他们必须要深入理解memory order和memory barrier。此外,那些想要“打破沙锅问到底”以及想要“知其然知其所以然”的工程师也可以跟随我们继续。

再举一个例子,摘自 perfbook memory barrier(14.2章节)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
1 thread0(void)
2 {
3 A = 1;
4 smp_wmb();
5 B = 1;
6 }
7
8 thread1(void)
9 {
10 while (B != 1)
11 continue;
12 barrier();
13 C = 1;
14 }
15
16 thread2(void)
17 {
18 while (C != 1)
19 continue;
20 barrier();
21 assert(A != 0);
22 }

开始,变量A,B,C的初始值都是0。根据程序逻辑:thread0中,A先于B赋值,thread1中,程序逻辑是一直等到B变量被赋值为1之后,再给C赋值。这里,人类的直觉告诉我们,如果变量C已经被赋值为1的时候(第13行程序),A一定已经被赋值为1了。同样的,在thread2中,第21行程序的assert一定是不会被触发的。

This line of reasoning, intuitively obvious though it may be, is completely and utterly incorrect. Please note that this is not a theoretical assertion: actually running this code on real-world weakly-ordered hardware (a 1.5GHz 16-CPU POWER 5 system) resulted in the assertion firing 16 times out of 10 million runs. Clearly, anyone who produces code with explicit memory barriers should do some extreme testing – although a proof of correctness might be helpful, the strongly counter-intuitive nature of the behavior of memory barriers should in turn strongly limit one’s trust in such proofs. The requirement for extreme testing should not be taken lightly, given that a number of dirty hardware-dependent tricks were used to greatly increase the probability of failure in this run.

上一节的推理从直觉上看是对的,但是在实际的CPU上运行的结果确是完全错误的。特别需要指出的是这个结果不是理论推导得出来的,是在真实的1.5GHz 16核的POWER 5系统(该cpu的内存模型属于weakly order)上观测得到的,平均每1千万次执行会有16次在21行代码处出现assert失败。很显然,当我们撰写显式调用memory barrier的代码的时候,必须进行非常大量的实际测试。在理论上进行正确性的推导是否有意义呢?也许有帮助,但是,你知道的,在使用memory barrier的时候会发生很多和你的直觉相悖的东西,这让理论的推导变得不那么确定。别小看那些看起来愚蠢的、非常重复性的大量测试,要知道不同的CPU会使用不同的硬件设计方法,因此在memory order和memory barrier方面表现各不相同,你的程序想要在各种硬件上,每次都运行成功不是一件容易的事情。


个人理解:
到底发生了什么让程序在21行的assert上失败?我们一起分析一下。我们假设CPU0、CPU1和CPU2分别执行thread0、thread1和thread2
1. 对于thread 0,我们假设A在CPU0的local cache中,但是状态是shared,因此当执行A=1的语句的时候,不能立刻执行,需要和其他CPU cache进行沟通(发送invalidate message去其他CPU),当然,cpu不会停下其脚步,将A的新值1放入store buffer,继续执行。
2. smp_wmb可以mark store buffer中A值,并且阻止后续的store操作进入cache,这时候,即便B在CPU0的local cache中,B=1的赋值也不能操作到cache,而是要进入store buffer,当然状态是unmarked。前面说过,后面进cache的话是marked先进然后unmarked进,由于存在Invalidate Queue这中东西,因此,CPU 0很快就可以收到来自其他CPU的响应,这时候,CPU0可以越过write memory barrier,完成对B的赋值。此时A的状态切到M,回写到cache中,B也跟着回写到cache中了。
3. 因此,对于thread1,很快可以感知B的新值“1”并执行了对C变量的赋值。来到thread2,同样的,对C变量的load操作也可以感知到thread1中的赋值因此跳出while循环。
4. 最关键的来了,第20行的barrier这个优化屏障不能阻止CPU对A变量的访问,但是,可能由于这时CPU cache操作非常繁忙,A变量的invalidate message还在其invalidate queue中,因此load A得到了旧的值0。

当然,要修正这个问题非常简单,修改20行代码为smp_rmb即可。一旦执行了smp_rmb,就会mark invalidate queue中的entry,这时候,CPU执行后续的load操作都必须要等到Invalidate queue中的所有缓存的invalidate message(当然,状态必须是marked)被处理并体现到cache中。因此,使用smp_rmb即可以在21行的load A操作中总是获取A的新值“1”从而避免了assert fail。
这里有个疑问就是例子中的barrier();这玩意到底到底代表啥意思,按照作者想要表达的意思是barrier()起不到读屏障的功能,要改为smp_rmb

简要归纳

硬件为了减少读写 memory 而有 cache。有 cache 就要确保 cache 之间的资料一致 (同一时间同一位置只有一个值)。但确保 cache 资料完全一致容易让 CPU 闲置,于是有了 store buffer 和 invalidate queue 降少 CPU 闲置。代价是只保证 CPU 自己会读到自己写入的最新数据,但其它 CPU 不一定。
为了让其它 CPU 有需要的时候也能读到最新的资料,针对 store buffer 和 invalidate queue 的副作用设计了 write/read memory barrier
于是写程序的人在需要的时候可以用 memory barrier 确保关键的数据有依正确的顺序更新 (没保证更新的时间)。 CPU 在多数情况下仍能避免闲置。
到此可以了解为什么这两种操作合在一起比较符合 CPU 架构:

  • 一个 thread 「先 write X 后执行 write memory barrier」
  • 另一个 thread 「先执行 read memory barrier 后 read X」

java内存模型

这里再谈一下java的内存模型,这个模型是抽象出来的,下面这个图网上找的也是老演员了,最初来自深入理解虚拟机一书


个人理解:
这里的java线程对应着cpu,工作内存其实是不存在的,可以简单的理解为是cpu的cache,save和load其实对应的是缓存一致性协议

JVM barrier

  • LoadLoad:两个 Load 操作之间内存屏障,smp_rmb 就是典型实现;
  • StoreStore:两个Store 操作之间的内存屏障,smp_wmb 典型实现;
  • LoadStore:在 Load 操作和 Store 操作之间的内存屏障;
  • StoreLoad:在 Store 操作和 Load 操作之间的内存屏障

个人理解添加
以StoreLoad为例,这个是上面四个中最重的,最耗性能的,storeload其实能涵盖上面三个,因为它既保证了写也保证了读,它和loadstore的侧重点不一样,loadstore对于后面的那个写什么时候能写进去不是非常要求,更侧重的是前面的写。前一个是写后一个是读,后一个读取不能重排到这个写操作之前,也就是load时要看到前面写的值,这也就要保证前一个写的内容如果在storebuffer中就一定要写到cache中.
然后load的时候不能直接去读cache的值,要将invalidqueue中的值处理掉,该标记无效的都要进行标记,确保读取出来的是最新的。

对于java中的volatile防止重排网上博客一大堆,有些文章从汇编角度来分析加了volatile前后的对比,本地测试过hsdis可以用来将java转换为对应的汇编,这里就不展开了

个人理解
volatile最重要的使命是为了可见性,为了达到可见性这个目的不得不设计出防止指令重排,因为如果不限制重排,就达不到可见性这个目的
所以可以理解防止重排只是达到可见性的一个不得已手段


参考文章
Memory Barriers and JVM Concurrency
Linux内核同步机制之(三):memory barrier
從硬體觀點了解 memory barrier 的實作和效果
P0098R0: Towards Implementation and Use ofmemoryorderconsume
LINUX MEMORY ORDERING ON SCORPION-MP AND KRAIT APPLICATION PROCESSORS
Memory Barriers Are Like Source Control Operations
从 Java 内存模型看内部细节
深入理解 java 内存模型
浅谈Cache Memory
Why Memory Barriers

CATALOG
  1. 1. Cache Memory
    1. 1.1. Cacheline
  2. 2. 缓存一致性
    1. 2.1. Store Buffer & Invalidate Queue
    2. 2.2. 一个小案例
    3. 2.3. write memory barrier
    4. 2.4. read memory barrier
    5. 2.5. 第二个小案例
    6. 2.6. 简要归纳
  3. 3. java内存模型
    1. 3.1. JVM barrier