本文從 CPU、緩存、內(nèi)存屏障、CAS到原子操作，再到無鎖實踐，逐一詳細介紹。

01存儲體系結(jié)構(gòu)?

速度快的存儲硬件成本高、容量小，速度慢的成本低、容量大。為了權(quán)衡成本和速度，計算機存儲分了很多層次，揚長避短，有寄存器、L1 cache、L2 cache、L3 cache、主存（內(nèi)存）和硬盤等。圖1 展示了現(xiàn)代存儲體系結(jié)構(gòu)。

圖1

根據(jù)程序的空間局部性和時間局部性原理，緩存命中率可以達到?70～90%?。因此，增加緩存可以讓整個存儲系統(tǒng)的性能接近寄存器，并且每字節(jié)的成本都接近內(nèi)存，甚至是磁盤。

所以緩存是存儲體系結(jié)構(gòu)的靈魂。

02緩存原理

2.1 緩存的工作原理

cache line（緩存行）是緩存進行管理的最小存儲單元，也叫緩存塊，每個 cache line?包含?Flag、Tag?和?Data?，通常 Data 大小是?64 字節(jié)，但不同型號 CPU 的 Flag 和 Tag 可能不相同。從內(nèi)存向緩存加載數(shù)據(jù)是按整個緩存行加載的，一個緩存行和一個相同大小的內(nèi)存塊對應(yīng)。

圖2

圖2中，緩存是按照矩陣方式排列(M × N)，橫向是組(Set)，縱向是路(Way)。每一個元素是緩存行(cache line)。

那么給定一個虛擬地址?addr?如何在緩存中定位它呢？首先把它所在的組號找到，即：

然后遍歷該組所有的路，找到?cache line?中的?Tag?與?addr?中?Tag?相等為止，所有路都沒有匹配成功，那么緩存未命中。

我電腦的CPU信息：

我電腦的緩存信息：

通過緩存行大小和路數(shù)可以倒推出緩存的組數(shù)，即：

2.2 緩存行替換策略

目前最常用的緩存替換策略是最近最少使用算法（Least Recently Used ，LRU）或者是類似 LRU 的算法。

LRU?算法比較簡單，如圖3，緩存有 4 路，并且訪問的地址都哈希到了同一組，訪問順序是 D1、D2、D3、D4 和 D5，那么 D1 會被 D5 替換掉。算法的實現(xiàn)方式有很多種，最簡單的實現(xiàn)方式是位矩陣。

首先，定義一個行、列都與緩存路數(shù)相同的矩陣。當(dāng)訪問某個路對應(yīng)的緩存行時，先將該路對應(yīng)的所有行置為 1，然后再將該路對應(yīng)的所有列置為 0。

最近最少使用的緩存行所對應(yīng)的矩陣行中 1 的個數(shù)最少，最先被替換出去。

圖3

2.3 緩存缺失

緩存缺失就是緩存未命中，需要把內(nèi)存中數(shù)據(jù)加載到緩存，所以運行速度會變慢。

就拿我的電腦來測試，L1d 的緩存大小是 32KB（32768B），8路，緩存行大小 64B，那么

運行下面的代碼

結(jié)果：循環(huán) 160000000 次，耗時 301 ms。除了第一次未命中緩存，后面每次讀寫數(shù)據(jù)都能命中緩存。

調(diào)整上面的代碼，并運行

結(jié)果：循環(huán) 160000000 次，耗時 959 ms。每一次讀寫數(shù)據(jù)都沒有命中緩存，所以耗時增加了 2 倍。

2.4 程序局部性

程序局部性就是讀寫內(nèi)存數(shù)據(jù)時讀寫連續(xù)的內(nèi)存空間，目的是讓緩存可以命中，減少緩存缺失導(dǎo)致替換的開銷。

我電腦上運行下面代碼

結(jié)果：循環(huán) 100000000 次，耗時 314 ms。利用了程序局部性原理，緩存命中率高。

修改上面的代碼如下，并運行

結(jié)果：循環(huán) 100000000?次，耗時 1187 ms。沒有利用程序局部性原理，緩存命中率低，所以耗時增加了 2 倍。

2.5 偽共享（false-sharing）

當(dāng)兩個線程同時各自修改兩個相鄰的變量，由于緩存是按緩存行來整體組織的，當(dāng)一個線程對緩存行中數(shù)據(jù)執(zhí)行寫操作時，必須通知其他線程該緩存行失效，導(dǎo)致另一個線程從緩存中讀取其想修改的數(shù)據(jù)失敗，必須從內(nèi)存重新加載，導(dǎo)致性能下降。

我電腦運行下面代碼

結(jié)果：耗時 512 ms，原因上面提到了，就是兩個線程互相影響，使對方的緩存行失效，導(dǎo)致直接從內(nèi)存讀取數(shù)據(jù)。

解決辦法是對上面代碼做如下修改：

結(jié)果：耗時 181 ms，原因是通過 long long noop[8] 把兩個數(shù)據(jù)（a 和 b）劃分到兩個不同的緩存行中，不再互相使對方的緩存失效，所以速度變快了。

本小節(jié)的測試代碼都沒有開啟編譯器優(yōu)化，即編譯選項為-O0?。?

【文章福利】小編推薦自己的Linux內(nèi)核技術(shù)交流群:【749907784】整理了一些個人覺得比較好的學(xué)習(xí)書籍、視頻資料共享在群文件里面，有需要的可以自行添加哦！?。。ê曨l教程、電子書、實戰(zhàn)項目及代碼)? ? ?

緩存一致性協(xié)議

在單核時代，增加緩存可以大大提高讀寫速度，但是到了多核時代，卻引入了緩存一致性問題，如果有一個核心修改了緩存行中的某個值，那么必須有一種機制保證其他核心能夠觀察到這個修改。

3.1 緩存寫策略

從緩存和內(nèi)存的更新關(guān)系來看，分為：

• 寫回（write-back）對緩存的修改不會立刻傳播到內(nèi)存，只有當(dāng)緩存行被替換時，這些被修改的緩存行才會寫回并覆蓋內(nèi)存中過時的數(shù)據(jù)。

• 寫直達（write through）緩存中任何一個字節(jié)的修改，都會立刻穿透緩存直接傳播到內(nèi)存，這種比較耗時。

從寫緩存時 CPU 之間的更新策略來看，分為：

• 寫更新（Write Update）每次緩存寫入新的值，該核心必須發(fā)起一次總線請求，通知其他核心更新他們緩存中對應(yīng)的值。

• 壞處：寫更新會占用很多總線帶寬；

• 好處：其他核心能立刻獲得最新的值。

• 寫無效（Write Invalidate）每次緩存寫入新的值，都將其他核心緩存中對應(yīng)的緩存行置為無效。

• 壞處：當(dāng)其他核心再次訪問該緩存時，發(fā)現(xiàn)緩存行已經(jīng)失效，必須從內(nèi)存中重新載入最新的數(shù)據(jù)；

• 好處：多次寫操作只需發(fā)一次總線事件，第一次寫已經(jīng)將其他核心緩存行置為無效，之后的寫不必再更新狀態(tài)，這樣可以有效地節(jié)省核心間總線帶寬。

從寫緩存時數(shù)據(jù)是否被加載來看，分為：

• 寫分配（Write Allocate）在寫入數(shù)據(jù)前將數(shù)據(jù)讀入緩存。當(dāng)緩存塊中的數(shù)據(jù)在未來讀寫概率較高，也就是程序空間局部性較好時，寫分配的效率較好。

• 寫不分配（Not Write Allocate）在寫入數(shù)據(jù)時，直接將數(shù)據(jù)寫入內(nèi)存，并不先將數(shù)據(jù)塊讀入緩存。當(dāng)數(shù)據(jù)塊中的數(shù)據(jù)在未來使用的概率較低時，寫不分配性能較好。

3.2?MESI 協(xié)議

MESI協(xié)議是?個基于失效的緩存?致性協(xié)議，是?持寫回（write-back）緩存的最常?協(xié)議。也稱作伊利諾伊協(xié)議 (Illinois protocol，因為是在伊利諾伊?學(xué)厄巴納-?檳分校被發(fā)明的)。

為了解決多個核心之間的數(shù)據(jù)傳播問題，提出了總線嗅探（Bus Snooping）策略。本質(zhì)上就是把所有的讀寫請求都通過總線（Bus）廣播給所有的核心，然后讓各個核心去嗅探這些請求，再根據(jù)本地的狀態(tài)進行響應(yīng)。

3.2.1 狀態(tài)

• 已修改Modified (M)：緩存?是臟的，與主存的值不同。如果別的CPU內(nèi)核要讀主存這塊數(shù)據(jù)，該緩存?必須回寫到主存，狀態(tài)變?yōu)楣蚕?S).

• 獨占Exclusive (E)：緩存?只在當(dāng)前緩存中，但是?凈的，緩存數(shù)據(jù)等于主存數(shù)據(jù)。當(dāng)別的緩存讀取它時，狀態(tài)變?yōu)楣蚕恚划?dāng)前寫數(shù)據(jù)時，變?yōu)橐研薷臓顟B(tài)。

• 共享Shared (S)：緩存?也存在于其它緩存中且是?凈的。緩存?可以在任意時刻拋棄。

• ?效Invalid (I)：緩存?是?效的。

這些狀態(tài)信息實際上存儲在緩存行（cache line）的?Flag?里。

3.2.2 事件

• 處理器對緩存的請求:

• PrRd：核心請求從緩存塊中讀出數(shù)據(jù)；

• PrWr：核心請求向緩存塊寫入數(shù)據(jù)。

• 總線對緩存的請求:

• BusRd：總線嗅探器收到來自其他核心的讀出緩存請求；

• BusRdX：總線嗅探器收到另一核心寫?個其不擁有的緩存塊的請求；

• BusUpgr：總線嗅探器收到另一核心寫?個其擁有的緩存塊的請求；

• Flush：總線嗅探器收到另一核心把一個緩存塊寫回到主存的請求；

• FlushOpt：總線嗅探器收到一個緩存塊被放置在總線以提供給另一核心的請求，和 Flush 類似，但只不過是從緩存到緩存的傳輸請求。

3.2.3?狀態(tài)機

圖4

表1是對狀態(tài)機圖4 的詳解講解（選讀）

3.2.4?動畫演示

圖5

各家 CPU 廠商沒有都完全按照 MESI 實現(xiàn)緩存一致性協(xié)議，導(dǎo)致 MESI 有很多變種，例如：Intel 采用的 MESIF 和 AMD 采用的 MOESI，ARM 大部分采用的是 MESI，少部分使用的是 MOESI 。

3.3?MOESI 協(xié)議（選讀）

MOESI 是一個完整的緩存一致性協(xié)議，它包含了其他協(xié)議中常用的所有可能狀態(tài)。除了四種常見的 MESI 協(xié)議狀態(tài)之外，還有第五種?Owned?狀態(tài)，表示修改和共享的數(shù)據(jù)。

這就避免了在共享數(shù)據(jù)之前將修改過的數(shù)據(jù)寫回主存的需要。雖然數(shù)據(jù)最終仍然必須寫回，但寫回可能是延遲的。

• 已修改Modified (M)：緩存?是臟的（dirty），與主存的值不同，并且緩存具有系統(tǒng)中唯一有效數(shù)據(jù)。處于修改狀態(tài)的緩存可以將數(shù)據(jù)提供給另一個讀取器，而無需將其傳輸?shù)絻?nèi)存，然后狀態(tài)變?yōu)?O，讀取者變?yōu)?S。

• 擁有Owned(O)：緩存?是臟的（dirty），與主存的值不同，但不是系統(tǒng)中唯一有效副本，一定存在其他的 S。為其他核心提供讀請求，較少核心間總線帶寬。
  

• 獨占Exclusive (E)：緩存?只在當(dāng)前緩存中，但是?凈的（clean），緩存數(shù)據(jù)同于主存數(shù)據(jù)。當(dāng)別的緩存讀取它時，狀態(tài)變?yōu)楣蚕恚划?dāng)前寫數(shù)據(jù)時，變?yōu)橐研薷臓顟B(tài)。

• 共享Shared (S)：緩存?也存在于其它緩存中且不一定是?凈的。如果 O 存在，就是臟的，反之亦然。

• ?效Invalid (I)：緩存?是?效的。

3.4?MESIF 協(xié)議（選讀）

MESIF 是一個緩存一致性和記憶連貫協(xié)議，該協(xié)議由五個狀態(tài)組成：已修改（M），互斥（E），共享（S），無效（I）和轉(zhuǎn)發(fā)（F）。

M，E，S 和 I 狀態(tài)與 MESI 協(xié)議一致。F 狀態(tài)是 S 狀態(tài)的一種特殊形式，當(dāng)系統(tǒng)中有多個 S 時，必須選取一個轉(zhuǎn)換為 F，只有 F 狀態(tài)的負責(zé)應(yīng)答。通常是最后持有該副本的轉(zhuǎn)換為 F，注意?F 是干凈的數(shù)據(jù)。

該協(xié)議與 MOESI 協(xié)議有較大的不同，也遠比 MOESI 協(xié)議復(fù)雜。該協(xié)議由 Intel 的?快速通道互聯(lián)?QPI（QuickPath Interconnect）技術(shù)引入，其主要目的是解決“基于點到點互聯(lián)的非一致性內(nèi)存訪問（Non-uniform memory access，NUMA）處理器系統(tǒng)”的緩存一致性問題，而不是“基于共享總線的一致性內(nèi)存訪問（Uniform Memory Access，?UMA）處理器系統(tǒng)”的緩存一致性問題。

04內(nèi)存屏障（Memory Barriers）

編譯器和處理器都必須遵守重排序規(guī)則。在單處理器的情況下，不需要任何額外的操作便能保持正確的順序。但是對于多處理器來說，保證一致性通常需要增加內(nèi)存屏障指令。即使編譯器可以優(yōu)化掉字段的訪問（例如因為未使用加載到的值），編譯器仍然需要生成內(nèi)存屏障，就好像字段訪問仍然存在一樣（可以單獨將內(nèi)存屏障優(yōu)化掉）。

內(nèi)存屏障只與內(nèi)存模型中的高級概念（例如?acquire?和?release）間接相關(guān)。內(nèi)存屏障指令只直接控制 CPU 與其緩存的交互，以及它的寫緩沖區(qū)（持有等待刷新到內(nèi)存的數(shù)據(jù)的存儲）和它的用于等待加載或推測執(zhí)行指令的緩沖。這些影響可能導(dǎo)致緩存、主內(nèi)存和其他處理器之間的進一步交互。

幾乎所有的處理器都至少支持一個粗粒度的屏障指令（通常稱為?Fence，也叫全屏障），它保證了嚴格的有序性：在 Fence 之前的所有讀操作（load）和寫操作（store）先于在 Fence 之后的所有讀操作（load）和寫操作（store）執(zhí)行完。對于任何的處理器來說，這通常都是最耗時的指令之一（它的開銷通常接近甚至超過原子操作指令）。大多數(shù)處理器還支持更細粒度的屏障指令。

• LoadLoad?Barrier（讀讀屏障）指令?Load1; LoadLoad; Load2?保證了 Load1 先于 Load2 和后續(xù)所有的 load 指令加載數(shù)據(jù)。通常情況下，在執(zhí)行預(yù)測讀（speculative loads）或亂序處理（out-of-order processing）的處理器上需要顯式的 LoadLoad Barrier。在始終保證讀順序（load ordering）的處理器上，這些屏障相當(dāng)于無操作（no-ops）。

• StoreStore?Barrier（寫寫屏障）指令?Store1; StoreStore; Store2?保證了 Store1 的數(shù)據(jù)先于 Store2 及后續(xù) store 指令的數(shù)據(jù)對其他處理器可見（刷新到內(nèi)存）。通常情況下，在不保證嚴格按照順序從寫緩沖區(qū)（store buffers）或者?緩存（caches）刷新到其他處理器或內(nèi)存的處理器上，需要使用 StoreStore?Barrier。

• LoadStore?Barrier（讀寫屏障）指令?Load1; LoadStore; Store2?保證了 Load1 的加載數(shù)據(jù)先于 Store2 及后續(xù) store 指令刷新數(shù)據(jù)到主內(nèi)存。只有在亂序（out-of-order）處理器上，等待寫指令（waiting store instructions）可以繞過讀指令（loads）的情況下，才會需要使用 LoadStore 屏障。

• StoreLoad?Barrier（寫讀屏障）刷新寫緩沖區(qū)，最耗時指令?Store1; StoreLoad; Load2?保證了 Store1 的數(shù)據(jù)對其他處理器可見（刷新數(shù)據(jù)到內(nèi)存）先于 Load2 及后續(xù)的 load 指令加載數(shù)據(jù)。StoreLoad 屏障可以防止后續(xù)的讀操作錯誤地使用了 Store1 寫的數(shù)據(jù)，而不是使用來自另一個處理器的更近的對同一位置的寫。因此只有需要將對同一個位置的寫操作（stores）和隨后的讀操作（loads）分開時，才嚴格需要 StoreLoad 屏障。StoreLoad 屏障通常是開銷最大的屏障，幾乎所有的現(xiàn)代處理器都需要該屏障。之所以開銷大，部分原因是它需要禁用繞過緩存（cache）從寫緩沖區(qū)（Store Buffer）讀取數(shù)據(jù)的機制。這可以通過讓緩沖區(qū)完全刷新，外加暫停其他操作來實現(xiàn)，這就是?Fence?的效果。一般用?Fence?代替 StoreLoad?Barrier ，所以事實上，執(zhí)行 StoreLoad 指令同時也獲得了其他三個屏障的效果，但是通過組合其他屏障通常不能獲得與 StoreLoad?Barrier?相同的效果。

表2 是各處理器支持的內(nèi)存屏障和原子操作

表2

4.1 寫緩沖與寫屏障

嚴格按照MESI協(xié)議，核心0 在修改本地緩存之前，需要向其他核心發(fā)送 Invalid 消息，其他核心收到消息后，使他們本地對應(yīng)的緩存行失效，并返回?Invalid acknowledgement 消息，核心0 收到后修改緩存行。這里核心0 等待其他核心返回確認消息的時間對核心來說是漫長的。

圖6

為了解決這個問題，引入了?Store Buffer?，當(dāng)核心想修改緩存時，直接寫入?Store uffer?，無需等待，繼續(xù)處理其他事情，由?Store Buffer?完成后續(xù)工作。

圖7

這樣一來寫的速度加快了，但是引來了新問題，下面代碼的?bar 函數(shù)中的斷言可能會失敗。

第一種情況：CPU 為了提升運行效率和提高緩存命中率，采用了亂序執(zhí)行；

第二種情況：Store Buffer?在寫入時，b 所對應(yīng)的緩存行是?E?狀態(tài)，a 所對應(yīng)的緩存行是?S?狀態(tài)，因為對 b 的修改不需要核心間同步，但是修改 a 則需要，也就是 b 會先寫入緩存。與之對應(yīng) CPU1 中 a 是?S?狀態(tài)，b 是?I?狀態(tài)，由于 b 所對應(yīng)的緩存區(qū)域是?I?狀態(tài)，它就會向總線發(fā)出 BusRd 請求，那么 CPU1 就會先把 b 的最新值讀到本地，完成變量 b 值的更新，但是從緩存直接讀取 a 值是 0?。

舉一個更極端的例子

第一種情況不會發(fā)生了，原因是代碼有依賴，不會亂序執(zhí)行。但由于 Store Buffer 的存在，第二種情況仍然可能發(fā)生，原因同上。這會讓人感到更加匪夷所思。

為了解決上面問題，引入了內(nèi)存屏障，屏障的作用是前邊的讀寫操作未完成的情況下，后面的讀寫操作不能發(fā)生。這就是?Arm?上?dmb?指令的由來，它是數(shù)據(jù)內(nèi)存屏障（Data Memory Barrier）的縮寫。

加上內(nèi)存屏障后，保證了 a 和 b 的寫入緩存順序。

總的來說，Store Buffer 提升了寫性能，但放棄了緩存的順序一致性，這種現(xiàn)象稱為弱緩存一致性。通常情況下，多個 CPU 一起操作同一個變量的情況是比較少的，所以 Store Buffer 可以大幅提升程序的性能。但在需要核間同步的情況下，還是需要通過手動添加內(nèi)存屏障來保證緩存一致性。

上面解決了核間同步的寫問題，但是核間同步還有一個瓶頸，那就是讀。

4.2?失效隊列與讀屏障

前面引入 Store Buffer 提升了寫入速度，那么 invalid 消息確認速度相比起來就慢了，帶來了速度不匹配，很容易導(dǎo)致?Store Buffer?的內(nèi)容還沒及時寫到緩存里，自己就滿了，從而失去了加速的作用。

為了解決這個問題，又引入了?Invalid Queue。收到 Invalid 消息的核心立刻返回 Invalid acknowledgement 消息，然后把 Invalid 消息加入 Invalid Queue ，等到空閑的時候再去處理?Invalid?消息。

圖8

運行上面增加內(nèi)存屏障的代碼，第 11 行的斷言又可能失敗了。

核心0 中?a 所對應(yīng)的緩存行是?S?狀態(tài)，b 所對應(yīng)的緩存行是?E?狀態(tài)；核心1中 a ?所對應(yīng)的緩存行是?S?狀態(tài)，b? ?所對應(yīng)的緩存行是?I?狀態(tài)；

• 因為有內(nèi)存屏障在，a 和 b的寫入緩存的順序不會亂。

• a 先向其他核心發(fā)送 Invalid 消息，并且等待 Invalid 確認消息；

• Invalid 消息先入 核心1 對應(yīng)的 Invalid Queue 并立刻返回確認消息，等待 核心1 處理；

• 核心0 收到確認消息后把 a 寫入緩存，繼續(xù)處理 b 的寫入，由于 b 是?E?狀態(tài)，直接寫入緩存；

• 核心1 發(fā)送 BusRd 消息，讀取到新的 b 值，然后獲取?a（S?狀態(tài)）值是0，因為使其無效的消息還在?Invalid Queue 中，第 11 行斷言失敗。

引入 Invalid Queue 后，對核心1 來說看到的 a 和 b 的寫入又出現(xiàn)亂序了。

解決辦法是繼續(xù)加內(nèi)存屏障，核心1 想越過屏障必須清空?Invalid Queue，及時處理了對 a 的無效，然后讀取到新的 a 值，如下代碼：

這里使用的內(nèi)存屏障是全屏障，包括讀寫屏障，過于嚴格了，會導(dǎo)致性能下降，所以有了細粒度的讀屏障和寫屏障。

4.3?讀寫屏障分離

分離的寫屏障和讀屏障的出現(xiàn)，是為了更加精細地控制?Store Buffer?和?Invalid Queue?的順序。

• 讀屏障不允許其前后的讀操作越過屏障；

• 寫屏障不允許其前后的寫操作越過屏障；

優(yōu)化前面的代碼如下

這種修改只有在區(qū)分讀寫屏障的體系結(jié)構(gòu)里才會有作用，比如?alpha?結(jié)構(gòu)。在?x86?和?Arm?中是沒有作用的，因為 x86 采用了?TSO?模型，后面會詳細介紹，而 Arm 采用了單向屏障。

4.4 單向屏障

單向屏障 (half-way barrier) 也是一種內(nèi)存屏障，但它不是以讀寫來區(qū)分的，而是像單行道一樣，只允許單向通行，例如 ARM 中的 stlr 和 ldar 指令就是這樣。

• stlr?的全稱是 store release register，包括 StoreStore barrier 和 LoadStore barrier（場景少），通常使用 release 語義將寄存器的值寫入內(nèi)存；

• ldar?的全稱是 load acquire register，包括 LoadLoad barrier 和 LoadStore?barrier（對，你沒看錯，我沒寫錯），通常使用 acquire 語義從內(nèi)存中將值加載入寄存器；

• release?語義的內(nèi)存屏障只不允許其前面的讀寫向后越過屏障，擋前不擋后；

• acquire?語義的內(nèi)存屏障只不允許其后面的讀寫向前越過屏障，擋后不擋前;

• StoreLoad barrier 就只能使用?dmb（全屏障） 代替了。

圖9?ARM?Figure 13.2. One-way barriers

理論普及的差不多了，接下單獨來說說服務(wù)端同學(xué)工作中最常用的 x86 內(nèi)存模型，填一下 4.3 中留下的坑。未完待續(xù)......

原文作者：一起學(xué)嵌入式