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

Markus Jevring m.jevring at iontrading.com
Wed Jan 18 09:16:24 EST 2012


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.

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


More information about the Concurrency-interest mailing list