Is it possible to reproduce non-compositional queues example in Java?-CodePudding

I'm reading The Art of Multiprocessor Programming, 2nd ed.
Sequential consistency is defined there this way:

Sequential consistency requires that method calls act as if they occurred in a sequential order consistent with program order.

It's noted that sequential consistency need not preserve the real-time order, as demonstrated by this example:

       q.enq(x)         q.deq(y)
A  ...=========........=========......>

                    q.enq(y)
B  ................=========..........>
FIGURE 3.7
Sequential consistency versus real-time order. Thread A enqueues x, and later thread B enqueues y, and finally A dequeues y. This execution may violate our intuitive notion of how a FIFO queue should behave because the method call enqueuing x finishes before the method call enqueuing y starts, so y is enqueued after x. But it is dequeued before x. Nevertheless, this execution is sequentially consistent.

And finally the book says that sequential consistency is not composable:

Is sequential consistency compositional? That is, is the result of composing multiple sequentially consistent objects itself sequentially consistent? The answer, unfortunately, is no. In Fig. 3.8, two threads, A and B, call enqueue and dequeue methods for two queue objects, p and q. It is not hard to see that p and q are each sequentially consistent: The sequence of method calls for p is the same as in the sequentially consistent execution shown in Fig. 3.7, and the behavior of q is symmetric. Nevertheless, the execution as a whole is not sequentially consistent.
     p.enq(x)     q.enq(x)    p.deq(y)
A  ..=======......=======.....=======..........>

           q.enq(y)     p.enq(y)    q.deq(x)
B  ........=======......=======.....=======....>
FIGURE 3.8
Sequential consistency is not compositional. Two threads, A and B, call enqueue and dequeue methods on two queue objects, p and q. It is not hard to see that p and q are each sequentially consistent, yet the execution as a whole is not sequentially consistent.

To see that there is no correct sequential execution of these methods calls that is consistent with their program order, assume, by way of contradiction, that there is such an execution. We use the following shorthand: ⟨p.enq(x) A⟩ → ⟨p.deq()x B⟩ means that any sequential execution must order A’s enqueue of x at p before B’s dequeue of x at p, and so on. Because p is FIFO and A dequeues y from p, y must have been enqueued at p before x:
    ⟨p.enq(y) B⟩ → ⟨p.enq(x) A⟩.
Similarly, x must have been enqueued onto q before y:
    ⟨q.enq(x) A⟩ → ⟨q.enq(y) B⟩.
But program order implies that
    ⟨p.enq(x) A⟩ → ⟨q.enq(x) A⟩ and ⟨q.enq(y) B⟩ → ⟨p.enq(y) B⟩.
Together, these orderings form a cycle.

Java Language Specification has this in Chapter 17.4.3:

If a program has no data races, then all executions of the program will appear to be sequentially consistent.

My question: Is the situation in Fig. 3.8 above possible in a multithreaded data-race-free Java program?

Also, maybe it's only possible for some concurrent queue implementations.
In this case it would be great to find out which queues from java.util.concurrent are composable and which aren't, and why.

CodePudding user response：

My question: Is the situation in Fig. 3.8 above possible in a multithreaded data-race-free Java program?

No. Your JLS quote is analytical, not aspirational:

If a program has no data races, then all executions of the program will appear to be sequentially consistent.

However, the JLS's definition of sequential consistency is different from your book's. The book is apparently defining the term with respect to individual objects (queues, in its examples) whereas Java defines the same term (only) with respect to whole program executions and programs' whole memory. With Java's definition, the book's "p and q are each sequentially consistent" is nonsensical.

It follows that if you observed behavior such as is depicted in the book's Figure 3.8 in a Java program, then that would be symptomatic of a data race. Indeed, I would say that the same applies to programs in any language, provided that you apply Java's definitions of terms.

Also, maybe it's only possible for some concurrent queue implementations. In this case it would be great to find out which queues from java.util.concurrent are composable and which aren't, and why.

If it were possible for any of the queue implementations in java.util.concurrent then that would constitute a bug in those implementations.