并发原理系列一：MESI与内存屏障

欢迎大家来到IT世界,在知识的湖畔探索吧!

现代的CPU比内存系统快很多，2006年的cpu可以在一纳秒之内执行10条指令，但是需要多个十纳秒去从内存读取一个数据，这里面产生了至少两个数量级的速度差距。在这样的问题下，cpu cache应运而生。

cache处于cpu与内存之间，读写速度比内存快很多，但也比较昂贵。

cache是以cache line为基本单位来进行读写的，cache line的大小是2的幂次，从16字节到256字节不等。

上图就是一个cpu cache的架构示意图，总共有32个cache line，每个cache line是256字节。cacheline的起始地址低8位都是0，使用内存地址的9-12位数据来进行hash。

当cpu在cache里寻找数据时，如果数据不存在，则会产生一个cache miss，这时候cpu需要等待数据从内存读回，这需要耗费很长时间，但是因为读取之后会存储到cache中，所以以后的读取就会变得非常快。为了减少cache miss造成的性能损失，现代的cpu单核可以超线程，一个线程等待的时候，另一个线程就能执行指令了。

为什么会有cache miss，一种是数据预热，机器刚启动的时候，cache是没有数据的，还有一种情况是cache不足，需要淘汰旧的数据。

我们用的最多的缓存一致性协议是MESI，四个字母分别表示modified, exclusive, shared, invalid，这是cache line的四种状态，

modified：数据是被该cpu独占的，其他cpu没有存储该数据。

exclusive：这个状态跟modified很类似，只是该状态下，cache的数据已经同步到主存了，所以即使丢弃也无所谓。

shared：数据存在于多个cpu cache里，每个cpu对该数据只能读，而不能简单地写

invalid：该cache line是空的

Read：read消息会带上cache line的物理内存地址向其他cpu获取数据

Read Response：如果其他cpu有这个cache line，并且处于modified，那么该cpu必须返回该消息，因为其他cpu的cache line和主存都没有最新的数据

Invalidate：invalidate消息会带上cache line的物理内存地址，来让其他cache把相应的数据从cache line里去除掉

Invalidate Acknowledge：如果一个cpu收到Invalidate消息，那么它必须在删除数据之后返回该消息

Read Invalidate：该消息是Read和Invalidate的组合，所以它需要一个Read Response和多个Invalidate Acknowledge

Writeback：modified状态的cache line写到主存，可以用来腾出空间给其他数据

我们现在来看一下MESI各种状态之间的迁移：

a) cpu把cacheline 回写到内存，此时该cpu对这个cacheline还是有独占权

b) cacheline 被cpu修改，该操作不需要cpu之间通信

c) cpu收到read invalidate之后，本地cacheline失效

d) cacheline 被本地cpu修改，需要和其他cpu通信，发出read invalidate 获取最新的数据

e) cacheline 被本地cpu修改，需要向其他cpu发出invalidate请求

f) 其他cpu发来read请求

g) 其他cpu发来read请求

h) cpu意识到它马上要写数据到cacheline，所以提前发出invalidate消息给其他cpu

i) 其他cpu发来read invalidate

j) cpu在写数据之前发出read invalidate消息给其他cpu，之后就处于e状态，该状态很快就可能变成m状态

k) cpu发出read请求

l) 收到invalidate请求

虽然MESI协议能保证读写内存的高性能，但还是有点问题：

当cpu0要写数据到本地cache的时候，如果不是M或者E状态，需要发送一个invalidate消息给cpu1，只有收到cpu1的acknowledgement才能写数据到cache中，在这个过程中cpu0需要等待，这大大影响了性能。一种解决办法是在cpu和cache之间引入store buffer，当发出invalidate之后直接把数据写入store buffer。当收到acknowledgement之后可以把store buffer中的数据写入cache。现在的架构图是这样的：

现在这样的架构引入了复杂性，看下面的例子：

cpu0cache里面有个b，初值为0，cpu1cache有个a，初值为0，现在cpu0运行代码

1 a=1;

2 b=a+1;

3 assert(b==2)

cpu0执行a=1的时候发现本地cache没有a，所以发送read invalidate给cpu1，然后把a=1写入store buffer

cpu1收到read invalidate之后把a传给cpu0并且本地cacheline置为无效

cpu0开始执行b=a+1

cpu0收到cpu1的read response，发现a=0

cpu0执行a+1，得到1赋给b

cpu0执行最后一句，失败

这里关键的问题是cpu会把自己的操作看做是全局的内存操作，但其实操作storebuffer没有操作到主存，所以我们需要在查cache的时候还得查一下store buffer,这种技术叫做store forwarding.

现在的架构是这样的：

上面是store buffer在一个cpu中碰到的问题，在多个cpu并发的过程中也可能存在问题，看下例：

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 }

同样的，cpu0cache里面有个b，初值为0，cpu1cache有个a，初值为0，现在cpu0运行foo, cpu1运行bar

cpu0 发现a不在本地cache，发送read invalidate去cpu1，并在store buffer中把a置为1

cpu1 执行while (b == 0)发现b不在本地内存，发送read消息去cpu0

cpu0 在本地cache置b为1

cpu0收到read消息，把cache中的b传送给cpu1，并把本地状态置为s

cpu1发现b为1，退出循环，因为这时候cpu1本地cache中a还是1，所以失败

cpu1收到read invalidate,把a传输给cpu0，并置本地cache为invalidate但是太晚了

cpu0收到cpu1关于a的read response，把本地的store buffer移到cache中

第一个问题硬件工程署可以解决，但是第二个很难处理，因为硬件无法知道变量之间的依赖关系，硬件工程师设计了memory barrier（内存屏障），软件可以使用这个工具来提示cpu变量之间的关系。新的代码如下：

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 }

内存屏障smp_mb()提示cpu在进行smp_mb之后的存储的时候，会先把store buffer里的数据刷新到cache中。有两种方式，1：cpu会等到store buffer清空之后再处理其他指令，或者2：之后的所有写操作都不写到cache，而是写到store buffer中，直到smp_mb之前的store buffer中的数据刷新到cache中。

上例中的执行效果如下：

cpu0执行 a=1,发现a不在本地cache中，进而把a=1写入store buffer，并发出read invalidate消息给cpu1

cpu1执行while (b == 0)，发现b不在本地cache中，进而发出read消息给cpu0

cpu0执行smp_mb，把store buffer中的a标记一下

cpu0执行b=1 发现状态为独占，所以可以直接写，但是因为store buffer中有标记过的值，所以把b=1写入store buffer，但是不标记

cpu0收到read消息，把cache中b的数据0发给cpu1，并把cacheline置为s

cpu1收到b=0，陷入循环中

cpu0收到read invalidate消息，进而把a=1从store buffer写入cache，这时候可以把store buffer中的b=1写入cache，但是发现这时候cache中的b属于s状态，所以发出invalidate消息给cpu1

cpu1收到invalidate消息之后把b设为1

cpu0收到invalidate ack之后把b的值1写入cache

cpu1要读取b的值，发出read消息给cpu0,

cpu0把b=1发给cpu1

cpu1收到b的值1，退出循环

cpu1发现a无效，发出read消息给cpu0

cpu0把a的值1发送给cpu1，并且把a置为s

cpu1得到a=1，成功

但是内存屏障的处理方法有个问题，那就是store buffer空间是有限的，如果store buffer中的空间被smp_mb之后的存储塞满，cpu还是得等待invalidate消息返回才能继续处理。解决这种问题的思路是让invalidate ack能更早得返回，一种办法是提供一种放置invalidate message的队列，称为invalidate queue. cpu可以在收到invalidate之后马上返回invalidate ack，而不是在把本地cache invalidate之后，并把invalidate message放置到invalide queue，以待之后处理。

但是这种方法会使得我们之前的内存屏障的例子也失效，主要是因为在cpu1收到cpu0关于a的invalidate消息之后直接ack，而没有真正invalidate cache，导致退出循环之后发现a是有效的，执行assert(a==1)失败

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 smp_mb();

12 assert(a == 1);

13 }

在assert之前插入内存屏障，作用是把invalidate queue标记下，在读取下面的数据的时候，譬如a的时候会先把invalidate queue中的消息都处理掉，这里的话会使得a失效而去cpu0获取最新的数据。

进而我们知道smp_mb有两个作用，1，标记store buffer，在处理之后的写请求之前需要把store buffer中的数据apply到cache，2，标记invalidate queue，在加载之后的数据之前把invalidate queue中的消息都处理掉

进而我们再观察上面的例子，我们发现，在foo中我们不需要处理invalidate queue，而在bar中，我们不需要处理store buffer，我们可以使用一种更弱的内存屏障来修改上例让我们程序的性能更高，smp_wmb写屏障，只会标记store buffer，smp_rmb读屏障，只会标记invalidate queue，代码如下：

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);

本文基本是对http://www.puppetmastertrading.com/images/hwViewForSwHackers.pdf的理解与翻译。

MESI缓存一致性协议，能保证缓存和内存数据一致

volatile表示不使用寄存器的值，每次都从内存读（不包括缓存）

dma越过cpu修改内存，会影响MESI

补充MESI：

缓存一致性协议给缓存行（通常为64字节）定义了个状态：独占（exclusive）、共享（share）、修改（modified）、失效（invalid），用来描述该缓存行是否被多处理器共享、是否修改。所以缓存一致性协议也称MESI协议。

协议协作如下：

另外MESI协议为了提高性能，引入了Store Buffe和Invalidate Queues，还是有可能会引起缓存不一致，还会再引入内存屏障来确保一致性

存储缓存(Store Buffe）

也就是常说的写缓存，当处理器修改缓存时，把新值放到存储缓存中，处理器就可以去干别的事了，把剩下的事交给存储缓存。

失效队列（Invalidate Queues）

处理失效的缓存也不是简单的，需要读取主存。并且存储缓存也不是无限大的，那么当存储缓存满的时候，处理器还是要等待失效响应的。为了解决上面两个问题，引进了失效队列（invalidate queue）。处理失效的工作如下：

• 收到失效消息时，放到失效队列中去。
• 为了不让处理器久等失效响应，收到失效消息需要马上回复失效响应。
• 为了不频繁阻塞处理器，不会马上读主存以及设置缓存为invlid，合适的时候再一块处理失效队列。

MESI和CAS关系

在x86架构上，CAS被翻译为”lock cmpxchg…“，当两个core同时执行针对同一地址的CAS指令时,其实他们是在试图修改每个core自己持有的Cache line,

假设两个core都持有相同地址对应cacheline,且各自cacheline 状态为S, 这时如果要想成功修改,就首先需要把S转为E或者M, 则需要向其它core invalidate 这个地址的cacheline,则两个core都会向ring bus发出 invalidate这个操作, 那么在ringbus上就会根据特定的设计协议仲裁是core0,还是core1能赢得这个invalidate, 胜者完成操作, 失败者需要接受结果, invalidate自己对应的cacheline,再读取胜者修改后的值, 回到起点.

对于我们的CAS操作来说, 其实锁并没有消失,只是转嫁到了ring bus的总线仲裁协议中. 而且大量的多核同时针对一个地址的CAS操作会引起反复的互相invalidate 同一cacheline, 造成pingpong效应, 同样会降低性能（参考[9]）。当然如果真的有性能问题，我觉得这可能会在ns级别体现了,一般的应用程序中使用CAS应该不会引起性能问题

个人理解缓存锁就是通过上面的CAS+MESI协议实现的