内存一致性模型

内存一致性模型描述的是程序在执行过程中内存操作正确性的问题。内存操作包括读操作和写操作，每一操作又可以用两个时间点界定：发出（Invoke）和响应（Response）。在假定没有流水线的情况下（即单个处理器内指令的执行是按顺序执行的），设系统内共有N个处理器，每个处理器可发出$s_n (0<n\le N)$个内存操作（读或写），那么总共有:$\frac{(\sum_{n=1}^{n=N}s_n)!}{\prod_{n=1}^{n=N}s_n!}$种可能的执行顺序。内存一致性模型描述的就是这些操作可能的执行顺序中那些是正确的。

内存一致性模型的研究历史和分类

按照传统冯诺依曼体系结构的计算模型来看，读操作应当返回最近的写操作所写入的结果，但是这里“最近”的含义是比较模糊的。因此必须将概念严格话，于是产生了线性一致性（或称做严格一致性 Strict consistancy、原子一致性 Atomic consistancy）的概念。但是线性一致性太难实现了，因为这里需要一个全局同步的时钟，于是Leslie Lamport提出了顺序一致性(Sequential consistency)的概念，这里全局的时钟变得不再需要，转而需要的是各个处理器局部的时钟，相应的，Maurice Herlihy和Nir Shavit等人后来又提出了静态一致性(Quiescent consistency)的概念。

然而，即使是顺序一致性在实际系统中也是很少使用的，主要是它严格限制了程序的优化执行，强行的使程序在本地处理器上按程序序(program order)执行在大多数情况下是没有必要的。于是在后来的研究中陆续提出了面向硬件的内存模型(Hardware-centric memory model)，其中包含了弱序一致性模型(WO, Week-order model)，处理器一致性模型(PC, Processor-consistency model)，松弛一致性模型(RC, Release consistency model)以及一系列相关的派生模型，如TSO一致性模型(Total store ordering)，PSO一致性模型(Partial Store Ordering)等。使用前面的这些模型对于程序员来说无疑是非常困惑的，因为这要求程序员在编写程序时必须考虑到各种硬件体系结构所对应的不同内存模型，于是后来的研究进一步提出了面向程序员的内存模型(Programmer-centric model)的概念，主要包括SCNF模型(Sequntial consistency nomal form)和PL模型(Properly-Labeled Model)等等。

内存一致性模型列表

• 线性一致性（Linearizability）或严格一致性、原子一致性
• 顺序一致性（Sequential consistency ）
• PRAM一致性（PRAM consistency）
• 静态一致性（Quiescent consistency）
• 处理器一致性（Processor consistency）
• 松弛一致性（Release consistency ）
• 因果一致性（Causal consistency ）
• TSO一致性（Total store ordering）
• PSO一致性（Partial store ordering）
• 弱序一致性（Weak-ordering consistency）

相关话题

• 任务并行
• 面向硬件的内存模型
• 面向程序员的内存模型

参考文献

1. Designing Memory Consistency Models For Shared-Memory Multiprocessors,Computer Sciences Technical Report #1198,University of Wisconsin-Madison December 1993,Sarita V. Adve
2. Distributed Computing,Principles, Algorithms, and Systems. Ajay D. Kshemkalyani University of Illinois at Chicago, Chicago and Mukesh Singhal University of Kentucky, Lexington

外部链接

存储一致性总结