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