[concurrency-interest] Lock-free implementation of min including assignment

Markus Jevring m.jevring at iontrading.com
Wed Jan 18 10:27:22 EST 2012


I do it to ensure that the value hasn't changed while we were doing 
non-atomic things like "<".
It fills the same function as the other update, namely that the whole 
operation can only succeed if nothing else has changed the state of the 
AtomicLong at the same time.

Markus

On 18/01/2012 16:09, Victor Luchangco wrote:
> On Jan 18, 2012, at 9:16 AM, Markus Jevring wrote:
>
>> I need to find a lock-free algorithm that will do min (or max) plus assignment atomically (to the extend that atomicity is possible without corresponding cpu instructions). I've been looking at j.u.c.AtomicLong for inspiration, and I've come up with this:
>>
>>     /**
>>      * Atomically checks if {@code potentialReplacement} is less than {@code value}, and if so,
>>      * sets {@code value} to {@code potentialReplacement}. This is modelled after how most methods
>>      * inside {@link AtomicLong} are implemented.
>>      *
>>      * @param potentialReplacement the potential replacement
>>      * @param value the current value
>>      * @return the smallest value
>>      */
>>     private long min(long potentialReplacement, AtomicLong value) {
>>         for (;;) {
>>             long current = value.get();
>>             if (potentialReplacement<  current) {
>>                 if (value.compareAndSet(current, potentialReplacement)) {
>>                     return potentialReplacement;
>>                 }
>>             } else {
>>                 if (value.compareAndSet(current, current)) {
>>                     return current;
>>                 }
>>             }
>>         }
>>     }
>>
>> Will this work? I'm counting on the .compareAndSet() to be my sanity check in the loop. I mean, the call returns the correct value, and the assignment also works, but will it work in the face under concurrent access? Tests show that it seems to work when hit concurrently, and it reasonably looks like it should.
> Why do the compareAndSet when current<= potentialReplacement?  Since you aren't changing the value, you can pretend that you wrote it exactly when you read it, so you can just return immediately.
>
> - Victor
>
>
>> If it doesn't, what are the conditions under which it might fail?
>>
>> If it does, I'm surprised it's not plastered all over the internet. Granted, it's taken me a significant amount of time to need such functionality, so perhaps it's rare.
>>
>> Markus
>> _______________________________________________
>> Concurrency-interest mailing list
>> Concurrency-interest at cs.oswego.edu
>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest


More information about the Concurrency-interest mailing list