cache一致性里的MESI协议

5,718 阅读6分钟

前言

在有多个核的处理器的处理器中,每个核都有自己的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: 窥探器请求指出整个缓存块被发到总线以发送给另外一个处理器(缓存到缓存的复制)

而状态之间的转换如下图:

处理器操作带来的状态转化
初始状态 操作 响应
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关键字有些相似,后续再详细展开了。