前言

在有多个核的处理器的处理器中，每个核都有自己的cache，而如何确保多个核的cache内容的一致则是一个很容易遇到的问题，MESI协议就是一个专门用来解决cache一致性的协议。很多处理器使用的都是MESI协议或者MESI协议的变体，而MESI协议其实也是MSI协议的变种。MESI协议采用了回写（write-back）的策略来更新cache，使得其性能进一步提高，但也带来了额外的风险，回写带来的问题可以在编写程序时使用内存屏障来规避。

MESI协议简介

MESI协议名字的由来是由其描述的四个cache状态组成的，分别是M(modified)、E(exclusive)、S(shared)和I(invalid)。各个状态的描述具体如下：

状态 描述
Modified 当前cache的内容有效，数据已被修改而且与内存中的数据不一致，数据只在当前cache里存在
Exclusive 当前cache的内容有效，数据与内存中的数据一致，数据只在当前cache里存在
Shared 当前cache的内容有效，数据与内存中的数据一致，数据在多个cache里存在
Invalid 当前cache无效

状态转移

MESI协议其实是一个状态机，cache的状态会跟根据外部事件的刺激而发生转移，具体的事件分为两类：处理器对cache的请求和总线对cache的请求：

  1. PrRd: 处理器请求读一个缓存块
  2. PrWr: 处理器请求写一个缓存块
  3. BusRd: 窥探器请求指出其他处理器请求读一个缓存块
  4. BusRdX: 窥探器请求指出其他处理器请求写一个该处理器不拥有的缓存块
  5. BusUpgr: 窥探器请求指出其他处理器请求写一个该处理器拥有的缓存块
  6. Flush: 窥探器请求指出请求回写整个缓存到主存
  7. FlushOpt: 窥探器请求指出整个缓存块被发到总线以发送给另外一个处理器（缓存到缓存的复制）

而状态之间的转换如下图： img

处理器操作带来的状态转化
初始状态 操作 响应
Invalid(I) PrRd
  • 给总线发BusRd信号
  • 其他处理器看到BusRd，检查自己是否有有效的数据副本，通知发出请求的缓存
  • 如果其他缓存有有效的副本，状态转换为(S)Shared
  • 如果其他缓存都没有有效的副本，状态转换为(E)Exclusive
  • 如果其他缓存有有效的副本, 其中一个缓存发出数据；否则从主存获得数据
PrWr
  • 给总线发BusRdX信号
  • 状态转换为(M)Modified
  • 如果其他缓存有有效的副本, 其中一个缓存发出数据；否则从主存获得数据
  • 如果其他缓存有有效的副本, 见到BusRdX信号后无效其副本
  • 向缓存块中写入修改后的值
Exclusive(E) PrRd
  • 无总线事务生成
  • 状态保持不变
  • 读操作为缓存命中
PrWr
  • 无总线事务生成
  • 状态转换为(M)Modified
  • 向缓存块中写入修改后的值
Shared(S) PrRd
  • 无总线事务生成
  • 状态保持不变
  • 读操作为缓存命中
PrWr
  • 发出总线事务BusUpgr信号
  • 状态转换为(M)Modified
  • 其他缓存看到BusUpgr总线信号，标记其副本为(I)Invalid.
Modified(M) PrRd
  • 无总线事务生成
  • 状态保持不变
  • 读操作为缓存命中
PrWr
  • 无总线事务生成
  • 状态保持不变
  • 写操作为缓存命中
不同总线操作带来的状态转化
初始状态 操作 响应
Invalid(I) BusRd
  • 状态保持不变，信号忽略
BusRdX/BusUpgr
  • 状态保持不变，信号忽略
Exclusive(E) BusRd
  • 状态变为共享
  • 发出总线FlushOpt信号并发出块的内容
BusRdX
  • 状态变为无效
  • 发出总线FlushOpt信号并发出块的内容
Shared(S) BusRd
  • 状态变为共享
  • 可能发出总线FlushOpt信号并发出块的内容（设计时决定那个共享的缓存发出数据）
BusRdX
  • 状态变为无效
  • 可能发出总线FlushOpt信号并发出块的内容（设计时决定那个共享的缓存发出数据）
Modified(M) BusRd
  • 状态变为共享
  • 发出总线FlushOpt信号并发出块的内容，接收者为最初发出BusRd的缓存与主存控制器（回写主存）
BusRdX
  • 状态变为无效
  • 发出总线FlushOpt信号并发出块的内容，接收者为最初发出BusRd的缓存与主存控制器（回写主存）

内存屏障的引入

MESI的设计比较简单直接，但是其中有两个地方会导致性能下降：一是更新invalidate状态的cache时，需要尝试从其他cpu甚至是内存获取最新的数据；二是使一个cache变为invalidate时需要等待其他cpu的确认；这两个操作都是比较耗时的，如果cpu在这两个过程中一直等待的话，就会形成浪费。

store buffer

为了降低写入invalidate状态的cache的延时，可以引入store buffer。既然写入操作无论如何一定会发生，那么cpu就先发出信号通知其他cpu这个cache已经失效，然后再将本次的写操作更新到store buffer中，等到其他cpu都确认收到信号后再将结果写到内存中。

这样就避免了更新cache时阻塞等待其他cpu确认的耗时，但是也会导致cpu的更新并没有及时写入cache，所以当cpu需要读取cache时，它需要先确认store buffer中是否有所需的数据，这个机制成为store forwarding。值得注意的是，当cpu在读写自己的store buffer时，对应的数据变更其他cpu是感知不到的。

invalidate queue

当cpu收到使某个cache失效的消息时，预期的行为是cpu马上执行这个失效操作。但实际上cpu并不会马上执行失效操作，而是先发送确认收到的消息，然后将失效操作加入到invalidate queue中，queue中的操作随后会在适当的时刻执行（并不一定是马上）。之所以需要invalidate queue同样是因为invalidate操作开销比较大，cpu为了执行invalidate操作必须丢弃cache，导致cache命中率下降。这样的好处是能够提高cpu的性能，但同时也导致cache中可能存在过期的数据。

内存屏障

针对store buffer和invalidate queue这两个优化带来的问题，我们又提供了内存屏障作为解决方案。内存屏障交给了编写程序的人的手里，利用它就可以规避上面提到的问题。

内存屏障分为写屏障和读屏障，编写程序时可以在期望的地方加入内存屏障。写屏障会强制cpu清空store buffer的内容，也就是将所有的变更都写入cache，随后变更也就写入了内存，使其对其他cpu可见；读屏障会强制cpu执行invalidate queue中的所有invalidate操作，使自身的cache内容失效，从而使cpu从内存或者其他cpu中获取最新的cache数据。

其他

MESI协议乍一看和java里的内存模型以及volatile关键字有些相似，后续再详细展开了。