在并发程序正确性的上下文中，根据 Maurice Herlihy 和 Nir Shavit 的 The art of multiprocessor programming（第 3 章）作者还在 3.4.1 中提到，顺序一致性执行比静态一致性更强。默契一致。我不明白怎么做。有人可以点亮或提供示例执行吗？
问问题
4097 次
1 回答
11
考虑一个队列 (FIFO)，您可以将元素入队和出队。
从这篇关于并发的论文中，我读到（第 20 页）：
图 2.1 显示了顺序一致性模型中允许而静态一致性模型中不允许的场景示例。两个进程共享一个并发队列数据结构。第一个进程将 x 排入队列。在某个不重叠的后续时间间隔，第二个进程将 y 排入队列。最后，第二个进程执行出列并接收 y。这个例子是顺序一致的，但不是静止一致的，假设入队操作之间的时间落在静止间隔之外。
图 2.1：
T1: --- enq(x) --------------------------- T2: ------------- enq(y) ---- deq():y ----这种历史被顺序一致性所允许，可以被静态一致性所允许或被禁止，被线性化一致性所禁止。
如果您假设在两个入队之间队列是静止的，那么 T2 应该会看到来自 T1 的更改，并且出队应该返回 x。如果您假设两个队列之间没有静止间隔，则可以根据需要对两个队列重新排序，并且 deq():y 是一致的。
于 2013-10-07T12:50:00.920 回答