MESI协议

MESI协议是一个基于失效的缓存一致性协议，是支持写回（write-back）缓存的最常用协议。也称作伊利诺伊协议 (Illinois protocol，因为是在伊利诺伊大学厄巴纳-香槟分校被发明的^[1])。与写直达（write through）缓存相比，回写缓冲能节约大量带宽。总是有“脏”（dirty）状态表示缓存中的数据与主存中不同。MESI协议要求在缓存不命中（miss）且数据块在另一个缓存时，允许缓存到缓存的数据复制。与MSI协议相比，MESI协议减少了主存的事务数量。这极大改善了性能。^[2]

状态

缓存行有4种不同的状态:

已修改Modified (M)

缓存行是脏的（dirty），与主存的值不同。如果别的CPU内核要读主存这块数据，该缓存行必须回写到主存，状态变为共享(S).

独占Exclusive (E)

缓存行只在当前缓存中，但是干净的（clean）--缓存数据同于主存数据。当别的缓存读取它时，状态变为共享；当前写数据时，变为已修改状态。

共享Shared (S)

缓存行也存在于其它缓存中且是干净的。缓存行可以在任意时刻抛弃。

无效Invalid (I)

缓存行是无效的

任意一对缓存，对应缓存行的相容关系:

	M	E	S	I
M
E
S
I

当块标记为 M (已修改), 在其他缓存中的数据副本被标记为I(无效).

操作

 

图 1.1 MESI协议的状态图 红色: 总线初始化事务； 蓝色: 处理器初始化事务^[3]

有限状态自动机的状态转换结束两种场景：缓存所在处理器的读写；其他处理器的读写。总线请求被总线窥探器（英语：Bus snooping）监视。^[4]

处理器对缓存的请求:

1. PrRd: 处理器请求读一个缓存块
2. PrWr: 处理器请求写一个缓存块

总线对缓存的请求:

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

解释

图1.1是MESI协议四种状态的转换图。

表1.1 处理器操作带来的状态转化

初始状态	操作	响应
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	无总线事务生成 状态保持不变 写操作为缓存命中

表1.2 不同总线操作带来的状态转化

初始状态	操作	响应
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的缓存与主存控制器（回写主存）

写操作仅在缓存行是已修改或独占状态时可自由执行。如果在共享状态，其他缓存都要先把该缓存行置为无效，这种广播操作称作Request For Ownership (RFO).

缓存对已修改状态的缓存行，要监听各处理器对其的读请求并插入其数据到总线。

缓存对共享状态的缓存行，要监听使其无效或请求拥有的广播，当匹配时把该缓存行置为无效。

已修改状态、独占状态是精确的，匹配于该缓存行在系统中的实际情况。共享状态可以是不精确的: 如果别的缓存抛弃了该行，只有当前缓存拥有该行，但其状态没有变为独占。其他缓存不需要广播通知其抛弃操作。

独占状态是一个优化机会：处理器修改共享状态的缓存行必须要先发出一个总线事务使得其他缓存中的该行失效；而独占状态下修改一行不需要总线事务。

MESI协议操作图解^[5]

假定下述读/写操作访问同一主存位置的数据。操作流是 : R1, W1, R3, W3, R1, R3, R2. 最初所有缓存为空。

表 1.3 MESI工作举例 所有操作引用同一缓存行 (例如: "R3" 值处理器3的读操作)

	本地 请求	P1	P2	P3	产生的 总线请求	数据提供者
0	最初	-	-	-	-	-
1	R1	E	-	-	BusRd	Mem
2	W1	M	-	-	-	-
3	R3	S	-	S	BusRd	P1's Cache
4	W3	I	-	M	BusUpgr	-
5	R1	S	-	S	BusRd	P3's Cache
6	R3	S	-	S	-	-
7	R2	S	S	S	BusRd	P1/P3's Cache

参见

• MOSI协议（英语：MOSI protocol）
• MOESI协议（英语：MOESI protocol）
• MESIF协议（英语：MESIF protocol）
• MERSI协议（英语：MERSI protocol）
• Dragon协议
• 萤火虫协议（英语：Firefly (cache coherence protocol)）

参考文献

1. Papamarcos, M. S.; Patel, J. H. A low-overhead coherence solution for multiprocessors with private cache memories. Proceedings of the 11th annual international symposium on Computer architecture - ISCA '84 (PDF). 1984: 348 [2013-03-19]. ISBN 0818605383. doi:10.1145/800015.808204. （原始内容 (PDF)于2012-12-24）. 
2. MESI Cache Coherence Simulator for Teaching Purposes. CLEI ELECTRONIC JOURNAL. 
3. Culler, David. Parallel Computer Architecture. Morgan Kaufmann Publishers. 1997: Figure 5–15 State transition diagram for the Illinois MESI protocol. Pg 286. 
4. Bigelow, Narasiman, Suleman. An evaluation of Snoopy Based Cache Coherence protocols (PDF). ECE Department, University of Texas at Austin. （原始内容 (PDF)于2020-05-18）. 
5. Solihin, Yan. Fundamentals of Parallel Multicore Architecture. Raleigh, North Carolina: Solihin Publishing and Consulting, LLC. 2015-10-09. ISBN 978-1-4822-1118-4. 

外部链接

• An interactive MESI simulation （页面存档备份，存于互联网档案馆）
• An open source MESI controller (Verilog) （页面存档备份，存于互联网档案馆）