Yebangyu's Blog

Fond of Concurrency Programming and Machine Learning

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

其中,S1、S2、L1、L2是语句代号(BTWS表示StoreL表示Load);r1r2是两个寄存器。xy是两个不同的内存变量。

两个线程执行完之后,r1r2可能是什么值?

注意到线程是并发、交替执行的,下面是可能的执行顺序和相应结果:

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

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

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 ConsistencySC)。

根据Leslie Lamport19799月发表的论文《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的执行顺序(我们称为Memory Order)必须respect每个线程的Program Order。什么是Program Order?对于以上程序,在Thread1中,S1先于L1(不妨记为S1<L1);在Thread2中,S2先于L2(记为S2<L2)。这就是Program Order

请时刻注意,Program Order只针对某个线程内的语句而言,不涉及到跨线程。比如Thread1中的S1Thread2中的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 OrderMemory Order。因为r1=0,说明L1<S2r2=0说明L2<S1;而S1<L1,S2<L2,不难看出这里形成了一个环。

Cache Coherence

还是先搬出这张图吧:

memorycache

(图片来源于Paul大叔的《Is Parallel Programming Hard》这本书第三章)

多个CPU cores,每个core上有自己的Cache。我们知道,Cache是部分内存的映射和缓存,或者说,副本。这就带来一个问题:副本一致性。内存只有一个,每个cpu cores却有自己的内存副本,如何保证大家看到的内容是一样的、一致的、正确的呢?这就是Cache Coherence(CC)要解决的问题。

Cache Coherence VS Memory Consistency

从以上分析,我们不难看出,CCMC涉及的是两个不同层面的东西,解决的是不同的问题,不可混淆。CC解决的是副本一致性问题;MC保证的是多线程程序访问内存时可以(可能)读到什么值。

两者有联系吗?有。实现Memory Consistency时可能会使用到Cache Coherence。细节下次我们接着聊。

附录

1,在并行编程中,我们常常有一个问题,或者需求:比如说上面的那个程序,如何保证线程2读到的x是线程1更新(x=1)后的x的值呢?

如果不加任何同步设施,仅仅考虑上面的程序,那么答案是:无法保证。因为线程的推进速度不同,哪条指令先被执行也一无所知。这个程序重跑几次,也可能输出不同的结果出来。

也就是说,Memory Model保证的是,例如,当线程2看到x等于1的时候,线程1是否已经执行了L1。也就是说,Memory Model确保当一件事情发生时,有其他什么事情has happened。在SC中,当L1发生时,说明或者说暗示着,S1已经发生了。

2,为什么x86下可能得出r1=0 r2=0的结果?

因为S1是写一个内存变量而L1是读取另一个内存变量(两个变量,或者说两个内存地址),这种情况下的写读可能被CPU乱序:先执行L1,再执行S1。(为了性能,所谓的延后写)

致谢

本文发出后,微博网友@linyvxiang 指出了其中的一个笔误,非常感谢。