文章目錄：
1、 CPU緩存
2、 總線鎖和緩存鎖
3、 緩存行
4、 緩存一致性協議（如：MESI）
5、 偽共享（false sharing）問題
6、 偽共享解決方案（如：緩存行填充）
6.1 Disruptor為什麼這麼快？
6.2 實驗證明
6.3 Jdk8中自帶註解@Contended
7、 總結
本篇文章主要介紹CPU緩存相關 的內容。 亦是上一篇文章幹掉面試官-volatile底層原理詳解的延伸和補充。
併發編程為何如此複雜？併發編程為什麼會產生可見性、有序性、原子性的線程或內存問題？
歸根結底，還是計算機硬件高速發展的原因。如果是單核的cpu，肯定不會出現多線程併發的安全問題。正是因為多核CPU架構，以及CPU緩存才導致一系列的併發問題。
1、 CPU緩存
相信大家都見過下面這張圖或類似的圖，計算機的存儲層次結構像一座金字塔。越往上訪問速度越快、成本更高，所以空間也越小。越往下訪問速度越慢、成本越低，空間也就越大。
CPU的運算速度最快，內存的讀寫速度無法和其速度匹配。假如定義cpu的一次存儲或訪問為一個時鐘週期，那麼內存的一次運算通常需要幾十甚至幾百個始終週期。如果在CPU直接讀取內存進行運算，那麼CPU大部分時間都在等在內存的訪問，利用率僅有幾十分之一甚至幾百分之一。為了解決CPU運算速度與內存讀寫速度不匹配的矛盾，在CPU和內存之間，引入了L1高速緩存、L2高速緩存、L3高速緩存，通過每一級緩存中所存儲的數據全部都是下一級緩存中的一部分，當CPU需要數據時，就從緩存中獲取，從而加快讀寫速度，提高CPU利用率、提升整體效率。
- L1高速緩存：也叫一級緩存。一般內置在內核旁邊，是與CPU結合最為緊密的CPU緩存。一次訪問只需要2~4個時鐘週期
- L2高速緩存：也叫二級緩存。空間比L1緩存大，速度比L1緩存略慢。一次訪問約需要10多個時鐘週期
- L3高速緩存：也叫三級緩存。部分單CPU多核心的才會有的緩存，介於多核和內存之間。存儲空間已達Mb級別，一次訪問約需要數十個時鐘週期。
當CPU要讀取一個數據時，首先從L1緩存查找，命中則返回；若未命中，再從L2緩存中查找，如果還沒有則從L3緩存查找（如果有L3緩存的話）。如果還是沒有，則從內存中查找，並將讀取到的數據逐級放入緩存。
2、 總線鎖和緩存鎖
上一篇文章講到過lock前綴：
lock前綴，會保證某個處理器對共享內存（一般是緩存行cacheline，這裡記住緩存行概念，後續重點介紹）的獨佔使用。它將本處理器緩存寫入內存，該寫入操作會引起其他處理器或內核對應的緩存失效。通過獨佔內存、使其他處理器緩存失效，達到了“指令重排序無法越過內存屏障”的作用
總線鎖 ：顧名思義就是，鎖住總線。通過處理器發出lock指令，總線接受到指令後，其他處理器的請求就會被阻塞，直到此處理器執行完成。這樣，處理器就可以獨佔共享內存的使用。但是，總線鎖存在較大的缺點，一旦某個處理器獲取總線鎖，其他處理器都只能阻塞等待，多處理器的優勢就無法發揮。
於是，經過發展、優化，又產生了緩存鎖。
緩存鎖：不需鎖定總線，只需要“鎖定”被緩存的共享對象（實際為：緩存行）即可，接受到lock指令，通過
緩存一致性協議，維護本處理器內部緩存和其他處理器緩存的一致性。相比總線鎖，會提高cpu利用率。但是緩存鎖也不是萬能，有些場景和情況依然必須通過總線鎖才能完成。
這裡又出現了兩個新概念：緩存行和緩存一致性協議
3、 緩存行
上一小章節中提到，緩存鎖會“鎖定”共享對象，如果僅鎖定所用對象，那麼有大有小、隨用隨取，對於CPU來說利用率還達不到最大化。所以採用，一次獲取一整塊的內存數據，放入緩存。那麼這一塊數據，通常稱為緩存行（cache line）。緩存行（cache line）是CPU緩存中可分配、操作的最小存儲單元。與CPU架構有關，通常有32字節、64字節、128字節不等。目前64位架構下，64字節最為常用。
4、 緩存一致性協議（如：MESI）
每個處理器都有自己的高速緩存，而又共享同一主內存。當多個處理器都涉及同一塊主內存區域的更改時，將導致各自的的緩存數據不一致。那同步到主內存時該以誰的緩存數據為準呢？為了解決一致性的問題，需要各個處理器訪問緩存時都遵循一些協議，在讀寫時要根據協議來進行操作，來保證處理器間緩存的一致性。這類協議有MSI、MESI、MOSI等。
下面重點介紹應用較為廣泛的MESI協議。MESI是Modified（修改）、Exclusive（獨佔）、Shared（共享）、Invaild（失效）四種狀態的縮寫，是用來修飾緩存行的狀態。在每個緩存行前額外使用2bit，來表示此四種狀態。
- Modified（修改）：該緩存行僅出現在此cpu緩存中，緩存已被修改，和內存中不一致，等待同步至內存。
- Exclusive（獨佔）：該緩存行僅出現在此cpu緩存中，緩存和內存中保持一致。
- Shared（共享）：該緩存行可能出現在多個cpu緩存中，且多個cpu緩存的緩存行和內存中的數據一致。
- Invalid（失效）：由於其他cpu修改了緩存行，導致本cpu中的緩存行失效。
在MESI協議中，每個緩存行不僅知道自己的讀寫操作，而且也監聽其它緩存行的讀寫操作。每個緩存行的狀態根據本cpu和其它cpu的讀寫操作在4個狀態間進行遷移。
它的監聽（嗅探）機制：
- 當緩存行處於Modified狀態時，會時刻監聽其他cpu對該緩存行對應主內存地址的讀取操作，一旦監聽到，將本cpu的緩存行寫回內存，並標記為Shared狀態
- 當緩存行處於Exclusive狀態時，會時刻監聽其他cpu對該緩存行對應主內存地址的讀取操作，一旦監聽到，將本cpu的緩存行標記為Shared狀態
- 當緩存行處於Shared狀態時，會時刻監聽其他cpu對使緩存行失效的指令（即其他cpu的寫入操作），一旦監聽到，將本cpu的緩存行標記為Invalid狀態（其他cpu進入Modified狀態）
- 當緩存行處於Invalid狀態時，從內存中讀取，否則直接從緩存讀取
總結：當某個cpu修改緩存行數據時，其他的cpu通過監聽機制獲悉共享緩存行的數據被修改，會使其共享緩存行失效。本cpu會將修改後的緩存行寫回到主內存中。此時其他的cpu如果需要此緩存行共享數據，則從主內存中重新加載，並放入緩存，以此完成了緩存一致性 。
5、 偽共享（false sharing）問題
緩存一致性協議針對的是最小存取單元：緩存行。依照64字節的緩存行為例，內存中連續的64字節都會被加載到緩存行中，除了目標數據還會有其他數據。
如下圖所示，假如變量x和變量y共處在同一緩存行中，core1需要操作變量x，core2需要操作變量y。
- core1修改緩存行內的變量x後，按照緩存一致性協議，core2需將緩存行置為失效，core1將最新緩存行數據寫回內存。
- core2需重新從內存中加載包含變量y的緩存行數據，並放置緩存。如果core2修改變量y，需要core1將緩存行置為失效，core2將最新緩存寫回內存。
- core1或其他處理器如需操作同一緩存行內的其他數據，同上述步驟。
上述例子，就是緩存行的偽共享問題。總結來說，就是多核多線程併發場景下，多核要操作的不同變量處於同一緩存行，某cpu更新緩存行中數據，並將其寫回緩存，同時其他處理器會使該緩存行失效，如需使用，還需從內存中重新加載。這對效率產生了較大的影響。
6、 偽共享解決方案（如：緩存行填充）
偽共享問題的解決思路有也很典型：空間換時間。
以64字節的緩存行為例，偽共享問題產生的前提是，併發情況下，不同cpu對緩存行中不同變量的操作引起的。那麼，如果把緩存行中僅存儲目標變量，其餘空間採用“無用”數據填充補齊64字節，就不會才產生偽共享問題。這種方式就是：
緩存行填充（也稱緩存行對齊）。Talk is cheap，show me the code.
下面，從三個實例去給大家解釋完緩存行填充，讓大家也能應用到自己的代碼中去。
6.1 Disruptor為什麼這麼快？
Disruptor是一個性能極強的開源的無鎖併發框架，基於Disruptor的LMAX架構交易平臺，號稱單線程內每秒可處理600萬筆訂單。簡直是一個不折不扣的性能小鋼炮。
Disruptor框架的核心是它的Ringbuffer環形緩衝。這裡不做框架的具體分析，有興趣可在github下載源碼（傳送門）。推薦大家閱讀併發編程網對Disruptor框架的介紹（傳送門）。
它的定位是高性能併發框架，肯定也會遇到我們上述的緩存偽共享問題，我們看一下Disruptor是怎麼解決的？
public long p1, p2, p3, p4, p5, p6, p7; // cache line padding
private volatile long cursor = INITIAL_CURSOR_VALUE;
public long p8, p9, p10, p11, p12, p13, p14; // cache line padding
Disruptor源碼中，有大量類似於上述的代碼，在目標變量前後定義多個"無實際含義的"變量進行緩存行填充（cache line padding）。
基礎類型long在java中佔用8字節，在額外填充7個long類型的變量，這樣在從內存中獲取目標變量放入緩存行時，可以達到緩存行中除了目標變量，剩下都是填充變量（由於無業務含義，其他cpu不會對其進行修改）。曲線救國，解決了緩存行偽共享的問題。思想：空間換時間 。
6.2 實驗證明
看了上述代碼，可能還有人心有存疑，搞出這麼多無用的字段，效率能提高？我不信。
下面我們就自己寫一個demo來證明：緩存行填充能提高併發效率。
例1：不填充緩存行
public class CacheLinePaddingBefore {
private static class Entity {
public volatile long x = 1L;
}
public static Entity[] arr = new Entity[2];
static {
arr[0] = new Entity();
arr[1] = new Entity();
}
public static void main(String[] args) throws InterruptedException {
Thread threadA = new Thread(() -> {
for (long i = 0; i < 1000_0000; i++) {
arr[0].x = i;
}
}, "ThreadA");
Thread threadB = new Thread(() -> {
for (long i = 0; i < 1000_0000; i++) {
arr[1].x = i;
}
}, "ThreadB");
final long start = System.nanoTime();
threadA.start();
threadB.start();
threadA.join();
threadB.join();
final long end = System.nanoTime();
System.out.println("耗時：" + (end - start) / 100_0000);
}
}
例1思路：
1、定義一個長度為2的數組arr，數組中是一個僅有一個long類型變量的對象；
2、定義兩個線程A和B，線程A修改arr[0]，線程B修改arr[1]。線程A和線程B併發修改1千萬次；
3、此處定義數組的目的是：保證線程A和線程B修改的變量儘可能是連續的，即兩個變量在同一緩存行中，以模擬偽共享問題。
測試結果：多次運行上述demo，平均耗時：240ms左右。
例2：填充緩存行
public class CacheLinePaddingAfter {
// 定義7個long類型變量，進行緩存行填充
private static class Padding{
public volatile long p1, p2, p3, p4, p5, p6, p7;
}
private static class Entity extends Padding{
// 使用@sun.misc.Contended註解，必須添加此參數：-XX:-RestrictContended
// @sun.misc.Contended
public volatile long x = 0L;
}
public static Entity[] arr = new Entity[2];
static {
arr[0] = new Entity();
arr[1] = new Entity();
}
public static void main(String[] args) throws InterruptedException {
Thread threadA = new Thread(() -> {
for (int i = 0; i < 1000_0000; i++) {
arr[0].x = i;
}
}, "ThreadA");
Thread threadB = new Thread(() -> {
for (int i = 0; i < 1000_0000; i++) {
arr[1].x = i;
}
}, "ThreadB");
final long start = System.nanoTime();
threadA.start();
threadB.start();
threadA.join();
threadB.join();
final long end = System.nanoTime();
System.out.println("耗時：" + (end - start)/100_0000);
}
}
例2思路：
1、定義一個包含7個long類型的“無實際意義”字段的填充對象；
2、實際對象Entity繼承填充對象，達到7+1=8個long類型字段，可以填充一整個64字節的緩存行；
3、重複例1中的動作。
測試結果：多次運行上述demo，平均耗時：70ms左右。
大家也可以直接拿上述兩個例子在自己的電腦進行測試。例2的執行效率遠超超例1的執行效率。我們通過實踐證明：緩存行填充顯著提高併發效率
6.3 Jdk8中自帶註解@Contended
Jdk8中引入了@sun.misc.Contended這個註解來解決緩存偽共享問題。使用此註解有一個前提，必須開啟JVM參數-XX:-RestrictContended，此註解才會生效。
此註解在一定程度上同樣解決了緩存偽共享問題。但底層原理並非緩存行填充，而是通過對對象頭內存佈局的優化，將那些可能會被同一個線程幾乎同時寫的字段分組到一起，避免形成競爭，來達到避免緩存偽共享的目的。此處不再鋪開講述，有興趣的可閱讀文章：併發編程網-有助於減少偽共享的@Contended註解和此文開頭提及Aleksey Shipilev的這封郵件
Jdk內部也大量使用了此註解
例1：java.lang.Thread類，修飾字段
例2：java.util.concurrent.ConcurrentHashMap類，修飾類
例3：使用註解@Contended改造上一章中的例2：緩存行填充demo
public class CacheLinePaddingAfter {
private static class Entity{
// 使用@sun.misc.Contended註解，必須添加此參數：-XX:-RestrictContended
@sun.misc.Contended
public volatile long x = 0L;
}
public static Entity[] arr = new Entity[2];
static {
arr[0] = new Entity();
arr[1] = new Entity();
}
public static void main(String[] args) throws InterruptedException {
Thread threadA = new Thread(() -> {
for (int i = 0; i < 1000_0000; i++) {
arr[0].x = i;
}
}, "ThreadA");
Thread threadB = new Thread(() -> {
for (int i = 0; i < 1000_0000; i++) {
arr[1].x = i;
}
}, "ThreadB");
final long start = System.nanoTime();
threadA.start();
threadB.start();
threadA.join();
threadB.join();
final long end = System.nanoTime();
System.out.println("耗時：" + (end - start)/100_0000);
}
}
測試結果：多次運行上述demo，平均耗時：70ms左右。
7、 總結
文章開頭提及本篇文章是上一篇文章volatile底層原理詳解（上） 的延伸和補充。所以下面帶大家整體回顧下這兩張的內容。如果沒看上篇文章或對volatile暫無興趣，請直接看下面的第3點總結即可。
我們對volatile關鍵字的作用和原理的瞭解，從Java代碼層面一路聊到計算機的硬件層面，硬件層面從cpu緩存到緩存行、緩存鎖，再到緩存一致性協議，最後分析了緩存行的偽共享問題以及它的解決方案。希望看完整篇之後再從頭到尾串一遍，將其中的“點”串成“線”，做到舉一反三，能對日後的工作有所幫助。最後，通過幾個問題，幫助大家回顧文章內容：
1、併發編程中的三大特性：原子性、可見性、有序性。volatile修飾的變量如何保證可見性、有序性？為何不能保證原子性？
2、volatile的底層實現：
a. Java代碼中如何使用volatile關鍵字？
b. volatile修飾的變量，編譯成class字節碼後，變量的訪問標誌有什麼變化？
c. JVM運行時，是判斷變量是被的volatile修飾的？賦值和取值同普通變量有何區別的？orderAccess.hpp頭文件中是對內存屏障的定義和作用的描述是怎樣的？lock前綴指令的作用是什麼？
d. 打印彙編輸出，可以看到JVM級別的實現：lock前綴指令。
3、可見性問題，有序性問題的產生一部分是cpu硬件架構引起的，那麼就有必要了解它的硬件原理，以及如何利用硬件寫出高性能的併發程序。
a. 金字塔的cpu存儲結構要能直觀呈現在腦子中。Cpu為什麼要有一、二、三級緩存？
b. Lock前綴的指令，能保證某個處理器對共享內存的獨佔使用，並且達到指令重排序無法越過內存屏障的目的。它是通過對緩存加鎖來實現。
緩存鎖瞭解一下。c. 緩存鎖針對的是對緩存行加鎖。緩存行是什麼？緩存一致性協議是什麼？
d. 緩存行偽共享問題是如何出現的？
e. 緩存行偽共享問題的解決方案：緩存行填充和JDK8中自帶的@Contented註解。併發編程中，我們可以嘗試應用，來提高程序運行效率。
