[concurrency-interest] AtomicReference weakCompareAndSet "Mayfailspuriously"?

Pete Soper pete at soper.us
Sun May 28 21:06:25 EDT 2006


OK, the happens-before establishes a partial ordering and it's 
irrespective of the number of operations involved with the memory in 
question (any number of reads or writes are divided by the 
happens-before relationship). 

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



More information about the Concurrency-interest mailing list