[concurrency-interest] AtomicReferenceweakCompareAndSet "Mayfailspuriously"?

David Holmes dcholmes at optusnet.com.au
Sun May 28 23:01:36 EDT 2006


I think confusion is spreading.

The original question regarding what "may fail spuriously" means was
answered  a while back: it means that weakCAS can fail for reasons other
than the current value not being the expected value. This has nothing to do
with being atomic or volatile, it has to do with how LL/SC works. See old
mail for details.

The weakCAS further does not have the volatile semantics that atomics
otherwise have. This means, as Bill has been describing, that a successful
weakCAS doesn't mean you will see the most recent values of other variables
(where a strong CAS would guarantee that).

What Cliff wants is an atomic integer for use with counters that is not
volatile, so that the extra memory barriers required for violatile semantics
can be elided. This gives rise to a large performance boost in the context
Cliff wants to use it - performance counters. Cliff can use weakCAS for this
purpose.

Bill proposed a way of describing the  non-volatile-ness of weakCAS, in a
way that I disagree with and have subsequently been discussing.

The "atomicity" of the weakCAS is not at issue - it is atomic. It is the
lack of memory barriers (ie volatile happens-before semantics) that means
that the weakCASing of the array reference does not guarantee you will see
the correct array elements.

Hope that clarifies things.

Cheers,
David

> -----Original Message-----
> From: concurrency-interest-bounces at cs.oswego.edu
> [mailto:concurrency-interest-bounces at cs.oswego.edu]On Behalf Of Pete
> Soper
> Sent: Monday, 29 May 2006 12:47 PM
> To: Bill Pugh
> Cc: concurrency-interest at cs.oswego.edu; dholmes at ieee.org
> Subject: Re: [concurrency-interest] AtomicReferenceweakCompareAndSet
> "Mayfailspuriously"?
>
>
> Ah. The original question brought a reference to the atomic package doc,
> which explains that "spurious failure" means a failure without apparent
> reason. This scenario below is an example of a reason that might not be
> apparent.  And Cliff is arguing the value of the weak CAS, and weak ==
> not atomic. If the CAS isn't atomic then it's wide open to data races.
> Surely "data race" would give more of a clue where "spurious" does not?
>
> The race is between the write of int[] and int[]{1} but it's enabled by
> the lack of atomicity of the CAS.
>
> I'm ready for the visible VM. Just turn the crank very, very slowly and
> all will be revealed. So in this case the surprising/not
> apparent/spurious/data race order is "read null, write int[], read
> int[], write int[]{1}".
>
> -Pete
>
> Bill Pugh wrote:
> > No, here is a concrete example of the issue:
> >
> >     AtomicReference<int []> r = new AtomicReference<int []>();
> >
> >     public void thread1() {
> >         r.weakCompareAndSet(null, new int [] {1});
> >     }
> >
> >     public int thread2() {
> >         int [] a = r.get();
> >         if (a == null) return -1;
> >         return a[0];
> >     }
> >
> > If weakCompareAndSet does not create a happens-before order, then it is
> > possible that thread2 will return 0.
> >
> > With a compareAndSet that creates a happen-before ordering, that would
> > not
> > be possible: the initialization of the array would be ordered before
> > the read of a[0], and thus seeing the value 0 would be impossible. But
> > without
> > a happens-before ordering, it would be valid to reorder the actions in
> > thread 1 to:
> >
> >     int [] tmp = new int[1];
> >     r.weakCompareAndSet(null, tmp);
> >     tmp[0] = 1;
> >
> > thus allowing thread2 to see the value 0.
> >
> >     Bill
> >
> >
> > On May 28, 2006, at 10:01 AM, Pete Soper wrote:
> >
> >> Bill Pugh wrote:
> >>> On May 21, 2006, at 6:36 PM, David Holmes wrote:
> >>>
> >>>
> >>>> Bill Pugh writes:
> >>>>
> >>>>> I would explain this differently (actually, the JMM requires that
> >>>>> it  be explained differently):
> >>>>>
> >>>>> weakCompareAndSet has volatile semantics, _except_ that it doesn't
> >>>>> create any happens-before edges.
> >>>>>
> >>>> But isn't the existence of those edges the only thing that
> >>>> distinguishes
> >>>> volatile semantics from non-volatile (barring the 64-bit atomicity
> >>>> issue)?
> >>>>
> >>>
> >>> Nope. Volatile semantics also mean that it it is a synchronization
> >>> action,
> >>> that there is a total order over synchronization actions, and that
> >>> each volatile
> >>> read sees the value of the write to that variable that occurred
> >>> most  recently
> >>> in that total order.
> >>>
> >>> Plus, the CAS happens atomically (or, for weak CAS, fails spuriously).
> >>>
> >> So for weak CAS the write  is  sometimes visible after  read, but for
> >> CAS, write visible  iff read visible?
> >>
> >> That is, given a "visible read" r and a "visible write" w, for CAS  w
> >> <==> r but for weak CAS it's w "sometimes after" r. That is, the
> >> visibility of the write of the CAS is stochastic (random), in
> >> relation to the read done by the CAS.
> >>
> >> (mostly rhetorical questions)
> >> If I understand this right then I understand your use of "fails" and
> >> I understand the unreliable performance counter that Cliff is
> >> yearning for. I guess the hard part of that API would be the spec?
> >> How do you specify something like this in a way that is crystal clear
> >> to all users or else prevents injury if they shouldn't be using it?
> >> "Use of this API requires certification that you understand Sipser
> >> 2nd edition section 0.3 'finding proofs'"?  How could we (everybody
> >> trying to make Java better) hope to communicate about visibility of
> >> memory operations in a lowly piece of API javadoc? It's easy to say
> >> we'd just leave "happens-before" out of the weak CAS spec, but that
> >> would be like a lion trap with a sign on the far side that says in an
> >> obscure dialect of Martian "Read this before proceeding. Look down."
> >> I guess I'm yearning for a java.spec.philosophy list.
> >>
> >> -Pete
> >>
> >> PS And this clarifies something I'd been pondering lately while
> >> blowing some cobwebs out of my math understanding, which is whether
> >> happens-before is impossible if there is no before or no after. I
> >> think I finally "get it" and there's hope for me properly writing a
> >> topological sort after all. It's been 30 years since Steve Schleimer
> >> (Data General mentor) caused me to wrestle with those and I cried
> >> "uncle" then (American slang wrestling term for "I concede: you won").
> >> PPS This list is fun!
> >>
> >>>     Bill
> >>>
> >>>
> >>>
> >>>>> So, here is the question we should discuss:
> >>>>>
> >>>>> **********
> >>>>>
> >>>>> Should weakCompareAndSet on an AtomicReference create happens
> >>>>> before  edges (just as compareAndSwap does)?
> >>>>>
> >>>>> **********
> >>>>>
> >>>> For consistency I'd say no. Arguably
> >>>> AtomicReference.weakCompareAndSet was a
> >>>> mistake and should be deprecated. But one-in all-in.
> >>>>
> >>>> We probably need to migrate the details from the package
> docs into the
> >>>> actual method docs.
> >>>>
> >>>> To address Cliff's problem I think the best solution is to add a
> >>>> WeakAtomicInteger class that has no volatile semantics at all. I
> >>>> wonder
> >>>> whether the JMX implementation would benefit from using such a class?
> >>>>
> >>>> David
> >>>>
> >>>
> >>> _______________________________________________
> >>> Concurrency-interest mailing list
> >>> Concurrency-interest at altair.cs.oswego.edu
> >>> http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
> >>>
> >>>
> >
> >
>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at altair.cs.oswego.edu
> http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest



More information about the Concurrency-interest mailing list