程序顺序在静态上是一致的,但在顺序上是不一致的示例?



作者在Maurice Herlihy和Nir Shavit的《多处理器编程的艺术》(第3章)一书中提到,顺序一致性和静态一致性是不相关的,并且有一些程序顺序的例子是一个而不是另一个。是否有一个程序顺序的例子是静态一致的,但顺序不一致?

我也在读这本书,我会试着解释我对这个问题的理解。我脑子里仍然没有全貌,所以有可能我弄错了什么:)

无论如何,请看一下书中的图 3.8。该示例显示组合不是顺序一致的。如果您了解该示例,则执行顺序不一致。

此示例按原样排列并非完全一致。让我们尝试更改它,使其静态一致,但仍然顺序不一致。我们需要做的就是延长线程 B 的方法调用,使其与线程 A 的调用重叠。例如,线程 B 中的q.enq(y)应与p.enq(x)q.enq(x)重叠,线程 B 中的p.enq(y)应与q.enq(x)p.deq(y)重叠,线程 B 中的q.deq(x)应与p.deq(y)重叠。

现在,同样的论点是有效的:这个系统在顺序上是不一致的。但是,该系统是静态一致的,因为所有内容都重叠,因此对事件的顺序没有限制。

因此,我们发现了一个静态一致但不按顺序排列的执行。

最新更新