一、內(nèi)存Cache還有哪些不足？

上一篇文章我們談到了內(nèi)存Cache，并且描述了典型的Cache一致性協(xié)議MESI。Cache的根本目的，是解決內(nèi)存與CPU速度多達(dá)兩個(gè)數(shù)量級(jí)的性能差異。一個(gè)包含Cache的計(jì)算機(jī)系統(tǒng)，其結(jié)構(gòu)可以簡(jiǎn)單的表示為下圖：

僅僅只有Cache的計(jì)算機(jī)系統(tǒng)，它還存在如下問(wèn)題：

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

2、在發(fā)生“warmup cache miss”、“capacity miss”、“associativity miss”時(shí)，CPU必須等待從內(nèi)存中讀取數(shù)據(jù)，此時(shí)CPU會(huì)處于一種Stall的狀態(tài)。其等待時(shí)間可能達(dá)到幾百個(gè)CPU指令周期。

顯然，這是現(xiàn)代計(jì)算機(jī)不能承受之重：）

二、Write buffer是為了解決什么問(wèn)題？

如果CPU僅僅是執(zhí)行foo = 1這樣的語(yǔ)句，它其實(shí)無(wú)須從內(nèi)存或者緩存中讀取foo現(xiàn)在的值。因?yàn)闊o(wú)論foo當(dāng)前的值是什么，它都會(huì)被覆蓋。在僅僅只有Cache的系統(tǒng)中，foo = 1 這樣的操作也會(huì)形成寫停頓。自然而然的，CPU設(shè)計(jì)者應(yīng)當(dāng)會(huì)想到在Cache 和CPU之間再添加一級(jí)緩存。由于這樣的緩存主要是應(yīng)對(duì)寫操作引起的Cache Miss，并且緩存的數(shù)據(jù)與寫操作相關(guān)，因此CPU設(shè)計(jì)者將它命名為“Write buffer”。調(diào)整后的結(jié)構(gòu)示意圖如下(圖中的store buffer即為write buffer)：

通過(guò)增加這些Write buffer，CPU可以簡(jiǎn)單的將要保存的數(shù)據(jù)放到Write buffer 中，并且繼續(xù)運(yùn)行，而不會(huì)真正去等待Cache從內(nèi)存中讀取數(shù)據(jù)并返回。

對(duì)于特定CPU來(lái)說(shuō)，這些Write buffer是屬于本地的?；蛘咴谟布嗑€程系統(tǒng)中，它對(duì)于特定核來(lái)說(shuō)，是屬于本地的。無(wú)論哪一種情況，一個(gè)特定CPU僅僅允許訪問(wèn)分配給它的Writebuffer。例如，在上圖中，CPU 0不能訪問(wèn)CPU 1的存儲(chǔ)緩沖，反之亦然。

Write buffer進(jìn)一步提升了系統(tǒng)性能，但是它也會(huì)為硬件設(shè)計(jì)者帶來(lái)一些困擾：

第一個(gè)困擾：違反了自身一致性。

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

1 a = 1;

2 b = a + 1;

3 assert(b == 2);

沒(méi)有哪一位軟件工程師希望斷言被觸發(fā)！

然而，如果采用上圖中的簡(jiǎn)單系統(tǒng)結(jié)構(gòu)，斷言確實(shí)會(huì)被觸發(fā)。理解這一點(diǎn)的關(guān)鍵在于：a最初被CPU 1所擁有，而CPU 0在執(zhí)行a = 1時(shí)，將a的新值存儲(chǔ)在CPU 0的Write buffer中。

在這個(gè)簡(jiǎn)單系統(tǒng)中，觸發(fā)斷言的事件順序可能如下：

1．CPU 0 開始執(zhí)行a = 1。

2．CPU 0在緩存中查找“a”，并且發(fā)現(xiàn)緩存缺失。

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

4．CPU 0將“a”記錄到存儲(chǔ)緩沖區(qū)。

5．CPU 1接收到“讀使無(wú)效”消息，它通過(guò)發(fā)送緩存行數(shù)據(jù)，并從它的緩存行中移除數(shù)據(jù)來(lái)響應(yīng)這個(gè)消息。

6．CPU 0開始執(zhí)行b = a + 1。

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

8．CPU 0從它的緩存中讀取到“a”的值，發(fā)現(xiàn)其值為0。

9．CPU 0將存儲(chǔ)隊(duì)列中的條目應(yīng)用到最近到達(dá)的緩存行，設(shè)置緩存行中的“a”的值為1。

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

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

針對(duì)這種情況，硬件設(shè)計(jì)者對(duì)軟件工程師還是給予了必要的同情。他們會(huì)對(duì)系統(tǒng)進(jìn)行稍許的改進(jìn)，如下圖：

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

Write buffer帶來(lái)的第二個(gè)困擾，是違反了全局內(nèi)存序?？紤]如下的代碼順序，其中變量“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 }

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

1．CPU 0 執(zhí)行a = 1。緩存行不在CPU0的緩存中，因此CPU0將“a”的新值放到Write buffer，并發(fā)送一個(gè)“讀使無(wú)效”消息。

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

3．CPU 0 執(zhí)行 b = 1，它已經(jīng)擁有了該緩存行（換句話說(shuō)，緩存行要么已經(jīng)處于“modified”，要么處于“exclusive”狀態(tài)），因此它存儲(chǔ)新的“b”值到它的緩存行中。

4．CPU 0 接收到“讀”消息，并且發(fā)送緩存行中的最近更新的“b”的值到CPU1，同時(shí)將緩存行設(shè)置為“shared”狀態(tài)。

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

6．CPU 1 現(xiàn)在結(jié)束執(zhí)行while (b ==0) continue，因?yàn)樗l(fā)現(xiàn)“b”的值是1，它開始處理下一條語(yǔ)句。

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

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

9．CPU 0 接收到包含“a”的緩存行，并且及時(shí)將存儲(chǔ)緩沖區(qū)的數(shù)據(jù)保存到緩存行中，CPU1的斷言失敗受害于該緩存行。

請(qǐng)注意，“內(nèi)存屏障”已經(jīng)在這里隱隱約約露出了它鋒利的爪子?。。?！

三、使無(wú)效隊(duì)列又是為了解決什么問(wèn)題？

一波未平，另一波再起。

問(wèn)題的復(fù)雜性還不僅僅在于Writebuffer，因?yàn)閮H僅有Write buffer，硬件還會(huì)形成嚴(yán)重的性能瓶頸。

問(wèn)題在于，每一個(gè)核的Writebuffer相對(duì)而言都比較小，這意味著執(zhí)行一段較小的存儲(chǔ)操作序列的CPU，很快就會(huì)填滿它的Writebuffer。此時(shí)，CPU在能夠繼續(xù)執(zhí)行前，必須等待Cache刷新操作完成，以清空它的Write buffer。

清空Cache是一個(gè)耗時(shí)的操作，因?yàn)楸仨氁谒贑PU之間廣播MESI消息(使無(wú)效消息)，并等待對(duì)這些MESI消息的響應(yīng)。為了加快MESI消息響應(yīng)速度，CPU設(shè)計(jì)者增加了使無(wú)效隊(duì)列。也就是說(shuō)，CPU將接收到的使無(wú)效消息暫存起來(lái)，在發(fā)送使無(wú)效消息應(yīng)答時(shí)，并不真正將Cache中的值無(wú)效。而是等待在合適的時(shí)候，延遲使無(wú)效操作。

下圖是增加了使無(wú)效隊(duì)列的系統(tǒng)結(jié)構(gòu)：

將一個(gè)條目放進(jìn)使無(wú)效隊(duì)列，實(shí)際上是由CPU承諾：在發(fā)送任何與該緩存行相關(guān)的MESI協(xié)議消息前，處理該條目。在Cache競(jìng)爭(zhēng)不太劇烈的情況下，CPU會(huì)很出色地完成此事。

使無(wú)效隊(duì)列帶來(lái)的問(wèn)題是：在沒(méi)有真正將Cache無(wú)效之前，就告訴其他CPU已經(jīng)使無(wú)效了。這多少有一點(diǎn)欺騙的意思。然而現(xiàn)代CPU確實(shí)是這樣設(shè)計(jì)的。

這個(gè)事實(shí)帶來(lái)了額外的內(nèi)存亂序的機(jī)會(huì)，看看如下示例：

假設(shè)“a”和“b”被初始化為0，“a”是只讀的（MESI“shared”狀態(tài)），“b”被CPU 0擁有（MESI“exclusive”或者“modified”狀態(tài)）。然后假設(shè)CPU 0執(zhí)行foo()而CPU1執(zhí)行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執(zhí)行a = 1。在CPU0中，相應(yīng)的緩存行是只讀的，因此CPU 0將“a”的新值放入存儲(chǔ)緩沖區(qū)，并發(fā)送一個(gè)“使無(wú)效”消息，這是為了使CPU1的緩存中相應(yīng)的緩存行失效。

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

3．CPU 1接收到CPU 0的“使無(wú)效”消息，將它排隊(duì)，并立即響應(yīng)該消息。

4．CPU 0接收到來(lái)自于CPU 1的響應(yīng)消息，因此它放心的通過(guò)第4行的smp_mb()，從存儲(chǔ)緩沖區(qū)移動(dòng)“a”的值到緩存行。

5．CPU 0執(zhí)行b = 1。它已經(jīng)擁有這個(gè)緩存行（也就是說(shuō)，緩存行已經(jīng)處于“modified”或者“exclusive”狀態(tài)），因此它將“b”的新值存儲(chǔ)到緩存行中。

6．CPU 0接收到“讀”消息，并且發(fā)送包含“b”的新值的緩存行到CPU 1，同時(shí)在自己的緩存中，標(biāo)記緩存行為“shared”狀態(tài)。

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

8．CPU 1現(xiàn)在可以完成while (b ==0) continue，因?yàn)樗l(fā)現(xiàn)“b”的值為1，接著處理下一條語(yǔ)句。

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

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

四、內(nèi)存屏障

既然硬件設(shè)計(jì)者通過(guò)Write buffer和使無(wú)效隊(duì)列引入了額外的內(nèi)存亂序問(wèn)題，那么就應(yīng)當(dāng)為軟件工程師提供某種方法來(lái)解決這個(gè)問(wèn)題。即使相應(yīng)的解決方法會(huì)折磨軟件工程師。

答案就是內(nèi)存屏障。對(duì)于Linux內(nèi)核資深工程師來(lái)說(shuō)，這個(gè)答案也顯得比較沉重，它太折磨人了：）

我們先看看Write buffer一節(jié)中，觸發(fā)斷言的例子，應(yīng)該怎么修改。

在那個(gè)例子中，硬件設(shè)計(jì)者不能直接幫助我們，因?yàn)?CPU沒(méi)有辦法識(shí)別那些相關(guān)聯(lián)的變量（例子中的a和b），更不用說(shuō)它們?nèi)绾侮P(guān)聯(lián)。因此，硬件設(shè)計(jì)者提供內(nèi)存屏障指令，以允許軟件告訴CPU這些關(guān)系的存在。程序必須修改，以包含內(nèi)存屏障：

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 }

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

1、簡(jiǎn)單的停頓下來(lái)，直到存儲(chǔ)緩沖區(qū)變成空；

2、也可能是使用存儲(chǔ)緩沖區(qū)來(lái)持有后續(xù)的存儲(chǔ)操作，直到前面所有的存儲(chǔ)緩沖區(qū)已經(jīng)被保存到緩存行中。

理解其中第2點(diǎn)，能夠幫助我們理解“內(nèi)存屏障”這個(gè)單詞的來(lái)歷！！

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

1．CPU 0執(zhí)行a= 1。緩存行不在CPU0的緩存中，因此CPU 0將“a”的新值放到存儲(chǔ)緩沖中，并發(fā)送一個(gè)“讀使無(wú)效”消息。

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

3．CPU 0執(zhí)行smp_mb()，并標(biāo)記當(dāng)前所有存儲(chǔ)緩沖區(qū)的條目。（也就是說(shuō)a = 1這個(gè)條目）。

4．CPU 0執(zhí)行b= 1。它已經(jīng)擁有這個(gè)緩存行了。（也就是說(shuō), 緩存行已經(jīng)處于“modified”或者“exclusive”狀態(tài)），但是在存儲(chǔ)緩沖區(qū)中存在一個(gè)標(biāo)記條目。因此，它不將“b”的新值存放到緩存行，而是存放到存儲(chǔ)緩沖區(qū)中。（但是“b”不是一個(gè)標(biāo)記條目）。

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

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

7．CPU 1現(xiàn)在可以裝載“b”的值了，但是，由于它發(fā)現(xiàn)其值仍然為“0”，因此它重復(fù)執(zhí)行while語(yǔ)句?！癰”的新值被安全的隱藏在CPU0的存儲(chǔ)緩沖區(qū)中。

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

9．CPU 0接收到包含“a”的緩存行，使用存儲(chǔ)緩沖區(qū)的值替換緩存行，將這一行設(shè)置為“modified”狀態(tài)。

10．由于被存儲(chǔ)的“a”是存儲(chǔ)緩沖區(qū)中唯一被smp_mb()標(biāo)記的條目，因此CPU0能夠存儲(chǔ)“b”的新值到緩存行中，除非包含“b”的緩存行當(dāng)前處于“shared”狀態(tài)。

11．CPU 0發(fā)送一個(gè)“使無(wú)效”消息給CPU 1。

12．CPU 1接收到“使無(wú)效”消息，使包含“b”的緩存行無(wú)效，并且發(fā)送一個(gè)“使無(wú)效應(yīng)答”消息給 CPU 0。

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

14．CPU 0接收到“使無(wú)效應(yīng)答”消息，將包含“b”的緩存行設(shè)置成“exclusive”狀態(tài)。CPU 0現(xiàn)在存儲(chǔ)新的“b”值到緩存行。

15．CPU 0接收到“讀”消息，同時(shí)發(fā)送包含新的“b”值的緩存行給 CPU 1。它也標(biāo)記該緩存行的復(fù)制為“shared”狀態(tài)。

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

17．CPU 1現(xiàn)在能夠裝載“b”的值了，由于它發(fā)現(xiàn)“b”的值為1，它退出while循環(huán)并執(zhí)行下一條語(yǔ)句。

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

正如你看到的那樣，這個(gè)過(guò)程涉及不少工作。即使某些事情從直覺(jué)上看是簡(jiǎn)單的操作，就像“加載a的值”這樣的操作，都會(huì)包含大量復(fù)雜的步驟。

前面提到的，其實(shí)是寫端的屏障，它解決Write buffer引入的內(nèi)存亂序。接下來(lái)我們看看讀端的屏障，它解決使無(wú)效隊(duì)列引入的內(nèi)存亂序。

要避免使無(wú)效隊(duì)列例子中的錯(cuò)誤，應(yīng)當(dāng)再使用讀端內(nèi)存屏障：

讀端內(nèi)存屏障指令能夠與使無(wú)效隊(duì)列交互，這樣，當(dāng)一個(gè)特定的CPU執(zhí)行一個(gè)內(nèi)存屏障時(shí)，它標(biāo)記無(wú)效隊(duì)列中的所有條目，并強(qiáng)制所有后續(xù)的裝載操作進(jìn)行等待，直到所有標(biāo)記的條目都保存到CPU的Cache中。因此，我們可以在bar函數(shù)中添加一個(gè)內(nèi)存屏障，如下：

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 }

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

1．CPU 0執(zhí)行a= 1。相應(yīng)的緩存行在CPU0的緩存中是只讀的，因此CPU0將“a”的新值放入它的存儲(chǔ)緩沖區(qū)，并且發(fā)送一個(gè)“使無(wú)效”消息以刷新CPU1相應(yīng)的緩存行。

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

3．CPU 1 接收到 CPU 0的“使無(wú)效”消息，將它排隊(duì)，并立即響應(yīng)它。

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

5．CPU 0 執(zhí)行b= 1。它已經(jīng)擁有該緩存行（換句話說(shuō), 緩存行已經(jīng)處于“modified”或者“exclusive”狀態(tài)），因此它存儲(chǔ)“b”的新值到緩存行。

6．CPU 0 接收到“讀”消息，并且發(fā)送包含新的“b”值的緩存行給CPU1，同時(shí)在自己的緩存中，標(biāo)記緩存行為“shared”狀態(tài)。

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

8．CPU 1 現(xiàn)在結(jié)束執(zhí)行while (b == 0) continue，因?yàn)樗l(fā)現(xiàn)“b”的值為 1，它處理下一條語(yǔ)句，這是一條內(nèi)存屏障指令。

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

10．CPU 1 處理已經(jīng)入隊(duì)的“使無(wú)效”消息，從它的緩存中使無(wú)效包含“a”的緩存行。

11．CPU 1 執(zhí)行assert(a== 1)，由于包含“a”的緩存行已經(jīng)不在它的緩存中，它發(fā)送一個(gè)“讀”消息。

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

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

即使有很多MESI消息傳遞，CPU最終都會(huì)正確的應(yīng)答。這一節(jié)闡述了CPU設(shè)計(jì)者為什么必須格外小心地處理它們的緩存一致性優(yōu)化操作。

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

難道在循環(huán)結(jié)束之前，會(huì)執(zhí)行assert(a == 1)？

對(duì)此有疑問(wèn)的讀者，您需要補(bǔ)充一點(diǎn)關(guān)于猜測(cè)（冒險(xiǎn)）執(zhí)行的背景知識(shí)！可以找CPU參考手冊(cè)看看。簡(jiǎn)單的說(shuō)，在循環(huán)的時(shí)候，a== 1這個(gè)比較條件，有可能會(huì)被CPU預(yù)先加載a的值到流水線中。臨時(shí)結(jié)果不會(huì)被保存到Cache或者Write buffer中，而是在CPU流水線中的臨時(shí)結(jié)果寄存器中暫存起來(lái) 。

這是不是非常的反直覺(jué)？然而事實(shí)就是如此。

審核編輯：劉清