并发对象历史

形式陈述 ​

并发对象历史 $H$ 是调用与返回事件的有限或无限序列。调用事件至少记录线程、对象、操作名、参数与请求标识；返回事件记录相同请求标识及结果。线程 $P$ 的投影 $H{|}_P$ 保留属于 $P$ 的事件。标准同步对象历史称为 well-formed，若每个 $H{|}_P$ 从调用开始，并在每次新调用前出现与上一调用匹配的返回；因此每线程至多有一个 outstanding operation。future、coroutine 或异步 API 允许多个并发请求时，应以请求标识定义匹配，而不能套用这一交替约定。

调用与返回都出现时构成完整操作，只有调用而没有返回时称为 pending。若操作 $o_1$ 的返回事件在 $H$ 中早于 $o_2$ 的调用事件，定义实时顺序

$$o_1{<}_H{o}_2.$$

区间重叠的操作在此关系下不可比。历史的 completion 可为部分 pending 调用补上匹配返回，再删除仍未完成的调用；采用哪种 completion 由具体正确性条件规定。

直觉 ​

对象历史刻意只保留客户端可见接口，把锁、CAS 重试和缓存操作隐藏起来。两个实现内部走过完全不同的路径，只要产生同一调用—返回历史，对顺序规格而言便不可区分。操作区间重叠留下的“尚无实时先后”正是并发模型允许选择线性化顺序的空间。

最终对象状态不足以代替历史：相同终态可能伴随不同返回值或违反实时顺序。正确性因此是历史集合上的条件，而不只是终态不变量。

例子与边界 ​

线程 $P$ 调用 “enqueue(1)”，随后 $Q$ 调用 “dequeue()”；若两个操作区间重叠，“dequeue” 返回 1 可以由先入队后出队的顺序解释。若返回 2，而此前没有任何 “enqueue(2)”，任何顺序化都无法满足队列规格。

若 “write(1)” 已返回，另一线程才调用 “read()”，便有 $\mathrm{write}{<}_H\mathrm{read}$；线性一致的读取不能再假装发生在写入之前。若读写区间重叠，则实时关系不排序二者。崩溃留下的 pending 调用可能已对其他操作产生可见效果，因此不能总是直接删除；线性一致性会通过 completion 精确处理。

推论与应用 ​

线性一致性公理库线性一致性Linearizability每次操作可放置在调用与返回之间的单点，使历史等价于满足实时顺序的顺序规范。在合法顺序历史之外还保持 ${<}_H$，顺序一致性公理库顺序一致性Sequential consistency共享内存中的读写操作可排成保持各线程程序顺序并解释所有读值的单一全序。只保持每线程投影。内存一致性模型在更细的读写事件上规定允许历史；并发对象、原子操作和历史检查器都以本条作为共同接口。

参考资料

• Maurice P. Herlihy and Jeannette M. Wing, “Linearizability: A Correctness Condition for Concurrent Objects,” ACM TOPLAS 12(3), 1990.
• Maurice Herlihy and Nir Shavit, The Art of Multiprocessor Programming, rev. 1st ed., Morgan Kaufmann, 2012, Chapter 3.