Re: [boost] [lockfree] review

Subject: Re: [boost] [lockfree] review
From: Gordon Woodhull (gordon_at_[hidden])
Date: 2011-08-01 02:38:42

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?

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.  At a low level it is sometimes necessary to use a variable for synchronization.  

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

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.

Gordon
(going back to metaprogramming where the syntax is awful but the semantics are clear as water)

[1] http://rsim.cs.illinois.edu/Pubs/10-cacm-memory-models.pdf