Understanding sequential consistency

Question

Assume there are 2 threads performing operations on a shared queue q. The lines of code for each thread are numbered, and initially the queue is empty.

Thread A:

A1) q.enq(x) 
A2) q.deq()

Thread B:

B1) q.enq(y)

Assume that the order of execution is as follows:

A1) q.enq(x)  
B1) q.enq(y)  
A2) q.deq()

and as a result we get y (i.e. q.deq() returns y)

This execution is based on a well-known book and is said to be sequentially consistent. Notice that the method calls don’t overlap. How is that even possible? I believe that Thread A executed A1 without actually updating the queue until it proceeded to line A2 but that's just my guess. I'm even more confused if I look at this explanation from The Java Language Specification:

Sequential consistency is a very strong guarantee that is made about visibility and ordering in an execution of a program. Within a sequentially consistent execution, there is a total order over all individual actions (such as reads and writes) which is consistent with the order of the program, and each individual action is atomic and is immediately visible to every thread.

If that was the case, we would have dequeue x.

I'm sure I'm somehow wrong. Could somebody throw a light on this?

Answer 1

Note that the definition of sequential consistency says "consistent with program order", not "consistent with the order in which the program happens to be executed".

It goes on to say:

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

(my emphasis of "appear").

Java's memory model does not enforce sequential consistency. As the JLS says:

If we were to use sequential consistency as our memory model, many of the compiler and processor optimizations that we have discussed would be illegal. For example, in the trace in Table 17.3, as soon as the write of 3 to p.x occurred, subsequent reads of that location would be required to see that value.

So Java's memory model doesn't actually support sequential consistency. Just the appearance of sequential consistency. And that only requires that there is some sequentially consistent order of actions that's consistent with program order.

Clearly there is some execution of threads A and B that could result in A2 returning y, specifically:

B1) q.enq(y)
A1) q.enq(x)
A2) q.deq()

So, even if the program happens to be executed in the order you specified, there is an order in which it could have been executed that is "consistent with program order" for which A2 returns y. Therefore, a program that returns y in that situation still gives the appearance of being sequentially consistent.

Note that this shouldn't be interpreted as saying that it would be illegal for A2 to return x, because there is a sequentially consistent sequence of operations that is consistent with program order that could give that result.

Note also that this appearance of sequential consistency only applies to correctly synchronized programs. If your program is not correctly synchronized (i.e. has data races) then all bets are off.