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

Oleksiy Khilkevich oleksiy.khilkevich at gmail.com
Tue Sep 6 08:07:15 EDT 2011


It just happens on occasion :)

2011/9/6 Oleksiy Khilkevich <oleksiy.khilkevich at gmail.com>

> Hi David and folks
>
> 2011/9/6 David Holmes <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]*On Behalf Of *Oleksiy
>> Khilkevich
>> *Sent:* Tuesday, 6 September 2011 8:14 PM
>> *To:* 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
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20110906/476fa4ac/attachment.html>


More information about the Concurrency-interest mailing list