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

[Herb Sutter]

This is very helpful, Doug. 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 Doug Lea
> Sent: Wednesday, September 07, 2005 12:45 PM
> To: cpp-threads at decadentplace.org.uk
> Subject: Re: [cpp-threads] Causality on more than two processors,write
> atomicity
> 
> Herb Sutter wrote:
> > ...
> 
> First, I'm not being intentionally evasive to be annoying, but because
> I think the approach you are taking here isn't very productive wrt
> lock-free algorithms. Luckily, Alexander has supplied some non-evasive
> answers about how to get some of the effects you describe.
> 
> >
> > 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)?
> 
> Actually, until fairly recently, research papers on non-blocking
> algorithms tended not to provide sufficient detail about assumed
> memory models, so you do sometimes need to be careful while reading
> them.
> 
> >
> > Now what about a general transformation that would make these
> > examples correct
> 
> 
> In general, non-blocking algorithms can rarely rely on
> relations among independently updated variables. And usually
> when you do rely in them, you explicitly test them. So you
> often see code like
> 
> for (;;) {
>    a = something.field;
>    b = anotherThing.anotherField;
>    if (a doesn't have required relation to b)
>      continue; // reread
>    stuffRelyingOnRelation(a, b);
> }
> 
> One reason the relation might not hold is inter-observer agreements
> about order of updates performed in different threads. But there are
> usually plenty of other reasons and "stronger" read/write rules
wouldn't
> help most of them, so it's easier/cheaper/better just to retry.
> 
> For a random example, see the dual-data structure algorithms
> we used in new versions of java.util.concurrent.SynchronousQueue,
> that are based on similar constructions in Michael & Scott wait-free
> queue. At:
> 
> http://gee.cs.oswego.edu/cgi-
>
bin/viewcvs.cgi/jsr166/src/main/java/util/concurrent/SynchronousQueue.ja
va
> 
> There's quite a lot of consistent-read retrying in the
> TransferQueue and TransferStack transfer methods
> 
> -Doug
> 
> 
> --
> cpp-threads mailing list
> cpp-threads at decadentplace.org.uk
> http://decadentplace.org.uk/mailman/listinfo/cpp-
> threads_decadentplace.org.uk