MESI協(xié)議
翻譯至https://en.wikipedia.org/wiki/MESI_protocol
EMSI是基于緩存無效化的一致性緩存協(xié)議，并且是一種最常見的支持回寫式緩存的協(xié)議。它也被稱為伊利諾伊州協(xié)議（由于其在伊利諾伊大學厄本那香檳分校被開發(fā)）?；貙懯骄彺婧蛯懭胧骄彺嫦啾瓤梢怨?jié)約很多的帶寬。回寫式緩存經(jīng)常會存在臟狀態(tài)，而臟狀態(tài)表明了高數(shù)緩存中的數(shù)據(jù)與主存中的數(shù)據(jù)不一致。EMSI要求當緩存未命中時并且別的緩存中有該數(shù)據(jù)，那么緩存和緩存間應該互相傳輸數(shù)據(jù)。MESI相對與MSI來說降低了與主存的交互次數(shù)，這帶來了顯著的性能提升。
狀態(tài)
MESI的四個字母分別代表了四個可以被標記在緩存行上的獨立狀態(tài)。（也就是用2bit來編碼）
Modified (M)
當緩存行處于Modified狀態(tài)時，它表明該緩存行只存在于當前緩存中。并且這個緩存行中的數(shù)據(jù)是臟數(shù)據(jù)，也就是說這個緩存行中的數(shù)據(jù)與主存中的數(shù)據(jù)不一致。緩存被要求在未來將緩存行的數(shù)據(jù)寫于主存中，但不用立即寫入。但如果別的緩存向該緩存請求這個數(shù)據(jù)，那必須保證該數(shù)據(jù)寫入主存已經(jīng)完成。當回寫回主存完成后，緩存行狀態(tài)會有Modified變?yōu)镾hared狀態(tài)。
Exclusive (E)
當緩存行處于Exclusive狀態(tài)時，它表明該緩存行只存在于當前緩存中，不過其中的數(shù)據(jù)與主存中的數(shù)據(jù)是一致的。當別的緩存向該緩存請求read當前緩存行時，緩存行狀態(tài)會變成Shared?；蛘弋斢衱rite操作時，他會變成Modified狀態(tài)。
Shared (S)
當緩存行處于Shared狀態(tài)時，它表明該緩存行可能同時存在與別的緩存中，并且其中的數(shù)據(jù)與主存中一致。這個緩存行隨時可能被丟棄（改變?yōu)镮nvalid狀態(tài)）。
Invalid (I)
當緩存行處于Invalid 狀態(tài)時，表明該緩存行是無效的。
對于給定的兩個緩存，以下是允許共同存在的狀態(tài):
| M | E | S | I | |
|---|---|---|---|---|
| M | ? | ? | ? | ? |
| E | ? | ? | ? | ? |
| S | ? | ? | ? | ? |
| I | ? | ? | ? | ? |
當一個緩存中的變量被標記為M狀態(tài)，那同樣擁有這個變量的別的緩存的緩存行會被標記為Invalid。
操作
從一個狀態(tài)到另一個狀態(tài)的轉變有兩個重要影響因素。第一個因素是處理器發(fā)出了特殊的讀寫請求。舉個栗子：處理器A的緩存中有變量X，然后這個處理器向自己的緩存發(fā)送了對于這個變量的讀寫請求。第二個影響因素是來自別的處理器的請求，這些處理器緩存中沒有這個變量，或者它們想要更新這個變量。這些總線請求被一個名叫Snoopers的監(jiān)聽器監(jiān)聽著。
下面解釋不同種類的處理器請求和總線請求
處理器請求包括如下兩種：
- PrRd：處理器對緩存中的一個變量發(fā)起讀請求
- PrWr：處理器對緩存中的一個變量發(fā)起寫請求
總線請求包括如下五種：
- BusRd：由一個處理器向另一個處理器發(fā)出的緩存讀請求
- BusRdX：由一個緩存中沒有該變量的處理器向另一個處理器發(fā)送的緩存寫請求
- BusUpgr：由一個緩存中擁有該變量的處理器向另一個處理器發(fā)送的緩存寫請求
- Flush：有一個處理器將變量寫回了主存
- FlushOpt：通知別的處理器修改變量的值（緩存間傳值）
如果從主存中獲取一個值需要等待的時間比通過緩存間傳值等待的時間長，那么我們就可以說緩存間傳值可以降低緩存未命中后的讀延遲。在多核架構下，一致性主要在二級緩存間保持，但處理器仍然有三級緩存，從三級緩存中獲取未命中的變量往往快于從二級緩存。
監(jiān)控操作：
所有緩存中的變量都擁有四種狀態(tài)的有限狀態(tài)機。
對于不同輸入的狀態(tài)轉換關系和回復如下表1.1和1.2
| 初始狀態(tài) | 操作 | 響應 |
|---|---|---|
| Invalid(I) | PrRd | * 向總線發(fā)送BusRd請求 * 別的緩存監(jiān)聽到BusRd請求后檢查自己是否有有效的該變量的緩存塊，并回復發(fā)送請求的緩存 * 狀態(tài)轉換為Shared如果別的緩存有有效的緩存塊 * 狀態(tài)轉換為Exclusive，如果所有的緩存都沒有有效的該緩存塊 *如果別的緩存有有效的緩存塊，它們中的一個會發(fā)送這個值，否者得從主存中獲取 |
| PrWr | * 向總線發(fā)送BusRdX請求 * 發(fā)出請求的緩存狀態(tài)變?yōu)镸odified * 如果別的緩存有這個緩存塊，則發(fā)送值，否者從主存中獲取 * 如果別的緩存有這個緩存塊，并且收到了BusRdX請求則將它們的緩存塊設為Invalid * 將緩存塊的值改為修改值 |
|
| Exclusive(E) | PrRd | * 不發(fā)送任何總線請求 * 狀態(tài)不改變 * 讀緩存命中 |
| PrWr | * 不發(fā)送任何總線請求 * 狀態(tài)變?yōu)镸odified * 寫緩存命中 |
|
| Shared(S) | PrRd | * 不發(fā)送任何總線請求 * 狀態(tài)不改變 * 讀緩存命中 |
| PrWr | * 向總線發(fā)送BusUpgr請求 * 狀態(tài)改為Modified * 別的緩存收到BusUpgr請求后將他們的緩存塊設為Invalid |
|
| Modified(M) | PrRd | * 不發(fā)送任何總線請求 * 狀態(tài)不改變 * 讀緩存命中 |
| PrWr | * 不發(fā)送任何總線請求 * 狀態(tài)不改變 * 寫緩存命中 |
| 初始狀態(tài) | 操作 | 響應 |
|---|---|---|
| Invalid(I) | BusRd | * 無事發(fā)生. |
| BusRdX/BusUpgr | * 無事發(fā)生 | |
| Exclusive(E) | BusRd | * 狀態(tài)轉化為Shared（） * 向總線發(fā)送FlushOpt 請求 |
| BusRdX | * 狀態(tài)轉化為Invalid. * 向總線發(fā)送FlushOpt 請求 |
|
| Shared(S) | BusRd | * 無事發(fā)生 * 可能向總線發(fā)送FlushOpt 請求 (取決與底層設計). |
| BusRdX | * 狀態(tài)轉化為Invalid * 可能向總線發(fā)送FlushOpt 請求 (取決與底層設計) |
|
| Modified(M) | BusRd | * 狀態(tài)轉化為Shared * 向總線發(fā)送FlushOpt，接受者為BusRd的發(fā)送者和主存. |
| BusRdX | * 狀態(tài)轉化為Invalid * 向總線發(fā)送FlushOpt，接受者為BusRd的發(fā)送者和主存. |
只有寫操作發(fā)生在Modified或Exclusive狀態(tài)的緩存行時，才緩存才不需要做額外操作。如果狀態(tài)為Shared的緩存行被寫入，那么首先別的緩存需要無效它們的緩存行。這個由一個叫Request For Ownership (RFO).的廣播操作執(zhí)行。
當一個變量為Modified時，這個緩存必須監(jiān)聽所有別的緩存對于該變量對應主存的讀請求，一旦監(jiān)聽到就必須將這個變量寫入主存。這個過程可以通過強制讓別的緩存等待的方法來完成。當完成了對主存的寫入，狀態(tài)變?yōu)镾hared。但同樣可以直接通知別的緩存這個變量的值，而不寫入主存。
當處于Shared狀態(tài)時，必須監(jiān)聽所有的rfo廣播，一旦收到就讓緩存中的變量無效。
Modified和Exclusive狀態(tài)是精確的，當有緩存行處于這個狀態(tài)就表明，這個變量是這個緩存獨有的。而Shared狀態(tài)時不精確的，當別的緩存丟棄了這個Shared狀態(tài)的緩存行，那么可能只存在一個緩存行狀態(tài)為Shared但它不會變?yōu)镋xclusive。丟棄Shared狀態(tài)行不會引起別的緩存的注意。
使用Exclusive可以帶來性能上的提升，因為修改Exclusive不需要通知別的緩存，而修改Shared狀態(tài)的緩存行需要告訴別的緩存，并使這些緩存行無效，這是耗時的。（這也是EMSI與MSI協(xié)議的區(qū)別）
內存屏障
MESI簡單直接的實現(xiàn)存在著兩個性能問題。1.當向一個Invalid的緩存行寫入時，需要從別的緩存獲取值，這是很耗時的。2.需要將別的緩存行的該值設置為Invalid這也是耗時的。為了解決這兩個問題，我們引入了存儲緩沖區(qū)和無效化隊列。
存儲緩沖區(qū)
當向一個無效的緩存行寫入時會用到儲存緩沖區(qū)。因為這個寫操作最終一定會被執(zhí)行，因此CPU發(fā)送讀無效消息（讓別的緩存中的該緩存行無效）并且將要寫入的值放到存儲緩存區(qū)中，當這個需要的緩存行寫入緩存時，存儲緩存區(qū)中存儲的值將被執(zhí)行寫入。
存儲緩存區(qū)存在帶來的后果是，當一個CPU進行寫操作，值不會立即寫入緩存中。因此，無論何時CPU讀取緩存中的值時，都需要先掃描自己的存儲緩沖區(qū)，確保緩沖區(qū)中是否還有未寫入的值。值得注意的時不同CPU之間存儲緩沖區(qū)時不可見的。
無效化隊列
當CPU收到無效請求時，它會將這寫無效請求放入無效化隊列中。放入隊列中的請求會被迅速執(zhí)行但不是立即執(zhí)行。所以CPU可以忽略它的緩存塊是無效的。CPU不能掃描它的無效隊列，這是和存儲緩沖區(qū)的區(qū)別。
可見存儲緩沖區(qū)帶來的是寫不同步，而無效化隊列則帶來讀不同步，為了解決這些不同步，我們需要內存屏障。寫屏障會刷新我們的存儲緩沖區(qū)，確保里面所有的寫都會被執(zhí)行到這個CPU的cache上，而讀屏障可以保證所有無效化隊列里的任務都被執(zhí)行，確保別的CPU的寫對自己可見。
