本文簡介：本文從硬體的角度引申出記憶體屏障，這不是記憶體屏障的詳盡手冊，但是相關知識對于了解RCU有所幫助。這不是一篇單獨的文章，這是《謝寶友：深入了解Linux RCU》系列的第2篇，前序文章：《謝寶友：深入了解 Linux RCU 從硬體說起之記憶體屏障》 作者簡介:謝寶友，在程式設計一線工作已經有20年時間，其中接近10年時間工作于Linux作業系統。在中興通訊作業系統産品部工作期間，他作為技術總工參與的電信級嵌入式實時作業系統，獲得了行業最高獎----中國工業大獎。 同時，他也是《深入了解并行程式設計》一書的譯者。該書作者Paul E.McKeney是IBM Linux中心上司者，Linux RCU Maintainer。《深入了解RCU》系列文章整理了Paul E.McKeney的相關著作，希望能幫助讀者更深刻的了解Linux核心中非常難于了解的子產品----RCU。 聯系方式：mail:[email protected] 微信：linux-kernel
上一篇文章我們談到了記憶體Cache，并且描述了典型的Cache一緻性協定MESI。Cache的根本目的，是解決記憶體與CPU速度多達兩個數量級的性能差異。一個包含Cache的計算機系統，其結構可以簡單的表示為下圖：
僅僅隻有Cache的計算機系統，它還存在如下問題：
1、Cache的速度，雖然比記憶體有了極大的提升，但是仍然比CPU慢幾倍。
2、在發生“warmup cache miss”、“capacity miss”、“associativity miss”時，CPU必須等待從記憶體中讀取資料，此時CPU會處于一種Stall的狀态。其等待時間可能達到幾百個CPU指令周期。
顯然，這是現代計算機不能承受之重：）
如果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所擁有：
沒有哪一位軟體工程師希望斷言被觸發！
然而，如果采用上圖中的簡單系統結構，斷言确實會被觸發。了解這一點的關鍵在于：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。
假設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．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這些關系的存在。程式必須修改，以包含記憶體屏障：
記憶體屏障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．CPU 0執行a= 1。相應的緩存行在CPU0的緩存中是隻讀的，是以CPU0将“a”的新值放入它的存儲緩沖區，并且發送一個“使無效”消息以重新整理CPU1相應的緩存行。
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來說，本文中的記憶體屏障知識已經可以了。
更深入的思考包括：
1、讀屏障、寫屏障、讀依賴屏障的概念
2、各個體系架構中，屏障的實作、及其微妙的差别
3、深入思考記憶體屏障是否是必須的，有沒有可能通過修改硬體，讓屏障不再有用？
4、記憶體屏障的傳遞性，這是Linux系統中比較微妙而難于了解的概念。
5、單核架構中的屏障，是為了解決什麼問題？怎麼使用？
6、屏障在核心同步原語中的使用，滿足了什麼樣的同步原語語義？
感興趣的讀者，可以參考如下資料：
1、我在CLK 2015大會上關于記憶體屏障的演講:
http://download.csdn.net/user/xiebaoyou
2、《深入了解并行程式設計》中文版本：
http://item.jd.com/12109309.html
文章來源于微信公衆号 Linuxer (ID:linuxdev)
本文僅代表作者觀點，不代