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)）