[concurrency-interest] Question on compareAndSet

raghuram nidagal raghuram.nidagal at gmail.com
Wed Nov 18 23:07:28 EST 2009


Thanks Jed. I will take a look.

On Thu, Nov 19, 2009 at 9:13 AM, Jed Wesley-Smith <jed at atlassian.com> wrote:

> raghuram,
>
> You are implementing what is known as a TestAndSet (TAS) lock. Such an
> algorithm is quite efficient in the uncontended case, but can have
> absolutely dreadful performance degradation as the rate of contention goes
> up. For a detailed description of why see "The Art of Multiprocessor
> Programming" (Herlihy, Shavit) pg 144-146.
>
> cheers,
> jed.
>
> raghuram nidagal wrote:
>
>> Thanks David.
>> I assume compareAndSet on a single variable by itself can be used to
>> provide locking functionality though..
>> while(notDone){
>> if(x.compareAndSet(true,false)){
>> //do something
>> notDone=false;
>> x.set(false);
>> }
>> else{
>> sleep..
>> }
>> }
>> is that different from synchronized except that this code does not block
>> trying to acquire the lock whereas synchronized would block ?
>>   On Wed, Nov 18, 2009 at 10:14 AM, David Holmes <
>> davidcholmes at aapt.net.au <mailto:davidcholmes at aapt.net.au>> wrote:
>>
>>    Hi Raghu,
>>        compareAndSet can only update a single variable, whereas locking
>>    can enforce an atomic action over as many variables as you like.
>>    Using multiple compareAndSets across different variables does not
>>    give you atomicity over the set actions.
>>        For example suppose you have a class Point:
>>          class Point {
>>         int x, y;
>>         void move(int newX, int newY) {
>>           x = newX;
>>           y = newY;
>>         }
>>      }
>>        For move(a,b) to be an atomic operation you need to use locking -
>>    eg synchronize the move() method. If you instead tried to do
>>    seperate CAS operations on x and y, you could end up with an x
>>    from one move() and a y from a distinct move() and that would
>>    violate the property of the Point, that it can only exist in an
>>    x,y position to which it has been moved.
>>        HTH
>>        David Holmes
>>        -----Original Message-----
>>        *From:* concurrency-interest-bounces at cs.oswego.edu
>>        <mailto:concurrency-interest-bounces at cs.oswego.edu>
>>        [mailto:concurrency-interest-bounces at cs.oswego.edu
>>        <mailto:concurrency-interest-bounces at cs.oswego.edu>]*On Behalf
>>        Of *raghuram nidagal
>>        *Sent:* Wednesday, 18 November 2009 2:34 PM
>>        *To:* concurrency-interest at cs.oswego.edu
>>        <mailto:concurrency-interest at cs.oswego.edu>
>>        *Subject:* [concurrency-interest] Question on compareAndSet
>>
>>        Hi,
>>        The documentation says "The compareAndSet method is not a
>>        general replacement for locking. It applies only when critical
>>        updates for an object are confined to a/ single/ variable"
>>        Can someone explain what this means? What are the scenarios
>>        where compareAndSet cannot be used for locking?
>>        Thanks
>>        Raghu
>>
>>
>> ------------------------------------------------------------------------
>>
>> _______________________________________________
>> Concurrency-interest mailing list
>> 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/20091119/01410322/attachment.html>


More information about the Concurrency-interest mailing list