CPU Cache結(jié)構(gòu)
CPU包含多個核心，每個核心又有獨自的一級緩存（細(xì)分成代碼緩存和數(shù)據(jù)緩存）和二級緩存，各個核心之間共享三級緩存，并統(tǒng)一通過總線與內(nèi)存進(jìn)行交互
運行程序時，每個核心都有數(shù)據(jù)的一個副本（在各自的緩存中），這將會導(dǎo)致數(shù)據(jù)的一致性問題
Cache Line
整個Cache被分成多個Line，每個Line通常是32byte或64byte
Cache Line是Cache和內(nèi)存交換數(shù)據(jù)的最小單位
每個Cache Line包含三個部分
Valid：當(dāng)前緩存是否有效
Tag：對應(yīng)的內(nèi)存地址
Block：緩存數(shù)據(jù)
映射
主存與Cache的對應(yīng)關(guān)系
將主存和Cache劃分成若干大小相等的塊
全關(guān)聯(lián)映射
主存任意一塊可以映射到Cache的任意一塊
優(yōu)點：空間利用率高、命中率高
缺點：訪問存儲器時，每次都要全部查找，速度低，基本不使用
直接映射
主存中的一塊只能映射到Cache的一個特定的塊中
優(yōu)點：映射簡單，訪問速度快
缺點：替換頻繁，命中率低
組相連映射
主存根據(jù)Cache大小劃分多個區(qū)，每個區(qū)劃分成多個組，每個組內(nèi)劃分多個塊
Cache劃分成多個組，每個組內(nèi)劃分多個塊
主存的每個區(qū)與Cache直接映射，組內(nèi)采用全映射方式
替換策略
隨機(jī)
隨機(jī)確定要替換的塊
先進(jìn)先出
選擇最先調(diào)入的塊進(jìn)行替換
LRU（最近最少使用）
根據(jù)塊的使用情況，選擇最近最少使用的塊進(jìn)行替換，反映了程序的局部性規(guī)律
寫模式
直寫（Write Through）
透過本級緩存，直接把數(shù)據(jù)寫到下一級緩存（或直接到內(nèi)存）中，如果對應(yīng)的段被緩存了，同時更新緩存中的內(nèi)容（甚至直接丟棄）
緩存中的段永遠(yuǎn)和它對應(yīng)的內(nèi)存內(nèi)容匹配
寫回（Write Back）
緩存不會立即把寫操作傳遞到下一級，而是僅修改本級緩存中的數(shù)據(jù)，并且把對應(yīng)的緩存段標(biāo)記為“臟”段。臟段會觸發(fā)回寫，也就是把里面的內(nèi)容寫到對應(yīng)的內(nèi)存或下一級緩存中?；貙懞?，臟段又變“干凈”了。當(dāng)一個臟段被丟棄的時候，總是先要進(jìn)行一次回寫
回寫定律：當(dāng)所有的臟段被回寫后，任意級別緩存中的緩存段的內(nèi)容，等同于它對應(yīng)的內(nèi)存中的內(nèi)容
弱一致性：要么緩存段的內(nèi)容和內(nèi)存一致（如果緩存段是干凈的話），要么緩存段中的內(nèi)容最終要回寫到內(nèi)存中（對于臟緩存段來說）
優(yōu)點：能過濾掉對同一地址的反復(fù)寫操作，并且，如果大多數(shù)緩存段都在回寫模式下工作，那么系統(tǒng)經(jīng)?？梢砸幌伦訉懸淮笃瑑?nèi)存，而不是分成小塊來寫，前者的效率更高
一致性
單核是沒有問題的，但多核情況下，每個核都有自己的緩存，該如何確保各核緩存數(shù)據(jù)的一致性？
窺探協(xié)議
所有內(nèi)存?zhèn)鬏敹及l(fā)生在一條共享的總線上，而所有的處理器都能看到這條總線：緩存本身是獨立的，但是內(nèi)存是共享資源，所有的內(nèi)存訪問都要經(jīng)過仲裁（arbitrate）：同一個指令周期中，只有一個緩存可以讀寫內(nèi)存。
緩存不僅僅在做內(nèi)存?zhèn)鬏數(shù)臅r候才和總線打交道，而是不停地在窺探總線上發(fā)生的數(shù)據(jù)交換，跟蹤其他緩存在做什么。所以當(dāng)一個緩存代表它所屬的處理器去讀寫內(nèi)存時，其他處理器都會得到通知，它們以此來使自己的緩存保持同步。只要某個處理器一寫內(nèi)存，其他處理器馬上就知道這塊內(nèi)存在它們自己的緩存中對應(yīng)的段已經(jīng)失效。
在直寫模式下，是很直接的，因為寫操作一旦發(fā)生，它的效果馬上會被“公布”出去，確保所有核都得到通知
在回寫模式下，就有問題了，因為有可能在寫指令執(zhí)行過后很久，數(shù)據(jù)才會被真正回寫到物理內(nèi)存中。在這段時間內(nèi)，其他處理器的緩存也可能會去寫同一塊內(nèi)存地址，導(dǎo)致沖突
MESI緩存一直性協(xié)議
每個Cache line有2個標(biāo)志：dirty（數(shù)據(jù)是否被修改）和valid（數(shù)據(jù)是否有效）標(biāo)志，描述了Cache和主存之間的數(shù)據(jù)關(guān)系
在MESI協(xié)議中，每個Cache line有4個狀態(tài)
| 狀態(tài) | 描述 |
|---|---|
| M(Modified) | 數(shù)據(jù)有效，數(shù)據(jù)被修改了，和內(nèi)存中的數(shù)據(jù)不一致，數(shù)據(jù)只存在于本Cache中 |
| E(Exclusive) | 數(shù)據(jù)有效，數(shù)據(jù)和內(nèi)存中的數(shù)據(jù)一致，數(shù)據(jù)只存在于本Cache中 |
| S(Shared) | 數(shù)據(jù)有效，數(shù)據(jù)和內(nèi)存中的數(shù)據(jù)一致，數(shù)據(jù)存在于很多Cache中 |
| I(Invalid) | 這行數(shù)據(jù)無效 |
M(Modified)和E(Exclusive)狀態(tài)的Cache line，數(shù)據(jù)是獨有的，不同點在于M狀態(tài)的數(shù)據(jù)是dirty的(和內(nèi)存的不一致)，E狀態(tài)的數(shù)據(jù)是clean的(和內(nèi)存的一致)
S(Shared)狀態(tài)的Cache line，數(shù)據(jù)和其他Core的Cache共享。只有clean的數(shù)據(jù)才能被多個Cache共享
E狀態(tài)
只有Core 0訪問變量x，它的Cache line狀態(tài)為E(Exclusive)
S狀態(tài)
3個Core都訪問變量x，它們對應(yīng)的Cache line為S(Shared)狀態(tài)
M狀態(tài)和I狀態(tài)
Core 0修改了x的值之后，這個Cache line變成了M(Modified)狀態(tài)，其他Core對應(yīng)的Cache line變成了I(Invalid)狀態(tài)
MESI協(xié)議狀態(tài)遷移
Local Read表示本內(nèi)核讀本Cache中的值，Local Write表示本內(nèi)核寫本Cache中的值，Remote Read表示其它內(nèi)核讀其它Cache中的值，Remote Write表示其它內(nèi)核寫其它Cache中的值，箭頭表示本Cache line狀態(tài)的遷移，環(huán)形箭頭表示狀態(tài)不變
| 當(dāng)前狀態(tài) | 事件 | 行為 | 下一個狀態(tài) |
|---|---|---|---|
| I(Invalid) | Local Read | 如果其它Cache沒有這份數(shù)據(jù)，本Cache從內(nèi)存中取數(shù)據(jù)，Cache line狀態(tài)變成E；如果其它Cache有這份數(shù)據(jù)，且狀態(tài)為M，則將數(shù)據(jù)更新到內(nèi)存，本Cache再從內(nèi)存中取數(shù)據(jù)，2個Cache 的Cache line狀態(tài)都變成S；如果其它Cache有這份數(shù)據(jù)，且狀態(tài)為S或者E，本Cache從內(nèi)存中取數(shù)據(jù)，這些Cache 的Cache line狀態(tài)都變成S | E/S |
| Local Write | 從內(nèi)存中取數(shù)據(jù)，在Cache中修改，狀態(tài)變成M；如果其它Cache有這份數(shù)據(jù)，且狀態(tài)為M，則要先將數(shù)據(jù)更新到內(nèi)存；如果其它Cache有這份數(shù)據(jù)，則其它Cache的Cache line狀態(tài)變成I | M | |
| Remote Read | 既然是Invalid，別的核的操作與它無關(guān) | I | |
| Remote Write | 既然是Invalid，別的核的操作與它無關(guān) | I | |
| E(Exclusive) | Local Read | 從Cache中取數(shù)據(jù)，狀態(tài)不變 | E |
| Local Write | 修改Cache中的數(shù)據(jù)，狀態(tài)變成M | M | |
| Remote Read | 數(shù)據(jù)和其它核共用，狀態(tài)變成了S | S | |
| Remote Write | 數(shù)據(jù)被修改，本Cache line不能再使用，狀態(tài)變成I | I | |
| S(Shared) | Local Read | 從Cache中取數(shù)據(jù)，狀態(tài)不變 | S |
| Local Write | 修改Cache中的數(shù)據(jù)，狀態(tài)變成M，其它核共享的Cache line狀態(tài)變成I | M | |
| Remote Read | 狀態(tài)不變 | S | |
| Remote Write | 數(shù)據(jù)被修改，本Cache line不能再使用，狀態(tài)變成I | I | |
| M(Modified) | Local Read | 從Cache中取數(shù)據(jù)，狀態(tài)不變 | M |
| Local Write | 修改Cache中的數(shù)據(jù)，狀態(tài)不變 | M | |
| Remote Read | 這行數(shù)據(jù)被寫到內(nèi)存中，使其它核能使用到最新的數(shù)據(jù)，狀態(tài)變成S | S | |
| Remote Write | 這行數(shù)據(jù)被寫到內(nèi)存中，使其它核能使用到最新的數(shù)據(jù)，由于其它核會修改這行數(shù)據(jù)，狀態(tài)變成I | I |
*MESI定律：在所有的臟緩存段（M狀態(tài)）被回寫后，任意緩存級別的所有緩存段中的內(nèi)容，和它們對應(yīng)的內(nèi)存中的內(nèi)容一致。此外，在任意時刻，當(dāng)某個位置的內(nèi)存被一個處理器加載入獨占緩存段時（E狀態(tài)），那它就不會再出現(xiàn)在其他任何處理器的緩存中。
偽共享（false sharing）
發(fā)生在不同處理器上的線程修改位于同一個cache line的變量的情景下（本來每個線程都訪問不同的數(shù)據(jù)，不會造成同步問題，但因為數(shù)據(jù)都處于同一cache line中，根據(jù)MESI協(xié)議，cache line中任意數(shù)據(jù)的修改都需要同步給其他內(nèi)核，導(dǎo)致不應(yīng)同步的操作變成同步了）
這會導(dǎo)致cache line失效并強(qiáng)制刷新，因此導(dǎo)致性能下降
解決辦法：字節(jié)對齊，將字節(jié)填滿一個cache line
Java中主要有sun.misc.Contended和Disruptor框架
參考
每個程序員都應(yīng)該了解的CPU高速緩存
關(guān)于CPU Cache -- 程序猿需要知道的那些事
緩存一致性（Cache Coherency）入門
《大話處理器》Cache一致性協(xié)議之MESI
偽共享(False Sharing)
Java 7與偽共享的新仇舊恨
Java8中用sun.misc.Contended避免偽共享(false sharing)
