[cpp-threads] Whence Sequential Consistency?

[Raul Silvera]

--
Raúl E. Silvera         IBM Toronto Lab   Team Lead, Toronto Portable
Optimizer (TPO)
Tel: 905-413-4188 T/L: 969-4188           Fax: 905-413-4854
D2/KC9/8200/MKM


cpp-threads-bounces at decadentplace.org.uk wrote on 01/18/2007 09:14:10 PM:

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

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.

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

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

Using a data structure implemented by locking doesn't give its client
automatic SC. It only provides SC on the internal state of the data
structure, which in general is not visible to the client. If the behavior
of the data structure is the same with the lock-free implementation, then
the client would lose nothing. Of course, you probably cannot take any
lock-based data structure and come up with a lock-free implementation, as
the behavior of the data structure may depend on the SCness of its internal
state.

> 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
>
> --
> cpp-threads mailing list
> cpp-threads at decadentplace.org.uk
> http://www.decadentplace.org.uk/cgi-bin/mailman/listinfo/cpp-threads