Boost logo

Boost :

Subject: Re: [boost] [lockfree] review
From: Gottlob Frege (gottlobfrege_at_[hidden])
Date: 2011-08-06 01:31:09


On Mon, Aug 1, 2011 at 11:00 AM, Dave Abrahams <dave_at_[hidden]> 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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk