The Dangers of Race Conditions in Five Minutes

A race condition is an undesired property of multithreaded code. It expresses that the program’s outcome depends on a particular order of operations but that the underlying platform (in the case of Java, the JVM) does not guarantee that order. As a consequence the outcome is often fluctuating across runs as it depends on how exactly operations from different threads interleave. In Java, race conditions occur most often when multiple threads share and mutate the same object.

The only prerequisite for this article is a basic knowledge of threads.

Race Conditions

A Simple Example

Let’s start with an example. Here I’ve implemented a Runnable that increments a shared counter ten thousand times:

class IncrementingRunnable implements Runnable {

    private final MutableInteger mutableInteger;

    public IncrementingRunnable(MutableInteger mutableInteger) {
        this.mutableInteger = mutableInteger;
    }

    @Override
    public void run() {
        for (int i = 0; i < 10_000; i++) {
            mutableInteger.increment();
        }
    }

}

Since a value of a standard Java Integer cannot be updated after it was created, I’ve implemented a simple MutableInteger class that has two methods:

• increment to increment its value
• getValue to get the result value.

class MutableInteger {

    private int value = 0;

    public void increment() {
        value++;
    }

    public int getValue() {
        return value;
    }

}

With this, we can pass the same counter to multiple threads that will increment it in parallel:

List<Thread> threads = new ArrayList<>();

// Variable to increment from multiple threads
MutableInteger integer = new MutableInteger();
// Run 10 threads to increment the same variable
for (int i = 0; i < 10; i++) {
    Thread thread = new Thread(new IncrementingRunnable(integer));
    thread.start();
    threads.add(thread);
}

// Wait until all threads are finished
for (Thread thread : threads) {
    thread.join();
}

System.out.println("Result value: " + integer.getValue());

(If you’re not sure how Thread::start or join work, read this five-minute intro to threads.)

Since we have ten threads and every thread performs 10,000 increments, we might expect the final value to be 100,000. But the actual result may surprise you:

Result value: 61505

What is more astonishing is that the total sum is different every time the application is executed, but it is always less than 100,000.

How Increment Creates a Race Condition

To understand what happens here we need to cover how the increment operation works. You may think that it is an indivisible operation and does not have any intermediate states, but in reality, a CPU executes several low-level instructions like these:

//i++
$tmp = i; // Store value to a temporary storage
$tmp = $tmp + 1; // Increment value in the temporary storage
i = $tmp; // Write result value back

This does not cause any issues when only one thread is updating a counter. But when there are multiple threads they can step on each other’s toes and execute those low-level operations in any order:

// T1 is Thread 1; T2 is Thread 2
T1: $tmp_1 = i;
T1: $tmp_1 = $tmp_1 + 1;
T2: $tmp_2 = i;
T2: $tmp_2 = $tmp_2 + 1;
T2: i = $tmp_2;
T1: i = $tmp_1;

In this particular example, threads 1 and 2 both load the same i, let’s say 5, into their respective temporary variable. Hence, after incrementing both write 6 back but the desired result for two increments would have been 7.

This is why when we run our application the final result is always less than 100,000. An individual thread is not aware that there are other threads that are also incrementing the same number. As a result, the final outcome depends on which thread accesses memory in which order.

A Not so Simple Example

Race conditions can also occur when we work with complex data structures. Let’s take a look at an example when multiple threads are updating the same instance of a LinkedList:

class ListAddRunnable implements Runnable {

    private final LinkedList<Integer> list;

    public ListAddRunnable(LinkedList<Integer> list) {
        this.list = list;
    }

    @Override
    public void run() {
        for (int i = 0; i < 10_000; i++) {
            list.add(i);
        }
    }

}

Using this Runnable, we can again start 10 threads that each is supposed to add 10_000 elements to the same list and wait for them to finish. Here is the output that I got:

Result value: 44157

What happened here? To understand it we first need to understand how LinkedList and particularly add work. Internally LinkedList is represented as a chain of nodes and every node contains two references: one to an element added to the list and another one to the next node. The add method adds a node to the end of the list – here’s a simplified version of that method:

void add(E element) {
    Node<E> newSecondLast = this.last;
    // create the new node (null says there is no next node)
    Node<E> newNode = new Node<>(element, null);
    // use it as the last node and let the old 'last' refer to it
    this.last = newNode;
    newSecondLast.next = newNode;
}

(You can read more about how LinkedList is implemented on Wikipedia.)

Now let’s take a look at one sequence of events that can happen if two threads are adding elements at the same time:

// First thread starts adding an element to the end of the list
T1: Node<E> newSecondLast = this.last;
T1: Node<E> newNode = new Node<>(element, null);
// Second thread adds an element to the end of the list
T2: Node<E> newSecondLast = this.last;
T2: Node<E> newNode = new Node<>(element, null);
T2: this.last = newNode;
T2: newSecondLast.next = newNode;
// First thread continues and overwrites the last element of the list
T1: this.last = newNode;
T1: newSecondLast.next = newNode1

Note that all variables are local to the two threads except this.last. It is the order in which they read from and write to that shared field that makes or breaks the program. In the case above both read the same last node and from there on there is no way to get to a correct state because either T1 overrides T2 or the other way around.

Again, the program’s behavior depends on the unpredictable interaction between threads.

Conclusions

In this post, you’ve learned that a race condition occurs when multiple threads update shared state in a way that is not guaranteed to be correct. It may be tricky to spot, especially if multithreading programming is new for you, but, as a rule of thumb, you should be especially careful every time you have an object accessible by multiple threads.

There are several ways to prevent race conditions. The most basic way to do it is to use synchronization and locks – low-level primitives to build concurrent algorithms. JDK also provides a wide range of concurrent collections and atomic values that can be used as high-level building blocks.

Another way to avoid race conditions is to avoid a mutable state in the first place. To do this, you need to use immutable objects and immutable data structures that create copies of themselves on every update instead of performing a change in-place.

Frequently Asked Questions (FAQs) about Race Conditions