线性一致性

在并发编程中，如果一个操作（或一组操作）由有序的调用和响应事件（事件）列表组成，则该操作（或一组操作）是可线性化的，可以通过添加响应事件来扩展该列表，例如：

• 扩展列表可以重新表示为顺序历史记录（可序列化）。
• 该顺序历史记录是原始未扩展列表的子集。

非正式地，这意味着未修改的事件列表是可线性化的，当且仅当它的调用是可序列化的，但串行调度的一些响应尚未返回。

在并发系统中，进程可以同时访问一个共享对象。 因为多个进程正在访问一个对象，所以可能会出现这样一种情况，即当一个进程正在访问该对象时，另一个进程会更改其内容。 使系统可线性化是解决此问题的一种方法。 在可线性化的系统中，尽管操作在共享对象上重叠，但每个操作似乎都是瞬时发生的。 线性一致性是一个强正确性条件，它限制了当一个对象被多个进程同时访问时可能的输出。 它是一种安全属性，可确保操作不会以意外或不可预测的方式完成。 如果一个系统是可线性化的，它允许程序员对系统进行推理。

线性一致性，它包含了对原子的更多限制性定义，例如原子操作是不能（或不会）被并发操作中断的操作，而并发操作通常是模糊的 当一个操作被认为开始和结束时。

一个原子对象可以从它的顺序定义中立即和完整地理解，作为一组并行运行的操作，它们似乎总是一个接一个地发生； 不会出现不一致。 具体来说，线性化保证系统的不变量被所有操作观察到并保持不变：如果所有操作单独保持不变量，那么整个系统都会保持不变。

并发系统由一组通过共享数据结构或对象进行通信的进程组成。 线性一致在这些并发系统中很重要，在这些系统中，对象可能同时被多个进程访问，并且程序员需要能够推理出预期的结果。 并发系统的执行会产生历史记录，即已完成操作的有序序列。

历史记录是由一组线程或进程对对象进行的一系列调用和响应。 可以将调用视为操作的开始，而响应是该操作的结束信号。 函数的每次调用都会有一个后续响应。 这可用于对对象的任何使用进行建模。 例如，假设两个线程 A 和 B 都试图获取一个锁，如果它已经被占用则退出。 这将被建模为两个线程都调用锁定操作，然后两个线程都收到响应，一个成功，一个失败。

顺序历史记录是所有调用都有立即响应的历史记录； 即调用和响应被认为是即时发生的。 顺序历史应该很容易推理，因为它没有真正的并发性； 前面的例子不是连续的，因此很难推理。 这就是线性化的用武之地。

如果已完成的操作存在线性顺序 σ，则历史是可线性化的，这样：

• 对于 σ 中每个完成的操作，该操作在执行中返回的结果与如果每个操作按 σ {displaystyle sigma 的顺序一个接一个地完成时操作返回的结果相同 } .
• 如果操作 op1 在 op2 开始（调用）之前完成（获得响应），则 op1 在 σ {displaystyle sigma } 中先于 op2。

换一种说法：

• 它的调用和响应可以重新排序以产生连续的历史记录；
• 根据对象的顺序定义，顺序历史是正确的；
• 如果响应先于原始历史记录中的调用，则在顺序重新排序中它仍必须先于它。

（请注意，这里的前两个要点与可串行化相匹配：操作似乎按某种顺序发生。这是线性化所独有的最后一点，因此是 Herlihy 和 Wing 的主要贡献。）

让我们看一下对上面的锁定示例重新排序的两种方法。

将 B 的调用重新排序在 A 的响应下方会产生顺序历史记录。 这很容易推理，因为所有操作现在都以明显的顺序进行。