[cpp-threads] Whence Sequential Consistency?

[Lawrence Crowl]

Jeremy Manson <jmanson at cs.umd.edu> writes:
> So, in short, all you have to do is make sure that your conflicting
> accesses are ordered by happens-before, and you get sequential
> consistency as a guarantee of the program.  It is unnecessary to
> guarantee that individual program instructions (like CAS) provide
> sequential consistency: only that they provide happens-before.

So why are we worried about whether or not the atomic operations
are sequentially consistent?  Shouldn't the discussion be "can
these primitives be used to build sequentially consistent programs"?

Raul Silvera <rauls at ca.ibm.com> writes:
> Not any use of locks is SC. To achieve sequential consistency, you
> need all atomic operations protected by the same lock variable. So,
> I think it can be said that SC is an emergent property of this
> specific use of locks.

If a program using only locks, but different locks, may not be
sequentially consistent, then we have no effective way to guarantee
sequential consistency, and therefore why are we worrying about it
in the atomic primitives?

> Locks certainly can be implemented using acquire/release atomic
> operations as currently proposed. They cannot be implemented using
> unordered atomic operations, though.

I am presuming that you mean locks that synchronize the data
accessed within the lock.  It is certainly possible to provide
mutual exclusion with non-ordered operations.

Doug Lea <dl at cs.oswego.edu> writes:
> 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.

The main lesson here being that we want a total order on writes to
a single location to be a defined property of atomics.

> 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.

But Raul Silvera (above) seems to imply that not all uses of locks
result in a sequentially consistent program.

>> 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.

This part is what is confusing me.  I think there is more than one
definition of sequentially consistent floating around, but setting
that aside, how can non-sequentially consistent atomics build a
sequentially consistent lock?  Perhaps, I should rephrase in a more
telling manner.  How can non-sequentially consistent atomics build
a lock that enforces sequentially consistent behavior on programs?

>> 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.)

I think you miss my point.  If the data structure exports sequential
consistency as an artifact of using locks, then replacing the locks
with atomics may retract sequential consistency, and the user of
the data structure may fail.

"Paul E. McKenney" <paulmck at linux.vnet.ibm.com> writes:
> A programmer cannot -in- -general- mechanically replace a
> lock-based data structure with a lockless data structure.

This statement worries me.  It will severely inhibit code evolution.
What can we do to enable evolution?  I do not wish to require
mechanical evolution, but I don't want to require changing users
of an abstraction.

> [do_it example omitted] This gives up some consistency in exchange
> for reduced lock contention and higher do_it_count() performance.

In this example, you changed the interface, which isn't really
relevant to my point.  Sometimes changing the interface is the
right thing to do, but sometimes it is not.

>> 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.

>       int not_associative(int a, int b, int c)
>       float not_associative(float a, float b, float c)

Again, in this case, you have changed 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?

> This begs the question of whether sequential consistency should be
> considered an absolute requirement for all uses of atomics.

On the contrary, it gets to the heart of the question.  If non-SC
atomics can produce SC programs, they can be useful.  If SC atomics
can yield non-SC programs, what is the point of having them?

> When you insist on SC atomics, you are telling me that this
> split-counter use case should be abolished.  Given that its use is
> well-nigh universal, you will have to give some extremely compelling
> reasons to abolish it.

I am not insisting on SC atomics.  (See N2145.)  I am reqesting that
we be very clear on the kinds of programs we are enabling and the
consequences on software development.  At present, there have been
many examples of code, but less discussion of these latter issues.

Please forgive me for being obtuse, but I think there is something we
are collectively missing, and I want to learn what that is.

-- 
Lawrence Crowl