Compare and Swap

Compare and swapis a technique used when designing concurrent algorithms. Basically, compare and swap compares an expected value to the concrete value of a variable, and if the concrete value of the variable is equals to the expected value, swaps the value of the variable for a new variable. Compare and swap may sound a bit complicated but it is actually reasonably simple once you understand it, so let me elaborate a bit further on the topic.

What Situations Compare And Swap is Intended to Support

A very commonly occurring patterns in programs and concurrent algorithms is the "check then act" pattern. The check then act pattern occurs when the code first checks the value of a variable and then acts based on that value. Here is a simple example:

class MyLock {

    private boolean locked = false;

    public boolean lock() {
        if(!locked) {
            locked = true;
            return true;
        }
        return false;
    }
}

This code has many errors if it was to be used in a multithreaded application, but please ignore that for now.

As you can see, thelock()method first checks if thelockedmember variable is equal tofalse(check), and if it is it seslockedto true (then act).

If multiple threads had access to the sameMyLockinstance, the abovelock()function would not be guaranteed to work. If a thread A checks the value oflockedand sees that it is false, a thread B may also check the value oflockedat exactly the same time. Or, in fact, at any time before thread A setslockedto false. Thus, both thread A and thread B may seelockedas being false, and both will then act based on that information.

To work properly in a multithreaded application, "check then act" operations must be atomic. By atomic is meant that both the "check" and "act" actions are executed as an atomic (non-dividable) block of code. Any thread that starts executing the block will finish executing the block without interference from other threads. No other threads can execute the atomic block at the same time.

Here is the code example from earlier with thelock()method turned into an atomic block of code using thesynchronizedkeyword:

class MyLock {

    private boolean locked = false;

    public 
synchronized
 boolean lock() {
        if(!locked) {
            locked = true;
            return true;
        }
        return false;
    }
}

Now thelock()method is synchronized so only one thread can executed it at a time on the sameMyLockinstance. Thelock()method is effectively atomic.

The atomiclock()method is actually an example of "compare and swap". Thelock()methodcomparesthe variablelockedto the expected valuefalseand iflockedis equal to this expected value, itswapsthe variable's value totrue.

Compare And Swap As Atomic Operation

Modern CPUs have built-in support for atomic compare and swap operations. From Java 5 you can get access to these functions in the CPU via some of the new atomic classes in thejava.util.concurrent.atomicpackage.

Here is an example showing how to implement thelock()method shown earlier using theAtomicBooleanclass:

public static class MyLock {
    private AtomicBoolean locked = new AtomicBoolean(false);

    public boolean lock() {
        return locked.compareAndSet(false, true);
    }

}

Notice how thelockedvariable is no longer abooleanbut anAtomicBoolean. This class has acompareAndSet()function which will compare the value of theAtomicBooleaninstance to an expected value, and if has the expected value, it swaps the value with a new value. In this case it compares the value oflockedtofalseand if it isfalseit sets the new value of theAtomicBooleantotrue.

ThecompareAndSet()method returnstrueif the value was swapped, andfalseif not.

The advantage of using the compare and swap features that comes with Java 5+ rather than implementing your own is that the compare and swap features built into Java 5+ lets you utilize the underlying compare and swap features of the CPU your application is running on. This makes your compare and swap code faster.