[concurrency-interest] AtomicReference.updateAndGet() mandatory updating

Alex Otenko oleksandr.otenko at gmail.com
Fri May 26 03:31:19 EDT 2017


It does not matter how CAS is implemented, as long as atomicity is guaranteed. Atomicity means that all other volatile stores are totally ordered with respect to CAS as a whole - whether it is implemented as a critical section or not.

I cannot quote full counterexamples, because they are proprietary. But we used CAS to 1. detect contention; 2. facilitate cooperation.

Detecting contention:

if (z.CAS(e, v)) {
  // I am the slave, and need to pick up the work
  // the other contenders left
} else {
  // I am the master,
  // the slave will pick up the work I left -
  // but of course the slave needs to observe
  // the work in its entirety, so the barrier is
  // expected (as was the case per earlier javadocs)
}


Facilitate cooperation:

if (z.CAS(e, e)) {
  // the update of z by slave is in the future,
  // so the slave will detect new work,
  // but of course the slave needs to observe
  // the work in its entirety, so the barrier is
  // expected
} else {
  // the update of z by slave is in the past,
  // contend to see who should do the work
}

It may not be obvious how one can use a store to z to coordinate (not necessarily a conditional store), but there are ways with arrays and atomic integers.


Of course, if JMM spec is leaning towards some new hardware trends (and perhaps CAS in hardware becoming more and more relaxed about barriers), we’d have to furnish barriers that are expected, but places like these would have to be fished out, which is not trivial. We couldn’t do this earlier, because the barrier API was not available in Java.

Eg “if(z.CAS(e,e))” is the same as “StoreLoad; LoadLoad; if (z==e)”, but there was no way to do that in Java 7.


Alex


> On 26 May 2017, at 00:44, Hans Boehm <boehm at acm.org> wrote:
> 
> Full counterexamples, with both threads, would be extremely useful here.
> 
> "guarantees that another thread reading z after CAS will observe *both* y=2 and x=1"
> 
> Only if it can somehow tell that it read z after the CAS. If the CAS didn't change the value of z, that's exceedingly hard to tell. Even if we presume there is a (non-volatile) store to w after the CAS, and the other thread sees the store to w, this is not guaranteed if e.g. the CAS is implemented with a critical section.
> 
> On Thu, May 25, 2017 at 3:41 PM, Alex Otenko <oleksandr.otenko at gmail.com <mailto:oleksandr.otenko at gmail.com>> wrote:
> Ok, if this is rare, then isn’t also a CAS with expected == new value rare?
> 
> It is not just about delaying the stores, but also about seeing them all at the same time.
> 
> x=1
> y=2
> z.CAS(…)
> 
> guarantees that another thread reading z after CAS will observe *both* y=2 and x=1.
> 
> If we make the case z.CAS(e, e) special (not a store, or no barrier before the volatile load in the “optimized” version), then this no longer can be guaranteed.
> 
> If the store is eliminated from CAS, then another thread does not synchronize-with the thread performing this CAS. In real terms this means it will not guarantee visibility of *both* y=2 and x=1.
> 
> Alex
> 
>> On 25 May 2017, at 23:01, Hans Boehm <boehm at acm.org <mailto:boehm at acm.org>> wrote:
>> 
>> IIUC, you're arguing that this transformation is valid only if we know that the implementation does not indefinitely delay the store to x past the do-while loop implementing compareAndSet()? E.g. if the compareAndSet thread subsequently prints something, and then goes into an infinite loop, I still have a guarantee that a thread that alternately reads x and y will eventually see x == 1?
>> 
>> I'm inclined to agree with that, though I expect that implementations violating this assumption are really rare.
>> 
>> On Thu, May 25, 2017 at 1:23 AM, Alex Otenko <oleksandr.otenko at gmail.com <mailto:oleksandr.otenko at gmail.com>> wrote:
>> How quickly you arrived at “no algorithm whatsoever”! :-)
>> 
>> x=1;
>> y.compareAndSet(e,v)
>> 
>> Under assumption that there are infinitely many volatile reads of y, the return from compareAndSet is a witness that there exists a read in the future that synchronizes-with this invocation of compareAndSet.
>> 
>> You cannot argue that sometimes you can skip the volatile store semantics on what would be a successful compareAndSet - because then the stores preceding compareAndSet are not guaranteed to be visible - ever. This optimization is a platform-specific decision.
>> 
>> 
>> You can argue about what happens if compareAndSet fails. My take is it should still have volatile store semantics - ie should be equivalent to the store of the value that is already there, so it appears unmodified, but synchronizes-with edges can be established.
>> 
>> 
>> Alex
>> 
>> > On 24 May 2017, at 20:38, Justin Sampson <jsampson at guidewire.com <mailto:jsampson at guidewire.com>> wrote:
>> >
>> > Andrew Haley wrote:
>> >> Mike Duigou wrote:
>> >>> I find that I write a lot of update functions which only occasionally
>> >>> change the value. For these cases I wonder if it would be reasonable to
>> >>> skip the update if the value of next is unchanged from previous.
>> >>
>> >> I don't think so, because the update has the effect of a volatile
>> >> write. If you skip the update you lose the happens-before ordering
>> >> of that write.
>> >
>> > That's strictly true (the memory barriers come out different), but no
>> > algorithm could actually rely on the difference. The reading thread can't
>> > tell if it's reading after the write (and therefore can depend on the
>> > happens-before) or reading before the write (and therefore cannot), since
>> > it sees the same value in either case.
>> >
>> > This kind of optimization is already done in some places in the JDK, such
>> > as AtomicStampedReference and AtomicMarkableReference, both of which skip
>> > the write if the current value is already equal to the new value in set(),
>> > compareAndSet(), etc.
>> >
>> > Cheers,
>> > Justin
>> >
>> > _______________________________________________
>> > Concurrency-interest mailing list
>> > Concurrency-interest at cs.oswego.edu <mailto:Concurrency-interest at cs.oswego.edu>
>> > http://cs.oswego.edu/mailman/listinfo/concurrency-interest <http://cs.oswego.edu/mailman/listinfo/concurrency-interest>
>> 
>> _______________________________________________
>> Concurrency-interest mailing list
>> Concurrency-interest at cs.oswego.edu <mailto:Concurrency-interest at cs.oswego.edu>
>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest <http://cs.oswego.edu/mailman/listinfo/concurrency-interest>
>> 
> 
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20170526/43d3ca6f/attachment-0001.html>


More information about the Concurrency-interest mailing list