緩存一緻性協定

現代CPU都是多核心+多級緩存架構，比方說我正在使用的這顆i5 6500，就有4顆實體核心，每顆核心獨享32K(資料)+32K(指令)的一級緩存，獨享256K的二級緩存，4顆核心共享6M的三級緩存

如果我們想要保證工作在不同核心上的線程讀取到的資料都是一緻的，最簡單的做法是保證所有讀寫操作直接在記憶體上發生

如果真的這麼做，會導緻L1/L2/L3全部失效，而且所有讀寫操作全部都會落在記憶體總線上，效率極其低下

下面是一些改進方法

1. 有效位 valid bit

為每個cache line增加一個額外的bit，用于表示這個cache line的狀态：valid/invalid，制定規則如下：

讀：

1. 緩存沒有命中（cache miss或者cache line狀态為invalid），直接從記憶體讀取資料+寫入到cache+标記cache line為valid

2. 緩存命中 && cache line狀态為valid，直接從cache中讀取資料

寫：

1. 向所有cache發送寫信号

2. 如果有cache中有這條資料 && cache line狀态為valid，将這個cache line的狀态改為invalid

3. 将新資料寫入到記憶體與cache，并将相關的cache line标記為valid

驅逐：

直接從cache中删除資料，無視cache line的狀态

優點：減少了從主存中讀取資料的次數

缺點：每次寫操作都要刷回主存

2. MSI Modified-Shared-Invalid

Modified：這條cache line已被修改，其資料與主存中不一緻，被标記為Modified的cache line在被驅逐時，需要把資料刷回到主存中

Shared：這條cache line與主存中的資料是一緻的，并且至少在一個核心中存在，這條cache line的資料在被驅逐時無需做額外操作

Invalid：這塊資料不存在，需要重新從主存中讀取

對應的讀寫規則如下：

1. 如果緩存不命中（cache miss或者cache line狀态為invalid），詢問其他cache是否含有這條資料且狀态為Modified

    a. 如果有，要求其他cache把資料寫回到記憶體 + 目前cache更新資料 + 兩個cache的狀态都被設為Shared。

    b. 如果沒有，直接将資料寫到cache中 + cache line标記為Shared

b. 如果緩存命中（cache line狀态為Modified或者Shared），直接從緩存中讀取資料

1. 如果緩存不命中（cache miss或者cache line狀态為invalid），詢問其他cache是否含有這條資料且狀态為Modified或者Shared

    a. 如果其他cache中有這條資料并且狀态為Modified，要求其他cache把資料寫回記憶體 + 目前cache擷取最新資料并與想要寫入的資料合并 + 目前cache line被标記為Modified + 其他cache line被标記為Invalid

    b. 如果其他cache中有這條資料并且狀态為Shared，那麼要求這些cache将對應的cache line設為Invalid + 目前cache取資料并将對應cache line标記為Modified

    c. 如果其他cache中不含有這條資料（或者含有但是狀态為Invalid），目前cache直接取資料并将對應cache line标記為Modified

2. 如果緩存命中并且cache line的狀态為Modified，直接寫入資料

3. 如果緩存命中并且cache line的狀态為Shared，要求其他cache将這條資料标記為Invalid，向本地cache line寫入資料，并将狀态修改為Modified

如果cache line狀态為Modified，先将資料寫回到記憶體

如果cache line狀态為Shared或者Invalid，直接删除這條cache line就可以了

MSI協定的好處是，不是每一條write操作都需要直接寫到記憶體（如果同一個核心對同一塊記憶體做連續的write操作，那麼這些write操作實際上都是在cache裡進行的）,減少了對記憶體寫入的次數

同時我們又發現一個問題，如果我們想要write某條狀态為Shared的cache line，需要先查詢其他cache上是否也有這條資料，但實際上這條資料可能隻被目前cache所占有。在這種情況下，其實無需做對其他cache的查詢操作。于是我們可以對MSI協定做進一步的改進，再添加一個狀态用于标記某個cache line中的資料是被目前cache獨占的情況。

于是得到了MESI協定

MESI Modified-Exclusive-Shared-Invalid

與MSI協定相比，Invalid不變，Modified有所調整，Shared分裂成了Shared與Exclusive。

Modified：這條cache line隻在目前cache中存在，而且是髒的（與主存中的資料不一緻）。在這條cache line被回寫到記憶體之前，禁止對記憶體中這條資料的read操作。在被回寫到記憶體中之後，這條cache line被标記為Exclusive。

Exclusive：這條cache line隻在目前cache中存在（獨享），這條cache line的資料與主存中一緻。如果這條cache line被其他cache讀取，Exclusive會轉為Shared。如果發生寫入，Exclusive會轉換為Modified

Shared：這條cache line可能在多個cache中存在，這個cache line的資料與主存保持一緻，這條cache line可以随時被轉化為Invalid。

Invalid：标記這條cache line是無用的

1. 如果緩存未命中（cache miss或者cache line狀态為Invalid），查詢其他cache中是否有對應的cache line處于Modified/Exclusive/Shared模式

    a. 如果其他cache中存在處于Modified狀态的cache line，那麼要求這條cache line刷回到主存，再儲存到目前cache中，然後兩條cache line的狀态都設定為Shared

    b. 如果其他cache中存在處于Exclusive或者Shared狀态的cache line，那麼直接把這些cache line複制到目前cache，然後将所有的cache line都設定為Shared狀态

    c. 如果其他cache中不存在Modified/Exclusive/Shared狀态的cache line，那麼從主存中讀取資料寫入到目前cache，并将這條cache line的狀态設定為Exclusive

2. 如果緩存命中（cache line狀态為Modified/Shared/Exclusive），那麼直接從cache中讀取資料

     a. 如果其他cache中存在處于Modified狀态的cache line，那麼要求其他cache中的cache line刷回到主存并修改狀态為Invalid。這些資料會被儲存到目前cache中，然後與寫入的資料合并，目前cache中的cache line的狀态為Modified

    b. 如果其他cache中存在處于Exclusive或者Shared狀态的cache line，那麼其他cache中的cache line都被标記為Invalid狀态，目前cache中的cache line被标記為Modified狀态

    c. 如果其他cache中不存在Modified/Exclusive/Shared狀态的cache line，那麼直接将目前cache中的cache line标記為Modified狀态

2. 如果緩存命中（cache line的狀态為Modified/Exclusive/Shared）

    a. 如果目前cache line的狀态為Modify或者Exclusive狀态，直接向cache line寫入資料，并且将其标記為Modified狀态

    b. 如果目前cache line的狀态為Shared狀态，那麼發起指令，讓其他cache中的Shared狀态的cache line狀态變更為Invalid狀态，然後向目前cache中的cache line寫入資料，并将其标記為Modified狀态

1. 如果cache line狀态為Modified，那麼将資料寫回到主存

2. 如果cache line的狀态為Exclusive/Shared/Invalid，那麼直接将這條cache line抛棄

MESI協定還是比較複雜的，但是它進一步減少了Cache與主存之間的互動操作

比方說在無競争的先讀後寫的場景下（i = i++）

MSI協定：先從主存中讀取i的值，這條cache line被标記為Shared。此時如果我們想要修改i，就需要廣播查詢其他cache中是否含有這條cache line（實際上這條cache line是獨享的，沒有必要做廣播查詢）

MESI協定：先從主存中讀取i的值，這條cache line被标記為Exclusive，此時我們可以确定這條cache line隻在目前cache中存在，是以就可以放心大膽的直接修改i，無需做廣播查詢操作。

參考文獻 

https://zhuanlan.zhihu.com/p/25876351

https://en.wikipedia.org/wiki/MESI_protocol

https://yq.aliyun.com/articles/8061