Implementation of the addAndGet in AtomicInteger class

Question

I was going through the Java(Java 6) souce code for the addAndGet method in the AtomicInteger class.

The corresponding code was as follows:

public final int addAndGet(int delta) {
    for (;;) {
        int current = get();
        int next = current + delta;
        if (compareAndSet(current, next))
            return next;
    }
}

The compareAndSet method calls a native method to carry out the assignment. There are mainly two questions:

1. How does the infinite loop help ?
2. What could be the scenarios, under which the "if (compareAndSet(current, next))" condition could return a false ? In such a case, the code might run into an infinite loop. If it is guaranteed that compareAndSet will always return a "true", then can we not do away with this check altogether ?

Similar doubts are with the decrementAndGet, getAndDecrement, getAndAdd methods as well.

Answer 1

How does the infinite loop help ?

This means: retry until it worked. Without the loop, it may not succeed the first time around (see below).

What could be the scenarios, under which the "if (compareAndSet(current, next))" condition could return a false ?

That happens if two threads try to modify the value at the same time. One of them will get there first. The other one will fail.

Imagine two threads (A and B) trying to increment from 5 to 6

A: int current = get();  // current = 5
B: int current = get();  // current = 5
B: int next = current + delta;  // next = 6
B: if (compareAndSet(current, next))  // OK
          return next;
A: int next = current + delta;  // next = 6 
A: if (compareAndSet(current, next))  
    // fails, because "current" is still 5
    // and that does not match the value which has been changed to 6 by B

Note that the whole point of this class is to avoid locks. So instead, you have this "optimistic currency control": Just assume no one else is working on the data at the same time, and if that turns out to be wrong, rollback and retry.

In such a case, the code might run into an infinite loop

Not really. It can only fail once for every other thread that does something to the value.

Thread A from above in the second iteration:

A: int current = get();  => current now 6
A: int next = current + delta;  => next = 7
A: if (compareAndSet(current, next))  => now OK

You could conceivably end up with one thread waiting forever if other threads incessantly update the value, but only then. To avoid that, you'd need some definition of "fairness" (which some other tools in the concurrency package support).