天天看點
傳回

CPU緩存一緻性原了解釋——MESI協定

作者：技術小兵

一些常識

CPU緩存一緻性原了解釋——MESI協定

CPU CL

  • CPU不能直接通路記憶體（write-back記憶體模型，也是主流模型），必須通過L1-L3才能通路到記憶體（具體執行是L3環形總線）;
  • CPU通路記憶體的粒度（write-back模型）——cacheline，是以64位元組為一塊來通路的，跟os中頁的概念類似，為了節約帶寬；（原因參考CPU的時空局部性原了解釋）
  • L3 cache實際上兼有總線的功能——可以用來傳遞資料與消息——叫做環形互聯——MESI——x86_64的緩存一緻性協定就是在這個層面實作；
  • 同一個CL在CPU中會有多分拷貝，不同層與不同核都有多個副本；如圖中C1會存在在L3-L1每層中，而不同核心因為多線程通路也會有副本；但盡管有這麼多副本，他們都代表同一塊虛拟記憶體空間；
  • 這篇文章要讨論的緩存一緻性協定在X86_64構架下叫做MESI協定。

什麼是MESI

  • MESI是4個單詞的縮寫：M-modified（修改的），E-exclusive（獨占的），S-shared（共享的）以及I-invalid（失效的）。
  • 而對于MESI需要了解的頭等大事是：MESI是用來控制CL同步的協定。我們從上圖可以看到，在SMP多核多線程通路共享變量的情況下，同一塊虛拟記憶體位址映射的CL會存在在不同CPU core中，那麼它們的讀寫必然會産生同步問題，就跟進階語言中的多線程同步一樣。 
public class shutDownThread implements Runnable {
    volatile int shutDownRequested;
    volatile int counter;
    public void shutDown(){
        shutDownRequested = true;
    }
    @Override
    public void run() {
        while (!shutDownRequested) {
            System.out.println(counter++);
        }
    }
}


public class Demo01 {
    public static void main(String[] args) throws InterruptedException {
        Thread[] th = new Thread[10];
        shutDownThread t = new shutDownThread();
        for(int i=0;i<=9;i++){
            th[i] = new Thread(t);
            th[i].start();
        }
        Thread.sleep(1000);
        t.shutDown();
    }
}

借用一下這段經典的程式說明下為什麼緩存行存在同步問題：

  1. Thread1将共享變量counter從記憶體加載進入core1核心的C1緩存行；
  2. 然後Thread2也将counter從記憶體加載進入core2核心的C1緩存行；
  3. Thread1對counter加1，然後将C1寫回；此時記憶體中counter為1；
  4. Thread2也對counter加1，接着寫回C1，此時記憶體counter還是1；
  5. 而我們想讓Thread1與Thread2合作，将counter加到2改怎麼做？對，進行同步才行，是以CPU也會有這個同步的問題，事實上隻要是對共享變量有多個計算單元進行操作，都會産生同步問題，JVM的鎖工作在高層，粒度更粗；而CPU的多核同步機制工作在底層，粒度更小而已機制都是一樣的。
  6. 多說一點，上面這段代碼在有MESI的情況下也不能實作線程同步，原因是counter++這條語句看上去隻有一句，但是對于CPU至少有三條： 
mov [counter] eax; //加載counter從記憶體到寄存器（這條mov還會繼續分解成操作CL的微指令）
add 1 eax  //+1
mov eax [counter] //寫回操作

可見counter++在執行的過程中，可能會被打斷（比如時鐘中斷）造成不可能是原子的。這時，你可能會問MESI的作用是啥？

  1. 如果java可以寫彙編，隻要将counter++改成lock inc [counter]就能立馬變成原子操作了，這就是MESI協定在做影響。有興趣的朋友可以試試看（intel x86 cpu哦)
  2. 這裡給個C++的實作，沒有用到C++的任何鎖，但是用彙編調起CPU原子鎖來做同步： 
#include <iostream>
#include <string>
#include <thread>

const int TC = 4;
int count = 0;
bool flag = true;
void inc_count()
{
    asm("movl   $1, %eax");
    asm("LOCK addl %eax,count(%rip)"); //count是個寄存器相對尋址。lock prefix是CPU原子指令。
}
void testRun()
{
    for(int i=0; i<10000;i++)
    {
        inc_count();
    }
}

int main()
{
    std::thread threads[TC]; // 預設構造線程
    for (int i = 0; i < TC; ++i)
    {
        threads[i] = std::thread(testRun); // move-assign threads
    }

    std::this_thread::sleep_for(std::chrono::seconds(1));
    std::cout << "main thread id:" << std::this_thread::get_id() << std::endl;
    flag = false;
    for (auto &thread : threads)
    {
        thread.join();
    }

    std::cout << "All threads joined!"
              << " count:" << count<<std::endl;
}

下面解釋MESI是如何工作的

首先解釋下MESI的含義

Modified（M）：更新狀态

  1. 整個多核系統中最多隻有一個CL的狀态是M；其他的CL副本都是I狀态，此時CL的值跟記憶體的值不相等；
  2. 在變到M之前應該先擷取CL的所有權，也就是先必須到E；這個過程是通過總線嗅探機制完成，類似隊列的監聽，所有core都會通過L3環形總線嗅探來自其他core的同步消息。這個過程簡單來說是個共識的過程，如果其他core都同意本core對CL的修改，就會将自己的狀态變成I，而發起core的狀态變成M；
  3. 當發起core更新CL完畢，此時core會發起write back回寫到記憶體，同時發消息給其他core通知它們拉取最新的CL值。最後都更新完畢後會回到S狀态；
  4. 這裡要注意一個細節，就是write back到記憶體是個漫長的過程，是以采用異步機制回寫，提高性能，具體步驟是：将CL回寫請求發給store buffer然後就算完成了；然後環形總線處理store buffer，回寫到記憶體。

Exclusive(E) 獨占狀态

  1. 跟M狀态一樣，整個SMP core中對于某個CL隻能有一個副本的狀态處于E這個狀态；
  2. 處于E狀态下的CL存儲的值跟記憶體中的值是一樣的；
  3. 處于E狀态的CL是唯一可以轉換成M狀态的狀态；
  4. 如果其他core也發起讀取這個記憶體塊的值請求，則這個CL副本會通過環形總線同步給其他core，此時所有這個CL的副本狀态都變成S；
  5. 如果本地core對CL的資料進行更改，則本地的core的狀态變成M。同時會發送消息給其他的core，通知它們将這個CL的狀态設定成I。

Shared(S) 共享狀态

  1. S狀态下，CL的資料跟記憶體中的一緻；
  2. S狀态說明CL的所有副本都是S狀态，所有CL的資料一緻；

Invalid(I)失效狀态

  1. I狀态CL說明本地CL已經已經失效，不能使用，等待更新完畢的通知。

狀态機

釋出訂閱模式

MESI協定的實作很像一個隊列服務（其實隊列是釋出訂閱異步模型的基礎，不論在網際網路分布式系統中還是作業系統中都占有重要的地位，可以說隻要有異步模型，就必定會有隊列。分布式系統的本質——隊列）。

  1. core釋出的消息（可以簡單了解為core發起讀、寫動作）
  • PrRd讀本地CL
  • PrWr寫本地CL
  • ack回報消息。當收到busRd與busWr的回報消息，可以包含資料。
  1. core訂閱的消息（通過L3總線嗅探機制，其實就是監聽某個其他核心群發的事件消息）
  • busRd其他core釋出的讀請求；
  • busWr其他core釋出的寫請求
  • flush更新完畢消息（獲得修改權的處于M狀态的CL，完成CL更新與完成write-back記憶體更新發送的消息）

轉換場景（簡化版，詳細版本可以參考wiki的解釋）

讀取場景

CPU緩存一緻性原了解釋——MESI協定
  • 如果core發生Cache Miss則會發送busRd消息給其他core，如果其他core有，就發送ack+data的消息完成同步，新的CL狀态設定成S;
  • 如果其他core都沒有這個CL，則CPU從磁盤load進來，設定CL狀态為E。

S E M狀态下的讀取

CPU緩存一緻性原了解釋——MESI協定
  • S與E狀态下記憶體的資料跟CL中一緻，緩存命中，效率很高，什麼消息都不用發；
  • M狀态也不用發同步消息是因為，新的資料本來就在自己的store buffer中了，是以也可以不去"擾民"。

I狀态下的讀取

CPU緩存一緻性原了解釋——MESI協定
  • 如果core讀取I狀态的CL，則一定會發起總線嗅探，發送busRd消息，看看其他core的CL情況；
  • 如果收到ack+data則更新自己的CL，說明M狀态已經flush完畢，自己可以更新本地的CL了，然後設定狀态到S；
  • 如果其他core都ack說自己沒有這個CL，就從記憶體load新的值，變成E狀态。

更新場景

CPU緩存一緻性原了解釋——MESI協定
  • core1要修改CL必須征得其他core的同意，這是同步的關鍵。此時core1會發送busWr總線消息去試圖征得大家的同意；
  • 如果有多個core試圖更新CL，也隻能有一個core最終獲得修改權，也就是進入E獨占狀态;
  • core1必須等到收齊所有其他3個core的ack ok消息以後才能将自己的狀态變到E；
  • 此時core2，core3，core4的CL狀态變成I，也就是CL緩存行失效。此時效果是，如果core2-4還對CL發起PrRd操作，則會pending。
CPU緩存一緻性原了解釋——MESI協定

2. 修改完畢

  • core1收齊所有ack ok的消息後，确定隻有自己可以修改CL，是以馬上發起PrWr的操作，對CL進行修改，此刻CL的狀态變成M；
  • 修改完畢後，發起flush消息到總線，core2-4收到後，更新自己的副本，并将狀态設定為S；
  • 同時core1還會将修改後的CL值同步回記憶體。
  • 這就是寫操作的步驟了。下面看看兩個重要的問題。

Store buffer與Invalidate queues

MESI協定的修改過程有兩個性能瓶頸：

  1. 發生在修改側：修改發起core必須發送busWr來跟其他core進行協同共識，這時發起core必須等到所有的ack消息集齊後才能開始動手修改，這就出現了阻塞；

  2. 發生在接收側：當其他core收到busWr消息後，必須要響應ack。這個過程跟隊列接收消息很類似，如果此刻core還有其他的消息要處理，這個消息隻能排隊，如果積壓比較嚴重，就會pending比較長的時間，發生阻塞。

    [圖檔上傳失敗...(image-ae81c2-1679042340818)]

  • 當出現阻塞要提高響應的性能，通常的做法是用異步代替同步；解決方案是store buffer與invalidate queue；
  • 當core1發出busWr的請求後，将等待->同步->flush的任務都委托給store buffer，自己就可以異步地執行下一條指令了；提高了系統的吞吐量；
  • 當core2接收到busWr後，不會直接到處理引擎，而是先将消息緩存到invalidate queue裡面，緊接着就發送ack給core1，提高吞吐量；此時core2的CL還沒有變成I狀态，但是等invalidate queue處理完成，最終會變成I，中間會有個延遲。

缺點

  • Store buffer：導緻資料實際更新時間比資料更新到記憶體要早；也就是記憶體資料更新出現了延遲；
  • Invalidation queue：core實際感受到資料失效的時間延遲了，也就是資料可見性延遲了。
  • 當然，在大部分時間不會有什麼問題，隻會感覺到系統性能提高了，但是在某些極端情況，比如：多線程，高并發的場景下因為延遲加大，是以就不能忽略了。要修正這個bug又要獲得效率就是大名鼎鼎的——記憶體屏障幹的事了。

總結

  • MESI是緩存行一緻性協定，有了這個協定，多核CPU可以實作核間高速的原子指令與資料共享；
  • 理論上一份記憶體資料隻要load到CPU一次，即可通過MESI協定實作多核資料共享，提高了吞吐量；
  • 緩存行在高并發、高性能程式設計中影響巨大，後面通過單獨章節詳細聊聊緩存行的結構與原理；
  • Store buffer與Invalidate Queues是MESI協定的副作用——導緻記憶體屏障技術出現的根本原因。後面章節會單獨讨論CPU中的原子指令與記憶體屏障。
  • 原子指令是實作高層鎖機制的基礎，它的性能直接影響到了作業系統與使用者程式的性能，在并發激烈或者對性能要求非常苛刻的作業系統中尤其突出。例如著名的spinlock自旋鎖的性能問題，x86就因為MESI協定在core的數量不斷增大的情況下，通過L3環形互聯發送的消息指數增長，而修改單個CL會導緻大量的同步消息釋出到互聯總線，産生了著名的驚群問題，性能也會急劇下降。這直接使得Linux這種非常看重擴充性的作業系統非常不滿，RCU這種真正的無鎖黑科技正式誕生，成為linux一個重要的子系統。後面在講述Linux的同步機制章節詳細展開讨論。

參考

  • 「連結」——MESI又叫做伊利諾伊同步協定
  • 頭條專欄：簡一說道的《高性能程式設計必備計算機硬體知識》

補充

重排序

CPU為了提高執行效率與指令的吞吐量，發明了很多黑科技其中指令重排序就是一個，而指令重排序中有一個就是Store buffer與Invalid queue的副作用導緻的。

  • store buffer會導緻目前的store指令（修改CL的指令）延後執行，相當于這條store指令往後挪了；
  • invalidation queue會導緻讀取到老的值，也就是load指令前移了。
CPU緩存一緻性原了解釋——MESI協定

還有哪些重排序？

  • 分支預測

  • 編譯器重排序

    這裡給我們了一個重要的啟示：任何優化都是雙刃劍，有好的一面就一定有副作用，做工程最重要的工作就是做好平衡，隻要平衡得好就是好的産品，不要什麼都想要，結果一塌糊塗。

    比如：MESI協定因為有了Store buffer與Invalidation Queue加快了速度，但是在大并發的多線程程式下可能出現指令重排序的bug，造成程式狀态紊亂；這時就要開發屏障指令來彌補。但是屏障指令的彌補肯定會抵消掉一部分Store buffer帶來的提升。但是這種平衡是可取的，因為多核多線程的目的就是提高CPU的并行能力，這部分的收益足以承擔屏障指令帶來的損耗，整體來看是個好的設計。

  • 同樣的道理也可以适用于分支預測與編譯器重排序這兩種提高性能的方式。
  • 好了，完畢！
緩存一緻性
上一篇: 資料結構與算法——線性表(1)
下一篇: 資料結構與算法——線性表線性表

繼續閱讀