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

Vitaly Davidovich vitalyd at gmail.com
Wed Jan 18 10:53:43 EST 2012


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> 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/7d09c17b/attachment-0001.html>


More information about the Concurrency-interest mailing list