Boost logo

Boost :

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

> 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

Boost list run by bdawes at, gregod at, cpdaniel at, john at