java.util.concurrent code review

Question

I'm study java.util.concurrent library and find many infinite loops in the source code, like this one

//java.util.concurrent.atomic.AtomicInteger by Doug Lea
public final int getAndSet(int newValue) {
    for (;;) {
        int current = get();
        if (compareAndSet(current, newValue))
            return current;
    }
}

I wonder, in what cases actual value can not be equal to the expected value (in this case compareAndSet returns false)?

Answer 1

Many modern CPUs have compareAndSet() map to an atomic hardware operation. That means, it is threadsafe without requiring synchronization (which is a relatively expensive operation in comparison). However, it's only compareAndSet() itself with is atomic, so in order to getAndSet() (i.e. set the variable to a given value and return the value it had at that time, without the possibility of it being set to a different value in between) the code uses a trick: first it gets the value, then it attempts compareAndSet() with the value it just got and the new value. If that fails, the variable was manipulated by another thread inbetween, and the code tries again.

This is faster than using synchronization if compareAndSet() fails rarely, i.e. if there are not too many threads writing to the variable at the same time. In an extreme case where many threads are writing to the variable at all times, synchronization can actually be faster because while there is an overhead to synchronize, other threads trying to access the variable will wait and be woken up when it's their turn, rather than having to retry the operation repeatedly.

Answer 2

When the value is modified in another thread, the get() and compareAndSet() can see different values. This is the sort of thing a concurrent library needs to worry about.