[ATOMIC_VARIABLES_TUTORIAL] Atomic Variables

Compare and swap (CAS)

The first processors that supported concurrency provided atomic test-and-set operations, which generally operated on a single bit. The most common approach taken by current processors, including Intel and Sparc processors, is to implement a primitive called compare-and-swap, or CAS. (On Intel processors, compare-and-swap is implemented by the cmpxchg family of instructions. PowerPC processors have a pair of instructions called "load and reserve" and "store conditional" that accomplish the same goal; similar for MIPS, except the first is called "load linked.")

A CAS operation includes three operands - a memory location (V), the expected old value (A), and a new value (B). The processor will atomically update the location to the new value if the value that is there matches the expected old value, otherwise it will do nothing. In either case, it returns the value that was at that location prior to the CAS instruction. (Some flavors of CAS will instead simply return whether or not the CAS succeeded, rather than fetching the current value.) CAS effectively says "I think location V should have the value A; if it does, put B in it, otherwise, don't change it but tell me what value is there now."

The natural way to use CAS for synchronization is to read a value A from an address V, perform a multistep computation to derive a new value B, and then use CAS to change the value of V from A to B. The CAS succeeds if the value at V has not been changed in the meantime.

Instructions like CAS allow an algorithm to execute a read-modify-write sequence without fear of another thread modifying the variable in the meantime, because if another thread did modify the variable, the CAS would detect it (and fail) and the algorithm could retry the operation. Listing below illustrates the behavior (but not performance characteristics) of the CAS operation, but the value of CAS is that it is implemented in hardware and is extremely lightweight (on most processors):

public class SimulatedCAS {

    private int value;

    public synchronized int getValue() {
        return value;
    }

    public synchronized int compareAndSwap(int expectedValue, int newValue) {
        int oldValue = value;
        if (value == expectedValue) {
            value = newValue;
        }
        return oldValue;
    }
}
					

Concurrent algorithms based on CAS are called lock-free, because threads do not ever have to wait for a lock (sometimes called a mutex or critical section, depending on the terminology of your threading platform). Either the CAS operation succeeds or it doesn't, but in either case, it completes in a predictable amount of time. If the CAS fails, the caller can retry the CAS operation or take other action as it sees fit. Listing below shows the counter class written to use CAS:

public class CASCounter {

    private SimulatedCAS value = new SimulatedCAS(); // starts with 0

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

    public int increment() {
        int oldValue = value.getValue();
        while (value.compareAndSwap(oldValue, oldValue + 1) != oldValue) {
            oldValue = value.getValue();
        }
        return oldValue + 1;
    }
}
					

Lock-free and wait-free algorithms

An algorithm is said to be wait-free if every thread will continue to make progress in the face of arbitrary delay (or even failure) of other threads. By contrast, a lock-free algorithm requires only that some thread always make progress.

Nonblocking algorithms are used extensively at the operating system and JVM level for tasks such as thread and process scheduling. While they are more complicated to implement, they have a number of advantages over lock-based alternatives - hazards like priority inversion and deadlock are avoided, contention is less expensive, and coordination occurs at a finer level of granularity, enabling a higher degree of parallelism.

Until Java SE 5, it was not possible to write wait-free, lock-free algorithms in the Java language without using native code. With the addition of the atomic variables classes in the java.util.concurrent.atomic package, that has changed. The atomic variable classes all expose a compare-and-set primitive (similar to compare-and-swap), which is implemented using the fastest native construct available on the platform (compare-and-swap, load linked/store conditional, or, in the worst case, spin locks). Nine flavors of atomic variables are provided in the java.util.concurrent.atomic package (AtomicInteger; AtomicLong; AtomicReference; AtomicBoolean; array forms of atomic integer; long; reference; and atomic marked reference and stamped reference classes, which atomically update a pair of values).

The atomic variable classes can be thought of as a generalization of volatile variables, extending the concept of volatile variables to support atomic conditional compare-and-set updates. Reads and writes of atomic variables have the same memory semantics as read and write access to volatile variables.

Operations on atomic variables get turned into the hardware primitives that the platform provides for concurrent access, such as compare-and-swap.

Java Atomic Operations

In Java the integer primitive increment operation is not an atomic operation. When an integer is incremented, the following logical steps are performed by the JVM:

So while we write the increment operator in a single line of Java code, such as:

int n = i++;
					

Each one of the aforementioned steps occurs in the JVM. The danger is that if you have multiple threads that all try to increment the same value, there is a chance that two or more of the threads will get the same value (step #1), then increment it (step #2), and then assign the new value to it (step #3). If two threads increment the number 5 then you would expect to see 7 but instead both increment the number 5, yielding a result of 6, and then assign 6 back to the integer's memory location.

With the release of Java SE 5, Sun included a java.util.concurrent.atomic package that addresses this limitation. And specifically they added classes including the following:

Each of these atomic classes provides methods to perform common operations, but each one is ensured to be performed as a single atomic operation. For example, rather than incrementing an integer using the standard increment operator, like the following:

int n = ++i;
					

You can ensure that the (1) get value, (2) increment value, (3) update memory, and (4) assign the new value to n is all accomplished without fear of another thread interrupting your operation by writing you code as follows:

AtomicInteger ai = new AtomicInteger(0);
int n = ai.incrementAndGet();
					

In addition, the AtomicInteger class provides the following operations:

Locks in Java

A lock is a thread synchronization mechanism like synchronized blocks except locks can be more sophisticated than Java's synchronized blocks.

From Java SE 5 the package java.util.concurrent.locks contains several lock implementations, so you may not have to implement your own locks:

Let's start out by looking at a synchronized block of Java code:

public class Counter {

    private int count = 0;

    public int inc() {
        synchronized (this) {
            return ++count;
        }
    }
}
					

Notice the synchronized(this) block in the inc() method. This block makes sure that only one thread can execute the return ++count at a time.

The purpose of the synchronized keyword is to provide the ability to allow serialized entrance to synchronized methods in an object. Although almost all the needs of data protection can be accomplished with this keyword, it is too primitive when the need for complex synchronization arises. More complex cases can be handled by using classes that achieve similar functionality as the synchronized keyword. These classes are available beginning in Java SE 5.

The synchronization tools in Java SE 5 implement a common interface: the Lock interface. For now, the two methods of this interface that are important to us are lock() and unlock(). Using the Lock interface is similar to using the synchronized keyword: we call the lock() method at the start of the method and call the unlock() method at the end of the method, and we have effectively synchronized the method.

The lock() method grabs the lock. The difference is that the lock can now be more easily envisioned: we now have an actual object that represents the lock. This object can be stored, passed around, and even discarded. As before, if another thread owns the lock, a thread that attempts to acquire the lock waits until the other thread calls the unlock() method of the lock. Once that happens, the waiting thread grabs the lock and returns from the lock() method. If another thread then wants the lock, it has to wait until the current thread calls the unlock() method.

The Counter class could have been written using a Lock instead of a synchronized block:

import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class Counter {

    private Lock lock = new ReentrantLock();

    private int count = 0;

    public int inc() {
        lock.lock();
        try {
            return ++count;
        } finally {
            lock.unlock();
        }
    }
}