Synchronization, the Java Memory Model, and other tricky bits, part two

In the first installment we looked briefly at the changes to the Java Memory Model introduced in version 5.0. Today we’ll take a closer look at what’s behind the new classes in java.util.concurrent. I drew on Brian Goetz’s articles, linked at the end.

If you’ve downloaded Java 5, you may have noticed the java.util.concurrent package. It contains classes for safe, convenient use in multithreaded applications. What you may not know is that most are implemented without much use of synchronized sections. Threads don’t sit idle waiting for a lock. Java 5.0 makes it possible to use nonblocking algorithms.

CAS

CAS stands for compare-and-swap, the instruction that underpins java.util.concurrent, but let’s take it in order. CAS has three arguments, a memory location M, an expected value A and a new value B, as in CAS(M, A, B). It reads the current value at M and compares it with A. If they’re equal, it puts B at M. Otherwise it does nothing.

The crucial point is that CAS is atomic. Two threads can’t change the same memory location in parallel. Thread X can’t compare the current and expected values and then have thread Y change the value before X writes the new one. CAS semantics are essentially the same as synchronized, except they’re implemented in hardware rather than in the JVM. That makes it much faster.

Support for CAS was added in Java 5.0 and exposed in the java.util.concurrent.atomic package, with primitives such as AtomicInteger and AtomicReference, which model CAS for different data types. With CAS, an implementation can replace synchronization with an optimistic approach.

Take a simple counter implemented with a synchronized block.

publi class Counter {
  private int counter;
  
  public synchronized int inc() {
    return counter++;
  }
}

Now compare that with using AtomicInteger.

publi class Counter {
  private final AtomicInteger counter = new AtomicInteger();
  
  public int inc() {
     return counter.incrementAndGet();
  }
}

Look at the code for incrementAndGet. Think of compareAndSet as our CAS instruction. The method get returns the current value.

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

As you can see, if the value changes between reading it and incrementing it, the code goes around again. It keeps trying until the thread manages to increment the value atomically. Other nonblocking algorithms used to implement the concurrency classes work on the same CAS principle.

Java 5.0’s changes, both the JMM and CAS, made it possible to build classes optimized for concurrent use. Their nonblocking algorithms and the new semantics of volatile usually offer much better performance than conventional synchronized.

If you need thread-safe objects such as maps or lists, I recommend exploring the java.util.concurrent package. It’ll save you a lot of debugging time and help application performance.

• Java theory and practice: Going atomic
• Java theory and practice: Introduction to nonblocking algorithms
• Java theory and practice: Building a better HashMap (How ConcurrentHashMap offers higher concurrency without compromising thread safety)