执行顺序一致但不是静态一致的示例 [英] Example of execution which is sequentially consistent but not quiescently consistent

问题描述

在并发程序的正确性的上下文中，顺序一致性比静态一致性更强的条件根据多核处理器编程的艺术由Maurice Herlihy和Nir Shavit（第3章）
作者还在3.4.1中提到，是顺序一致的执行，不是静态一致的。我不明白怎么样。

解决方案

考虑一个队列（FIFO），您将入队和出队元素。

关于并发的本篇论文 ，我阅读（p.20）：

在连续一致性允许的情况下的一个例子
模型和不允许在静态一致性模型中显示为
图2.1。两个进程共享并发队列数据结构。
第一个进程入队x。在一些不重叠的后续间隔，
，第二个进程使y排队。最后，第二个进程执行
出队并接收y。这个例子是顺序一致的，但是
不是静态一致的，假设enqueue
操作之间的时间落在静止间隔之外。

图2.1：

  T1：--- enq（x）----------------- ---------- 
 T2：------------- enq（y）---- deq（）：y ---- 
  

此历史记录是由顺序一致性允许的，可以是
允许或禁止由静态一致性，并被禁止
线性化一致性。

如果假设两个队列之间的队列是静止的，从T1，并且出队应该返回x。如果假设两个入队之间没有静态间隔，那么可以根据需要重新排序两个入队，而deq（）：y是一致的。

In the context of correctness of concurrent programs, Sequential consistency is stronger condition than quiescent consistency according to The art of multiprocessor programming by Maurice Herlihy and Nir Shavit(chapter 3) Authors also mention in 3.4.1 that there are sequentially consistent executions that are not quiescently consistent. I don't understand how. Could somebody throw a light or provide sample execution ?

解决方案

Consider a queue (FIFO) to which you enqueue and dequeue elements.

From this dissertation about concurrency, I read (p.20):

An example of a scenario that is allowed in the sequential consistency model and disallowed in the quiescent consistency model is shown in Figure 2.1. Two processes share a concurrent queue data structure. The first process enqueues x. At some non-overlapping subsequent interval, a second process enqueues y. Finally the second process performs a dequeue and receives y. This example is sequentially consistent but is not quiescently consistent, assuming that the time between enqueue operations 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 either permitted or forbidden by quiescent consistency, and is forbidden by linearizable consistency.

If you assume that between the two enqueue the queue was quiescent, then T2 should see the changes from T1, and the dequeue should return x. If you assume there was no quiescent interval between the two enqueues, then two enqueues can be reorderd as you wish, and deq():y is consistent.

这篇关于执行顺序一致但不是静态一致的示例的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！