[cpp-threads] Whence Sequential Consistency?

[Peter Dimov]

Lawrence Crowl wrote:
> On 1/19/07, Peter Dimov <pdimov at mmltd.net> wrote:
>> Lawrence Crowl wrote:
>>> How can non-sequentially consistent atomics build
>>> a lock that enforces sequentially consistent behavior on programs?
>>
>> Why not? For one thing, a lock is allowed to wait until SC is
>> achieved, while the atomics are non-blocking.
>
> What about busy waiting?  Is this the distinction that you are drawing
> between a lock and an atomic?

OK, let's take this example:

void lock( x )
{
    while( atomic_test_and_set_acquire( x ) );
}

atomic_test_and_set_acquire is not SC; the while loop can produce non-SC 
executions. However, on the upper level, where the number of iterations is 
not visible, this doesn't matter; correctly locked programs are SC. 
Rephrased, acquire/release atomics are not sequentially consistent, but they 
can be used to build higher-level primitives that offer the user the ability 
to write SC programs. Lock-free data structures and shared_ptr (in its 
race-free uses) are other examples of SC primitives that don't require SC 
atomics.