並發編程二、CPU多級緩存架構與MESI協議的誕生

​前言：

  1. 文章內容：線程與進程、線程生命周期、線程中斷、線程常見問題總結
  2. 本文章內容來源於筆者學習筆記，內容可能與相關書籍內容重合
  3. 偏向於知識核心總結，非零基礎學習文章，可用於知識的體系建立，核心內容複習，如果幫助，十分榮幸
  4. 相關文獻：並發編程實戰、計算機原理

CPU多級緩存架構

要學習多級緩存架構，我們首先要了解一些計算機的小知識

CPU緩存行（CPU Cache Line）:

  • CPU緩存中可分配的最小存儲單元，通常64位元組，緩存行是分段的，一個段對應一塊。
  • CPU看到一條讀取內存的指令時，會把內存地址傳遞給一級數據緩存，一級數據緩存會檢查它是否有對這個內存地址對應的緩存段，如果沒有就把整個緩存段從主存或更高一級的緩存中加載進來。

寄存器：

  • 特點：每個處理器都有自己的寄存器，CPU內部元件，擁有非常高的讀寫速度，寄存器之間數據傳輸非常快
  • 能力：寄存器內的數據可以執行算術及運算邏輯、存於寄存器內的地址可用來尋址，寄存器可以用來讀寫數據到電腦的周邊設備
  • 可見性問題的產生：變量有時候會被放進寄存器中暫時存儲，多個處理器各自運行一個線程時，可能導致某個變量放到寄存器中，會導致各個線程沒法看到其他處理器寄存器里修改過的變量值，這就出現了可見性問題

寫緩衝器：

  • 多個處理器交互時因為都要跟各自的主內存，或者高速緩存進行讀寫操作，而這個讀寫操作可能非常耗時，為了解決這個耗時問題，引入寫緩衝器
  • 一個處理器在寫數據的時候，不直接將數據寫入主內或高速緩存，而是寫入寫緩衝器後直接返回，在特殊場景下才最終寫入主存或高速緩存。寫緩衝器加快處理器在寄存器間的計算交互

 CPU多級緩存架構

　　相關概念：

  • BUS：負責將CPU連到內存，BUS頻率直接影響到CPU與內存數據交換速度。頻率越高CPU與內存之間數據傳輸量越大。所有的內存傳輸都發生在一條共享總線上，所有處理器都能看到這條總線，緩存本身是獨立的，但是內存是共享資源，所有的內存訪問都經過總線。同一個指令周期中，只有一個CPU緩存可以讀寫內存。
  • 高速緩存：介於主存和CPU之間，系統將一些CPU在近幾個時間段經常訪問的數據存入高速緩存，當CPU需要時先在高速緩存中找。

CPU執行計算流程：

  1. 程序及數據被加載到主內存、指令和數據被加載到CPU高速緩存
  2. CPU執行指令，將結果存到高速緩存、高速緩存把數據寫回到主內存

為什麼要高速緩存呢？

  • CPU頻率太快，主存跟不上，CPU常常需要等待主存浪費了資源，利用高速緩存，緩解主存和CPU之間的速度不匹配問題。
  • 高速緩存容量遠小於主存，高速緩存無法包含CPU所需要的所有數據，它存在的意義是局部性原理：
    • 時間局部性：如果某個數據被訪問，在不久的將來可能被再次訪問
    • 空間局部性：如果某個數據被訪問，與它相鄰的數據很快也可能被訪問

高速緩存的結構：

        CPU的高速緩存分為L1、L2、L3三級緩存

  1. L1：第一層高速緩存，容量較小一般在256KB。主要緩存指令和數據，對CPU性能影響十分大
  2. L2：會影響到CPU性能，容量第二大
  3. L3：進一步降低內存的延遲，同時提升海量數據計算時的性能，三級緩存不同於前兩級，它是CPU共享的，容量最大
  4. CPU訪問內存邏輯：如果寄存器有這個數據，CPU 就直接從寄存器取數據即可，如果寄存器沒有這個數據，CPU 就會查詢 L1 ⾼速緩存，如果 L1 沒有，則查詢 L2 ⾼速緩存，L2 還是沒有的話就查詢 L3 ⾼速緩存，L3 依然沒有的話，才去內存中取數據

 MESI

 緩存一致性問題的誕生：

  • 單核CPU多線程：多個線程同時訪問進程中的共享數據，不同線程訪問相同的物理地址都會映射到相同的緩存位置，發生線程切換緩存也不會失效，並且任何時間只能一個線程在執行，也不會出現緩存訪問衝突。
  • 多核CPU多線程：每個核都有自己的多級緩存，多線程訪問進程中某個共享內存，多個線程在不同核心執行，每個核心都在自己的緩存中保留一份共享內存的數據。多核並行的情況下，多個線程可能同時寫各自的緩存，導致同一個數據的緩存內存不一致這就存在緩存一致性問題。
  • 緩存一致性協議MESI：定義了Cache Line的四種狀態，CPU對Cache line的四種操作可能導致不一致的狀態，因此緩存控制器監聽到本地和遠程操作時，會對地址一致的Cache line狀態進行一致性修改，從而保證數據在多個緩存之間保持一致性
  • MESI規定對一個共享變量的讀操作可以多處理器並發執行，對於一個共享變量的寫操作，只有一個處理器可以執行，通過排它鎖機制保證
  • MESI規定一組消息，各個處理器在操作內存數據時，都會往總線發消息，而且各個處理器還會不停從總線嗅探最新的消息，通過這個總線消息傳遞來保證各個處理器的協作。
  • 上面的特性保證了可見性和有序性問題

MESI協議處理cache entry的flag狀態：

  1. invalid：L，無效，當前cache entry無效，裏面數據不可用
  2. shared：S，共享，當前cache entry有效，裏面的數據在各個處理器有各自的副本，副本的值跟主存一致，各個處理器就是並發的在讀
  3. exclusive：E，獨佔，當前處理器對這個數據獨佔，只有它可以有這個副本，其他處理器不能包含這個副本
  4. modified：M，修改過，只能有一個處理器對共享數據更新，所以只有更新數據的處理器的cache entry，才是獨佔狀態，表明當前線程更新了這個數據，這個副本的數據跟主存不一致

下面我們從更底層來分析可見性問題的產生，首先我們來學習下高速緩存的拉鏈散列表結構：

 

 

　　高速緩存的底層結構是拉鏈散列表結構，很多個bucket，每個bucket掛了很多的cache entry。每個cache entry由tag、cache line和flag組成。cache line是緩存的數據，可以包含多個變量的值，tag指向緩存數據在主存中的數據地址，flag標識緩存行的狀態。

那麼CPU操作變量時，如何在高速緩存中進行定位呢？

        處理器在讀寫高速緩存的時候，實際上會根據變量名執行一個內存地址解碼操作，解析出來index，tag和offset

  1. index用於定位到拉鏈散列表中某個bucket
  2. tag用於定位cache entry，指向這個緩存數據在主存中的數據的地址
  3. offset是定位一個變量在cache line中的位置。如果成功定位且flag還標誌有效，則緩存命中。不滿足就是未命中。如果連續未命中，會從主內存重新加載數據到高速緩存中。

了解了這些知識後，我們再來詳細聊一下MESI的工作過程：

  1. 處理器讀取某個變量數據時，首先根據index、tag、offset從高速緩存的拉鏈散列表讀取數據。如果發現狀態是無效，會發送read消息到總線
  2. 接着主內存會返回對應數據給總線，通過read返回值返回給處理器。處理器把數據放到高速緩存，同時cache entry的flag狀態設置為共享
  3. 在處理器對一個數據更新時，如果數據狀態是共享，就需要發送一個invalidate消息到總線，嘗試讓其他處理器的高速緩存的cache entry全部變無效，已獲得數據的獨佔鎖
  4. 其他處理器會從總線嗅探到invalidate消息，此時把自己的cache entry設置為無效，即過期掉自己的本地緩存，然後返回ack消息給總線，傳遞迴更新數據的處理器，必須收到所有處理器返回的ack
  5. 然後處理器就會將自己的cache entry設置為獨佔，在獨佔期間其他處理器不能修改數據，因為處理器此時發出invalidate消息，這個處理器是不會返回ack的，除非他先修改完了。
  6. 接着處理器修改這個數據，將數據設置為修改過，也可能是把數據強制寫回主存。
  7. 然後其他處理器看到這個數據狀態都是無效了，如果要讀，全部需要重新發read消息，從主存或其他處理器來加載，看具體底層硬件實現。
  8. 這套機制就是緩存一致性在硬件緩存模型下的完整執行原理，解決存在的可見性和有序性問題，但是存在串行的性能問題

        串行化問題：每次寫數據都要發送invalidate消息並等待所有處理器ack，獲取到獨佔鎖才能寫數據。會導致性能很差，對於共享變量的寫操作，在硬件級別變成串行。因此在硬件層面引入寫緩衝器和無效隊列。

寫緩衝器和無效隊列：

  • 寫緩衝器
  1. 作用是處理器寫數據，直接把數據寫入緩衝器，同時發送invalidate消息，就認為寫完成了。
  2. 然後處理器之後收到其他處理器的ack，會把寫緩衝器中的寫結果拿出來，通過對cache entry設置為獨佔，同時修改數據，設置為修改過，獨佔這條數據的讀寫操作
  3. 寫緩衝器通過不同步阻塞等待ack，提升硬件層面執行效率。查詢數據時，會先從緩衝器查，因為有可能剛修改的值在這裡，然後才會走高速緩存。通過存儲轉發，同樣提升了效率
  • 無效隊列：其他處理器收到invalidate消息，不需要立馬過期本地緩存，直接把消息放入無效隊列，然後返回ack給寫處理器，加速性能。然後從無效隊列中取出消息，過期本地緩存
  •  通過這兩個方式解決串行化效率問題。但是寫緩衝器和無效隊列的數據不能立馬回刷高速緩存的話，會導致可見性問題。

寫緩衝器和無效隊列導致的可見性問題：

        由於寫緩衝器和無效隊列，可能導致寫數據時不一定立馬寫入高速緩存或主存，因為可能寫入了寫緩衝器。讀數據不一定立馬從別人的高速緩存或主存刷新最新值，invalidate消息在無效隊列里，有可能獲取到的值還是高速緩存或主存的舊值

寫緩衝器和無效隊列導致的有序性問題：

  • Store Load重排序
a = 1; int b = c;
  1. a=1是store，b=c是load。可能處理器對store操作先寫入寫緩衝器，此時這個寫操作就相當於沒有執行。然後就load操作了。這就導致第二行代碼的load先執行了，第一行代碼的store後執行。
  2. 第一個store操作寫到寫緩衝器，導致其他線程讀不到看不到。代表第二個load操作成功的執行StoreLoad重排，常見的有store先執行，load後執行，load先執行，store後執行。
  • Store Store重排序
resoure = loadResource(); loaded = true;

　　兩個寫操作，如果第一個寫到寫緩衝器，第二個直接修改的高速緩存，就會導致兩個寫操作的重排序。

        有序性問題就是如此，會因為MESI的機制而發生。可見性也是如此，寫入寫緩衝器後，沒有刷入高速緩存，就導致別人讀不到；讀數據時候，可能invalidate消息在無效隊列里，導致沒發立馬感知到過期的緩存，立馬加載到最新數據。

引入內存屏障，解決硬件級別的可見性和有序性問題：

  • Store+Load解決可見性問題：
  1. Store屏障：該屏障強制性要求對一個寫操作必須阻塞等待其他處理器返回invalidate ack後，對數據加鎖，然後修改數據到高速緩存中，必須在寫數據後強制執行flush操作。
  2. flush處理器緩存：把自己更像的值刷新到高速緩存或主存。因為必須要刷新後才有可能通過一些特殊機制讓其他處理器從自己的高速緩存或主存讀取到最新的值。
  3. Load屏障：在從高速緩存中讀取數據時，如果發現無效隊列里有一個invalidate消息，會立馬強制根據那個invalidate消息把自己本地高速緩存的數據，設置為無效，然後強制從其他處理器的高速緩存中加載最新值。這就是refresh操作。解決本地讀操作對自己處理器數據過期的可見性問題
  4. refresh處理器緩存：除了flush外，還會發送一個消息到總線，通知其他處理器，某個變量值被他修改。refresh表示處理器中的線程在讀取一個變量值時，如果發現其他處理器的線程更新了變量的值，必須從其他處理器的高速緩存或主存，讀取這個最新的值，更新到自己的高速緩存。
  5. 可見性保障底層是通過MESI協議、flush處理器緩存、refresh處理器緩存實現。
  6. flush是強制刷新數據到高速緩存或主存，不要僅僅停留在寫緩衝器裏面。refresh是從總線嗅探發現某個變量被修改，必須強制從其他必須從其他處理器的高速緩存或主存，讀取這個最新的值，更新到自己的高速緩存。
  • Acquire+Release解決有序性問題：
  1. Acquire屏障：即StoreStore屏障，會強制讓寫操作全部按照順序寫入寫緩衝器，不會讓兩個寫操作一個寫到寫緩衝器，另一個直接修改高速緩存。
  2. Release屏障：即StoreLoad屏障，會強制先將寫緩衝器的數據寫入高速緩存，接着讀數據時強行清空無效隊列，對裏面的validate消息全部過期掉高速緩存中的條目，然後強制從主存重新加載數據。

內存模型  

作用：

        保障共享內存的正確性（三特性），其定義了共享內存系統中多線程程序讀寫操作的規範。主要採用限制處理器優化（通過優化屏障避免編譯器的重排序優化操作）和使用內存屏障（通過讀寫屏障強制限制內存訪問順序）。

JAVA內存模型（JMM）：

  1. 符合內存模型規範，屏蔽了各種硬件和操作系統訪問差異，保證java程序在各種平台下對內存的訪問都能保證效果一致的機制及規範
  2. 該模型規定所有變量都存儲在主內存中，每個線程有自己的工作內存，保存了該線程用到的變量在主內存中的副本拷貝。線程對變量的操作都必須在自己的工作內存中進行不能直接讀寫主內存，不同線程之間工作內存不能直接訪問，線程間變量的傳遞需要在自己工作內存和主內存直接進行數據同步。
  3. 在JMM中，數據用read從主存讀取數據，用load將數據加入工作內存，user將工作內存數據讀出並計算，assign將計算好的數據賦值到工作內存，store將工作內存數據寫入主內存，write將寫入store過去的變量賦值給主內存中順序不能打亂，保證使用變量前一定是從主存拿的新值、assign、write順序不能打斷，保證賦值後馬上寫入主內存。 因此在use前插入讀屏障，從主存拿最新值，讓工作內存中數據失效。在assign之後插入寫屏障，保證寫入工作內存的最新數據更新到主內存被其他線程可見。

Happens-before(先行發生原則)：

  1. 程序順序性規則：在一個線程中，按代碼順序，前面的操作先行發生於後續的任意操作
  2. volatile變量規則：對一個volatile變量的寫操作先行發生於後面對這個變量的讀操作
  3. 傳遞性：如果A先行發生於B且B先行發生於C，那A先行發生於C
  4. 鎖的規則：一個鎖的解鎖操作先行發生於後續對這個鎖的加鎖
  5. 線程啟動規則：Thread對象的start()方法先行發生於此線程的每一個動作，在主線程執行過程中，啟動子線程，那麼主線程在啟動子線程之前對共享變量的修改結果對子線程可見。
  6. 線程join()規則：在主線程執行過程中，子線程終止，那麼子線程在終止之前對共享變量的修改結果在主線程中可見（join方法）
  7. 線程中斷規則：對線程interrupt()方法的調用先行發生於被中斷線程的代碼檢測到中斷事件的發生，可以通過Thread.interrupted()方法檢測到是否有中斷髮生。
  8. 對象終結規則：一個對象的初始化完成(構造函數執行結束)先行發生於它的finalize()方法的開始。

​

Tags:

VirMach 便宜 VPS

QNews

QNews