[cpp-threads] Whence Sequential Consistency?

[Lawrence Crowl]

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?

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 would
have to use platform-specific techniques, which would surely inhibit
development of new locks.

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.  The reason is that sequential consistency became an
implied property of the locked data structure and removing that
property would throw unknown numbers of clients into the land of
undefined and untested behavior.

An important property of programming languages is interface
invariance.  It ought to be possible for the implementation of an
interface to change without changing the properties of the interface.
So, if locks and atomics have different sequential consistency
properties, how do I not get sequential consistency by adding locks?
How do I preserve sequential consistency when removing locks?

-- 
Lawrence Crowl