Re: [boost] [lockfree] review

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 <gordon-AT-woodhull.com> 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.

Exactly.

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

Exactly.

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