[concurrency-interest] AtomicReference weakCompareAndSet "Mayfailspuriously"?

Pete Soper pete at soper.us
Sun May 28 22:46:45 EDT 2006

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}".


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

More information about the Concurrency-interest mailing list