Cache一致性协议MESI

2020-07-12 约 3480 字预计阅读 7 分钟次阅读

概述

处理器上有一套完整的协议，来保证Cache一致性。比较经典的Cache一致性协议当属MESI协议，奔腾处理器有使用它，很多其他的处理器都是使用它的变种。

单核Cache中每个Cache line有2个标志：dirty和valid标志，它们很好的描述了Cache和Memory(内存)之间的数据关系(数据是否有效，数据是否被修改)，而在多核处理器中，多个核会共享一些数据，MESI协议就包含了描述共享的状态。

概念：多个cpu从主内存读取同一个数据到各自的高速缓存，当其中某个cpu修改了缓存里的数据，该数据会马上同步回主内存，其他cpu通过总线嗅探机制可以感知到数据的变化从而将自己缓存里的数据失效。

总线嗅探：各个cpu监听总线传输情况，各个cpu构成一个队列

在MESI协议中，每个Cache line有4个状态，可用2个bit表示，它们分别是：

状态	描述
M(Modified)	这行数据有效，数据被修改了，和内存中的数据不一致，数据只存在于本Cache中。
E(Exclusive)	这行数据有效，数据和内存中的数据一致，数据只存在于本Cache中。
S(Shared)	这行数据有效，数据和内存中的数据一致，数据存在于很多Cache中。
I(Invalid)	这行数据无效。

MESI状态

M(Modified)和E(Exclusive)状态的Cache line，数据是独有的，不同点在于M状态的数据是dirty的(和内存的不一致)，E状态的数据是clean的(和内存的一致)。

S(Shared)状态的Cache line，数据和其他Core的Cache共享。只有clean的数据才能被多个Cache共享。

I(Invalid)表示这个Cache line无效。

E状态示例如下：

只有Core 0访问变量x，它的Cache line状态为E(Exclusive)。

S状态示例如下：

3个Core都访问变量x，它们对应的Cache line为S(Shared)状态。

M状态和I状态示例如下：

Core 0修改了x的值之后，这个Cache line变成了M(Modified)状态，其他Core对应的Cache line变成了I(Invalid)状态。

状态迁移

在MESI协议中，每个Cache的Cache控制器不仅知道自己的读写操作，而且也监听(snoop)其它Cache的读写操作。每个Cache line所处的状态根据本核和其它核的读写操作在4个状态间进行迁移。

MESI协议状态迁移图如下：

在上图中，Local Read表示本内核读本Cache中的值，Local Write表示本内核写本Cache中的值，Remote Read表示其它内核读其它Cache中的值，Remote Write表示其它内核写其它Cache中的值，箭头表示本Cache line状态的迁移，环形箭头表示状态不变。

当内核需要访问的数据不在本Cache中，而其它Cache有这份数据的备份时，本Cache既可以从内存中导入数据，也可以从其它Cache中导入数据，不同的处理器会有不同的选择。MESI协议为了使自己更加通用，没有定义这些细节，只定义了状态之间的迁移，下面的描述假设本Cache从内存中导入数据。

MESI状态之间的迁移过程如下：

eg

core0 cache line 状态S， core1 cache line状态S,

core0 需要修改cache line值，发出Remote Write信号，此时core0 等待其他core的失效确认(为了解决等待问题引入了Store Bufferes)

core1收到rw信号将自身状态置为I 并发出ack

core0收到后再将值写入cache line，修改自身状态为M

存储缓存和失效队列

MESI协议为了提高性能，引入了Store Buffe和Invalidate Queues，还是有可能会引起缓存不一致，还需要再引入内存屏障来确保一致性(比如java中的volatile)。

此处内存屏障是作用与cpu和cache line之间的存储缓冲区(Store Buffer)

存储缓存(Store Buffe）

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

失效队列（Invalidate Queues）

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

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

MESI失效的情况

数据跨越多个缓存行
系统不支持缓存一致性协议

当MESI失效之后，那么系统会自动将启用总线加锁机制，那么执行效率则会大打折扣。

总线锁定把CPU和内存的通信给锁住了，使得在锁定期间，其他处理器不能操作其他内存地址的数据，从而开销较大，所以后来的CPU都提供了缓存一致性机制

协议演化

AMD的Opteron处理器使用从MESI中演化出的MOESI协议，O(Owned)是MESI中S和M的一个合体，表示本Cache line被修改，和内存中的数据不一致，不过其它的核可以有这份数据的拷贝，状态为S。

Intel的core i7处理器使用从MESI中演化出的MESIF协议，F(Forward)从Share中演化而来，一个Cache line如果是Forward状态，它可以把数据直接传给其它内核的Cache，而Share则不能。

Cache一致性

在 SMP(多处理器) 系统里，每个 CPU 都有自己本地的 Cache。因此，同一个变量，或者同一行 Cache Line，有在多个处理器的本地 Cache 里存在多份拷贝的可能性，因此就存在数据一致性问题。

这里要注意，导致一致性问题的原因有两个，一个是同一个内存引用存放到多处理器各自的cache line；

假设每个组有4个cache line，引用b在core0存放在cache的位置是第3组第1个cache line，引用a在core1也存放在第三组第1个cache line的位置，此时另一个线程运行在core1上，也使用引用b，存放到cache的位置是第三组第2个cache line。

另一个是不同的引用存放到多处理器其中两个或多个相同行的cache line。

只要中间几位相同就可能存放到相同位置的cache line上

通常，处理器都实现了 Cache 一致性 (Cache Coherence）协议。如历史上 x86 曾实现了 MESI 协议以及 MESIF 协议。

假设两个处理器 A 和 B, 都在各自本地 Cache Line 里有同一个变量的拷贝时，此时该 Cache Line 处于 Shared 状态。当处理器 A 在本地修改了变量，除去把本地变量所属的 Cache Line 置为 Modified 状态以外，还必须在另一个处理器 B 读同一个变量前，对该变量所在的 B 处理器本地 Cache Line 发起 Invaidate 操作，标记 B 处理器的那条 Cache Line 为 Invalidate 状态。随后，若处理器 B 在对变量做读写操作时，如果遇到这个标记为 Invalidate 的状态的 Cache Line，即会引发 Cache Miss，从而将内存中最新的数据拷贝到 Cache Line 里，然后处理器 B 再对此 Cache Line 对变量做读写操作。

Cache伪共享

Cache Line 伪共享问题，就是由多个 CPU 上的多个线程同时修改自己的变量引发的。这些变量表面上是不同的变量，但是实际上却存储在同一条 Cache Line 里。

比如第三位到第六位作为set分组，一个cache line大小是8个字节那么000000111000和000000111001的command line位置相同，000000111000和000010111001位置也相同，也就是只要中间分组的那几位相同即可。

在这种情况下，由于 Cache 一致性协议，两个处理器都存储有相同位置的 Cache Line 拷贝的前提下，本地 CPU 变量的修改会导致本地 Cache Line 变成 Modified 状态，然后在其它共享此 Cache Line 的 CPU 上，引发 Cache Line 的 Invaidate 操作，导致 Cache Line 变为 Invalidate 状态，从而使 Cache Line 再次被访问时，发生本地 Cache Miss，从而伤害到应用的性能。在此场景下，多个线程在不同的 CPU 上高频反复访问这种 Cache Line 伪共享的变量，则会因 Cache 颠簸引发严重的性能问题。

下图即为两个线程间的 Cache Line 伪共享问题的示意图，

解决伪共享的案例

disruptor

Disruptor 是英国外汇交易公司 LMAX 开发的一个无锁高性能的线程间消息传递的框架。目前包括 Apache Storm、Camel、Log4j2 等知名项目都是用了 Disruptor；

Disruptor 中的一个很重要的结构 RingBuffer 和 JDK 中的 ArrayBlockingQueue 很相似，其内部都是一个环形数组。

声明指针的代码如下：

1
2
3


public long p1,p2,p3,p4,p5,p6,p7;// cache line padding
private volatile long cursor = INITIAL_CURSOR_VALUE;
public long p8,p9,p10,p11,p12,p13,p14;// cache line padding

可以看到指针独占command line，因此不会出现因cache颠簸引发的性能问题。

jdk7 中的 LinkedTransferQueue 也有采用这种写法。

参考

大话处理器》Cache一致性协议之MESI

Cache Line 伪共享发现与优化

Disruptor 详解一

目录