缓存一致性与MESI协议

对 于cpu来说，直接访问内存是比较耗时的，为了提高访问性能，现代计算机在cpu模块都加上了缓存（一般有3级缓存），cpu访问缓存的速度比直接访问内存的速度提高了很多。cpu在计算时会先从缓存中查找数据，如果在缓存中没有找到（缓存未命中），则从内存中查找并加载到缓存中，然后再把数据从缓存加载到寄存器中进行计算。

在多核cpu的计算机中，缓存在提高了cpu访问速度的同时，也带来了相应的问题：

在上左图中，由于cpu1和cpu2都保存着同一缓存行x的拷贝，如果cpu1将x修改为1，则cpu1缓存中的x与cpu2缓存中的x，以及内存中的x的值是不一致的，这就是缓存一致性问题。接下来cpu2如果读取x，则读取的依然是x的旧值0（正确的情况下cpu读取的x应为新值1）。

在上右图中，由于可能发生cpu1和cpu2同时对x进行修改，这又会产生写顺序问题。如果cpu1和cpu2同时对x加1，最后都将值回写到了内存，则内存的值为1（正确的情况下x应为2），也就是说其中一个cpu对x加1这个计算是无效的。

针对以上2个问题，可以提出2个一致性要求来解决：1.cpu的读操作必须能读到修改后的新值；2.cpu对同一缓存行的写操作不能同时发生。第1点保证了数据的一致性，第2点保证了写数据的顺序性。

^{有2种缓存的写策略可以满足以上一致性要求°?写无效策略可以同时满足以上2点，写更新策略是否可以满足第2点要求待证实}，从而解决一致性问题。

• 写无效：任一cpu在写某个数据时，会使其他cpu的缓存中的拷贝失效。在这种策略下，cpu写数据前，会先通过总线使其他缓存中拷贝失效，这就相当于取得了该数据的唯一访问权，因此接下来写数据就不会导致一致性问题。而其他cpu要读该数据时，由于该数据已失效，就必须先从其他缓存或内存中获得最新的值。
• 写更新：任一cpu在写数据时，会通过总线广播使其他缓存中的拷贝进行更新。

由于写无效策略在性能上优于写更新策略，如对同一数据多个写而中间无读的情况，写更新需要多次写广播操作，而在写无效协议下只需一次写无效操作，因此，在基于总线的多核计算机中，写无效策略成为大多数系统设计的选择。

上述的2种缓存写策略解决了导致缓存一致性的核心问题，但是还不够，若要完整的解决一致性问题，势必需要更加完整的方案，它们是：目录协议和监听协议。本文主要讲解监听协议。

监听协议使用共享总线连接多个cpu的私有缓存和内存，共享总线保证所有处理器内核的数据请求串行执行。任何处理器发出的数据请求将被广播到所有的cpu缓存控制器，所有cpu的缓存控制器都时刻监视着总线。如果收到读请求，数据所有者将把有效数据返回给发出此请求的cpu；如果收到写请求，拥有有效副本的cpu便无效或更新本cpu上的数据，数据所有者将把有效数据返回到发出此请求的cpu。数据所有者可能是cpu，也可能是内存。

如下图所示情景，cpu1发生写数据前，会把写请求广播到总线，此时cpu2的缓存控制器监听到此总线请求便会将x置为无效并给总线广播回复信号，cpu1收到回复信号确认其他cpu已将x的拷贝全部置为无效后，才会修改x。（如果cpu1，cpu2同时修改x，则必然其中一个cpu先获取总线控制权，之后它使cpu2的缓存上的拷贝失效。）接下来如果cpu2读取x，因为x是无效的状态，所以会向总线广播读请求，cpu1监听到该总线请求后会把x的内容通过总线传给cpu2的缓存。

概述

MESI协议是MSI的拓展协议，它是采用^{写回°@“写回”是一种规定了缓存在被修改后何时刷新至内存的策略，它规定仅当一个缓存块需要被替换回内存时，才将其内容写入内存。这意味着在缓存中被修改的数据可能不会被及时地写回内存。另外的一种策略为“写通”策略，它规定每当缓存接收到写数据指令，都直接将数据写回到内存，这种刷新内存的策略保证了被修改的缓存行能立即刷新至内存。}和写无效策略的监听协议，被广泛用于维护缓存一致性。MESI指的是缓存行4个状态的首字母。

MESI协议包含的4个状态

这些一致性状态通过高速缓存和内存之间的通信进行维护。 当缓存中的某行被读或写时，或者当缓存通过总线接收到其他缓存发出的读写信号时，它需要据此来做出动作并调整自己的状态。

当缓存收到cpu的读请求时，如果一个缓存行处于“M”或“S”状态，则它会直接提供数据。但如果缓存行尚未被加载到缓存(处于“I”状态)，则在加载该缓存行之前，cpu中的缓存控制器会向总线广播这个读请求，在收到这个广播后，其他缓存中处于"E"状态的拷贝直接修改为“S"状态就可以了；而处于“M”状态的拷贝，则会将数据地址广播到总线，以供读请求的cpu拿到新数据，并且写回内存，在提供数据后，该拷贝修改为“S”状态。

当缓存收到cpu的写请求时，如果这缓存行处于"M"状态，则缓存只需要修改本地的数据。 如果缓存行处于"S"状态，则必须先将其他缓存中的拷贝置为“I”状态后，在修改本地的数据。 如果缓存行处于"I"状态，则其他处于”S"状态的拷贝只需将拷贝置为“I”状态；如果有一个拷贝处于"M"状态，那么它必须先将数据通过总线提供给请求数据的缓存，并写回内存，然后将拷贝置为“I”状态。如果此时缓存尚未装载该缓存行的数据，则修改前要先将其从内存中读取。在数据被修改之后，缓存行处于"M"的状态。

对于任何给定的两个缓存，如果他们具有对应相同地址的缓存行，则允许的状态如下表所示：

状态转换

MESI协议可以看作是一个^{有限状态机°@有限状态机（英语：finite-state machine，缩写：FSM）又称有限状态自动机（英语：finite-state automation，缩写：FSA），简称状态机，是表示有限个状态以及在这些状态之间的转移和动作等行为的数学计算模型。}，它的4种状态转换来自两种场景：缓存所在处理器的读写，这种情景下处理器会向缓存发送读写请求；其他处理器的读写，这种情景下可能产生其他处理器向总线发送总线请求。

处理器向高速缓存发出的请求包括：

• PrRd：处理器请求读取一个缓存块。
• PrWr：处理器请求改写一个缓存块。

此外，还有总线方面的请求。 包括：

• BusRd：当某个处理器的高速缓存的读操作出现未命中，它会向总线发送一个BusRd请求，并预期能够收到该缓存行的数据。
• BusRdX：当某个处理器的高速缓存的写操作出现未命中，它会向总线发送一个BusRdX请求，预期能够收到该缓存行的数据，并且使其他处理器中对应相同地址的缓存行无效。
• BusUpgr：当某个处理器的高速缓存的写操作命中时，它它会向总线发送一个BusUpgr，使其他处理器中对应相同地址的缓存行无效。
• Flush：该请求表明一个缓存行正在被写回内存。

状态转移图

举例说明

下面举个例子，来说明在MESI协议下，各个cpu是如何协同工作以保证缓存一致性的。

1.cpu1读取x（x的初始值为0）
• cpu1向缓存发出PrRd请求
• 由于读未命中（缓存C1尚未装载x，x的状态为I），cpu1的缓存控制器向总线广播BusRd请求
• 由于C2未装载x（x的x状态是I），所以会忽略掉总线请求（这种情况称为监听未命中），C1未收到其他cpu的回复信号，从内存中装载x，并将x状态设置为E

2.cpu2读取x
• cpu2向缓存发出PrRd请求
• 由于读未命中（C2尚未装载x，x的状态为I），cpu2的缓存控制器向总线广播BusRd请求
• cpu1的缓存控制器监听到总线请求（这种情况称为监听命中），将x的地址广播到总线上（用于将值传给C2），然后将x状态设置为S
• C2装载x，并将x的状态设置为S

3.cpu1修改x为1
• cpu1向缓存发出PrWr请求
• 由于写命中，cpu1的缓存控制器向总线广播BusUpgr请求，并将x的状态设置为M
• cpu2的缓存控制器监听到总线请求，将C2中的x的状态设置为I，并向总线广播回复信号
• cpu1收到回复信号，确认其他缓存将x的拷贝都已置为无效后，修改x

4.cpu2再次读取x
• cpu2向缓存发出PrRd请求
• 由于读未命中（C2中的x状态为I），cpu2的缓存控制器向总线广播BusRd请求
• cpu1的缓存控制器监听到总线请求，会暂时取得总线控制权，向总线广播FlushOpt请求并发出x的值（用于将x回写到内存和传给C2），然后将x的状态设置为S
• cpu2的缓存控制器再次取得总线控制权后，获得x的值（1），并将x的状态设置为S