并发数据结构-1.1.4 复杂度测量&1.1.5 正确性

原文链接，译文链接，译者：张军，校对：周可人

1.1.4 复杂度测量

一个被广泛研究的方向是在理想化模型，如并行随机存取机上分析并发数据结构和算法的渐进复杂度[35, 122, 135]。然而，很少有将这些数据结构放在一个真实的多处理器上进行建模的。这里有多种原因，大部分原因跟系统硬件架构与线程异步执行的相互作用有关。想想组合树(combining tree)的例子，虽然我们能通过计算（指令数）得到O(P/logP)的加速比，但这无法反映在实证研究中[52, 129]。真实世界的行为是被上述其他因素支配的，如竞争开销，缓存行为，同步操作(例如CAS)开销，请求到达率，退避延时，数据结构在内存中的布局等等。这些因素很难用一个精确的涵盖目前所有架构的模型来量化。

采集这些方面的复杂度（的）测量方法已经由Dwork [28] ，Anderson，Yang [7]等人提出，虽然这些方法在算法设计上提供了有用的见解，但它们还是不能准确捕捉所有上述因素的影响。因此，并发数据结构的设计者通过在真实机器和模拟架构[9, 52, 97, 103]上运行微基准测试实证地比较他们的设计。在本章的剩余部分，我们普遍地根据这些数据结构基于经验观察到的行为来评价他们，并且用简单的复杂度变量来辅助直觉进行判断。

1.1.5 正确性

很容易发现，简单的基于锁的计数器，其行为跟那些顺序的实现是“相同”的。然而，很明显我们更难看到对合并树(combining tree)而言，同样如此。一般情况下，并发数据结构的实现往往是很精细的，不正确的实现并不少见。因此，声明并严格证明一个特定的设计正确地实现了所要求的并发数据结构是非常重要的。我们不希望达到这些而不精确地指明什么是“正确”。

顺序数据结构的数据结构规格描述通常更容易。例如，我们可以通过选择一组状态，并提供一个以状态，操作名，以及该操作的参数作为函数参数，将新的状态和操作返回值作为函数返回值的转换函数(trainsition function)来指明一个顺序数据结构的语义。加上指定的初始状态，转换函数(transition function)指定了该数据结构上所有可接受操作序列。计数器的顺序语义定义如下：计数器的状态是一组整数，初始状态是0。fetch-and-inc操作的转换函数在旧状态上加一来获取新状态，返回值是计数器的旧状态。

顺序数据结构上的操作是一次一个顺序执行的，我们只简单要求顺序操作的结果遵循如上讨论所指定的顺序语义。然而，对并发数据结构来说，操作不一定完全按照顺序。并发数据结构的正确性条件一般要求有些操作完全按照顺序以满足顺序语义。不同正确性条件的区别在于对总顺序的需求不同。

一个常见的正确性条件是Lamport的顺序一致性(sequential consistency)[81]，这要求总顺序上保证每个线程执行操作的顺序。从软件工程的角度来看顺序一致性有个缺点：使用顺序一致性组件实现的数据结构本身可能不是顺序一致的。

一个自然，广泛使用且克服上述问题的正确性条件是Herlihy, Wing的可线性化(linearizability)[58]，它是一个用于数据库事务的串行化条件的一个变种。可线性化需要（满足两个特性：(1)该数据结构是顺序一致的 ，(2)使其满足顺序一致性的总体顺序遵循操作执行的实时顺序。遵循实时顺序意味着如果操作O1在操作O2开始之前完成(操作之间不是并发的)，那么O1必须排在O2之前。该正确性条件的另外一种理解方式是，它要求我们能够确定每个操作执行时间间隔中的不同点，称为可线性化点，这样，如果我们根据可线性化点的顺序来对操作排序，那么排序结果会遵循顺序一致性语义。

很容易看到，基于锁的计数器是可线性化的，计数器的状态始终存储在变量X中。我们将存储增加后的值到变量X定义为fetch-and-inc操作的可线性化点。基于CAS的无锁(lock-free)实现的计数器的可线性化点同样简单，除了使用CAS指令的语义而不是论证锁语义，我们能得出结论，计数器每被修改一次就加一。

对于合并树(combining tree)来说，很明显我们更难看到它是可线性化的，因为计数器的状态在同一时间不止加一，并且因为一个fetch-and-inc操作实际上可能由之前合并的另一个操作来执行。我们定义基于合并树(combining tree)的计数器上的fetch-and-inc操作的可线性化点如下：当一个获胜线程到达树的根节点并将其累积值加到计数器上时，我们将其之前合并的操作线性化。这些操作根据之后被分发到对应操作的返回值的顺序线性化。虽然详细的可线性化证明超出了我们讨论的范围，但我们应该清楚即使是简单并发数据结构的严格的正确性证明，也是相当具有挑战性的。

直观的吸引力和模块化使可线性化(linearizability)成为一个广受欢迎的正确性条件。在本章剩余部分我们讨论的大部分并发数据结构实现都是可线性化的。然而，在某些情况下，性能和可扩展性可通过满足较弱正确性得到提高。例如，静态一致性(quiescent consistency)条件[10]降低了对总操作顺序满足实时排序的要求，但要求所有静态状态(其中无任何操作执行)之后执行的操作必须排在该状态之前执行的操作之后。一个满足这种弱正确性条件的实现是否有用跟应用有关。相比之下，可线性化的实现始终是有用的，因为设计者可以将其视为具有原子性。