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

Markus Jevring m.jevring at iontrading.com
Thu Jan 19 02:36:50 EST 2012


That may very well be true. Since I'm holding the smallest value in 
'value' constantly anyway, this is less of an issue, though.

On 18/01/2012 16:53, Vitaly Davidovich wrote:
>
> Hi Markus,
>
> I think Viktor's point is that even if nothing has changed when you do 
> the compareAndSet in the else clause, by the time you return the value 
> it might be stale so there doesn't seem to be much value in doing the CAS.
>
> Sent from my phone
>
> On Jan 18, 2012 10:29 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/23b9ddcd/attachment-0001.html>


More information about the Concurrency-interest mailing list