On Mon, Aug 1, 2011 at 11:00 AM, Dave Abrahams <dave@boostpro.com> wrote:
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.
It would mean that we could use our "traditional" reasoning. But yes, as soon as you get more than a couple of variables, it quickly becomes exponentially harder to keep track of things. Even the r1, r2 example, with only 2 shared variables, has an uncomfortable number of possible outcomes to consider. In lockfree programming you need to look at what is in your data structure, what are the possible states. At any 'atomic sequence point' or 'publication point' which known good state are you in. This is somewhat the same as any program - "what states can you be in, they better all be correct". Lockfree just tends to have more states in a small amount of code, and less (ie 0) "internal blocks" where you can temporarily break the invariants. Your code needs to be somewhat convoluted so that: 1. temporary internal spots exist where invariants can be broken 2. publication/restoration of the invariant state is a single atomic operation Tony