[concurrency-interest] Question on compareAndSet

Jed Wesley-Smith jed at atlassian.com
Wed Nov 18 22:43:12 EST 2009


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
>   



More information about the Concurrency-interest mailing list