[concurrency-interest] AtomicReference weakCompareAndSet "Mayfailspuriously"?

Bill Pugh pugh at cs.umd.edu
Sun May 28 18:27:49 EDT 2006

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.


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