[cpp-threads] Whence Sequential Consistency?

[Doug Lea]

Lawrence Crowl wrote:
> Something about sequential consistency has been bothering me for a
> while, and I am not sure how to articulate the problem, but I will
> give it a shot.
> 
> Where does sequential consistency come from?
> 
> The prevailing notion is that atomic operations are not (necessarily)
> sequentially consistent, but that the equivalent locked code is.
> How is this so?
> 

First, a mechanics-level answer:

Locks that are implemented using CAS (or even writes, as in
Dekker's algorithm etc) leverage the fact that on
cache-coherent machines, writes to a given location (i.e.,
the one serving as a lock) are globally totally ordered.
So a successful CAS globally orders two attempted lock acquires.
And in a race-free program, that lock covers all of the
variables accessed within it, so they are also ordered.
Most other lock-like synchronization works similarly.
But optimistic techniques differ in that they allow
unordered concurrent reads, but must check before
committing that the variables weren't concurrently
modified since reading them. Since the commits entail
CAS or write, they are per-location totally ordered,
so all is well modulo famous issues like the ABA problem
and reliance on causal consistency in addition
to cache coherence.

> If locks are implemented with atomic operations, then it does not
> seem to me that sequential consistency would be an emergent property
> of locks, which then implies that it is a defined property of locks.
> If so, then no one could write a new lock using pure C++. 

They can if they have an atomics library, plus, hopefully, an API to
OS blocking primitives so you don't have to just live with spinlocks.
That's what we do in java.util.concurrent -- create synchronization
constructs out of these low-level contructs that most programmers never
use directly. (See http://gee.cs.oswego.edu/dl/papers/aqs.pdf in
case you are curious about details about the main lock-construction
toolkit in j.u.c.)

> More importantly, a difference in sequential consistency between
> locks and atomics implies that a programmer _cannot_ replace a
> poor-performing lock-based data structure with a lock-free data
> structure. 

If someone implements a lock in a way that does not maintain
the lock's specified consistency properties, then it is a bug.
(People can also build other things using atomics that are not locks.)

In java.util.concurrent, we updated specs for Java 6 to more
clearly specify the happens-before properties guaranteed by all
classes/methods. Hopefully C++ libraries will do the same.

-Doug