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

[Herb Sutter]

P.S.: In all of this I have been assuming that P2 is able to check the
invariant atomically (i.e., read x and y as an atomic operation), else
there are other problems not due to visibility.

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: Wednesday, September 07, 2005 10:08 AM
> To: cpp-threads at decadentplace.org.uk
> Subject: RE: [cpp-threads] Causality on more than two processors,write
> atomicity
> 
> 
> Doug:
> > >>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.
> 
> Herb:
> > > 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...):
> 
> Doug:
> > You've just listed a bunch of things for which (to the best of
> > my knowledge) no lock free algorithms exist. (We are still in
> > the dark ages here.)
> 
> Hmm. Again off the top of my head (and I admit ignorance about
lock-free
> research), I know there are various lock-free hash table
> implementations. Can't all of the above be implemented on top of a
> shared hash table (albeit inefficiently, this is just to try to show
> existence)?
> 
> > I guess what I am saying is that lock-free algorithms have to deal
> > with so much other chaos that the lack of transitivity of visibility
> > across observers doesn't seem to make anything any harder. They are
> > already plenty hard enough though.
> 
> It seemed to me that "multi-variable invariants whose parts could be
> updated by >1 threads and observed by another thread" sounded like a
> case that could be common unless deliberately avoided. Are you saying
> that if I read through the published lock-free algorithms, each one
> would know and state whether it relies on this (or should do so)?
> 
> Now what about a general transformation that would make these examples
> correct by introducing another write, by changing "var == value" into
> "cas( &var, value, value )"?
> 
>   int x, y;
> 
>   start: x == y == 0;
>   invariant: x <= y <= x+1
> 
>   P0: if( cas( &x, 0, 0 ) ) x = 1;
>   P1: if( cas( &x, 1, 1 ) ) y = 2;
>   P2: assert( invariant );
> 
> Now certainly the invariant never breaks for P2 (under a sane memory
> model, including the JMM), right? Similarly, it seems to me that
> 
>   if( var < value ) // or any other nonequal comparison
>     ...
> 
> could be transformed to
> 
>   lvar = var;
>   if( lvar < value )
>    if( cas( &var, lvar, lvar ) )
>     ...
> 
> Presumably this is known, and just too expensive?
> 
> Herb
> 
> 
> --
> cpp-threads mailing list
> cpp-threads at decadentplace.org.uk
> http://decadentplace.org.uk/mailman/listinfo/cpp-
> threads_decadentplace.org.uk