CPU有緩存一致性協議MESI，為何還需要Volatile？
前言
- 并發編程從操作系統底層工作的整體認識開始
- 深入理解Java內存模型(JMM)及volatile關鍵字
前面我們從操作系統底層了解了現代計算機結構模型中的CPU指令結構、CPU緩存結構、CPU運行調度以及操作系統內存管理，并且學習了Java內存模型(JMM)和 volatile 關鍵字的一些特性。本篇來深入理解CPU緩存一致性協議(MESI)，最后來討論既然CPU有緩存一致性協議(MESI)，為什么JMM還需要volatile關鍵字?
CPU高速緩存(Cache Memory)
CPU為何要有高速緩存
CPU在摩爾定律的指導下以每18個月翻一番的速度在發展，然而內存和硬盤的發展速度遠遠不及CPU。這就造成了高性能能的內存和硬盤價格及其昂貴。然而CPU的高度運算需要高速的數據。為了解決這個問題，CPU廠商在CPU中內置了少量的高速緩存以解決I\O速度和CPU運算速度之間的不匹配問題。
在CPU訪問存儲設備時，無論是存取數據抑或存取指令，都趨于聚集在一片連續的區域中，這就被稱為局部性原理。
時間局部性(Temporal Locality)：如果一個信息項正在被訪問，那么在近期它很可能還會被再次訪問。
比如循環、遞歸、方法的反復調用等。
空間局部性(Spatial Locality)：如果一個存儲器的位置被引用，那么將來他附近的位置也會被引用。
比如順序執行的代碼、連續創建的兩個對象、數組等。
帶有高速緩存的CPU執行計算的流程
- 程序以及數據被加載到主內存
- 指令和數據被加載到CPU的高速緩存
- CPU執行指令，把結果寫到高速緩存
- 高速緩存中的數據寫回主內存
目前流行的多級緩存結構
由于CPU的運算速度超越了1級緩存的數據I/O能力，CPU廠商又引入了多級的緩存結構。多級緩存結構示意圖如下：
多核CPU多級緩存一致性協議MESI
多核CPU的情況下有多個一級緩存，如果保證緩存內部數據的一致，不讓系統數據混亂。這里就引出了一個一致性的協議MESI。
MESI 協議緩存狀態
MESI 是指4個狀態的首字母。每個 Cache line 有4個狀態，可用2個bit表示，它們分別是：
緩存行(Cache line)：緩存存儲數據的單元
注意：對于M 和 E 狀態而言是精確的，它們在和該緩存行的真正狀態是一致的，而 S 狀態可能是非一致的。
如果一個緩存將處于S狀態的緩存行作廢了，而另一個緩存實際上可能已經獨享了該緩存行，但是該緩存卻不會將緩存行升遷為E狀態，這是因為其他緩存不會廣播它們作廢掉該緩存行的通知，同樣由于緩存并沒有保存該緩存行的copy數量，因此(即使有這種通知)也沒有辦法確定自己是否已經獨享了該緩存行。
從上面的意義來看 E狀態 是一種投機性的優化：如果一個CPU想修改一個處于 S狀態 的緩存行，總線事物需要將所有該緩存行的 copy 變成 invalid 狀態，而修改 E狀態 的緩存不需要使用總線事物。
MESI 狀態轉換
理解該圖的前置說明：
1.觸發事件
1.cache分類
- 前提：所有的cache共同緩存了主內存中的某一條數據。
- 本地cache：指當前cpu的cache。
- 觸發cache：觸發讀寫事件的cache。
- 其他cache：指既除了以上兩種之外的cache。
- 注意：本地的事件觸發 本地cache和觸發cache為相同。
上圖的切換解釋：
下圖示意了，當一個cache line的調整的狀態的時候，另外一個cache line 需要調整的狀態。
舉例子來說：假設 cache 1 中有一個變量 x = 0 的 cache line 處于 S狀態(共享)。 那么其他擁有 x 變量的 cache 2 、cache 3 等 x 的cache line 調整為 S狀態(共享)或者調整為 I狀態(無效)。
多核緩存協同操作
假設有三個CPU A、B、C，對應三個緩存分別是cache a、b、 c。在主內存中定義了x的引用值為0。
單核讀取
那么執行流程是： CPU A 發出了一條指令，從主內存中讀取x。
從主內存通過bus讀取到緩存中(遠端讀取Remote read),這是該 Cache line 修改為 E狀態(獨享).
雙核讀取
那么執行流程是：
- CPU A 發出了一條指令，從主內存中讀取x。
- CPU A 從主內存通過bus讀取到 cache a 中并將該 cache line 設置為 E狀態。
- CPU B 發出了一條指令，從主內存中讀取x。
- CPU B 試圖從主內存中讀取x時，CPU A 檢測到了地址沖突。這時CPU A對相關數據做出響應。此時x 存儲于cache a和cache b中，x在chche a和cache b中都被設置為S狀態(共享)。
修改數據
那么執行流程是：
- CPU A 計算完成后發指令需要修改x.
- CPU A 將x設置為 M狀態(修改)并通知緩存了x的CPU B, CPU B將本地cache b中的x設置為 I狀態(無效)
- CPU A 對x進行賦值。
同步數據
那么執行流程是：
- CPU B 發出了要讀取x的指令。
- CPU B 通知 CPU A，CPU A將修改后的數據同步到主內存時 cache a 修改為 E(獨享)
- CPU A同步CPU B的x，將cache a和同步后cache b中的x設置為 S狀態(共享)。
緩存行偽共享
什么是偽共享?
CPU緩存系統中是以緩存行(cache line)為單位存儲的。目前主流的CPU Cache 的 Cache Line 大小都是64Bytes。在多線程情況下，如果需要修改“共享同一個緩存行的變量”，就會無意中影響彼此的性能，這就是偽共享(False Sharing)。
舉個例子: 現在有2個long 型變量 a 、b，如果有t1在訪問a，t2在訪問b，而a與b剛好在同一個cache line中，此時t1先修改a，將導致b被刷新!
怎么解決偽共享?
Java8中新增了一個注解： @sun.misc.Contended 。加上這個注解的類會自動補齊緩存行，需要注意的是此注解默認是無效的，需要在jvm啟動時設置 -XX:-RestrictContended 才會生效。
- @sun.misc.Contended
- public final static class VolatileLong {
- public volatile long value = 0L;
- //public long p1, p2, p3, p4, p5, p6;
- }
MESI優化和他們引入的問題
緩存的一致性消息傳遞是要時間的，這就使其切換時會產生延遲。當一個緩存被切換狀態時其他緩存收到消息完成各自的切換并且發出回應消息這么一長串的時間中CPU都會等待所有緩存響應完成。可能出現的阻塞都會導致各種各樣的性能問題和穩定性問題。
CPU切換狀態阻塞解決-存儲緩存(Store Bufferes)
比如你需要修改本地緩存中的一條信息，那么你必須將 **I(無效)狀態 **通知到其他擁有該緩存數據的CPU緩存中，并且等待確認。等待確認的過程會阻塞處理器，這會降低處理器的性能。因為這個等待遠遠比一個指令的執行時間長得多。
Store Bufferes
為了避免這種CPU運算能力的浪費，**Store Bufferes** 被引入使用。處理器把它想要寫入到主存的值寫到緩存，然后繼續去處理其他事情。當所有失效確認(Invalidate Acknowledge)都接收到時，數據才會最終被提交。但這么做有兩個風險。
Store Bufferes的風險
- 第一：就是處理器會嘗試從存儲緩存(Store buffer)中讀取值，但它還沒有進行提交。這個的解決方案稱為 Store Forwarding，它使得加載的時候，如果存儲緩存中存在，則進行返回。
- 第二：保存什么時候會完成，這個并沒有任何保證。
- value = 3；
- void exeToCPUA(){
- value = 10;
- isFinsh = true;
- }
- void exeToCPUB(){
- if(isFinsh){
- //value一定等于10？！
- assert value == 10;
- }
- }
試想一下開始執行時，CPU A 保存著 isFinsh 在 E(獨享)狀態，而 value 并沒有保存在它的緩存中。(例如，Invalid)。在這種情況下，value 會比 isFinsh 更遲地拋棄存儲緩存。完全有可能 CPU B 讀取 isFinsh 的值為true，而value的值不等于10。即isFinsh的賦值在value賦值之前。
這種在可識別的行為中發生的變化稱為重排序(reordings)。注意，這不意味著你的指令的位置被惡意(或者好意)地更改。 它只是意味著其他的CPU會讀到跟程序中寫入的順序不一樣的結果。
硬件內存模型
執行失效也不是一個簡單的操作，它需要處理器去處理。另外，存儲緩存(Store Buffers)并不是無窮大的，所以處理器有時需要等待失效確認的返回。這兩個操作都會使得性能大幅降低。為了應付這種情況，引入了失效隊列(invalid queue)。它們的約定如下：
- 對于所有的收到的Invalidate請求，Invalidate Acknowlege消息必須立刻發送
- Invalidate并不真正執行，而是被放在一個特殊的隊列中，在方便的時候才會去執行。
- 處理器不會發送任何消息給所處理的緩存條目，直到它處理Invalidate。
即便是這樣處理器已然不知道什么時候優化是允許的，而什么時候并不允許。
干脆處理器將這個任務丟給了寫代碼的人。這就是內存屏障(Memory Barriers)。
- 寫屏障 Store Memory Barrier(a.k.a. ST, SMB, smp_wmb)是一條告訴處理器在執行這之后的指令之前，應用所有已經在存儲緩存(store buffer)中的保存的指令。
- 讀屏障Load Memory Barrier (a.k.a. LD, RMB, smp_rmb)是一條告訴處理器在執行任何的加載前，先應用所有已經在失效隊列中的失效操作的指令。
- void executedOnCpu0() {
- value = 10;
- //在更新數據之前必須將所有存儲緩存（store buffer）中的指令執行完畢。
- storeMemoryBarrier();
- finished = true;
- }
- void executedOnCpu1() {
- while(!finished);
- //在讀取之前將所有失效隊列中關于該數據的指令執行完畢。
- loadMemoryBarrier();
- assert value == 10;
- }
總結
既然CPU有緩存一致性協議(MESI)，為什么JMM還需要volatile關鍵字?
volatile是java語言層面給出的保證，MSEI協議是多核cpu保證cache一致性的一種方法，中間隔得還很遠，我們可以先來做幾個假設：
1.回到遠古時候，那個時候cpu只有單核，或者是多核但是保證sequence consistency，當然也無所謂有沒有MESI協議了。那這個時候，我們需要java語言層面的volatile的支持嗎?
當然是需要的，因為在語言層面編譯器和虛擬機為了做性能優化，可能會存在指令重排的可能，而volatile給我們提供了一種能力，我們可以告訴編譯器，什么可以重排，什么不可以。
2.那好，假設更進一步，假設java語言層面不會對指令做任何的優化重排，那在多核cpu的場景下，我們還需要volatile關鍵字嗎?
答案仍然是需要的。因為 MESI只是保證了多核cpu的獨占cache之間的一致性，但是cpu的并不是直接把數據寫入L1 cache的，中間還可能有store buffer。有些arm和power架構的cpu還可能有load buffer或者invalid queue等等。因此，有MESI協議遠遠不夠。
3.再接著，讓我們再做一個更大膽的假設。假設cpu中這類store buffer/invalid queue等等都不存在了，cpu是數據是直接寫入cache的，讀取也是直接從cache讀的，那還需要volatile關鍵字嗎?
你猜得沒錯，還需要的。原因就在這個“一致性”上。consistency和coherence都可以被翻譯為一致性，但是MSEI協議這里保證的僅僅coherence而不是consistency。那consistency和cohence有什么區別呢?
下面取自wiki的一段話： Coherence deals with maintaining a global order in which writes to a single location or single variable are seen by all processors. Consistency deals with the ordering of operations to multiple locations with respect to all processors.
因此，MESI協議最多只是保證了對于一個變量，在多個核上的讀寫順序，對于多個變量而言是沒有任何保證的。很遺憾，還是需要volatile～～
4.好的，到了現在這步，我們再來做最后一個假設，假設cpu寫cache都是按照指令順序fifo寫的，那現在可以拋棄volatile了吧?你覺得呢?
那肯定不行啊!因為對于arm和power這個weak consistency的架構的cpu來說，它們只會保證指令之間有比如控制依賴，數據依賴，地址依賴等等依賴關系的指令間提交的先后順序，而對于完全沒有依賴關系的指令，比如x=1;y=2，它們是不會保證執行提交的順序的，除非你使用了volatile，java把volatile編譯成arm和power能夠識別的barrier指令，這個時候才是按順序的。
最后總結，答案就是：還需要～～
參考資料
- [1] http://igoro.com/archive/gallery-of-processor-cache-effects/
- [2] https://en.wikipedia.org/wiki/Sequential_consistency
- [3] https://en.wikipedia.org/wiki/Consistency_model
- [4] Maranget, Luc, Susmit Sarkar, and Peter Sewell. "A tutorial introduction to the ARM and POWER relaxed memory models." Draft available from http://www. cl. cam. ac. uk/~ pes20/ppc-supplemental/test7. pdf (2012).
- [5] https://www.zhihu.com/question/296949412?sort=created
PS：以上代碼提交在 Github ：
https://github.com/Niuh-Study/niuh-juc-final.git
