3.3 设计考虑
这个问题可以归结为:如何使多线程程序的行为与串行程序行为一致?
这就需要不同作用的一致性模型。一致性模型是一套规则,它定义了系统特定的行为方式。已经提出了大量一致性模型,每个模型都在效率和严格性之间权衡。其中一个实例是顺序一致性模型(sequential consistency model)。
在顺序一致性模型中,在共享存储器对象进行操作的所有事件应该发生在不同的时间点。此外,这些事件的时间点顺序应该符合每个线程的内部顺序。不同线程中的事件可以重排,从而使对一个对象总的事件/方法调用执行序列的效果满足串行规范(亦即与单个线程执行时的行为一致)。图3-5展示了这种顺序重排的一个实例。
这种情况下顺序一致性模型的问题在于其非组合性:将两个保证顺序一致性的软件模块组合在一起并不能保证整体满足顺序一致性。图3-6展示了一个实例用以说明这种情况,其中图3-5中的序列被复制了一份,虽然两个独立序列是顺序一致性的,但是没有办法保证两个时间线的组合依然满足顺序一致性。
更为严格的一致性模型是序列化(linearizability)[45]:事件满足同一时刻执行一个事件并且立即生效。后一要求是由于称为序列点的需要。序列点是一个方法调用期间生效的时间点。序列点的引入有两个意义。
1.可以根据方法的序列点来进行全排序。在一个方法的开始调用和结束返回这一时间窗口期间可以以任意点作为序列点。最后的排序结果必须与考虑序列化的并发执行的一个串行执行结果一致。
2.虽然并不强制加锁(并且实际上从性能角度考虑也应该避免加锁),但是在一个方法调用期间对一个对象加锁等价于使其效果立即生效并对所有其他线程可见。最简单的方法是使用加锁机制,因此接下来的几节讨论这些机制。
每个序列化执行都满足顺序一致性,但反之则不一定。图3-7展示了一个序列化执行示例。
接下来的几节将研究两种加锁机制,虽然其在功能上是等价的,但是在同步线程时导致不同的模式。