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来使用。细节下次我们接着聊。