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
> x = 1;
> y = 1;
> 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
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
> 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
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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk