閑聊內(nèi)存模型(Memory Model)

1、前言

現(xiàn)在大多數(shù)多核芯片在硬件中支持共享內(nèi)存，設(shè)計和評估一個正確的共享內(nèi)存系統(tǒng)需要準(zhǔn)確理解內(nèi)存模型。不同CPU可能采用不同的內(nèi)存模型，比如ARM和RISC-V的Related模型，Intel和AMD的TSO模型以及IBM的Power模型等等。盡管這些模型千奇百怪，各有優(yōu)缺點，但我們只要抓住它們的本質(zhì)，就可以輕松拿捏它們。不要太在意邊邊角角的點，不然很容易陷進(jìn)去。本文閑聊的內(nèi)容框架大致如下，如果有出現(xiàn)專有名詞，就不再解釋了，請各位自行搜索下，或者翻看我的歷史文章。

2、內(nèi)存模型

Memory consistency model又稱Memory model (內(nèi)存模型)，定義了使用Shared memory(共享內(nèi)存)執(zhí)行多線程(Multithread)程序所允許的行為規(guī)范。

內(nèi)存模型主要是抓住program order(程序順序)和global memory order(全局內(nèi)存順序)，根據(jù)這兩個order允許的行為，可以把內(nèi)存模型劃分為SC(Sequential Consistency)、TSO(Total Store Order)和Relaxed(weaker) model。

簡單來說，如果global memory order保持每個Core的program order，那么內(nèi)存模型就是SC模型。SC模型是最直觀而且最容易讓程序員推理代碼的執(zhí)行結(jié)果，但過于死板，限制了硬件的發(fā)揮，于是就進(jìn)一步發(fā)展了TSO模型。

不管地址是否相同，TSO模型的older store和younger load的program order在global memory order中可以不保留，這就允許Core中加入FIFO類型的Store buffer，用于緩存已經(jīng)在Core pipeline上Commit的Store數(shù)據(jù)，但還沒有寫到memory當(dāng)中，隱藏了store寫到memory的latency來提高性能，后續(xù)的younger load如果發(fā)現(xiàn)可以從Store buffer中獲取想要的數(shù)據(jù)，那么Store buffer可以直接forward過去。在TSO模型中，對于單個Core來說，程序的執(zhí)行結(jié)果看起來還是符合預(yù)期。但多個Core情況下，會有一些出乎意料的結(jié)果，因此引入了FENCE指令，如果想要讓older store和younger load的program order一定與global memory order一致，那么需要在它們兩個之間插入FENCE指令。TSO模型一定程序上也限制了硬件的優(yōu)化，于是就進(jìn)一步發(fā)展了Relaxed模型。

Relaxed模型只尋求保留程序員需要的順序，讓一些程序員不關(guān)心的指令順序可以亂序執(zhí)行，從而允許軟硬件更多的優(yōu)化。Relaxed模型對于不同地址的load和store，可以讓它們亂序執(zhí)行，對于同地址的load和store，讓它們保持TSO模型的規(guī)則，也就是older store和younger load可以不遵循global memory order，但load必須可以得到最新store的值。這就允許Core可以將TSO中FIFO類型的Store buffer升級為非FIFO類型的Store buffer。且允許多筆store數(shù)據(jù)的merge行為。在Relaxed模型中，對于單個Core來說，程序的執(zhí)行結(jié)果看起來還是符合預(yù)期。但多個Core情況下，會出現(xiàn)更多出乎意料的結(jié)果，因此也引入了FENCE指令，以便程序員可以指示哪些指令間需要遵循global memory order。

總得來說，這三類模型，對于單Core來說，程序執(zhí)行結(jié)果是確定的，但對于多Core來說，程序執(zhí)行結(jié)果會存在不一致的情況。SC模型為同一線程中l(wèi)oad和store的所有四種組合(Load->Load, Load->Store, Store->Store, ?Store->Load)提供global memory order保序。TSO模型為同一線程中l(wèi)oad和store的三種組合(Load->Load, Load->Store, Store->Store)提供global memory order保序，不對 Store->Load做global memory order保序。Relaxed模型對不同地址的memory操作，允許它們亂序執(zhí)行，但是對相同地址的memory操作，它和TSO的規(guī)則一致。

3、一致性協(xié)議

雖然一致性協(xié)議眾多，但本質(zhì)上講，所有一致性協(xié)議都通過將寫入的數(shù)據(jù)傳播到所有一致性cache來使一個core的寫入對其它core可見。對于一致性協(xié)議，需要謹(jǐn)遵兩個原則：

原則一：Single-Writer, Multiple-Read(簡稱SWMR)，也就是在任意時刻，對于某一個地址，只有一個Core可以寫它(也可以讀它)，或者多個Core讀它。永遠(yuǎn)不會存在一個Core可以寫入地址A，而其它Core可以同時讀取或?qū)懭氲刂稟的情況。

原則二：Data Value Continuity(簡稱DVC)，對于一個地址所存儲的數(shù)據(jù)，它的值是連續(xù)的，所有Cores要以相同的順序看到該地址的寫數(shù)據(jù)。具體來說，可以把時間切割成很多小片段，上一個片段結(jié)束的數(shù)據(jù)值與下一個片段開始的數(shù)據(jù)值相同，而且處于同一個切片中，所有Core能讀取到的數(shù)據(jù)必須相同，不可能存在在某個片段中，Core0對地址A讀取到x，Core1對地址A讀取到y(tǒng)的情況。也就是每個地址的數(shù)據(jù)值需要被正確傳播。

4、掛死

掛死(hang)顧名思義就是Core無法正常推進(jìn)了，要么Core的PC值不再變化，要么Core的PC值一直處于某個循環(huán)之中，無法進(jìn)行其它操作。主要三類死鎖、餓死和活鎖。

死鎖：如果有兩個或多個參與者互相等待對方執(zhí)行某些操作，那么就可能產(chǎn)生資源循環(huán)依賴，導(dǎo)致死鎖。特別是如果有個多個請求者在共享某些資源，而且它們的動作之間還存在依賴，就要警惕死鎖。

餓死：如果一個Core或多個Core無法取得進(jìn)展，而其它Core仍然可以取得進(jìn)展，沒有進(jìn)展的Core就處于餓死狀態(tài)。常規(guī)例子就是不公平仲裁容易出現(xiàn)餓死。因此，當(dāng)有多個請求者爭搶某個資源時，一定要注意是否有可能某個請求者永遠(yuǎn)也無法獲取到該資源。

活鎖：如果有兩個或多個參與者執(zhí)行操作并改變狀態(tài)，但它們最終從未取得進(jìn)展的情況，就發(fā)生活鎖了?？此拼蠹叶荚谡J(rèn)真干活，但是什么都沒有干成。常規(guī)例子就是多個Core使用exclusive操作進(jìn)行搶鎖導(dǎo)致的活鎖。因此，如果某個資源會被多個請求者共享，請求者搶到后還必須進(jìn)行某些操作才會釋放，否則就一直爭搶，有這種傾向的場景就必須要注意活鎖的存在。