CODEWITHSUNDEEP
javamultithreadingsynchronizationnonblocking
Tudor
Tudor

Reputation: 62439

Greater-than compare-and-swap

As the title suggests, I'm looking for a compare-and-swap implementation, but with greater-than comparison:

if(newValue > oldValue) {
    oldValue = newValue;
}

where oldValue is some global shared state and newValue is private to each thread, without doing this:

synchronized(locker) {
    if(newValue > oldValue) {
        oldValue = newValue;
    }       
}

because I want a non-blocking solution. From studying source codes of other non-blocking operations, I've come up with this (assuming the values are integers):

AtomicInteger oldValue; // shared global variable

...

public boolean GreaterThanCAS(int newValue) {

    while(true) {
        int local = oldValue;
        if(local == oldValue) {
            if(newValue > local) {
                 if(oldValue.compareAndSet(local, newValue) {
                     return true;  // swap successful
                 } // else keep looping
            } else {
                 return false; // swap failed
            }
        } // else keep looping
    }
}

when // else keep looping happens, it means that another thread has changed the oldValue in the meantime and so I need to loop and try again.

Is this implementation correct (thread-safe)?

Upvotes: 27

Views: 10293

Answers (4)

Vadzim
Vadzim

Reputation: 26180

Since Java 8 this can be simplified with use of updateAndGet:

public boolean greaterThanCAS(int newValue) {
    return oldValue.updateAndGet(x -> x < newValue ? newValue : x) == newValue;
}

Note that this would return true also in case when old and new values are equal. Give a try to @Adam's answer if this is not desired behaviour.

Upvotes: 24

NPE
NPE

Reputation: 500357

I see no problems with your implementation, provided that no thread ever decreases the value of the AtomicInteger. If they do, your code is open to race conditions.

Note that the code can be simplified as follows:

public boolean GreaterThanCAS(int newValue) {
    while(true) {
        int local = oldValue.get();
        if(newValue <= local) {
             return false; // swap failed
        }
        if(oldValue.compareAndSet(local, newValue)) {
             return true;  // swap successful
        }
        // keep trying
    }
}

Upvotes: 11

Adam
Adam

Reputation: 236

@Vadzim, I would have commented on your post, but stackoverflow says I don't have enough points to post comments. Your answer is almost correct, but your function will always return false because getAndUpdate always returns the previous value, or 'x' in your case. I think all you would need to do is replace your last '==' with '<', e.g.:

 // return true if the assignment was made, false otherwise
 public boolean greaterThanCAS(int newValue) {
    return oldValue.getAndUpdate(x -> x < newValue ? newValue : x) < newValue;
 }

Upvotes: 4

John Vint
John Vint

Reputation: 40256

I would re write it to look more like:

while(true) {
    int local = oldValue.get();
    if(newValue > local){
       if(oldValue.compareAndSwap(local, newValue) {
              return true;  // swap successful
        } // else keep looping 
    }else 
        return false;
 }

The equivalence check before the greater than check is redundant.

Otherwise it should work fine.

Upvotes: 3

Related Questions