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