Cache一致性協議與偽共享問題

2022 年 1 月 10 日
筆記
JAVA, 並發編程

Cache一致性協議

在說偽共享問題之前，有必要聊一聊什麼是Cache一致性協議

局部性原理

時間局部性：如果一個資訊項正在被訪問，那麼在近期它很可能還會被再次訪問
比如循環、方法的反覆調用等

空間局部性：如果一個存儲器的位置被引用，那麼將來他附近的位置也會被引用
比如順序結構、數組

Cache的作用

CPU在摩爾定律的指導下以每18個月翻一番的速度在發展，然而記憶體和硬碟的發展速度遠遠不及CPU。為了解決這個問題，CPU廠商在CPU中內置了少量的高速快取Cache，以解決訪存速度和CPU運算速度之間不匹配的問題

帶Cache的CPU訪存過程

CPU和Cache交換數據以字為單位。Cache與主存以塊為單位，一個快取行（Cache Line）對應一個主存塊

讀：

Cache命中，則直接從Cache中讀取數據
Cache不命中，則訪問主存，並將一個主存塊調入Cache中，存入為一個快取行。這個過程中可能由於Cache滿而發生替換，替換演算法包括RAND、FIFO、LRU、LFU

寫：

Cache命中時
- 寫回法（write back）：CPU只將數據寫入Cache，只有當數據調出Cache時，才寫入主存
- 寫穿法（write through）：CPU同時將數據寫入Cache和主存
Cache不命中時
- 寫分配法：從主存中將數據塊調入Cache，並修改Cache，和寫回法配合使用
- 非寫分配法：只寫入主存，不調入Cache，和寫穿法配合使用

Cache和主存的映射方式（三種）：直接映射、全相聯映射、組相聯映射

如果是單CPU結構，這麼執行沒有其他問題。但是現代系統往往包含多個CPU，每個CPU都有各自的Cache。多核CPU的情況下有多個一級快取，如何保證快取內部數據的一致性，不讓系統數據混亂。這裡就引出了Cache一致性協議——MESI。注意，這並不是唯一的快取一致性協議，還有其他協議如MOSEI（相對於MESI多引入了一個Owned狀態，並重新定義了S狀態），這裡不多介紹

MESI協議詳解

MESI（Modified Exclusive Shared Or Invalid），也稱伊利諾斯協議，是一種廣泛使用的、支援寫回策略的快取一致性協議。MESI協議其實就是使用4種狀態來標記各個快取行（Cache Line）的狀態，而這些狀態英文首字母縮寫就構成了「MESI」

MESI協議中的各種狀態

每個快取行都使用一個狀態來標記，該狀態總共有4種，使用2bit進行存儲：

M（Modified）：相應的數據只被快取在該CPU的Cache中，但數據是被修改過的（臟數據），即與主存中的數據不一致。該快取行中的記憶體需要在未來的某個時間點，但必須是其它CPU讀取主存中相應記憶體之前，將數據寫回主存
E（Exclusive）：相應的數據只被快取在該CPU的快取中，數據是未被修改過的，與主存中的數據一致
S（Shared）：相應的數據被多個CPU快取，且各個CPU的Cache中的數據和主存都是一致的
I（Invalid）：該快取行中的數據是無效的，因為有其他CPU修改了數據

匯流排嗅探機制（監聽）

每個CPU都可以感知其他CPU的行為，比如讀、寫某個快取行，這就是嗅探機制，也稱監聽。所有的快取行（除了Invalid狀態）都需要監聽自己和其他CPU對相應的快取行的讀寫操作，也稱觸發事件，從而根據觸發事件和自身狀態，進行狀態的轉換

各種觸發事件

觸發事件	描述
本地讀取（Local Read）	本CPU讀取本Cache的數據
本地寫入（Local Write）	本CPU向本Cache寫入數據
遠端讀取（Remote Read）	其他CPU讀取它們各自Cache的數據
遠端寫入（Remote Write）	其他CPU向它們各自Cache寫入數據

MESI中各個狀態之間的轉換

下圖描述了當前快取行在不同觸發事件下的狀態切換：

下表是對上圖的一個詳細解釋：

舉例

假設CPU0、CPU1、CPU2、CPU3中有一個快取行（包含變數x）都是S狀態

此時CPU1要對變數x進行寫操作，這時候通過匯流排嗅探機制，CPU0、CPU2、CPU3中的快取行會置為I狀態（無效），然後給CPU1發響應，收到全部響應後CPU1會完成對變數x的寫操作，並更新CPU1內的快取行為M狀態，但不會將數據x同步到主存中

接著CPU0想要對變數x執行讀操作，卻發現本地快取行是I狀態，就會觸發CPU1去把快取行寫回到主存中，然後CPU0再去主存中同步最新的值

其他一些細節

1、寫緩衝
前面的描述隱藏了一些細節，比如實際CPU1在執行寫操作，更新快取行的時候，其實並不會等待其他CPU的狀態都置為I狀態，才去做些操作，這是一個同步行為，效率很低。當前的CPU都引入了寫快取器技術，也就是在CPU和cache之間又加了一層buffer，在CPU執行寫操作時直接向寫緩衝寫入數據，然後就忙其他事去了，等其他CPU都置為I之後，CPU1才把buffer中的數據寫入到快取行中

2、多級快取

現代系統都會採用多級快取架構，L1-L3級快取，其中L3快取是所有CPU共享的一個快取，但MESI的描述中並沒有涉及L3快取。其實上文提到的所有跟「主存」交換數據的地方，在L3快取存在的情況下，都應該替換為L3快取。比如我上一節舉的例子中，CPU0中某快取行是I，CPU1 中是M。當CPU0想到執行local read操作時，就會觸發CPU1中的快取寫入到主存中，然後CPU0從主存中取最新的快取行。其實這裡的描述是不準確的，因為由於L3快取的存在，這裡其實是直接從L3快取讀取快取行，而不直接訪問主存。個人認為是如果在描述MESI的狀態流轉時，如果引入L3快取，會使得描述過於複雜，因此一般的描述都會刻意忽略L3快取

作者：酒冽出處：//www.cnblogs.com/frankiedyz/p/15786362.html

版權：本文版權歸作者和部落格園共有

轉載：歡迎轉載，但未經作者同意，必須保留此段聲明；必須在文章中給出原文連接；否則必究法律責任

偽共享

由於記憶體和Cache之間的交換單位是記憶體塊/快取行，因此如果訪問一個變數，會將一整個記憶體塊讀入一個快取行。但是如果多個執行緒訪問的變數不相同，且這些變數在記憶體中的位置臨近，那麼很可能在同一個快取行中。在Cache一致性協議（如MESI協議）的約束下，多個執行緒（CPU）在並行讀寫相對應的快取行會有限制，因此其他執行緒不得不去訪問低級別的Cache甚至是主存，這會導致cache沒有起到真正的作用，程式性能下降

偽共享示例

如圖，執行緒1訪問變數x，而執行緒2訪問變數y，而這兩個變數在記憶體中的位置臨近（在同一個記憶體塊中），雖然執行緒都將該記憶體塊讀入到各自的工作記憶體（Cache）中，但是在Cache一致性協議的約束下，同一時間兩個執行緒很難自由地讀寫相同位置的快取行，那麼可能就會讓其中一個執行緒去低級別的記憶體中讀寫數據，性能因此降低，這就是偽共享

一般地址連續的多個變數更可能被放在同一個快取行中，例如創建數組時，數組中的多個元素更可能被放入同一個快取行中

如何避免偽共享問題

JDK8之前

JDK8之前，使用位元組填充的方式，即創建一個變數時，使用填充欄位填充該變數所在的快取行，從而避免多個變數被放入同一個快取行中，如下：

public final static class FilledLong {
    public volatile long value = 0L;
    public long p1, p2, p3, p4, p5, p6;
}

一般來說，快取行為64 Byte，而經過填充的FilledLong對象有7*8 Byte=56 Byte，而FilledLong對象的對象頭也有8 Byte，正好填滿一個快取行

JDK8及之後

JDK8提供了一個註解——sun.misc.Contended，用於解決偽共享問題，上述程式碼可以修改為如下：

@sun.misc.Contended
public final static class FilledLong {
	public volatile long value = 0L;
}

在Thread類中，也有這樣的欄位，如下：

@sun.misc.Contended("tlr")
long threadLocalRandomSeed;

/** Probe hash value; nonzero if threadLocalRandomSeed initialized */
@sun.misc.Contended("tlr")
int threadLocalRandomProbe;

/** Secondary seed isolated from public ThreadLocalRandom sequence */
@sun.misc.Contended("tlr")
int threadLocalRandomSecondarySeed;

但是，@Contended註解只用於Java核心類，而用戶類路徑下的類使用該註解，需要添加JVM參數-XX:-RestrictContended。填充寬度默認為128 Byte，也可以自定義寬度，通過JVM參數-XX:ContendedPaddingWidth來設定

Tags: JAVA 並發編程