[concurrency-interest] Composite compare-and-swap based on two values

Nathan Reynolds nathan.reynolds at oracle.com
Thu Sep 8 17:02:35 EDT 2011


The correct way is to copy the volatile state into a local variable, as 
you have done.  Then test the conditions on the local variable.

Are CounterState.value and CounterState.boundary final?

Nathan Reynolds 
<http://psr.us.oracle.com/wiki/index.php/User:Nathan_Reynolds> | 
Consulting Member of Technical Staff | 602.333.9091
Oracle PSR Engineering <http://psr.us.oracle.com/> | Server Technology

On 9/8/2011 9:50 AM, Oleksiy Khilkevich wrote:
> Hi All
>
> Getting back to this I'd like to present what I've came up with. I 
> need a volunteer for code review.
>
> I'm going to give a tech talk about java.util.concurrent soon, so The 
> Right Way(tm) and bug-free code is critical
>
> Here is a piece of cyclic counter responsible for reset
>
>     // CounterState is private nested class to hold value and 
> boundary, see attached source
>     @Override
>     public boolean reset() {
>         for (;;) {
>             int[] stampHolder = new int[1];
>             CounterState current = stateRef.get(stampHolder); // 1
>             int currentStamp = stampHolder[0];
>
>             if (current.value == current.boundary) return false;
>
>             CounterState next = new CounterState(current.boundary, 
> current.boundary);
>             if (stateRef.compareAndSet(current, next, currentStamp, 
> currentStamp + 1)) {
>                 return true;
>             }
>         }
>     }
>
> If I am not mistaken, at (!) i can't just access 
> stateRef.getReference().value and stateRef.getReference.boundary, as 
> stamp can change in between of that reads, so i need to get
>
> Also in general, the more complex is shared state, the more 
> performance degradation would be on state writes, as there is more 
> contention over the shared state.
>
> I've attached the source in case you may wanna look
>
> Thanks and waiting for the feedback
> Oleksiy
>
> 2011/9/7 David Holmes <davidcholmes at aapt.net.au 
> <mailto:davidcholmes at aapt.net.au>>
>
>     But I should add that this form of DCAS is no different to
>     choosing to encode your two values into one variable.
>     David
>
>         -----Original Message-----
>         *From:* David Holmes [mailto:davidcholmes at aapt.net.au
>         <mailto:davidcholmes at aapt.net.au>]
>         *Sent:* Wednesday, 7 September 2011 7:48 AM
>         *To:* Oleksiy Khilkevich
>         *Cc:* Concurrency-interest at cs.oswego.edu
>         <mailto:Concurrency-interest at cs.oswego.edu>
>         *Subject:* RE: [concurrency-interest] Composite
>         compare-and-swap based on two values
>
>         Sorry - yes I was mixing AtomicMarkableReference and
>         AtomicStampedreference. AtomicStampedReference does present
>         itself in a form similar to DCAS.
>         Good luck.
>         David
>
>             -----Original Message-----
>             *From:* Oleksiy Khilkevich
>             [mailto:oleksiy.khilkevich at gmail.com
>             <mailto:oleksiy.khilkevich at gmail.com>]
>             *Sent:* Tuesday, 6 September 2011 10:46 PM
>             *To:* dholmes at ieee.org <mailto:dholmes at ieee.org>
>             *Cc:* Concurrency-interest at cs.oswego.edu
>             <mailto:Concurrency-interest at cs.oswego.edu>
>             *Subject:* Re: [concurrency-interest] Composite
>             compare-and-swap based on two values
>
>             I guess you mean AtomicMarkableReference. stamped one
>             indeed provides the versioning that can help - it stores
>             the int as a stamp. I think it's quite possible to emulate
>             DCAS with help of these classes.
>
>             Regarding the reset() i'm just trying to stick to the
>             contract i've imposed on it (so it return true if the
>             counter value was really reset). Without requirement to
>             return change status, i'd not bother at all
>
>             But surprisingly to provide more information out of
>             reset() i faced this interesting issue. The drawback is
>             the performance drop on reset() due to possible
>             contention, but i expect value to be changed magnitudes
>             more frequently than boundary, so performance should not
>             be a problem.
>
>             TBH, I can't even imagine the practical case when i'd need
>             reset() at all, I am very short on useful and realistic
>             concurrency examples. If anybody has a treasure chest of
>             such examples, I'd be infinitely grateful.
>
>             But since reset() it's there, I now can't ignore it :)
>
>             Oleksiy
>
>             2011/9/6 David Holmes <davidcholmes at aapt.net.au
>             <mailto:davidcholmes at aapt.net.au>>
>
>                 DCAS is double-compare-and-swap. It allows you to
>                 atomically check and update two independent memory
>                 locations. No current hardware that I
>                 know supports it. It makes some lock-free algorithms
>                 trivial to implement in theory.
>                 AtomicStampedReference is a special variant of storing
>                 two logical values in one variable, but if I recall
>                 correctly the second variable here is limited to 1-bit
>                 - a mark or stamp bit. This could be implemented by
>                 using the unused address bits to hold the stamp/mark
>                 while the variable holds the actual data. But in the
>                 JDK it is just doned with locking. Some lock free
>                 algorthims are based on having this kind of composite
>                 variable.
>                 But based on your description of the counter and the
>                 boundary it isn't clear to me that reset() needs to be
>                 atomic, as the boundary or value could change the
>                 instant after you set them anyway.
>                 Cheers,
>                 David
>
>                     -----Original Message-----
>                     *From:* Oleksiy Khilkevich
>                     [mailto:oleksiy.khilkevich at gmail.com
>                     <mailto:oleksiy.khilkevich at gmail.com>]
>                     *Sent:* Tuesday, 6 September 2011 10:07 PM
>                     *To:* dholmes at ieee.org <mailto:dholmes at ieee.org>;
>                     Concurrency-interest at cs.oswego.edu
>                     <mailto:Concurrency-interest at cs.oswego.edu>
>                     *Subject:* Re: [concurrency-interest] Composite
>                     compare-and-swap based on two values
>
>                     It just happens on occasion :)
>
>                     2011/9/6 Oleksiy Khilkevich
>                     <oleksiy.khilkevich at gmail.com
>                     <mailto:oleksiy.khilkevich at gmail.com>>
>
>                         Hi David and folks
>
>                         2011/9/6 David Holmes
>                         <davidcholmes at aapt.net.au
>                         <mailto:davidcholmes at aapt.net.au>>
>
>                             You can not compose CAS operations to get
>                             atomic updates to multiple variables. A
>                             DCAS would solve your problem but we don't
>                             have one :) AtomicStampedReference (as
>                             mentioned by Daniel) is a very restricted
>                             form of DCAS and in fact is implemented by
>                             locking in the JDK.
>
>                         Can you tell in more detail about DCAS
>                         concept? Maybe some relevant link? Google is
>                         not of much help unfortunately. I'll try to
>                         figure AtomicStampedReference in the meantime.
>
>                             You either need a mutual exclusion
>                             mechanism that is applied to all variables
>                             (eg locking), or you need a protocol that
>                             allows optimistic updates and can account
>                             for conflicts/contention. Or you encode
>                             both variables into a single atomic variable.
>
>                         I thought about encoding the state in a single
>                         variable as well, but I was also looking for
>                         some general approach to such case.
>                         Single-state variable is not very scalable.
>
>                             I must admit though that I don't really
>                             understand the semantics of your reset()
>                             operation, and I'm unclear why the value
>                             and the boundary can be modified
>                             independently.
>
>                         The cyclic counter is supposed to
>                         incrementally decrease its value from some
>                         boundary till zero and set it value again to
>                         boundary, in my implementation, the boundary
>                         is supposed to be adjustable, so you can
>                         increase or decrease counter value space in
>                         thread-safe manner. the reset() is supposed to
>                         reset the counter value to it's boundary.
>
>                         I plan to reuse this interface further to
>                         implement work schedulers and few similar
>                         things on top of it in my further journey
>                         through java.util.concurrent.*
>
>                         I've attached the interface so you have an
>                         idea about it.
>
>                         @Viktor: no, am looking into it, transactional
>                         memory is somewhere deep inside my learning
>                         backlog :o)
>                         Thanks for all your answers
>                         Oleksiy
>
>                             David Holmes
>
>                                 -----Original Message-----
>                                 *From:*
>                                 concurrency-interest-bounces at cs.oswego.edu
>                                 <mailto:concurrency-interest-bounces at cs.oswego.edu>
>                                 [mailto:concurrency-interest-bounces at cs.oswego.edu
>                                 <mailto:concurrency-interest-bounces at cs.oswego.edu>]*On
>                                 Behalf Of *Oleksiy Khilkevich
>                                 *Sent:* Tuesday, 6 September 2011 8:14 PM
>                                 *To:*
>                                 Concurrency-interest at cs.oswego.edu
>                                 <mailto:Concurrency-interest at cs.oswego.edu>
>                                 *Subject:* [concurrency-interest]
>                                 Composite compare-and-swap based on
>                                 twovalues
>
>                                 Hi Concurrency Champs
>
>                                 I'm implementing non-blocking cyclic
>                                 counter mostly for learning purposes,
>                                 and faced the following problem, which
>                                 i'm not sure how to solve.
>
>                                 The method in question implements the
>                                 following
>
>                                     /**
>                                      * Sets counter value to initial
>                                 (boundary) value
>                                      * @return true if counter value
>                                 was changed
>                                      */
>                                     boolean reset();
>
>                                 The implementation I'm not sure about
>
>                                     @Override
>                                     public boolean reset() {
>                                         for (;;) {
>                                             int curValue = value.get();
>                                             int curBoundary =
>                                 boundary.get();
>                                             if (curValue ==
>                                 curBoundary) return false;
>
>                                             // TODO: if boundary and
>                                 value were not changed, set the value
>                                 to boundary
>
>                                             return true;
>                                         }
>                                     }
>
>                                 Here I have two values which are both
>                                 AtomicIntegers and which may change -
>                                 value can be incremented or
>                                 decremented by another thread, and
>                                 boundary can be changed too.
>
>                                 I'm not quite sure how to do this
>                                 without introducing critical sections.
>                                 In general the question refers to any
>                                 shared state change based on values of
>                                 several other shared states.
>
>                                 What is the correct way to implement
>                                 such operation atomically without
>                                 critical sections? IS it possible to
>                                 build composite CAS operations based
>                                 on AtomicInteger#compareAndSet ?
>
>                                 Thank you and kindly waiting for your
>                                 ideas
>                                 Oleksiy
>
>
>
>
>
>
>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20110908/a02c31c3/attachment-0001.html>


More information about the Concurrency-interest mailing list