concurrency - 顺序一致但非静态一致的执行示例

Question

根据 Maurice Herlihy 和 Nir ​​Shavit 的多处理器编程艺术(第 3 章)，在并发程序的正确性方面，顺序一致性是比静态一致性更强的条件
作者还在 3.4.1 中提到有顺序一致的执行不是静态一致的。我不明白怎么做。有人可以扔灯或提供示例执行吗？

Answer 1

考虑一个 queue (FIFO)您将元素入队和出队的位置。
来自 this dissertation关于并发，我读到(第 20 页):

An example of a scenario that is allowed in the sequential consistencymodel and disallowed in the quiescent consistency model is shown inFigure 2.1. Two processes share a concurrent queue data structure. Thefirst process enqueues x. At some non-overlapping subsequent interval,a second process enqueues y. Finally the second process performs adequeue and receives y. This example is sequentially consistent but isnot quiescently consistent, assuming that the time between enqueueoperations falls outside the quiescence interval.

Figure 2.1:

T1:  --- enq(x) ---------------------------
T2:  ------------- enq(y) ---- deq():y ----

This history is permitted by sequential consistency, can be eitherpermitted or forbidden by quiescent consistency, and is forbidden bylinearizable consistency.

如果您假设在两个入队之间队列是静止的，那么 T2 应该看到来自 T1 的变化，出队应该返回 x。如果您假设两个队列之间没有静止间隔，那么可以根据需要对两个队列进行重新排序，并且 deq():y 是一致的。