CODEWITHSUNDEEP
javaconcurrency
smatter
smatter

Reputation: 29248

CAS and Non Blocking Counter

I have been reading JCIP by Brian Goetz. He explains the implementation of a non-blocking counter using CAS instruction. I could not understand how the increment is happening using CAS instruction. Can anyone help me understand this. 

public class CasCounter {
    private SimulatedCAS value;

    public int getValue() {
        return value.get();
    }

    public int increment() {
        int v;
        do {
            v = value.get();
        }
        while (v != value.compareAndSwap(v, v + 1));
        return v + 1;
    }
}

Upvotes: 4

Views: 1310

Answers (2)

Michael Burr
Michael Burr

Reputation: 340516

The compareAndSwap() method will perform the following operations atomically:

- determine if `value` is equal to `v`
- if so, it will set `value` to `v+1`
- it returns whatever `value` was when the method was entered (whether or not `value` was updated)

The caller can check to see if value was what they expected it to be when the called compareAndSwap(). If it was, then the caller knows it's been updated. If it wasn't what was expected, the caller knows that it wasn't updated, and will try again, using the 'new' current value of value as what's expected (that's what the loop is doing).

This way, the caller can know that the increment operation doesn't get lost by some other thread that tries to modify value at the same moment.

Upvotes: 3

casablanca
casablanca

Reputation: 70721

value.compareAndSwap(v, v + 1) is equivalent to the following, except that the entire block is atomic: (see compare-and-swap for details)

int old = value.val;
if (old == v) {
  value.val = v + 1;
}
return old;

Now v = value.get() gets the current value of the counter, and if nobody else is trying to update the counter at the same time, old == v will be true, so the value is set to v+1 (i.e. it is incremented) and old is returned. The loop terminates since v == old.

Suppose someone else incremented the counter just after we did v = value.get(), then old == v would be false, and the method will immediately return old, which is the updated value. Since v != old now, the loop continues.

Upvotes: 4

Related Questions