Re: [boost] [lockfree] review

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

On Aug 1, 2011, at 10:49 AM, Dave Abrahams wrote:
> on Mon Aug 01 2011, Gordon Woodhull <gordon-AT-woodhull.com> wrote:
>> 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.

This is the part of the theory that seems like a cop-out to me.  You can declare certain variables to be atomic/for synchronization and then *by definition* it's not a data race?  Excuse me?  No.  It's still a race, but it's one that's condoned because you've told the implementation that you want it to be there.

Of limited usefulness maybe.  But the brilliant insight is that there is finally a way to tell the implementation which parts of the program order must be obeyed.

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

Yes.  The nice thing about the new system is that you describe the barrier effect that you want for the accesses, with a default of sequential consistency.  Instead of having plain atomic operations and having to guess where to put the barriers.  

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

Definitely not bogus.  This is the essence of a two-thread busy waiting mutual-exclusion algorithm.  If you pry apart pthread locks they may have something like this inside.  Each thread is trying to say "you first" by setting X and Y.  You only have to add another variable or two and a little logic to actually enter and leave a critical section.

Look for Peterson's "Myths about the mutual exclusion problem" for a concise description of a full algorithm (extended to N).  (Thanks to Alberto Lerner for the fine references!)

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

C++ is a multi-paradigm language.  Just as the world needs people of all different temperaments and abilities, C++ needs to support both really abstract, safe things, and really low level stuff you'd build an operating system out of.  I wouldn't advise metaprogramming for anything that's not a library.  I wouldn't advise lock-free for anything beyond the most low-level (and tiny) libraries.  But these techniques are priceless when you need them.

There may be a really intuitive way programming model for lockfree that isn't well-known yet, a way to describe invariants across many threads.  Right now they rely on many-page-long mathematical proofs.  

I heard there is a proof that CAS or LL/SC is all you need for any concurrent algorithm.  Who knows what the future holds.  But most of us should be thinking about how to make our code truly data-race free, with very few atomics.

Cheers,
Gordon