Re: [boost] [lockfree] review

Subject: Re: [boost] [lockfree] review
From: Dave Abrahams (dave_at_[hidden])
Date: 2011-08-27 13:50:45

on Fri Aug 26 2011, "Boehm, Hans" <hans.boehm-AT-hp.com> wrote:

> I agree with Alexander and most of the recent postings.  If I write
>
> mx.lock();
> x = 1;
> mx.unlock();
> my.lock();
> y = 1;
> my.unlock();
>
> There is nothing to prevent the stores to x and y from becoming visible out of 
> order at the hardware level.  Enforcing ordering here would add needless and 
> substantial cost.  But a data-race-free program cannot observe such 
> reordering.  (One reference for that is Sarita Adve's and my PLDI 08 paper. 
> Unofficial TR version at http://www.hpl.hp.com/techreports/2008/HPL-2008-
> 56.html.  I believe Mark Batty et al have a much more complete and formal 
> proof.)

And that actually supports what I've been saying.  It doesn't really
matter if a program with data races can observe such a reordering,
because programs with data races invoke undefined behavior, so they can
observe the moon being carved open to reveal green cheese.

> If we change x and y to be atomic variables, and the stores to be 
> memory_order_relaxed, then an observer can tell the difference.  

Meaning a data-race-free observer. 

> I.e. if x and y are initially zero, and another thread does
>
> r1 = y;
> r2 = x;
>
> (or the acquire versions), it can see r1 = 1 and r2 = 0, since there are no 
> synchronizes-with relationships between threads, and thus nothing to enforce 
> ordering.  If you use memory_order_relaxed, or even the acquire/release forms, 
> things do get MUCH more complicated.

Right, but\just for the record\we were explicitly discussing the default
behaviors.

> In my mind, the main way in which sequential consistency differs from the 
> cheaper acquire/release semantics that Alexander wants is that
>
> a) Dekker's algorithm (which by itself isn't that practically interesting), 
> plus a number of real lock-free algorithms (which do matter) don't
> work.

Don't work with with SC or with acquire/release semantics?

> b) In my mind, acquire/release is a far more difficult model to explain to non-
> experts than the model for C++ with only sequentially consistent atomics.  You 
> can no longer reason about interleaving thread actions, either for purposes of 
> determining the existence of a data-race, nor when defining what data-race-
> free programs mean.

How *do* you reason about data races in that model?

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com