[cpp-threads] Failed compare-and-swap

[Boehm, Hans]

> -----Original Message-----
> From: Peter Dimov
> Sent: Wednesday, August 01, 2007 11:33 AM
> To: C++ threads standardisation
> Subject: Re: [cpp-threads] Failed compare-and-swap
> 
> Boehm, Hans wrote:
> 
> > FWIW, java.lang.concurrent.atomic.compareAndSet returns only a 
> > Boolean. But (unlike weakCompareAndSet) it may not fail spuriously, 
> > and hence I think still needs acquire semantics in the 
> failure case to 
> > provide sequential consistency for race-free programs.
> 
> Why do you people keep claiming that acquire semantics 
> provide sequential consistency? I must be missing something. 
> 
In my view, acquire semantics in the failure case are necessary to
provide sequential consistency, if a failed CAS returns the value that
was read.  Such a CAS can clearly be used as an (expensive) replacement
for a load.  This a failed SC CAS has to provide at least the samantics
of an SC load.  Acquire semantics are clearly not sufficient, but they
are necessary.

Without spurious failures, and without returning the loaded value, I
think this should still be true:

(Atomics implicitly SC:)

Thread1:
	x = 42;
	x_init.store(true);

Thread 2:
	while (x_init.StrongCAS(false, false));
	r1 = x;

It seems like a real stretch to call an execution in which r1 != 42
sequentially consistent.  I agree that one could define this to be a
race, but that doesn't strike me as natural.  It would clearly
invalidate a theorem that for locks (except trylock abuses) + SC
atomics, our definition of race is equivalent to the natural one based
on simultaneous conflicting operations in an SC execution.  I personally
think that theorem is important, since real programmers aren't going to
look at the happens-before definition in the standard.

Hans