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

Yuval Shavit yshavit at akiban.com
Wed Jan 18 10:58:14 EST 2012


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>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<Concurrency-interest at cs.oswego.edu>
>>> http://cs.oswego.edu/mailman/**listinfo/concurrency-interest<http://cs.oswego.edu/mailman/listinfo/concurrency-interest>
>>>
>> ______________________________**_________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.**oswego.edu <Concurrency-interest at cs.oswego.edu>
> http://cs.oswego.edu/mailman/**listinfo/concurrency-interest<http://cs.oswego.edu/mailman/listinfo/concurrency-interest>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20120118/4d14a208/attachment.html>


More information about the Concurrency-interest mailing list