[jmm-dev] Sequential Consistency

Doug Lea dl at cs.oswego.edu
Tue Feb 25 04:26:45 PST 2014


On 02/24/2014 05:44 PM, Paul E. McKenney wrote:
> This is my experience as well -- I have seen very few actual algorithms
> that relied on SC.

This seems to be the attitude of almost all developers of
non-lock-based algorithms: Explicit ordering constraints are
critical, but program-wide SC is not. Which is nearly opposite
to almost every developer's view of lock-based programs: any ordering
is OK so long as SC is maintained.

One place these different views meet up is when creating locks
out of non-blocking primitives. So there must be guaranteed
ways of achieving SC using modeful/fenced accesses.

Beyond that, the problem seems underconstrained.

I'm not sure that litmus-test-style examples will suffice
to provide an answer. When you are not dealing with locks,
it seems that for every odd consequence of some non-SC rule,
you can find an equally odd one for an SC-based rule.
For example, Ali Sezgin (who is on this list) has written up some
especially bizarre sequentially consistent examples in:
Sezgin, Ali, and Ganesh Gopalakrishnan. "On the definition of sequential 
consistency." Information processing letters 2005.
http://www.cs.utah.edu/formal_verification/publications/june2013update/dblp/2005/2/j23.pdf

-Doug



More information about the jmm-dev mailing list