A Primer on Memory Consistency & Cache Coherence 笔记1

本文是对《A Primer on Memory Consistency and Cache Coherence》这本书前一半内容的记录和理解，主要涉及memory consistency model。

1. 引言

对于多处理器共享内存系统来说，consistency和coherence都关注的是共享内存(shared memory)及cache的正确性问题，而人们把这个问题拆成两个方面是为了更好地将这个复杂问题分治解决。

1.1 Consistency

一般需要被详细讨论的是多核(或线程)共享内存(shared memory)的consistency模型，因为单核单线程问题相对简单直观。内存consistency模型规定的是：多线程同时进行load/store操作时，怎样的执行顺序是对的，怎样是错的。比较简单直接的consistency模型包括sequential consistency、TSO(total store consitency，x86使用)等。

1.2 Coherence

本文主要记录与consistency有关的内容，但因为consistency的实现与coherence有关，所以要简单介绍下coherence及其与consistency的关系。

虽然coherence的中文也翻译成“一致性”，但coherence这个词通常跟在cache后面，即缓存一致性(cache coherence)，解决缓存一致性问题的方法也被称为缓存一致性协议(cache coherence protocol)。那么共享内存系统的cache为什么需要coherence协议保证共享内存系统正确性呢？这是因为cache一般分为L1、L2和L3等很多层，L1等比较高的层级中，cache是每个核所独占的，一般只有L3、memory等层级才是共享的。在每个核独占的层级中，可能出现统一内存地址的数据在不同独占cache中数值不一样的情况，这时cache的状态可以称为incoherent。通过无效化等coherence协议，可以保证多核系统cache的正确性。

1.3 Consistency 和 Coherence的关系

对于sequential consistency和TSO等比较简单的consistency model来说，保证了coherence的cache可以被看成一个“黑盒”甚至对consistency model透明，黑盒中有cache实现有保证cache使用正确的coherence protocol，而consistency更关注程序(或处理器核)的访存顺序。因此对于简单的consistency model和coherence protocol来说，两者是解耦的。

1.4 一个小例子

如果上边几段不易理解，作者在书中用一个例子解释了这两个名词的基本含义，简单记录如下，有改编：

consistency的例子

设想有三个人，计算机体系结构课程老师、教务处网站管理员和上课的学生，老师最开始在教务处上登记了上课的地点是152教室，但是开学第一节课后发现选课的人太多了152坐不下，于是准备下节课开始换到更大的252教室，于是老师先①找教务处网站管理员说“请你把网站上我课的教室信息改到252（要求①），随后通知学生们去教务处网站查询下节课的上课地点（要求②）。这就产生了一个问题，网站管理员可能是第二天才更新的网站，而学生是接到老师的通知马上重新查看了教务处网站，因此学生下周又来到了152教室，老师的计划和最后的结果出现了不一致情况。

问题就出在老师的做法无法保证学生在网站被修改之后再去网站查询。要想保证学生查到正确的信息，一种简单的办法就是保证管理员的确更新了数据，然后再通知学生们。这种简单的办法就可以称为一种一致性模型。

我们把这个例子对应到实际的内存系统中，给管理员和学生要做的两件事（要求①和②）可以分别看成一条store命令和一条load命令，目标都是教务处网站上老师的教室号，这个目标可以看成同一块内存地址，因此对同一内存地址执行的store和load命令是否可以调换顺序(管理员在学生查询才修改了网站)，调换顺序后是否破坏了程序的正确性，就是内存一致性模型memory consistency model所负责的。也就是说，出现上述情况算不算错，应该是当前的一致性模型所判断的：相对于我们每个人心中直觉上的一致性模型，这种走错教室的情况肯定是错了，但是对于一个性格怪异的老师，也许他觉得这样也是对的，比如他可以找他的同事帮他上152教室的课，他自己上252教室的课，也正因他如此怪异，所以他最开始联系网站管理员时也遵循了他心中的怪异的一致性模型，没有等网站确实修改就给学生们发了查询教室的通知。

coherence的例子

紧接上个例子，与之不同的是，很多学生在最开始选课的时候就把《体系结构》这门课的教室152记在了自己的小本本上，但是后来，管理员将网站上教室信息改成了252。虽然学生的小本本上和教务处网站上的信息应该是同一个信息，应该是一样的，但是这时两者一个152，一个252，这就出现了incoherent的情况。

在内存系统中，学生的小本本就相当于cache，而教务处网站相当于memory，学生将memory中的某个值拷贝到了cache中，当memory被其他人更新时，学生自己的cache就应该同时立即处于无效的状态。这里出现incoherent的原因就是没有一个cache coherence protocol来保证cache的正确性。比如，一个简单的coherence protocol可以这么干：在网站更新后，老师挨个找到每个学生，把他们的小本本记的152划掉?，无效化协议就是这种思想。

2. Coherence的基本概念

要了解consistency，需要稍微了解coherence。首先，给incoherence带来可能的是多用户的访存操作，这里的“用户”一般指核，但是也可以指DMA等其他可以访问内存的设备。

书的作者为了定义cache coherence，给出了两个限制条件：

single-write-multiple-reader (SWMR)：对于任意位置的内存，任何时候只能由一个核进行读写或者多个核进行只读操作。（类似读写锁的功能）
Data-Value Invariant： 某个epoch开始时，内存中某个位置的值等于上一次读写epoch结束时候的值。

其他一些细节：①无效化协议是最常用的cache coherence protocol；②coherence同样有粒度问题，一般是1到64字节之间；③coherence还有很多其他的定义，具体见书14页；④coherence protocol的管理范围包括各级cache以及TLB等。⑤有些consistency model依赖coherence protocol，有些则不依赖，甚至有时一个inherent的系统在默写consistency model下依然是正确的。因为coherence 并不从属于architecture（？）。⑥读写称为状态M，只读状态称为状态S，申请这两种状态可以分别用getM和getS表示（下文同）。

3. Consistency

一般来说，memory consistency和cache coherence不一样，它们分别在两个层面，coherence要保证的是cache对程序是透明的，就像处理器核直接读写没有cache的内存一样；而consistency则更关心shared memory的load与store的执行顺序问题，比如load-load、store-store和load-store它们之间是否可以交换顺序，即out-of-order execution。因此，即使是发生了错误的乱序执行，设计完好的coherence protocol也无能为力，它们处于两个层次上。而且，consistency关注的是整个内存，而coherence每次关注的是一块内存。

3.1 Sequential Consistency (SC)

顺序一致性(SC)是最直观的一种consistency model，意思是对于每个程序，在程序(核)自己看来，指令都是按照原来的顺序执行的；在memory看来，指令的执行顺序可能是在不同的程序所属的指令之间来回切换的：

# 注意：
# A <p B 代表处理器看来的执行顺序A在B之前(program order)
# A <m B 代表内存看来的执行顺序A在B之前(memory order)
# (下同)

如果：  指令1 <p 指令2
那么：  指令1 <m 指令2
这里的指令包括Load、Store和RMW

下表中列表示指令1，行表示指令2，”X”表示不能交换顺序

	load	store	RMW
load	X	X	X
store	X	X	X
RMW	X	X	X

SC将所有线程的所有指令都没有任何乱序执行，是最强的consistency模型，其与DBMS并发控制中的冲突串行化道理上很相似。

实现：

可以抽象成多个core都按程序的指令顺序进行访存请求，而一个switch不停地随机选取下一个将要执行的core：

这个switch可以换成cache：

通过cache coherence、预取、推测执行和多线程等方法，多个核可以并发地进行访存，这遮盖了访存的延迟，提升了性能。

注意：

SC只规定了访存的顺序不被打乱，但是进行coherence状态的请求(指getM、getS等)的顺序可以任意，只要保证访存时，相关的地址处于适当的coherence状态即可。
一个核支持多线程的问题，其实可以等加成多个核的问题。
RMW问题(read-modify-write, test-and-set, fetch-and-increment, compare-and-swap)是实现spin-lock的基础，是个原子操作。其涉及一个load和一个store，应该先getM，再进行load和store操作。

3.2 Total Store Order (TSO)

TSO是一个与x86的行为相一致的内存一致性模型，其与SC很类似，唯一的区别是store可以延到后load之后，即前面的store可以延迟到后边的load之后：

       如果:           那么:
    S1 <p L2    L2 <m S1 或 S1 <m L2
    S1 <p S2    S1 <m S2
    L1 <p L2    L1 <m L2
    L1 <p S2    L1 <m S2
# 注意：
# 若是同核且同地址，那么即使Store延后到Load之后，Load也会读到Store最新的值

Bypass问题：

如果被乱序的Load和Store指令都是一个核，且地址也是一样的，即使Store被延迟到Load之后，Load依然会读到Store最新存的值。这是因为TSO本质上就是在SC基础上加了一个write-buffer，那些可能被延后乱序的Store其实还是按原来未顺序将值在本地cache中进行改写，只是没有写到memory中，这称为Load命令bypass了Store命令，依然会读到Store的最新值。

FENCE问题：

FENCE是用来避免潜在的乱序的指令，这TSO中，只有Store延后到Load之后这一种乱序，因此FENCE只有防止Store延后到Load后这一个作用。

下表示TSO的一个总结：B表示可以乱序，并且如果是同一地址，应该用Bypass

	load	store	RMW	FENCE
load	X	X	X	X
store	B	X	X	X
RMW	X	X	X	X
FENCE	X	X	X	X

实现： 与SC的区别是多一个write-buffer，在我理解，以上所有定义都是因为多了这个write-buffer：

RMW： 需要注意，TSO中，write-buffer是FIFO的，因此实现原子RMW时，不能直接load和store write-buffer中的“锁”，而应该现将write-buffer写到memory，再像SC一样获取M状态，然后进行所需的load和store。

注意：

TSO比SC的consistency要求更弱。

Relaxed Memory Consistency

TSO比SC要弱，但也只是放开了一种乱序，对应还有更弱的memory consistency，任意指令都可以交换，要想在局部进行顺序执行，只能由程序员在命令间全部插入FENCE。

JciX ~

Jc's Blog