文章目錄

1. CPU緩存
2. CPU緩存一致性協(xié)議
   2.1 局部性原理
   2.2 Cache Line
   2.3 cache的寫方式
   2.4 一致性協(xié)議MESI
3. 偽共享
4. 復(fù)現(xiàn)偽共享
5. 如何避免偽共享

偽共享的非標準定義為：緩存系統(tǒng)中是以緩存行（cache line）為單位存儲的，當(dāng)多線程修改互相獨立的變量時，如果這些變量共享同一個緩存行，就會無意中影響彼此的性能，這就是偽共享

下面我們就來詳細剖析偽共享產(chǎn)生的前因后果。首先，我們要了解什么是緩存系統(tǒng)。

1. CPU緩存

CPU 緩存（Cache Memory）是位于 CPU 與內(nèi)存之間的臨時存儲器，它的容量比內(nèi)存小的多但是交換速度卻比內(nèi)存要快得多。

高速緩存的出現(xiàn)主要是為了解決 CPU 運算速度與內(nèi)存讀寫速度不匹配的矛盾，因為 CPU 運算速度要比內(nèi)存讀寫速度快很多，這樣會使 CPU 花費很長時間等待數(shù)據(jù)到來或把數(shù)據(jù)寫入內(nèi)存。

• 來自百度百科

CPU 緩存可以分為一級緩存，二級緩存，部分高端 CPU 還具有三級緩存。每一級緩存中所儲存的全部數(shù)據(jù)都是下一級緩存的一部分，越靠近 CPU 的緩存越快也越小。所以 L1 緩存很小但很快(譯注：L1 表示一級緩存)，并且緊靠著在使用它的 CPU 內(nèi)核。L2 大一些，也慢一些，并且仍然只能被一個單獨的 CPU 核使用。L3 在現(xiàn)代多核機器中更普遍，仍然更大更慢，并且被單個插槽上的所有 CPU 核共享。主內(nèi)存由全部插槽上的所有 CPU 核共享。
關(guān)系如下圖：

CPU共享

當(dāng) CPU 執(zhí)行運算的時候，它先去 L1 查找所需的數(shù)據(jù)，再去 L2，然后是 L3，最后如果這些緩存中都沒有，所需的數(shù)據(jù)就要去主內(nèi)存拿。走得越遠，運算耗費的時間就越長。所以如果你在做一些很頻繁的事，你要確保數(shù)據(jù)在 L1 緩存中。

具有高速緩存的CPU執(zhí)行計算的流程

1. 程序以及數(shù)據(jù)被加載到主內(nèi)存
2. 指令和數(shù)據(jù)被加載到CPU的高速緩存
3. CPU執(zhí)行指令，把結(jié)果寫到高速緩存
4. 高速緩存中的數(shù)據(jù)寫回主內(nèi)存

2. CPU緩存一致性協(xié)議

2.1 局部性原理

緩存之所以有效，主要是因為程序運行時對內(nèi)存的訪問呈現(xiàn)局部性（Locality）特征。這種局部性既包括空間局部性（Spatial Locality），也包括時間局部性（Temporal Locality）。有效利用這種局部性，緩存可以達到極高的命中率。

在CPU訪問存儲設(shè)備時，無論是存取數(shù)據(jù)抑或存取指令，都趨于聚集在一片連續(xù)的區(qū)域中，這就被稱為局部性原理。

• 時間局部性（Temporal Locality）：如果一個信息項正在被訪問，那么在近期它很可能還會被再次訪問。比如循環(huán)、遞歸、方法的反復(fù)調(diào)用等。
• 空間局部性（Spatial Locality）：如果一個存儲器的位置被引用，那么將來他附近的位置也會被引用。比如順序執(zhí)行的代碼、連續(xù)創(chuàng)建的兩個對象、數(shù)組等。

2.2 Cache Line

cache line是cache與內(nèi)存數(shù)據(jù)交換的最小單位，根據(jù)操作系統(tǒng)一般是32byte或64byte。如下圖：

cacheline

cache的內(nèi)容除了存的數(shù)據(jù)（data）之外，還包含存的數(shù)據(jù)的物理內(nèi)存的地址信息（tag），因為CPU發(fā)出的尋址信息都是針對物理內(nèi)存發(fā)出的，所以cache中除了要保存數(shù)據(jù)信息之外，還要保存數(shù)據(jù)對應(yīng)的地址，這樣才能在cache中根據(jù)物理內(nèi)存的地址信息查找物理內(nèi)存中對應(yīng)的數(shù)據(jù)為了加快尋找速度，cache中一般還包含一個有效位（valid），用來標記這個cache line保存著的數(shù)據(jù)的狀態(tài)。一個tag和它對應(yīng)的數(shù)據(jù)組成的一行稱為一個cache line

Data、Valid、Tag各有多大？
cache中數(shù)據(jù)部分占的空間表示cache的容量，也就是32byte或64byte。

單核Cache中每個Cache line有2個標志：dirty和valid標志，它們很好的描述了Cache和Memory(內(nèi)存)之間的數(shù)據(jù)關(guān)系(數(shù)據(jù)是否有效，數(shù)據(jù)是否被修改)，而在多核處理器中，多個核會共享一些數(shù)據(jù)，占2個字節(jié)。

一個cache line中tag字段和valid位占4[2]+2[1]=6bit

2.3 cache的寫方式

cache的寫操作方式有四中：

1. 寫通 write through：每次CPU修改了cache中的內(nèi)容，立即更新到內(nèi)存，也就意味著每次CPU寫共享數(shù)據(jù)，都會導(dǎo)致總線事務(wù)，因此這種方式常常會引起總線事務(wù)的競爭，高一致性，但是效率非常低；
2. 寫回 write back：每次CPU修改了cache中的數(shù)據(jù)，不會立即更新到內(nèi)存，而是等到cache line在某一個必須或合適的時機才會更新到內(nèi)存中；
3. 寫失效 write invalidate：當(dāng)一個CPU修改了數(shù)據(jù)，如果其他CPU有該數(shù)據(jù)，則通知其為無效；
4. 寫更新 write update：當(dāng)一個CPU修改了數(shù)據(jù)，如果其他CPU有該數(shù)據(jù)，則通知其跟新數(shù)據(jù)；

寫更新會導(dǎo)致大量的更新操作，因此在MESI協(xié)議中，采取的是寫失效（即MESI中的I：ivalid，如果采用的是寫更新，那么就不是MESI協(xié)議了，而是MESU協(xié)議）。

2.4 一致性協(xié)議MESI

緩存一致性：在多核CPU中，內(nèi)存中的數(shù)據(jù)會在多個核心中存在數(shù)據(jù)副本，某一個核心發(fā)生修改操作，就產(chǎn)生了數(shù)據(jù)不一致的問題。而一致性協(xié)議正是用于保證多個CPU cache之間緩存共享數(shù)據(jù)的一致。

為了達到數(shù)據(jù)訪問的一致，需要各個處理器在訪問緩存時遵循一些協(xié)議，在讀寫時根據(jù)協(xié)議來操作，常見的協(xié)議有MSI，MESI，MOSI等。其中最經(jīng)典的MESI協(xié)議

現(xiàn)在主流的處理器都是用它來保證緩存的相干性和內(nèi)存的相干性。M、E、S 和 I 代表使用 MESI 協(xié)議時緩存行所處的四個狀態(tài)：

cache操作
MESI協(xié)議中，每個cache的控制器不僅可以操作（local read和local write）自己的cache，每個核心的緩存控制器通過監(jiān)聽也知道其他CPU中cache的操作（remote read和remote write），確定自己cache中共享數(shù)據(jù)的狀態(tài)是否需要調(diào)整。

• local read（LR）：讀本地cache中的數(shù)據(jù)；
• local write（LW）：將數(shù)據(jù)寫到本地cache；
• remote read（RR）：其他cache讀取本地cache數(shù)據(jù)；
• remote write（RW）：其他cache寫入本地cache數(shù)據(jù)；

下面說明四個狀態(tài)是如何轉(zhuǎn)換的：

初始：一開始時，緩存行沒有加載任何數(shù)據(jù)，所以它處于 I 狀態(tài)。
本地寫（Local Write）：如果本地處理器寫數(shù)據(jù)至處于 I 狀態(tài)的緩存行，則緩存行的狀態(tài)變成 M。

本地讀（Local Read）：如果本地處理器讀取處于 I 狀態(tài)的緩存行，很明顯此緩存沒有數(shù)據(jù)給它。此時分兩種情況：

1. 其它處理器的緩存里也沒有此行數(shù)據(jù)，則從內(nèi)存加載數(shù)據(jù)到此緩存行后，再將它設(shè)成 E 狀態(tài)，表示只有我一家有這條數(shù)據(jù)，其它處理器都沒有；
2. 其它處理器的緩存有此行數(shù)據(jù)，則將此緩存行的狀態(tài)設(shè)為 S 狀態(tài)。（備注：如果處于M狀態(tài)的緩存行，再由本地處理器寫入/讀出，狀態(tài)是不會改變的）

遠程讀（Remote Read）：假設(shè)我們有兩個處理器 c1 和 c2，如果 c2 需要讀另外一個處理器 c1 的緩存行內(nèi)容，c1 需要把它緩存行的內(nèi)容通過內(nèi)存控制器 (Memory Controller) 發(fā)送給 c2，c2 接到后將相應(yīng)的緩存行狀態(tài)設(shè)為 S。在設(shè)置之前，內(nèi)存也得從總線上得到這份數(shù)據(jù)并保存。

遠程寫（Remote Write）：其實確切地說不是遠程寫，而是 c2 得到 c1 的數(shù)據(jù)后，不是為了讀，而是為了寫。也算是本地寫，只是 c1 也擁有這份數(shù)據(jù)的拷貝，這該怎么辦呢？c2 將發(fā)出一個 RFO (Request For Owner) 請求，它需要擁有這行數(shù)據(jù)的權(quán)限，其它處理器的相應(yīng)緩存行設(shè)為 I，除了它自已，誰不能動這行數(shù)據(jù)。這保證了數(shù)據(jù)的安全，同時處理 RFO 請求以及設(shè)置I的過程將給寫操作帶來很大的資源消耗。

注意：當(dāng)多個處理器對相同的緩存行時（數(shù)據(jù)相同，在不同的cache中）進行寫操作時，也就是當(dāng)產(chǎn)生RFO，相當(dāng)于爭奪緩存的所有權(quán)會帶來巨大的資源消耗，這也為造成偽共享低效率的因素。
參考：https://zh.wikipedia.org/wiki/MESI%E5%8D%8F%E8%AE%AE

3. 偽共享

回到CPU緩存，緩存行（cache line）是CPU緩存的基本單位，緩存行通常是 32/64 字節(jié),緩存利用了局部性原理,當(dāng)我們訪問一個數(shù)據(jù)時，獲取一個值后，其相鄰的值也被緩存到就近的緩存行中。比如訪問一個long類型數(shù)組，當(dāng)數(shù)組中的一個值被加載到緩存中，它會額外加載另外 7 個，以致你能非?？斓乇闅v這個數(shù)組。因此可以非?？焖俚谋闅v在連續(xù)的內(nèi)存塊中分配的任意數(shù)據(jù)結(jié)構(gòu)。

但是天下沒有免費的午餐，某種情況下有多個線程操作不同的成員變量，但是多個變量處于相同的緩存行。顯然帶來了PFO操作。借用一張經(jīng)典的圖：

一個運行在處理器 core1上的線程想要更新變量 X 的值，同時另外一個運行在處理器 core2 上的線程想要更新變量 Y 的值。但是，這兩個頻繁改動的變量都處于同一條緩存行。兩個線程就會輪番發(fā)送 RFO 消息，占得此緩存行的擁有權(quán)。當(dāng) core1 取得了擁有權(quán)開始更新 X，則 core2 對應(yīng)的緩存行需要設(shè)為 I 狀態(tài)。當(dāng) core2 取得了擁有權(quán)開始更新 Y，則 core1 對應(yīng)的緩存行需要設(shè)為 I 狀態(tài)(失效態(tài))。輪番奪取擁有權(quán)不但帶來大量的 RFO 消息，而且如果某個線程需要讀此行數(shù)據(jù)時，L1 和 L2 緩存上都是失效數(shù)據(jù)，只有 L3 緩存上是同步好的數(shù)據(jù)。從前一篇我們知道，讀 L3 的數(shù)據(jù)非常影響性能。更壞的情況是跨槽讀取，L3 都要 miss，只能從內(nèi)存上加載。

表面上 X 和 Y 都是被獨立線程操作的，而且兩操作之間也沒有任何關(guān)系。只不過它們共享了一個緩存行，但所有競爭沖突都是來源于共享。

4. 復(fù)現(xiàn)偽共享

public class FalseShareTest {

  final static long iteration = 1000000;
  static long totalTime = 0L;
  static VolatileLong volatileLong = new VolatileLong();

  public static void main(final String[] args) throws InterruptedException {
    //運行十次
    for (int j = 0; j < 10; j++) {
      final long start = System.nanoTime();
      runSys();
      final long end = System.nanoTime();
      totalTime += end - start;
      System.out.println(j + " : " + (end - start));
    }
    System.out.println("平均耗時：" + totalTime / 10);
  }
  public static void runSys() throws InterruptedException {
     Thread thread1 = new Thread(() -> {
      for (int i = 0; i < iteration; i++) {
        volatileLong.value1++;
      }
    });
     Thread thread2 = new Thread(() -> {
      for (int j = 0; j < iteration; j++) {
        volatileLong.value2++;
      }
    });
    thread1.start();
    thread2.start();
    thread1.join();
    thread2.join();
  }
 static class VolatileLong {
    public volatile   long value1;
    //public long p1, p2, p3, p4, p5, p6, p7,p8;
    public volatile   long value2;
  }
}

通過兩個線程修改一個類中的兩個變量。value 設(shè)為 volatile 是為了讓 value 的修改對所有線程都可見。JVM系列：六、Java內(nèi)存模型和多線程文章中提到過：

使用volatile關(guān)鍵字的話，當(dāng)線程2進行修改時，會導(dǎo)致線程1的工作內(nèi)存中緩存變量stop的緩存行無效

這里如果我們通過兩個線程，分別修改value1和value2，這兩個變量被加載到同一個緩存行中，產(chǎn)生偽共享。

倒數(shù)第二行代碼是為了防止這兩個變量被加載到同一個緩存行中，分別執(zhí)行兩種情況，偽共享的情況是執(zhí)行時間是破壞偽共享的兩倍。

5. 如何避免偽共享

正如上一節(jié)中的做法，防止其他數(shù)據(jù)導(dǎo)致偽共享的問題常用增加padding，叫做緩存行填充的方式來解決，例如在前后加上無用的數(shù)據(jù)。

在JDK1.8中，新增了一種注解@sun.misc.Contended，來使各個變量在Cache line中分隔開。注意，jvm需要添加參數(shù)-XX:-RestrictContended才能開啟此功能 。類前加上代表整個類的每個變量都會在單獨的cache line中。屬性前加代表該屬性會在單獨的cacheline中。

@sun.misc.Contended
static class VolatileLong {
  public volatile   long value1;
  //public long p1, p2, p3, p4, p5, p6, p7,p8;
  public volatile   long value2;
}

替換上面的代碼，執(zhí)行時間和我們手動填充緩存行的是一樣的。