[cpp-threads] A niggle on the atomic model (N2145)

[Paul E. McKenney]

On Thu, Apr 19, 2007 at 02:51:59PM +0100, Nick Maclaren wrote:
> "Paul E. McKenney" <paulmck at linux.vnet.ibm.com> wrote:
> >
> > As I understand it, this will unconditionally fail.  The locations of a
> > load_linked() and the corresponding store_conditional() must match, or the
> > store_conditional() will fail.  In this case, the enclosing "if" statement
> > guarantees mismatch, which in turn guarantees store_conditional() failure.
> 
> That is not my understanding, and would make it a most unhelpful
> interface, but I will check when I get back.

The usual use is "fetch-and-op":

	do {
		r1 = load_linked(&x);
		r2 = f(r1);
	} while (!store_conditional(&x, r2));

This allows you to atomically perform a more-or-less arbitrary operation
f() on a single variable.  There have been generalizations of this
proposed by various researchers, for example, transactional memory,
but this "fetch-and-op"-ready functionality is what is available on
commercial RISC-based machines.

> > Even given an extended load_linked()/store_conditional() that did what you
> > want, in most implementations, store_conditional() is subject to spurious
> > failures due to interrupts, context switches, exceptions, and the like.
> 
> That is not the point.  Such uses will cause a delay, but not an
> infinite one, unless there is a hard error.  The example above is
> something that will NEVER complete (i.e. it will loop indefinitely).

OK.  I was concerned about restarting the copy -- for example, if
the first store_conditional were to succeed and the second to fail.

> > My take was that the point of the address-free requirement is that
> > the data structure should itself either contain or identify any
> > mutual-exclusion apparatus required to make accesses to the same object
> > from different virtual addresses be atomic.  But I must defer to Lawrence
> > and Hans on this.
> 
> How?  Virtually no operating system lets applications even find out
> post-hoc what the virtual/physical translations are.  To do that
> needs operating system support, of a form that has been strenuously
> resisted for 4 decades.  How do you do it without that and without
> a global barrier?

My guess would be that one would either use an atomic operation that
covers the entire atomic object, place the mutual-exclusion data structure
in the atomic object itself, place a pointer to the mutual-exclusion
data structure in the atomic object itself, or simply use a global lock
for all atomic objects.  But there are a very large numbers of ways to
approach this.

						Thanx, Paul