1、CPU高速緩存（CacheMemory）
1.1、CPU為何要有高速緩存
CPU在摩爾定律的指導下以每18個月翻一番的速度在發展，然而記憶體和硬碟的發展速度遠遠不及CPU。這就造成了高性能能的記憶體和硬碟價格極其昂貴。然而CPU的高度運算需要高速的資料。為了解決這個問題，CPU廠商在CPU中内置了少量的高速緩存以解決I\O速度和CPU運算速度之間的不比對問題。
在CPU通路儲存設備時，無論是存取資料抑或存取指令，都趨于聚集在一片連續的區域中，這就被稱為局部性原理。
時間局部性（Temporal Locality）：如果一個資訊項正在被通路，那麼在近期它很可能還會被再次通路。比如循環、遞歸、方法的反複調用等。
空間局部性（Spatial Locality）：如果一個存儲器的位置被引用，那麼将來他附近的位置也會被引用。比如順序執行的代碼、連續建立的兩個對象、數組等。
1.2、帶有高速緩存的CPU執行計算的流程
流程如下：
- 程式以及資料被加載到主記憶體
- 指令和資料被加載到CPU的高速緩存
- CPU執行指令，把結果寫到高速緩存
- 高速緩存中的資料寫回主記憶體
目前流行的多級緩存結構
由于CPU的運算速度超越了1級緩存的資料I\O能力，CPU廠商又引入了多級的緩存結構。
2、多核CPU多級緩存一緻性協定MESI
多核CPU的情況下有多個一級緩存，如何保證緩存内部資料的一緻,不讓系統資料混亂。這裡就引出了一個一緻性的協定MESI。
2.1、MESI協定緩存狀态
MESI 是指4種狀态的首字母。每個Cache line（緩存行，緩存存儲資料的單元）有4個狀态，可用2個bit表示，它們分别是：
| 狀态 | 描述 | 監聽任務 |
| M修改（Modified) | 該Cache line有效，資料被修改了，和記憶體中的資料不一緻，資料隻存在于本Cache中。 | 緩存行必須時刻監聽所有試圖讀該緩存行相對就主存的操作，這種操作必須在緩存将該緩存行寫回主存并将狀态變成S（共享）狀态之前被延遲執行。 |
| E獨享互斥（Exclusive） | 該Cache line有效，資料和記憶體中的資料一緻，資料隻存在于本Cache中。 | 緩存行也必須監聽其它緩存讀主存中該緩存行的操作，一旦有這種操作，該緩存行需要變成S（共享）狀态。 |
| S共享（Shared) | 該Cache line有效，資料和記憶體中的資料一緻，資料存在于很多Cache中。 | 緩存行也必須監聽其它緩存使該緩存行無效或者獨享該緩存行的請求，并将該緩存行變成無效（Invalid）。 |
| I無效 （Invalid） | 該Cache line無效。 | 無 |
注意：
對于M和E狀态而言總是精确的，他們在和該緩存行的真正狀态是一緻的，而S狀态可能是非一緻的。如果一個緩存将處于S狀态的緩存行廢棄了，而另一個緩存實際上可能已經獨享了該緩存行，但是該緩存卻不會将該緩存行升遷為E狀态，這是因為其它緩存不會廣播他們廢棄掉該緩存行的通知，同樣由于緩存并沒有儲存該緩存行的copy的數量，是以（即使有這種通知）也沒有辦法确定自己是否已經獨享了該緩存行。
從上面的意義看來E狀态是一種投機性的優化：如果一個CPU想修改一個處于S狀态的緩存行，總線事務需要将所有該緩存行的copy變成invalid狀态，而修改E狀态的緩存不需要使用總線事務。
2.2、MESI狀态轉換
了解該圖的前置說明：
1.觸發事件
| 觸發事件 | 描述 |
| 本地讀取（local read) | 本地cache讀取本地cache資料 |
| 本地寫入（local write) | 本地cache寫入本地cache資料 |
| 遠端讀取（remote read) | 其他cache讀取本地cache資料 |
| 遠端寫入（remote write) | 其他cache寫入本地cache資料 |
2.cache分類：
前提：所有的cache共同緩存了主記憶體中的某一條資料。
本地cache: 指目前cpu的cache。
觸發cache: 觸發讀寫事件的cache。
其他cache: 指既除了以上兩種之外的cache。
注意：本地的事件觸發 本地cache和觸發cache為相同。
上圖的切換解釋：
| 狀态 | 觸發本地讀取 | 觸發本地寫入 | 觸發遠端讀取 | 觸發遠端寫入 |
| M(修改) | 本地cache:M 觸發cache:M 其他cache:I | 本地cache:M 觸發cache:M其他cache:I | 本地cache:M→E→S 觸發cache:I→S 其他cache:I→S 同步主記憶體後修改為E獨享,同步觸發、其他cache後本地、觸發、其他cache修改為S共享 | 本地cache:M→E→S→I 觸發cache:I→S→E→M 其他cache:I→S→I 同步和讀取一樣,同步完成後觸發cache改為M，本地、其他cache改為I |
| E（獨享） | 本地cache:E 觸發cache:E 其他cache:I | 本地cache:E→M 觸發cache:E→M 其他cache:I 本地cache變更為M,其他cache狀态應當是I（無效） | 本地cache:E→S 觸發cache:I→S 其他cache:I→S 當其他cache要讀取該資料時，其他、觸發、本地cache都被設定為S(共享) | 本地cache:E→S→I 觸發cache:I→S→E→M 其他cache:I→S→I 當觸發cache修改本地cache獨享資料時時，将本地、觸發、其他cache修改為S共享.然後觸發cache修改為獨享，其他、本地cache修改為I（無效），觸發cache再修改為M |
| S（共享） | 本地cache:S 觸發cache:S 其他cache:S | 本地cache:S→E→M 觸發cache:S→E→M 其他cache:S→I 當本地cache修改時，将本地cache修改為E,其他cache修改為I,然後再将本地cache為M狀态 | 本地cache:S 觸發cache:S 其他cache:S | 本地cache:S→I 觸發cache：S→E→M 其他cache:S→I 當觸發cache要修改本地共享資料時，觸發cache修改為E（獨享）,本地、其他cache修改為I（無效）,觸發cache再次修改為M(修改) |
| I（無效） | 本地cache:I→S或者I→E 觸發cache:I→S或者I →E 其他cache:E、M、I→S、I 本地、觸發cache将從I無效修改為S共享或者E獨享，其他cache将從E、M、I 變為S或者I | 本地cache:I→S→E→M 觸發cache:I→S→E→M 其他cache:M、E、S→S→I | 既然是本cache是I，其他cache操作與它無關 | 既然是本cache是I，其他cache操作與它無關 |
下圖示意了，當一個cache line調整狀态的時候，另外一個cache line 需要調整的狀态。
| M | E | S | I | |
| M | × | × | × | √ |
| E | × | × | × | √ |
| S | × | × | √ | √ |
| I | √ | √ | √ | √ |
舉例說明：
假設cache 1 中有一個變量x = 0的cache line 處于S狀态(共享)。
那麼其他擁有x變量的cache 2、cache 3等x的cache line調整為S狀态（共享）或者調整為 I 狀态（無效）。
2.3、緩存行僞共享
什麼是僞共享？
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 TulingVolatileLong {
public volatile long value = 0L;
} 3、MESI優化和他們引入的問題
緩存的一緻性消息傳遞是要時間的，這就使其切換時會産生延遲。當一個緩存被切換狀态時，其他緩存收到消息完成各自的切換并且發出回應消息，這麼一長串的時間中CPU都會等待所有緩存響應完成，可能出現的阻塞都會導緻各種各樣的性能問題和穩定性問題。
3.1、CPU切換狀态阻塞解決-存儲緩存（Store Bufferes）
比如你需要修改本地緩存中的一條資訊，那麼你必須将I（無效）狀态通知到其他擁有該緩存資料的CPU緩存中，并且等待确認。等待确認的過程會阻塞處理器，這會降低處理器的性能。應為這個等待遠遠比一個指令的執行時間長的多。
Store Bufferes
為了避免這種CPU運算能力的浪費，Store Bufferes被引入使用。處理器把它想要寫入到主存的值寫到緩存，然後繼續去處理其他事情。當所有失效确認（Invalidate Acknowledge）都接收到時，資料才會最終被送出。
這麼做有兩個風險
Store Bufferes的風險
第一、就是處理器會嘗試從存儲緩存（Store buffer）中讀取值，但它還沒有進行送出。這個的解決方案稱為Store Forwarding，它使得加載的時候，如果存儲緩存中存在，則進行傳回。
第二、儲存什麼時候會完成，這個并沒有任何保證。
int value = 3；
void exeToCPUA(){
value = 10;
isFinsh = true;
}
void exeToCPUB(){
if(isFinsh){
//value一定等于10？
assert value == 10;
}
} 想象一下開始執行時，CPU A儲存着finished在E(獨享)狀态，而value并沒有儲存在它的緩存中。（例如，Invalid）。在這種情況下，value會比finished更遲地抛棄存儲緩存。完全有可能CPU B讀取finished的值為true，而value的值不等于10。
即finished的指派在value指派前
這種在可識别的行為中發生的變化稱為重排序（reordings）。注意，這不意味着你的指令的位置被惡意（或者好意）地更改。
它隻是意味着其他的CPU會讀到跟程式中寫入的順序不一樣的結果
硬體記憶體模型
執行失效也不是一個簡單的操作，它需要處理器去處理。另外，存儲緩存（Store Buffers）并不是無窮大的，是以處理器有時需要等待失效确認的傳回。這兩個操作都會使得性能大幅降低。為了應付這種情況，引入了失效隊列。它們的約定如下：
- 對于所有的收到的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;
}