理解顺序一致性

Leslie Lamport 关于顺序一致性的定义如下：

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.

其中有以下几个关键词：

• Processor：在多核架构下，它指代处理器核心；在分布式架构下，就是不同的运算节点。

• Operations：读写共享内存的操作，应该保证其原子性。

• Program Order：代码序

顺序一致性的定义可以理解为，系统无论如何运行，执行的结果像是：

1. 所有处理器上的操作按照一定顺序排列执行

2. 每个处理器内部执行顺序与程序定义一致

以下面的例子为例(来自于维基百科):

 processor 1:     <-- A1 run --> <-- B1 run -->        <-- C1 run --> processor 2:       <-- A2 run --> <-- B2 run --> Time --------------------------------------------------------------------->

其中 A1, B1, C1 的顺序是固定的，A2, B2 也是如此。B2 与 C1、A1 与 B1 等顺序是不固定的(无要求)。

顺序一致性的意义

顺序一致性要求 Processor 串行执行，但是实际环境为了性能考虑，均为并行执行。那么顺序一致性实际意义是什么呢？

我们应该注意到定义里面的 as if, 像是。这个时候就需要理解为尽管实际是并发执行，但是他工作的结果与顺序执行是一致的。而且如果程序是按照顺序执行的，后一个处理器可以看到前一个的内存操作。

所以说顺序一致性模型要求：

• 不同处理器间内存操作的全局可见。

• 处理器内部执行结果应该与代码序执行结果一致。

顺序一致性模型

综上，我们就会有一个全局的顺序一致性模型，它提供了一个全局串行化的内存操作。

1. 它由一个全局内存、多路开关和多个处理器组成。

2. 每个处理器内部以编码顺序分发内存操作。

3. 开关每次会随机连接一个处理器执行内存操作。

这样所有处理器内存操作立马对其他处理器可见，不存在并发冲突的问题。

顺序一致性问题

现实环境纷繁复杂，但是为了得到一个正确的结果，我们需要进行相关处理保证顺序一致性，例如：

• 如何在多核的情况下，使各处理器间多级缓存保持一致? (MESI)

• 如何在 CPU 内部乱序执行，存储采用 invalid queue、store buffer 的情况下，正确插入内存屏障，使程序正确同步？

• 如何正确使用锁、volatile 等关键字，使程序正确同步，得到顺序一致性模型？

References

1. 深入浅析一致性模型之Sequential Consistency
   

2. Sequential consistency