一、來(lái)自于霍金的難題

據(jù)說(shuō)斯蒂芬·霍金曾經(jīng)聲稱(chēng)半導(dǎo)體制造商面臨兩個(gè)基本問(wèn)題：

（1）有限的光速

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

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

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

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

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

還有一種稱(chēng)為“量子點(diǎn)”的解決方法，使得可以制造體積小得多的半導(dǎo)體設(shè)備，不過(guò)該方法還處于研究階段。

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

二、原子操作有多慢？

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



對(duì)于普通變量操作（非原子操作）來(lái)說(shuō)，電信號(hào)則不必在所有CPU核之間傳播并來(lái)回傳遞：

不能忘記一點(diǎn)：Linux操作系統(tǒng)可以運(yùn)行在超過(guò)1024個(gè)CPU的大型系統(tǒng)中。在這些大型系統(tǒng)中，在所有CPU之間廣播傳遞電信號(hào)，需要花費(fèi)“很長(zhǎng)”的時(shí)間。

但是，很長(zhǎng)究竟是多長(zhǎng)？

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

三、變量可以擁有多個(gè)值

這不是天方夜譚。

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

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

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 將保存一個(gè)時(shí)間戳，這是賦值的時(shí)間。lasttb 也保存一個(gè)時(shí)間戳，它是對(duì)共享變量保持最后賦予的值時(shí)刻的采樣值，如果在進(jìn)入循環(huán)前，共享變量已經(jīng)變化，那么就等于firsttb。

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

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

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

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

四、為什么需要MESI

請(qǐng)不要說(shuō)：我還不知道MESI是什么？

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

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

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

經(jīng)過(guò)一段時(shí)間后，CPU的緩存將會(huì)被填滿，后續(xù)的緩存缺失需要換出緩存中現(xiàn)有的數(shù)據(jù)，以便為最近的訪問(wèn)項(xiàng)騰出空間。這種“cache miss”被稱(chēng)為“capacitymiss”，因?yàn)樗怯捎诰彺嫒萘肯拗贫斐傻摹５牵词勾藭r(shí)緩存還沒(méi)有被填滿，大量緩存也可能由于一個(gè)新數(shù)據(jù)而被換出。這是由于大量的緩存是通過(guò)硬件哈希表來(lái)實(shí)現(xiàn)的，這些哈希表有固定長(zhǎng)度的哈希桶（或者叫“sets”，CPU設(shè)計(jì)者是這樣稱(chēng)呼的），如下圖。

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

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

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

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

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

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

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

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

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

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

處于“invalid”狀態(tài)的行是空的，換句話說(shuō)，它沒(méi)有保存任何有效數(shù)據(jù)。當(dāng)新數(shù)據(jù)進(jìn)入緩存時(shí)，它被放置到一個(gè)處于“invalid”狀態(tài)的緩存行。這個(gè)方法是比較好的，因?yàn)樘鎿Q其他狀態(tài)的緩存行將引起大量的緩存缺失。

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

六、MESI消息

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Transition (l)：其他CPU存儲(chǔ)一個(gè)數(shù)據(jù)到緩存行，但是該緩存行處于只讀狀態(tài)（因?yàn)槠渌鸆PU也持有該緩存行）。這個(gè)轉(zhuǎn)換開(kāi)始于接收到一個(gè)“使無(wú)效”消息，當(dāng)前CPU最終響應(yīng)一個(gè)“使無(wú)效應(yīng)答”消息。




審核編輯：劉清