[cpp-threads] Causality on more than two processors, write atomicity

[Herb Sutter]

BTW, a typo:

>   invariant: x <= y <= x+1

should have been:

>   invariant: x-1 <= y <= x+1

There are probably more. Thanks,

Herb


> -----Original Message-----
> From: Cpp-threads_decadentplace.org.uk-bounces at decadentplace.org.uk
> [mailto:Cpp-threads_decadentplace.org.uk-bounces at decadentplace.org.uk]
On
> Behalf Of Herb Sutter
> Sent: Tuesday, September 06, 2005 4:13 PM
> To: cpp-threads at decadentplace.org.uk
> Subject: RE: [cpp-threads] Causality on more than two processors,write
> atomicity
> 
> > Herb Sutter wrote:
> > > Does that mean I can't always reliably maintain invariants, if I'm
> using
> > > unsynchronized updates (no locks) and the variables involved in
the
> > > invariant can be updated by more than one thread over the life of
> the
> > > program?
> 
> Doug replied:
> > And historically, almost no algorithms/programs have ever been
> > found to require such strong guarantees. We once challenged
> > people to come up with non-toy examples, and never got any.
> 
> Really? Off the top of my head (imagine these represent a bounded
queue,
> or a series of state changes in a FSM, or a series of barrier/gate
> flags, or...):
> 
>   int x, y;
> 
>   start: x == y == 0;
>   invariant: x <= y <= x+1
> 
>   P0: if( x == 0 ) x = 1;
>   P1: if( x == 1 ) y = 2;
>   P2: assert( invariant );
> 
> Each of P0 and P1 preserve the invariant, but P2 might fail -- is that
> right, or did I misunderstand the issue?
> 
> Assuming the above example breaks: I don't think that's a toy example,
> because it's only a degenerate case of this producer/consumer code
with
> a bounded queue of size 1 (for just one example). Here P0 can only
> dequeue an item when y is ahead of x, and P1 and only enqueue an item
> when y equals x:
> 
>   P0 (consumer, moves x forward):
>     int N = 0;
>     while(true)
>       if( y == N+1 ) {
>         // process item in position N
>         N++;
>         x = N;
>       }
> 
>   P1 (producer, moves y forward):
>     int N = 0;
>     while(true)
>       if( x == N ) {
>         // add item to queue in position N+1
>         N++;
>         y = N;
>       }
> 
> And this is fine until someone else tries to look at it:
> 
>   P2 (the observer):
>     assert( invariant );
> 
> That breaks, right? Sorry if the code's not quite right, I'm literally
> just tossing it out off the top of my head as the first thing that
comes
> to mind.
> 
> The general form of what breaks seems to be just:
> 
>   1. Pn can observe an effect E
> 
>   2. Pn cannot observe the value C that caused E
> 
>   3. C and E are related in some program invariant => inconsistency
> 
> Assuming I haven't made some other stupid oversight above (which is
> entirely likely, and please do enlighten me): I'm not sure how even a
> genius could program reliably without locks in such an environment.
> 
> Hopefully I'm missing something, because I'm not following the thread
in
> depth and you guys all have way more experience with this than I do,
but
> this part got me interested and I always like to learn what I don't
know
> so I can make progress. So, enlightenment would be appreciated!
Thanks,
> 
> Herb
> 
> 
> --
> cpp-threads mailing list
> cpp-threads at decadentplace.org.uk
> http://decadentplace.org.uk/mailman/listinfo/cpp-
> threads_decadentplace.org.uk