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

Markus Jevring m.jevring at iontrading.com
Thu Jan 19 02:38:22 EST 2012


What I need is for 'value' to always contain the smallest value. I'm 
less concerned with the method returning the smallest value. Ideally it 
should return the smallest value at the time of invocation, but I could 
technically make this void and simply return, considering I'm keeping 
the smallest value in 'value' anyway.

On 18/01/2012 16:58, Yuval Shavit wrote:
> Seems to me you can just return current in the else. Sure, there's a 
> race condition in that someone else may have put in a smaller value 
> between the value.get() and the return, but that race condition is 
> inherent to this kind of code, since someone could also put in a 
> smaller value between value.compareAndSet(current,current) and return 
> current -- or between return current and when the value is used at the 
> call site.
>
> I think the only thing you can guarantee with this method, with 
> respect to the return value, is that it will be <= 
> potentialReplacement, and that at some point it was the minimum value 
> of the AtomicLong.
>
> On Wed, Jan 18, 2012 at 10:27 AM, Markus Jevring 
> <m.jevring at iontrading.com <mailto:m.jevring at iontrading.com>> wrote:
>
>     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
>             <mailto:Concurrency-interest at cs.oswego.edu>
>             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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20120119/2dac1792/attachment.html>


More information about the Concurrency-interest mailing list