Demonstrating surprising but correct behavior of sequentially consistent program ...

[kedar mhaswade]

This might be a stupid question but I believe it to be sympathetic to the machine. Please be forgiving.

The book 'The Art of Multiprocessor Programming (Herlihy/Shavit)' says (3.4.1):

This execution may violate our intuitive notion of how a FIFO queue should behave: the call enqueuing x finishes before the call dequeuing y starts, so although y is enqueued after x, it is dequeued before. Nevertheless, this execution is sequentially consistent. Even though the call that enqueues x happens before the call that enqueues y, these calls are unrelated by program order, so sequential consistency is free to reorder them.

 

Is it possible to demonstrate this at all by writing a program? 

I have done a naive (and perhaps incorrect) attempt at: https://gist.github.com/kedarmhaswade/6894081. A few runs [1] of this Java program (on my quadcore Linux box) make me believe that it's possible that the FIFO contract of the queue is violated while the program still remains correct as far as the sequential consistency is concerned. Is this what the book trying to say above? And is this program I've written any good?

1.

➜  mt git:(master) ✗ java -server SurprisingSequentialConsistency

➜  mt git:(master) ✗ java -server SurprisingSequentialConsistency

➜  mt git:(master) ✗ java -server SurprisingSequentialConsistency

surprising!

aput_time: 1381284014019

bput_time: 1381284014020

put value: 3

took value: 1

➜  mt git:(master) ✗ java SurprisingSequentialConsistency        

➜  mt git:(master) ✗ !javac

➜  mt git:(master) ✗ javac -g SurprisingSequentialConsistency.java

➜  mt git:(master) ✗ java -server SurprisingSequentialConsistency 

surprising!

aput_time: 1381284035117

bput_time: 1381284035118

put value: 151

took value: 66

[Attila-Mihaly Balazs]

I think the code shows that currentTimeMillis is not synchronized across cores rather than timing inconsistencies. In multithreaded environment I don't think it's useful to try to deduce the "global ordering" of things. Rather we should concentrate on the "happened before" (ie. can we say that A happened before B). A short, somewhat related video :-) - https://www.youtube.com/watch?v=kGsbBw1I0Rg

Best,

Attila