一、內存Cache還有哪些不足？

上一篇文章我們談到了內存Cache，并且描述了典型的Cache一致性協議MESI。Cache的根本目的，是解決內存與CPU速度多達兩個數量級的性能差異。一個包含Cache的計算機系統，其結構可以簡單的表示為下圖：

僅僅只有Cache的計算機系統，它還存在如下問題：

1、Cache的速度，雖然比內存有了極大的提升，但是仍然比CPU慢幾倍。

2、在發生“warmup cache miss”、“capacity miss”、“associativity miss”時，CPU必須等待從內存中讀取數據，此時CPU會處于一種Stall的狀態。其等待時間可能達到幾百個CPU指令周期。

顯然，這是現代計算機不能承受之重：）

二、Write buffer是為了解決什么問題？

如果CPU僅僅是執行foo = 1這樣的語句，它其實無須從內存或者緩存中讀取foo現在的值。因為無論foo當前的值是什么，它都會被覆蓋。在僅僅只有Cache的系統中，foo = 1 這樣的操作也會形成寫停頓。自然而然的，CPU設計者應當會想到在Cache 和CPU之間再添加一級緩存。由于這樣的緩存主要是應對寫操作引起的Cache Miss，并且緩存的數據與寫操作相關，因此CPU設計者將它命名為“Write buffer”。調整后的結構示意圖如下(圖中的store buffer即為write buffer)：

通過增加這些Write buffer，CPU可以簡單的將要保存的數據放到Write buffer 中，并且繼續運行，而不會真正去等待Cache從內存中讀取數據并返回。

對于特定CPU來說，這些Write buffer是屬于本地的。或者在硬件多線程系統中，它對于特定核來說，是屬于本地的。無論哪一種情況，一個特定CPU僅僅允許訪問分配給它的Writebuffer。例如，在上圖中，CPU 0不能訪問CPU 1的存儲緩沖，反之亦然。

Write buffer進一步提升了系統性能，但是它也會為硬件設計者帶來一些困擾：

第一個困擾：違反了自身一致性。

考慮如下代碼：變量“a”和“b”都初始化為0，包含變量“a”緩存行，最初被CPU 1所擁有，而包含變量“b”的緩存行最初被CPU0所擁有：

1 a = 1;

2 b = a + 1;

3 assert(b == 2);

沒有哪一位軟件工程師希望斷言被觸發！

然而，如果采用上圖中的簡單系統結構，斷言確實會被觸發。理解這一點的關鍵在于：a最初被CPU 1所擁有，而CPU 0在執行a = 1時，將a的新值存儲在CPU 0的Write buffer中。

在這個簡單系統中，觸發斷言的事件順序可能如下：

1．CPU 0 開始執行a = 1。

2．CPU 0在緩存中查找“a”，并且發現緩存缺失。

3．因此，CPU 0發送一個“讀使無效（read-invalidate message）”消息，以獲得包含“a”的獨享緩存行。

4．CPU 0將“a”記錄到存儲緩沖區。

5．CPU 1接收到“讀使無效”消息，它通過發送緩存行數據，并從它的緩存行中移除數據來響應這個消息。

6．CPU 0開始執行b = a + 1。

7．CPU 0從CPU 1接收到緩存行，它仍然擁有一個為“0”的“a”值。

8．CPU 0從它的緩存中讀取到“a”的值，發現其值為0。

9．CPU 0將存儲隊列中的條目應用到最近到達的緩存行，設置緩存行中的“a”的值為1。

10．CPU 0將前面加載的“a”值0加1，并存儲該值到包含“b”的緩存行中（假設已經被CPU 0所擁有）。

11．CPU 0 執行assert(b == 2)，并引起錯誤。

針對這種情況，硬件設計者對軟件工程師還是給予了必要的同情。他們會對系統進行稍許的改進，如下圖：

在調整后的架構中，每個CPU在執行加載操作時，將考慮（或者嗅探）它的Writebuffer。這樣，在前面執行順序的第8步，將在存儲緩沖區中為“a”找到正確的值1 ，因此最終的“b”值將是2，這正是我們期望的。

Write buffer帶來的第二個困擾，是違反了全局內存序。考慮如下的代碼順序，其中變量“a”、“b”的初始值是0。

1 void foo(void)

2 {

3 a = 1;

4 b = 1;

5 }

6

7 void bar(void)

8 {

9 while (b == 0) continue;

10 assert(a == 1);

11 }

假設CPU 0執行foo()，CPU1執行bar()，再進一步假設包含“a”的緩存行僅僅位于CPU1的緩存中，包含“b”的緩存行被CPU 0所擁有。那么操作順序可能如下：

1．CPU 0 執行a = 1。緩存行不在CPU0的緩存中，因此CPU0將“a”的新值放到Write buffer，并發送一個“讀使無效”消息。

2．CPU 1 執行while (b == 0) continue，但是包含“b”的緩存行不在它的緩存中，因此它發送一個“讀”消息。

3．CPU 0 執行 b = 1，它已經擁有了該緩存行（換句話說，緩存行要么已經處于“modified”，要么處于“exclusive”狀態），因此它存儲新的“b”值到它的緩存行中。

4．CPU 0 接收到“讀”消息，并且發送緩存行中的最近更新的“b”的值到CPU1，同時將緩存行設置為“shared”狀態。

5．CPU 1 接收到包含“b”值的緩存行，并將其值寫到它的緩存行中。

6．CPU 1 現在結束執行while (b ==0) continue，因為它發現“b”的值是1，它開始處理下一條語句。

7．CPU 1 執行assert(a == 1)，并且，由于CPU 1工作在舊的“a”的值，因此斷言驗證失敗。

8．CPU 1 接收到“讀使無效”消息，并且發送包含“a”的緩存行到CPU 0，同時在它的緩存中，將該緩存行變成無效。但是已經太遲了。

9．CPU 0 接收到包含“a”的緩存行，并且及時將存儲緩沖區的數據保存到緩存行中，CPU1的斷言失敗受害于該緩存行。

請注意，“內存屏障”已經在這里隱隱約約露出了它鋒利的爪子！！！！

三、使無效隊列又是為了解決什么問題？

一波未平，另一波再起。

問題的復雜性還不僅僅在于Writebuffer，因為僅僅有Write buffer，硬件還會形成嚴重的性能瓶頸。

問題在于，每一個核的Writebuffer相對而言都比較小，這意味著執行一段較小的存儲操作序列的CPU，很快就會填滿它的Writebuffer。此時，CPU在能夠繼續執行前，必須等待Cache刷新操作完成，以清空它的Write buffer。

清空Cache是一個耗時的操作，因為必須要在所在CPU之間廣播MESI消息(使無效消息)，并等待對這些MESI消息的響應。為了加快MESI消息響應速度，CPU設計者增加了使無效隊列。也就是說，CPU將接收到的使無效消息暫存起來，在發送使無效消息應答時，并不真正將Cache中的值無效。而是等待在合適的時候，延遲使無效操作。

下圖是增加了使無效隊列的系統結構：

將一個條目放進使無效隊列，實際上是由CPU承諾：在發送任何與該緩存行相關的MESI協議消息前，處理該條目。在Cache競爭不太劇烈的情況下，CPU會很出色地完成此事。

使無效隊列帶來的問題是：在沒有真正將Cache無效之前，就告訴其他CPU已經使無效了。這多少有一點欺騙的意思。然而現代CPU確實是這樣設計的。

這個事實帶來了額外的內存亂序的機會，看看如下示例：

假設“a”和“b”被初始化為0，“a”是只讀的（MESI“shared”狀態），“b”被CPU 0擁有（MESI“exclusive”或者“modified”狀態）。然后假設CPU 0執行foo()而CPU1執行bar()，代碼片段如下：

1 void foo(void)

2 {

3 a = 1;

4 smp_mb();

5 b = 1;

6 }

7

8 void bar(void)

9 {

10 while (b == 0) continue;

11 assert(a == 1);

12 }

操作順序可能如下：

1．CPU 0執行a = 1。在CPU0中，相應的緩存行是只讀的，因此CPU 0將“a”的新值放入存儲緩沖區，并發送一個“使無效”消息，這是為了使CPU1的緩存中相應的緩存行失效。

2．CPU 1執行while (b == 0)continue，但是包含“b”的緩存行不在它的緩存中，因此它發送一個“讀”消息。

3．CPU 1接收到CPU 0的“使無效”消息，將它排隊，并立即響應該消息。

4．CPU 0接收到來自于CPU 1的響應消息，因此它放心的通過第4行的smp_mb()，從存儲緩沖區移動“a”的值到緩存行。

5．CPU 0執行b = 1。它已經擁有這個緩存行（也就是說，緩存行已經處于“modified”或者“exclusive”狀態），因此它將“b”的新值存儲到緩存行中。

6．CPU 0接收到“讀”消息，并且發送包含“b”的新值的緩存行到CPU 1，同時在自己的緩存中，標記緩存行為“shared”狀態。

7．CPU 1接收到包含“b”的緩存行并且將其應用到本地緩存。

8．CPU 1現在可以完成while (b ==0) continue，因為它發現“b”的值為1，接著處理下一條語句。

9．CPU 1執行assert(a == 1)，并且，由于舊的“a”值還在CPU 1的緩存中，因此陷入錯誤。

10．雖然陷入錯誤，CPU 1處理已經排隊的“使無效”消息，并且（遲到）在自己的緩存中刷新包含“a”值的緩存行。

四、內存屏障

既然硬件設計者通過Write buffer和使無效隊列引入了額外的內存亂序問題，那么就應當為軟件工程師提供某種方法來解決這個問題。即使相應的解決方法會折磨軟件工程師。

答案就是內存屏障。對于Linux內核資深工程師來說，這個答案也顯得比較沉重，它太折磨人了：）

我們先看看Write buffer一節中，觸發斷言的例子，應該怎么修改。

在那個例子中，硬件設計者不能直接幫助我們，因為 CPU沒有辦法識別那些相關聯的變量（例子中的a和b），更不用說它們如何關聯。因此，硬件設計者提供內存屏障指令，以允許軟件告訴CPU這些關系的存在。程序必須修改，以包含內存屏障：

1 void foo(void)

2 {

3 a = 1;

4 smp_mb();

5 b = 1;

6 }

7

8 void bar(void)

9 {

10 while (b == 0) continue;

11 assert(a == 1);

12 }

內存屏障smp_mb()將導致CPU在刷新后續的緩存行（包含b的緩存行）之前，前面的Write buffer被先刷新。在繼續處理之前，CPU可能采取的動作是：

1、簡單的停頓下來，直到存儲緩沖區變成空；

2、也可能是使用存儲緩沖區來持有后續的存儲操作，直到前面所有的存儲緩沖區已經被保存到緩存行中。

理解其中第2點，能夠幫助我們理解“內存屏障”這個單詞的來歷！！

后一種情況下，操作序列可能如下所示：

1．CPU 0執行a= 1。緩存行不在CPU0的緩存中，因此CPU 0將“a”的新值放到存儲緩沖中，并發送一個“讀使無效”消息。

2．CPU 1 執行while(b == 0) continue，但是包含“b”的緩存行不在它的緩存中，因此它發送一個“讀”消息。

3．CPU 0執行smp_mb()，并標記當前所有存儲緩沖區的條目。（也就是說a = 1這個條目）。

4．CPU 0執行b= 1。它已經擁有這個緩存行了。（也就是說, 緩存行已經處于“modified”或者“exclusive”狀態），但是在存儲緩沖區中存在一個標記條目。因此，它不將“b”的新值存放到緩存行，而是存放到存儲緩沖區中。（但是“b”不是一個標記條目）。

5．CPU 0接收“讀”消息，隨后發送包含原始“b”值的緩存行給CPU1。它也標記該緩存行的復制為“shared”狀態。

6．CPU 1讀取到包含“b”的緩存行，并將它復制到本地緩存中。

7．CPU 1現在可以裝載“b”的值了，但是，由于它發現其值仍然為“0”，因此它重復執行while語句。“b”的新值被安全的隱藏在CPU0的存儲緩沖區中。

8．CPU 1接收到“讀使無效”消息，發送包含“a”的緩存行給CPU 0，并且使它的緩存行無效。

9．CPU 0接收到包含“a”的緩存行，使用存儲緩沖區的值替換緩存行，將這一行設置為“modified”狀態。

10．由于被存儲的“a”是存儲緩沖區中唯一被smp_mb()標記的條目，因此CPU0能夠存儲“b”的新值到緩存行中，除非包含“b”的緩存行當前處于“shared”狀態。

11．CPU 0發送一個“使無效”消息給CPU 1。

12．CPU 1接收到“使無效”消息，使包含“b”的緩存行無效，并且發送一個“使無效應答”消息給 CPU 0。

13．CPU 1執行while(b == 0) continue，但是包含“b”的緩存行不在它的緩存中，因此它發送一個“讀”消息給 CPU 0。

14．CPU 0接收到“使無效應答”消息，將包含“b”的緩存行設置成“exclusive”狀態。CPU 0現在存儲新的“b”值到緩存行。

15．CPU 0接收到“讀”消息，同時發送包含新的“b”值的緩存行給 CPU 1。它也標記該緩存行的復制為“shared”狀態。

16．CPU 1接收到包含“b”的緩存行，并將它復制到本地緩存中。

17．CPU 1現在能夠裝載“b”的值了，由于它發現“b”的值為1，它退出while循環并執行下一條語句。

18．CPU 1執行assert(a== 1)，但是包含“a”的緩存行不在它的緩存中。一旦它從CPU0獲得這個緩存行，它將使用最新的“a”的值，因此斷言語句將通過。

正如你看到的那樣，這個過程涉及不少工作。即使某些事情從直覺上看是簡單的操作，就像“加載a的值”這樣的操作，都會包含大量復雜的步驟。

前面提到的，其實是寫端的屏障，它解決Write buffer引入的內存亂序。接下來我們看看讀端的屏障，它解決使無效隊列引入的內存亂序。

要避免使無效隊列例子中的錯誤，應當再使用讀端內存屏障：

讀端內存屏障指令能夠與使無效隊列交互，這樣，當一個特定的CPU執行一個內存屏障時，它標記無效隊列中的所有條目，并強制所有后續的裝載操作進行等待，直到所有標記的條目都保存到CPU的Cache中。因此，我們可以在bar函數中添加一個內存屏障，如下：

1 void foo(void)

2 {

3 a = 1;

4 smp_mb();

5 b = 1;

6 }

7

8 void bar(void)

9 {

10 while (b == 0) continue;

11 smp_mb();

12 assert(a == 1);

13 }

有了這個變化后，操作順序可能如下：

1．CPU 0執行a= 1。相應的緩存行在CPU0的緩存中是只讀的，因此CPU0將“a”的新值放入它的存儲緩沖區，并且發送一個“使無效”消息以刷新CPU1相應的緩存行。

2．CPU 1 執行while(b == 0) continue，但是包含“b”的緩存行不在它的緩存中，因此它發送一個“讀”消息。

3．CPU 1 接收到 CPU 0的“使無效”消息，將它排隊，并立即響應它。

4．CPU 0 接收到CPU1的響應，因此它放心的通過第4行的smp_mb()語句，將“a”從它的存儲緩沖區移到緩存行。

5．CPU 0 執行b= 1。它已經擁有該緩存行（換句話說, 緩存行已經處于“modified”或者“exclusive”狀態），因此它存儲“b”的新值到緩存行。

6．CPU 0 接收到“讀”消息，并且發送包含新的“b”值的緩存行給CPU1，同時在自己的緩存中，標記緩存行為“shared”狀態。

7．CPU 1 接收到包含“b”的緩存行并更新到它的緩存中。

8．CPU 1 現在結束執行while (b == 0) continue，因為它發現“b”的值為 1，它處理下一條語句，這是一條內存屏障指令。

9．CPU 1 必須停頓，直到它處理完使無效隊列中的所有消息。

10．CPU 1 處理已經入隊的“使無效”消息，從它的緩存中使無效包含“a”的緩存行。

11．CPU 1 執行assert(a== 1)，由于包含“a”的緩存行已經不在它的緩存中，它發送一個“讀”消息。

12．CPU 0 以包含新的“a”值的緩存行響應該“讀”消息。

13．CPU 1 接收到該緩存行，它包含新的“a”的值1，因此斷言不會被觸發。

即使有很多MESI消息傳遞，CPU最終都會正確的應答。這一節闡述了CPU設計者為什么必須格外小心地處理它們的緩存一致性優化操作。

但是，這里真的需要一個讀端內存屏障么？在assert()之前，不是有個循環么？

難道在循環結束之前，會執行assert(a == 1)？

對此有疑問的讀者，您需要補充一點關于猜測（冒險）執行的背景知識！可以找CPU參考手冊看看。簡單的說，在循環的時候，a== 1這個比較條件，有可能會被CPU預先加載a的值到流水線中。臨時結果不會被保存到Cache或者Write buffer中，而是在CPU流水線中的臨時結果寄存器中暫存起來 。

這是不是非常的反直覺？然而事實就是如此。

對CPU世界中反直覺的東西有興趣的朋友，甚至可以看看量子力學方面的書，量子計算機真的需要懂量子力學。讓《深入理解并行編程》一書中提到的“薛定諤的貓”來燒一下腦，這只貓已經折磨了無數天才的大腦。除了霍金，還有愛因斯坦的大腦！

五、關于內存屏障進一步的思考

本文僅僅從硬件的角度，引申出內存屏障。其目的是為了后續文章中，更好的講解RCU。因此，并不會對內存屏障進行深入的剖析。但是，對于理解RCU來說，本文中的內存屏障知識已經可以了。

審核編輯：劉清