on Mon Aug 01 2011, Tim Blechmann <tim-AT-klingt.org> wrote:
[quick post, have some more in my outbox, but i'm at a conference this week, where they cut imap/smtp ports]
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 fifo code for example contains code like:
atomic<> head_, tail_;
head = head_.load(); tail = tail_.load();
head2 = head_.load();
if (head == head2) do something
the correctness of this algorithm depends on the order of the loads: load head before tail and load tail before head2. without a memory model, both the compiler and the CPU are allowed to reorder loads (or head2 could simply use the value of head without actually reloading it)
But I never said we don't need a memory model! Of course, we do need rules that allow us to ensure temporal sequencing of operations. All I said was that sequential consistency doesn't seem to make parallelism much easier. In particular, in C++ we're only talking about sequential consistency for data-race-free programs, which is kind of a funny hedge. It means that your atomics and the code around them as a whole blob respect some plausible interleaving of the instructions in single threads, but it doesn't say anything about the interaction of most variables, which (I hope) are not atomic. In other words, sequential consistency only helps those people already working in the rarified air of atomics and lock-free algorithms, where if you're going to play you'd better have a firm grasp of even lower-level concepts like memory barriers. OK, I guess this all scales up to those of us using locks... if you don't have sequential consistency among sections using the same mutex, the mutex can hardly be said to be working. So let me try saying what I mean differently: even a hypothetical programming model where *everything* (including non-atomics) is guaranteed to be sequentially consistent still seems insufficient to make parallel programming tractable. -- Dave Abrahams BoostPro Computing http://www.boostpro.com