[jmm-dev] Sequential Consistency

[Doug Lea]

Another in the continuing series of issues to contemplate:

There's a tension between those who believe that all "correct"
programs are provably sequentially consistent versus those who
consider sequential consistency as a goal only of lock-based programs;
not necessarily of those using lock-free techniques and/or are
components of distributed systems. (see for example Herlihy & Shavit's
"The Art of Multiprocessor Programming"
http://store.elsevier.com/The-Art-of-Multiprocessor-Programming/Maurice-Herlihy/isbn-9780080569581/)

No one disagrees about the need for a memory model guaranteeing that
DRF lock-based programs are sequentially consistent.

Other cases may be less clear cut.  For the most famous example: Can a
program using non-lock-based techniques (for example, using Java
volatile loads/stores) be "correct" if it fails some variant of the IRIW
test?  Is IRIW conformance an unnecessary action-at-a-distance
by-product of SC, or does it play some intrinsically useful role in
assuring correctness?

IRIW is not the only example of a case in which SC imposes conditions
that some programmers in some contexts seem not to care about.  But
it is most famous because it so clearly impacts the nature and cost of
mappings (for various modes of load, store, and CAS) on some existing
processors as well as potential mappings on future processors.

I won't yet try to summarize different positions and rationales,
but for now just invite further discussion.

-Doug

PS: As a reminder, here's IRIW. Given global x, y:
   Thread 1: x = 1;
   Thread 2: y = 1;
   Thread 3: r1 = x; r2 = y;  // sees r1 == 1, r2 == 0
   Thread 4: r3 = y; r4 = x;  // sees r3 == 1, r4 == 0