Boost logo

Boost :

Subject: Re: [boost] [lockfree] review
From: Dave Abrahams (dave_at_[hidden])
Date: 2011-08-01 10:49:37

on Mon Aug 01 2011, Gordon Woodhull <> wrote:

> On Jul 31, 2011, at 1:05 PM, Dave Abrahams wrote:
>>> and threads may see each others' actions in the wrong order, so a
>>> weak memory model can actually break invariants even if the code is
>>> good.
>> I don't get it. Please, show me an example.
> I am definitely not an expert. I'll quote a diagram from this
> fascinating paper by Adve and Boehm [1], using Dekker's mutual
> exclusion algorithm as an example
> Initially X = Y = 0
> Thread 1
> X = 1;
> r1 = Y;
> Thread 2
> Y = 1;
> r2 = X;
> Can r1 = r2 = 0?

Sure they can, that's a race condition: Thread1 modifies X while thread
2 reads it. Anything could happen. Why would anyone expect otherwise.

> And they give various reasons why the processor might reorder the
> instructions. After all, with each thread considered its own program,
> there is no dependency between X and Y that should mean it's incorrect
> to reverse the operations.


>> Anyway, what's the "wrong order?" If one thread is depending on the
>> order of things that happen in another thread without both threads using
>> the synchronization necessary to ensure that order, it's a race
>> condition (a.k.a. a bug), right?
> All of the classic lock-free algorithms, including those that are the
> basis for the synchronization primitives we should usually use, have
> data races.

IIUC, accesses to atomics are not in and of themselves data races. But
it doesn't surprise me a bit to learn (again) that lock-free algorithms
are hard to think about.

> At a low level it is sometimes necessary to use a variable for
> synchronization.

Sure, an atomic variable. And along with those come associated memory
barrier effects, right?

> The same paper argues that we should be writing our programs race-free
> except with specially marked synchronization variables, e.g. Java/C#
> "volatile" or IIUC C++11 atomics with the default options.
> "To write Figure 1 correctly under data-race-free, we need simply
> identify the shared variables X and Y as synchronization variables.
> This would require the implementation to do whatever is necessary
> to ensure sequential consistency, in spite of those simultaneous
> accesses."

Meh. Isn't this a bogus example? What is "correctly" supposed to mean?
They don't even describe the intended semantics (or you haven't quoted
that description).

> And then the implementation is allowed to do almost anything it wants
> with the rest of our code, since we programmers have agreed to keep it
> race-free.
> IMO using variables for synchronization does make for confusing
> programs and should be reserved only for very tiny components or very
> simple purposes. Plus we must remind ourselves over and over how
> expensive atomic operations and the now-implicit memory barriers are.
> Use Locks.


Dave Abrahams
BoostPro Computing

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