执行的示例,它是顺序一致但不是静止一致的

Question

在并发程序的正确性的背景下,顺序一致性是比静态一致性更强的条件,根据Maurice Herlihy和Nir Shavit的多处理器编程技术(第3章)作者在3.4.1中也提到有顺序一致的执行不是静止一致.我不明白怎么做.有人可以投光还是提供样品执行？

Answer 1

考虑一个队列(FIFO),您将元素排入队列并使其出列.

从这篇关于并发的论文中,我读到了(第20页):

序列一致性模型中允许且静态一致性模型中不允许的场景示例如图2.1所示.两个进程共享并发队列数据结构.第一个进程排队x.在某些非重叠的后续间隔中,第二个过程将y排队.最后,第二个进程执行出队并接收y.假设排队操作之间的时间超出静止间隔,此示例是顺序一致但不是静态一致的.

图2.1:

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

此历史记录是通过顺序一致性允许的,可以是静态一致性允许或禁止的,并且可以通过线性化一致性来禁止.

如果你假设在两个队列之间队列是静止的,那么T2应该看到T1的变化,并且dequeue应该返回x.如果假设两个队列之间没有静止区间,则可以根据需要重新排序两个队列,并且deq():y是一致的.