謝寶友教你學Linux：深入理解Linux RCU之從硬件說起

據(jù)說斯蒂芬·霍金曾經(jīng)聲稱半導體制造商面臨兩個基本問題：

（1）有限的光速

（2）物質(zhì)的原子本質(zhì)

第一個難題，決定了在一個CPU周期內(nèi)，電信號無法在整個系統(tǒng)所有CPU中廣播。換句話說，某個CPU指令對一個內(nèi)存地址的寫操作，不會在這條指令執(zhí)行完畢后，馬上被其他CPU識別到操作結果。例如：CPU0對全局變量foo執(zhí)行foo = 1，當CPU 0執(zhí)行完相應的匯編代碼后，其他CPU核仍然看到foo賦值前的值。剛接觸操作系統(tǒng)的讀者，需要注意這一點。

第二個難題，導致我們至少需要一個原子來存儲二進制位。沒有辦法在一個原子中存儲一個字、一段內(nèi)存、一個完整的寄存器內(nèi)容......最終的結果是，硬件工程師沒有辦法縮小芯片流片面積。當CPU核心增加時，核間通信的負擔會變得更加沉重。

當然，作為理論物理學家，霍金的這兩個問題都是理論性的。半導體制造商很有可能已經(jīng)逼近這兩個限制。雖然如此，還是有一些研發(fā)報告關注于如何規(guī)避這兩個基本限制。

其中一個繞開物質(zhì)原子本質(zhì)的辦法是一種稱為“high-K絕緣體”的材料，這種材料允許較大的器件模擬超小型器件的電氣屬性。這種材料存在一些重大的生產(chǎn)困難，但是總算能將研究的前沿再推進一步。另一個比較奇異的解決方法是在單個電子上存儲多個比特位，這是建立在單個電子可以同時存在于多個能級的現(xiàn)象之上。不過這種方法還有待觀察，才能確定能否在產(chǎn)品級的半導體設備中穩(wěn)定工作。

還有一種稱為“量子點”的解決方法，使得可以制造體積小得多的半導體設備，不過該方法還處于研究階段。

第一個限制不容易被繞過，雖然量子技術、甚至弦論，理論上允許通信速度超過光速。但是這僅僅是理論研究，實際工程中還未應用。

二、原子操作有多慢？

這里的原子操作，是特指Linux內(nèi)核中，類似于atomic_long_add_return這樣的API。簡單的說，就是當某個原子操作完成時，確保所有CPU核已經(jīng)識別到對原子變量的修改，并且在原子操作期間，其他CPU核不會同步對該變量進行修改。這必然要求相應的電信號在所有的CPU之間廣播。如下圖：

對于普通變量操作（非原子操作）來說，電信號則不必在所有CPU核之間傳播并來回傳遞：

不能忘記一點：Linux操作系統(tǒng)可以運行在超過1024個CPU的大型系統(tǒng)中。在這些大型系統(tǒng)中，在所有CPU之間廣播傳遞電信號，需要花費“很長”的時間。

但是，很長究竟是多長？

在上表中，一次“CAS cache miss”的CPU周期是266，夠長了吧？而這個測試結果，是在比較新的、4核CPU的多核系統(tǒng)中進行的。在老一點的系統(tǒng)中，或者在更多CPU核心的系統(tǒng)中，這個時間更長。

三、變量可以擁有多個值

這不是天方夜譚。

假設CPU 0向全局變量foo寫入一個值1，我們會很自然的認為：其他CPU會立即識別到foo的值為1。即使有所疑惑，我們可能也會退一步認為，在稍后某個時刻，其他“所有”CPU都會“同時”識別到foo的值為1。而不會出現(xiàn)一種奇怪的現(xiàn)象：在某個時刻，CPU 1識別到其值為1，而CPU 2識別到其值為0。不幸的是，是時候告別這種想法了。并行計算就是這么神奇和反直覺。如果不能理解這一點，就沒辦法真正理解RCU。

要明白這一點，考慮下面的代碼片段。它被幾個CPU并行的執(zhí)行。第 1行設置共享變量的值為當前CPU的ID，第2行調(diào)用gettb()函數(shù)對幾個值進行初始化，該函數(shù)讀取硬件時間計數(shù)，這個計數(shù)值由SOC硬件給出，并且在所有CPU之間共享。當然，這個硬件計數(shù)值主要是在power架構上有效，筆者在powerpce500架構上經(jīng)常使用它。第3-8行的循環(huán)，記錄變量在當前CPU上保持的時間長度。

1 state.variable = mycpu;

2 lasttb = oldtb = firsttb = gettb();

3 while (state.variable == mycpu) {

4 lasttb = oldtb;

5 oldtb = gettb();

6 if (lasttb - firsttb >1000)

7 break;

8 }

在退出循環(huán)前，firsttb 將保存一個時間戳，這是賦值的時間。lasttb 也保存一個時間戳，它是對共享變量保持最后賦予的值時刻的采樣值，如果在進入循環(huán)前，共享變量已經(jīng)變化，那么就等于firsttb。

這個數(shù)據(jù)是在一個1.5GHz POWER5 8核系統(tǒng)上采集的。每一個核包含一對硬件線程。CPU 1、2、3和4記錄值，而CPU 0 控制測試。時間戳計數(shù)器周期是5.32ns，這對于我們觀察緩存狀態(tài)來說是足夠了。

上圖的結果，展示出每個CPU識別到變量保持的時間。每一個水平條表示該CPU觀察到變量的時間，左邊的黑色區(qū)域表示相應的CPU第一次計數(shù)的時間。在最初5ns期間, 僅僅CPU 3擁有變量的值。在接下來的10ns，CPU 2和3看到不一致的變量值，但是隨后都一致的認為其值是“2”。 但是，CPU 1在整個300ns內(nèi)認為其值是“1”，并且 CPU 4 在整個500ns內(nèi)認為其值是“4”。

這真是一個匪夷所思的測試結果。同一個變量，竟然在不同的CPU上面被看到不同的值?。。?！

如果不理解硬件，就不會接受這個匪夷所思的測試結果。當然了，此時如果有一位大師站在你的面前，你也不能夠跟隨大師的節(jié)奏起舞。

四、為什么需要MESI

請不要說：我還不知道MESI是什么？

簡單的說，MESI是一種內(nèi)存緩存一致性協(xié)議。

現(xiàn)代CPU的速度比現(xiàn)代內(nèi)存系統(tǒng)的速度快得多。2006 年的CPU可以在每納秒內(nèi)執(zhí)行十條指令。但是需要很多個十納秒才能從物理內(nèi)存中取出一個數(shù)據(jù)。它們的速度差異（超過2個數(shù)量級）導致在現(xiàn)代CPU中出現(xiàn)了數(shù)兆級別的緩存。這些緩存與CPU是相關聯(lián)的，如下圖。典型的，緩存可以在幾個時鐘周期內(nèi)被訪問。借助于CPU流水線的幫助，我們暫且可以認為，緩存能夠抵消內(nèi)存對CPU性能的影響。

CPU緩存和內(nèi)存之間的數(shù)據(jù)流是固定長度的塊，稱為“緩存行”，其大小通常是2的N次方。范圍從16到256字節(jié)不等。當一個特定的數(shù)據(jù)第一次被CPU訪問時，它在緩存中還不存在，這稱為“cache miss”(或者可被更準確的稱為“startup cache miss”或者“warmupcache miss”)。“cache miss”意味著：CPU在從物理內(nèi)存中讀取數(shù)據(jù)時，它必須等待(或處于“stalled”狀態(tài)) 數(shù)百個CPU周期。但是，數(shù)據(jù)將被裝載入CPU緩存以后，后續(xù)的訪問將在緩存中找到，因此可以全速運行。

經(jīng)過一段時間后，CPU的緩存將會被填滿，后續(xù)的緩存缺失需要換出緩存中現(xiàn)有的數(shù)據(jù)，以便為最近的訪問項騰出空間。這種“cache miss”被稱為“capacitymiss”，因為它是由于緩存容量限制而造成的。但是，即使此時緩存還沒有被填滿，大量緩存也可能由于一個新數(shù)據(jù)而被換出。這是由于大量的緩存是通過硬件哈希表來實現(xiàn)的，這些哈希表有固定長度的哈希桶（或者叫“sets”，CPU設計者是這樣稱呼的），如下圖。

這個緩存有16個“sets”和2“路”，共32個“緩存行”，每個節(jié)點包含一個256字節(jié)的“緩存行”，它是一個256字節(jié)對齊的內(nèi)存塊。這個緩存行稍微顯得大了一點，但是這使得十六進制的運行更簡單。從硬件的角度來說，這是一個兩路組相聯(lián)緩存，類似于帶16個桶的軟件哈希表，每個桶的哈希鏈最多有兩個元素。大小 (本例中是32個緩存行) 和相連性 (本例中是2) 都被稱為緩存的“geometry”。由于緩存是硬件實現(xiàn)的，哈希函數(shù)非常簡單：從內(nèi)存地址中取出4位（哈希桶數(shù)量）作為哈希鍵值。

在程序代碼位于地址0x43210E00- 0x43210EFF，并且程序依次訪問地址0x12345000-0x12345EFF時，圖中的情況就可能發(fā)生。假設程序正準備訪問地址0x12345F00，這個地址會哈希到 0xF行，該行的兩路都是空的，因此可以提供對應的256字節(jié)緩存行。如果程序訪問地址0x1233000，將會哈希到第0行，相應的256字節(jié)緩存行可以放到第1路。但是，如果程序訪問地址0x1233E00，將會哈希到第0xE行，必須有一個緩存行被替換出去，以騰出空間給新的行。如果隨后訪問被替換的行，會產(chǎn)生一次“cache miss”，這樣的緩存缺失被稱為“associativitymiss”。

更進一步說，我們僅僅考慮了讀數(shù)據(jù)的情況。當寫的時候會發(fā)生什么呢？由于在一個特定的CPU寫數(shù)據(jù)前，讓所有CPU都意識到數(shù)據(jù)被修改這一點是非常重要的。因此，它必須首先從其他CPU緩存中移除，或者叫“invalidated”（使無效）。一旦“使無效”操作完成，CPU可以安全的修改數(shù)據(jù)項。如果數(shù)據(jù)存在于該CPU緩存中，但是是只讀的，這個過程稱為“write miss”。一旦某個特定的CPU使其他CPU完成了“使無效”操作，該CPU可以反復的重新寫（或者讀）數(shù)據(jù)。

最后，如果另外某個CPU試圖訪問數(shù)據(jù)項，將會引起一次緩存缺失，此時，由于第一個CPU為了寫而使得緩存項無效，這被稱為“communication miss”。因為這通常是由于幾個CPU使用緩存通信造成的（例如，一個用于互斥算法的鎖使用這個數(shù)據(jù)項在CPU之間進行通信）。

很明顯，所有CPU必須小心的維護數(shù)據(jù)的一致性視圖。這些問題由“緩存一致性協(xié)議”來防止，常用的緩存一致性是MESI。

五、MESI的四種狀態(tài)

MESI 存在“modified”，“exclusive”，“shared”和“invalid”四種狀態(tài)，協(xié)議可以在一個指定的緩存行中應用這四種狀態(tài)。因此，協(xié)議在每一個緩存行中維護一個兩位的狀態(tài)標記，這個標記附著在緩存行的物理地址和數(shù)據(jù)后面。

處于“modified”狀態(tài)的緩存行是由于相應的CPU最近進行了內(nèi)存存儲。并且相應的內(nèi)存確保沒有在其他CPU的緩存中出現(xiàn)。因此，“modified”狀態(tài)的緩存行可以被認為被CPU所“擁有”。由于該緩存保存了“最新”的數(shù)據(jù)，因此緩存最終有責任將數(shù)據(jù)寫回到內(nèi)存，也應當為其他緩存提供數(shù)據(jù)，并且必須在緩存其他數(shù)據(jù)之前完成這些事情。

“exclusive”狀態(tài)非常類似于“modified”狀態(tài)，唯一的差別是該緩存行還沒有被相應的CPU修改，這也表示緩存行中的數(shù)據(jù)及內(nèi)存中的數(shù)據(jù)都是最新的。但是，由于CPU能夠在任何時刻將數(shù)據(jù)存儲到該行，而不考慮其他CPU，因此，處于“exclusive”狀態(tài)也可以認為被相應的CPU所“擁有”。也就是說，由于物理內(nèi)存中的值是最新的，該行可以直接丟棄而不用回寫到內(nèi)存，也不用通知其他CPU。

處于“shared”狀態(tài)的緩存行可能已經(jīng)被復制到至少一個其他CPU的緩存中，這樣在沒有得到其他CPU的許可時，不能向緩存行存儲數(shù)據(jù)。與“exclusive”狀態(tài)相同，此時內(nèi)存中的值是最新的，因此可以不用向內(nèi)存回寫值而直接丟棄緩存中的值，也不用通知其他CPU。

處于“invalid”狀態(tài)的行是空的，換句話說，它沒有保存任何有效數(shù)據(jù)。當新數(shù)據(jù)進入緩存時，它被放置到一個處于“invalid”狀態(tài)的緩存行。這個方法是比較好的，因為替換其他狀態(tài)的緩存行將引起大量的緩存缺失。

由于所有CPU必須維護緩存行中的數(shù)據(jù)一致性視圖，因此緩存一致性協(xié)議提供消息以標識系統(tǒng)中緩存行的動作。

六、MESI消息

MESI協(xié)議需要在CPU之間通信。如果CPU在單一共享總線上，只需要如下消息就足夠了：

• 讀消息：“讀”消息包含要讀取的緩存行的物理地址。

• 讀響應消息：“讀響應”消息包含較早前的“讀”消息的數(shù)據(jù)。這個“讀響應”消息可能由物理內(nèi)存或者其他CPU的緩存提供。例如，如果一個緩存處于“modified”狀態(tài)，那么，它的緩存必須提供“讀響應”消息。

• 使無效消息：“使無效”消息包含要使無效的緩存行的物理地址。其他的緩存必須從它們的緩存中移除相應的數(shù)據(jù)并且響應此消息。

• 使無效應答：一個接收到“使無效”消息的CPU必須在移除指定數(shù)據(jù)后響應一個“使無效應答”消息。

• 讀使無效：“讀使無效”消息包含緩存行要讀取的物理地址。同時指示其他緩存移除數(shù)據(jù)。因此，它同時包含一個“讀”消息和一個“使無效”消息?！白x使無效”消息同時需要“讀響應”消息以及“使無效應答”消息進行答應。

• 寫回：“寫回”消息包含要回寫到物理內(nèi)存的地址和數(shù)據(jù)。(并且也許會“探測”其他CPU的緩存)。這個消息允許緩存在必要時換出處于“modified”狀態(tài)的數(shù)據(jù)以騰出空間。

再次重申，所有這些消息均需要在CPU之間傳播電信號，都面臨霍金提出的那兩個IT難題。

七、MESI狀態(tài)轉(zhuǎn)換

• Transition (a)：緩存行被寫回到物理內(nèi)存，但是CPU仍然將它保留在緩存中，并在以后修改它。這個轉(zhuǎn)換需要一個“寫回”消息。

• Transition (b)：CPU將數(shù)據(jù)寫到緩存行，該緩存行目前處于排它訪問。不需要發(fā)送或者接收任何消息。

• Transition (c)：CPU收到一個“讀使無效”消息，相應的緩存行已經(jīng)被修改。CPU必須使無效本地副本，然后響應“讀響應”和 “使無效應答”消息，同時發(fā)送數(shù)據(jù)給請求的CPU，標示它的本地副本不再有效。

• Transition (d)：CPU進行一個原子讀—修改—寫操作，相應的數(shù)據(jù)沒有在它的緩存中。它發(fā)送一個“讀使無效”消息，通過“讀響應”消息接收數(shù)據(jù)。一旦它接收到一個完整的“使無效應答”響應集合，CPU就完成此轉(zhuǎn)換。

• Transition (e)：CPU進行一個原子讀—修改—寫操作，相應的數(shù)據(jù)在緩存中是只讀的。它必須發(fā)送一個“使無效”消息，并等待“使無效應答”響應集合以完成此轉(zhuǎn)換。

• Transition (f)：其他某些CPU讀取緩存行，其數(shù)據(jù)由本CPU提供，本CPU包含一個只讀副本。數(shù)據(jù)只讀的原因，可能是由于數(shù)據(jù)已經(jīng)回寫到內(nèi)存中。這個轉(zhuǎn)換開始于接收到一個“讀”消息，最終本CPU響應了一個“讀響應” 消息。

• Transition (g)：其他CPU讀取數(shù)據(jù)，并且數(shù)據(jù)是從本CPU的緩存或者物理內(nèi)存中提供的。無論哪種情況，本CPU都會保留一個只讀副本。這個事務開始于接收到一個“讀”消息，最終本CPU響應一個“讀響應”消息。

• Transition (h)：當前CPU很快將要寫入一些數(shù)據(jù)到緩存行，于是發(fā)送一個“使無效”消息。直到它接收到所有“使無效應答”消息后，CPU才完成轉(zhuǎn)換?？蛇x的，所有其他CPU通過“寫回”消息將緩存行的數(shù)據(jù)換出（可能是為其他緩存行騰出空間）。這樣，當前CPU就是最后一個緩存該數(shù)據(jù)的CPU。

• Transition (i)：其他某些CPU進行了一個原子讀—修改—寫操作，相應的緩存行僅僅被本CPU持有。本CPU將緩存行變成無效狀態(tài)。這個轉(zhuǎn)換開始于接收到“讀使無效”消息，最終本CPU響應一個“讀響應”消息以及一個“使無效應答”消息。

• Transition (j)：本CPU保存一個數(shù)據(jù)到緩存行，但是數(shù)據(jù)還沒有在它的緩存行中。因此發(fā)送一個“讀使無效”消息。直到它接收到“讀響應”消息以及所有“使無效應答”消息后，才完成事務。緩存行可能會很快轉(zhuǎn)換到“修改”狀態(tài)，這是在存儲完成后由Transition (b)完成的。

• Transition (k)：本CPU裝載一個數(shù)據(jù)，但是數(shù)據(jù)還沒有在緩存行中。CPU發(fā)送一個“讀”消息，當它接收到相應的“讀響應”消息后完成轉(zhuǎn)換。

• Transition (l)：其他CPU存儲一個數(shù)據(jù)到緩存行，但是該緩存行處于只讀狀態(tài)（因為其他CPU也持有該緩存行）。這個轉(zhuǎn)換開始于接收到一個“使無效”消息，當前CPU最終響應一個“使無效應答”消息。

本文未完待續(xù)...