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

[Doug Lea]

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.java

There's quite a lot of consistent-read retrying in the
TransferQueue and TransferStack transfer methods

-Doug