Introduction
Writing correct programs is hard, but writing correct concurrent programs is far harder. Despite that, a Java developer (at any competence level) can't just ignore the problem. And in the very last year, there’s another good reason to take care even more of multithreading programming: the race towards always higher CPU frequency and number of transistors integrated on a single core is going to finish because the CPU makers are starting to face some physical limitations with the request of less power demanding devices. Today it is already possible to find lots of (even low-end) devices having two or more cores.
For these reason, programs are moving from being concurrent, serving more requests at the same time, to being parallel, having the possibility to split the execution of a complex time-consuming request in more subtasks that can run together in order to take advantage of multi-processor or multi-core systems. This scenario brings new (stimulating) challenges on the desktop of each Java developer and each one of us should try to acquire the necessary skills to win these challenges.
The Base Example
The purpose of this article is to mention and illustrate some simple but very important rules for writing effective and bug-free Java multithreaded programs. The rationale behind those rules will be justified by analyzing and improving this very simple Java class:
public class FactorialCalculator {
public BigInteger factorialOf(BigInteger i) {
BigInteger result = calculateFactorial(i);
return result;
}
private BigInteger calculateFactorial(BigInteger i) {
int compare = i.compareTo(BigInteger.ONE);
if (compare < 0) throw new IllegalArgumentException();
else if (compare == 0) return i;
BigInteger i1 = i.subtract(BigInteger.ONE);
return i.multiply(calculateFactorial(i1));
}
}
Stateless is Thread-safe
This class has only a single public method that calculates the factorial of the given BigInteger parameter. What happens if we share an instance of this class through different threads? Is that instance thread-safe? Of course, the answer is yes and for a very simple reason: one thread accessing a FactorialCalculator cannot influence the result of another thread accessing the same object, because the two threads do not share state. This is probably the easiest to understand and at the same time most important rule of multithreaded programming: stateless objects are always thread-safe.
Modify State Consistently
Of course to have objects with some sort of state is often just unavoidable. In order to add a little state to the first example, let's make it just a bit more complicated by adding a variable that counts the number of times the factorialOf() method is called:
public class FactorialCalculator {
private long count;
public BigInteger factorialOf(BigInteger i) {
BigInteger result = calculateFactorial(i);
++count;
return result;
}
public long getCount() { return count; }
}
What about thread-safety now? Since our FactorialCalculator is no longer a stateless object, we have to pay a bit more attention to what could happen during a multithreaded execution. Actually while the increment operation (++count) may look like a single action because of its compact syntax, it is not atomic, which means that it does not execute as a single, indivisible operation. Instead, it is a shorthand for a sequence of three discrete operations: fetch the current value, add one to it, and write the new value back. Even worse, in this example, we could not only read a stale value, but also a pseudo-random value that has not been written by any thread. That’s why the Java Memory Model requires fetch and store operations to be atomic, but for nonvolatile long and double variables, the JVM is permitted to treat a 64-bit read or write as two separate 32-bit operations. These considerations make it evident that our object is now susceptible to what is called a lost update and that its thread-safety is definitively broken. This problem put in evidence the second simple rule for a bug-free multithreaded program: always check for atomicity.
Know Your Library
To fix the lack of atomicity problem in our simple code is quite easy. Starting from Java 5.0, the java.util.concurrent.atomic package contains atomic variable classes for effecting atomic state transitions on numbers and object references. By replacing the long counter with an AtomicLong, we ensure that all actions that access the counter state are atomic:
public class FactorialCalculator {
private final AtomicLong count = new AtomicLong(0);
public BigInteger factorialOf(BigInteger i) {
BigInteger result = calculateFactorial(i);
count.incrementAndGet();
return result;
}
public long getCount() { return count.get(); }
}
Atomic variable classes are just one of the many improvements offered by Java 5 over the previous versions that allow to make concurrent development easier. Other fundamental features provided by Java 5 are a new set of thread-safe collections, an executor framework for running unrelated tasks and several other kinds of classes that have been added to better support advanced concurrent design like Semaphore, ReentrantLock and CountDownLatch. A good knowledge of these classes and their APIs allow to build our concurrent programs on a set of well-proven thread-safe libraries without the need to reinvent the wheel.
Preserve Invariants
Now suppose we want to improve the FactorialCalculator even a bit more. In particular, we discovered that for some reason the clients of our object tend to ask the factorial of a given number more than once quite often, so we decided to improve its performance by caching the last computed factorial value as it follows:
public class FactorialCalculator {
private final AtomicReference<BigInteger> lastNumber =
new AtomicReference<BigInteger>();
private final AtomicReference<BigInteger> lastFactorial =
new AtomicReference<BigInteger>();
public BigInteger factorialOf(BigInteger i) {
if (i.equals(lastNumber.get()))
return lastFactorial.get();
BigInteger result = calculateFactorial(i);
lastNumber.set(i);
lastFactorial.set(result);
return result;
}
}
We update the values of lastNumber and lastFactorial via AtomicReferences so the object’s thread safety is still guaranteed, isn't it? Unfortunately no. This approach does not work, because even though the atomic references are individually thread-safe, FactorialCalculator still has a race condition that could make it produce the wrong answer.
An invariant is a condition that, in order to preserve the correctness of a multi-threaded program, needs to be verified immediately before and after each atomic operation performed by the program itself. The only invariant of FactorialCalculator is that the factorial value cached in lastFactorial has to correspond to the value cached in lastNumber and it is correct only if this invariant always holds. What is said implies that the third rule to keep bugs out of our parallel programs is: ensure that invariants are preserved regardless of timing or interleaving of operations in multiple threads.
Use Small Synchronized Blocks
As stated, in order to preserve the FactorialCalculator invariant, we need to keep synchronized the code that modifies its state as it follows:
public class FactorialCalculator {
private final AtomicReference<BigInteger> lastNumber =
new AtomicReference<BigInteger>();
private final AtomicReference<BigInteger> lastFactorial =
new AtomicReference<BigInteger>();
public BigInteger factorialOf(BigInteger i) {
synchronized(this) {
if (i.equals(lastNumber.get()))
return lastFactorial.get();
}
BigInteger result = calculateFactorial(i);
synchronized(this) {
lastNumber.set(i);
lastFactorial.set(result);
}
return result;
}
}
This last version of our class enforces the invariant of the last cached result by guarding the read and write operations on lastNumber and lastFactorial with the same lock. Note that we could achieve the same result in an easier (and more readable way) by synchronizing the whole factorialOf() method, but this poor choice implies that all the invocations to that method will be completely serialized, making useless our effort to write a thread safe class that can perform well in a multithreaded environment. From this last consideration derives the fourth rule: keep synchronized blocks as small as possible (but not smaller) in order to not excessively compromise the parallel execution of our code.
History
- 28th February, 2009: Initial post
