线性一致性（Linearizability），或称原子一致性或严格一致性指的是分布式系统与并发编程中的一种模型，确保在一个多线程或多节点的并发系统中，所有操作看起来像是瞬间發起和完成的，并且按照一个全局的时间顺序（即实际时间的先后）执行完毕，就像一个单核处理器在处理所有请求一样。
历史
线性一致性是Maurice P. Herlihy 与 Jeannette M. Wing共同提出的关于并行对象行为正确性的一个条件模型。在此之前，Lamport已经提出了顺序一致性的概念。
严格的定义
I/O自动机
Herlihy 的论文中采用了 Nancy A. Lynch 和 Mark R. Tuttle 所发明的 I/O自动机（I/O automata） 模型来定义线性一致性的概念。在 I/O automata 中程序的执行用 历史(History/schedule)来描述。所谓历史就是指一个有限的方法调用和响应事件构成的集合。严格地：我们先定义执行片段(Execution fragment)为序列：{s_0, e_1, s_1, . . . . e_n,s_n}，其中s_i为此I/O自动机的状态集，定义执行序列(Execution sequence)为s_0是初始状态的执行片段。那么历史就是执行序列中的事件子序列。在我们即将研究的并发系统中，历史中的输出事件(Output event)和输入事件(Input event)分别对应线程P对对象X的调用(Invoke)和响应(Response)。下面将响应事件记做R(P,res,X)，将调用事件记做I(P,op,X)其中P为线程名称，op为操作名称，X为对象名称，res为返回值。
基本概念
*定义响应事件R(P,res,X)与调用事件I(P',op,X')相匹配(match)，如果P=P',X=X'。
*顺序历史(Sequential history)：历史H是顺序的，如果满足以下两个条件：
**H中的第一个成员为调用事件；
**除了H中的最后一个调用事件之外，H 由相邻的、两两相匹配的调用事件和响应事件组成。
*并发历史(Concurrent history)：不是顺序历史的历史称为并发历史。
*在线程P上的子历史(Process subhistory)H|P定义为H在线程P上的射影，即H中所有线程名为P的事件构成的子集。
*如果对于H中任意的P，H|P 是顺序历史，则称H是良形式的(well-formed)。
*等价的两个历史H与H'：H \iff H' 定义为 \forall P, H|P=H'|P。
操作(Operation) e* 定义为相匹配的一对调用事件和响应事件。
*完备化函数Complete(H)：Complete(H)的结果是包含在H中的、最大的、仅含有互相匹配的调用事件和响应事件的时间序列。
*历史集S是前缀闭(prefix-closed)的，如果\forall H\in S,\forall e,H^e\in S，其中H^e代表H中以操作e结尾的一个前缀。
*对象X顺序性说明(Sequential specification)定义为对象X的前缀闭的顺序历史集。顺序性说明描述了一个对象所有可能的顺序行为。
合法的(Legal)顺序历史指的是\forall x,H|x（指H中对象为x的那些事件）属于x*的顺序性说明。
线性一致性的形式化定义
*对于给定的一个历史H，其中必然蕴含着一个非自反的偏序关系（可称之为“之前” - precede），其定义如下：e_0 ， 若 res(e_0)在inv(e_1)之前。
如果满足以下条件，则定义历史 H是线性一致的(或可线性化的*-linearizable)：
#首先我们将H 扩展为 \mathbf{H'}；
#Complete(\mathbf{H'})等价于一个合法的顺序历史S；
#
例子
线性一致性的性质
*线性一致性最重要的性质就是其“局部性”（Local property, 或可组合性 - Compositional），即数个线性一致单对象历史的组合也是线性一致的。
*线性一致性的非阻塞性(Non-blocking property)：线程P对完全操作(total function)的调用永远不会阻塞。
严格一致性
相关的话题
*任务并行
*内存一致性模型
*顺序一致性
参考资料
评论 (0)