Memory Consistency和Cache Coherence

Memory Consistency

Memory Consistency(MC)，有時候又叫做Memory Consistency Model或者Memory Model。為了理解為什么需要引入這種東西，我們首先看以下程序：

初始：x=0 y=0

Thread1：

S1：x=1

L1：r1=y

Thread2：

S2：y=2

L2：r2=x

兩個線程執行完之后，r1和r2可能是什么值？

注意到線程是并發、交替執行的，下面是可能的執行順序和相應結果：

S1 L1 S2 L2 那么r1=0 r2=2 S1 S2 L1 L2 那么r1=1 r2=2 S2 L2 S1 L1 那么r1=2 r2=0

這些都是意料之內、情理之中的。但是在x86體系結構下，很可能得到r1=0 r2=0這樣的結果。是不是大吃一驚？

如果沒有Memory Consistency，那么程序員對于自己編寫的多線程程序會輸出什么將一無所知：天知道會輸出什么。

因此，Memory Consistency就是一種程序員（編程語言）、編譯器、CPU間的協議。這個協議保證了程序讀取內存時可能得到什么值，會得到什么值。

Sequential Consistency

在Sequential Consistency這種Memory Model下，剛才討論的那個程序不可能輸出r1=0 r2=0這種結果。此話怎講？這就牽涉到一個問題：什么是Sequential Consistency（SC）

根據Leslie Lamport在1979年9月發表的論文”How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs”里提出的SC的定義：

the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program.

根據這個定義，在SC模型下，任何execution的執行順序（我們稱為Total Order）必須respect每個線程的Program Order。什么是Program Order？對于以上程序，在Thread1中，S1先于L1；在Thread2中，S2先于L2。這就是Program Order。

請時刻注意，Program Order只針對某個線程內的語句而言，不涉及到跨線程。比如Thread1中的S1和Thread2中的L2，就無所謂什么Program Order了。

好了，現在知道為什么在SC下，有些結果可能出現，有些不可能了。

S1 L1 S2 L2 那么r1=0 r2=2 沒問題，沒有違背S1<L1 S2<L2 S1 S2 L1 L2 那么r1=1 r2=2 沒問題，沒有違背S1<L1 S2<L2 S2 L2 S1 L1 那么r1=2 r2=0 沒問題，沒有違背S1<L1 S2<L2

而對于r1=0 r2=0，在SC下，我們找不到一個能respect Program Order的Memory Order。因為r1=0，說明L1<S2，r2=0說明L2<S1；而S1<L1，S2<L2，不難看出這里形成了一個環。

Cache Coherence

還是先搬出這張圖吧:

(圖片來源于Paul大叔的《Is Parallel Programming Hard》這本書第三章)

多個CPU cores，每個core上有自己的Cache。我們知道，Cache是部分內存的映射和緩存，或者說，副本。這就帶來一個問題：副本一致性。內存只有一個，每個cpu cores卻有自己的內存副本，如何保證大家看到的內容是一樣的、一致的、正確的呢？這就是Cache Coherence(CC)要解決的問題。

Cache Coherence VS Memory Consistency

從以上分析，我們不難看出。CC和MC涉及的是兩個不同層面的東西，解決的是不同的問題，不可混淆。CC解決的是副本一致性問題；MC保證的是多線程程序可以讀到什么值。

兩者有聯系嗎？有。實現Memory Consistency時，Cache Coherence有時候可以作為一個black box tool來使用。細節下次我們接著聊。