[cpp-threads] Whence Sequential Consistency?

[Jeremy Manson]

I can answer this for Java; I believe that the C++ case is a little more 
complicated, but substantively the same.

In Java, we made a clear decision to pursue certain properties of 
programs.  We built it on some notions that are fairly common in the 
literature:

1) We say that two accesses conflict if they are accesses to the same 
shared variable, and at least one is a write.

2) When two conflicting accesses are not ordered by happens-before in a 
particular execution of a program, they are said to be in a data race.

3) If, in all sequentially consistent executions of a program, there are 
no data races, then the program is said to be "data race free".

4) We guarantee sequentially consistent behavior for all data race free 
programs.

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.

An example, using Java's volatile, which is sounding less and less as if 
it will be SC:

Let's say int x = 0 and volatile int v = 0

Thread 1:
x = 1;
v = 1;

Thread 2:
r1 == v;
if (r1 == 1) {
   r2 = x;
}

There is a happens-before relationship between every write to a volatile 
variable, and every read that sees the value that was written.  Thread 2 
will only read from x if it sees 1 for v, in which case there was a 
happens-before relationship between the write to v in Thread 1 and the 
read of v in Thread 2.  Therefore, there can be no accesses of x in an 
execution of this program that are not ordered by the happens-before 
relationship -- no data races.  Because this program is data-race-free, 
it will behave in a sequentially consistent fashion.

I believe that this high-level intuition maps pretty easily to low level 
implementation.  Does that go any distance to answering your question?

					Jeremy

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