Data races and synchronized

A board hangs on the kitchen wall, where the cooks mark how many dishes went out. Having served a dish, a cook walks up to the board, reads the number, adds one in their notepad and writes the new number over the old one. One day two cooks reach the board at the same moment: both read 5, both write 6. Two dishes went out, but the board grew by one.

The same failure happens in a program. Two threads, main and helper, increase one field count, 100,000 times each. We expect 200000:

public class Main {
    static int count = 0;
    static void addMany() {
        for (int i = 0; i < 100_000; i++) {
            count++;
        }
    }
    public static void main(String[] args) throws InterruptedException {
        Thread helper = new Thread(() -> addMany());
        helper.start();
        addMany();
        helper.join();
        System.out.println(count);
    }
}

count is a static field, so both threads work with the same variable. The program compiles without a single warning. But on a computer with several cores it almost always prints less than 200000, and a different number on every run, for example 135017.

Why increments go missing

count++ looks like one action, but it is not. Compile the program with the command javac Main.java and look into the bytecode with the command javap -c Main: there are four instructions for count++, and in meaning they are three steps:

1. read: getstatic fetches the value of count;
2. add: iconst_1 takes a one, and iadd adds;
3. write: putstatic puts the result back into count.

Between the read and the write, the number lives not in count but on the operand stack, a scratchpad that bytecode instructions put numbers on and take them from. Each thread has its own scratchpad, like each cook's own notepad.

The steps of two threads can mix in any order. If both threads read 5 before either of them writes its result, both write 6, and one increment is lost, as it was on the cooks' board.

Try it yourself: press Step A and Step B in different orders and watch how much ends up in count once both threads finish. Each step is labeled with its bytecode instruction.

This bug is called a data race: two threads access one variable, and at least one of them writes. Nothing decides who touches it when; a lock, coming below, is such a rule. Java does not report it: there is no compile error and no exception, only a wrong number. Interviewers like to ask this: why does count++ from two threads lose increments?

A race is treacherous because it does not always show. If the threads do little work, they may never overlap, and the program prints the right result many runs in a row. But Java does not promise that: on any run, increments can go missing.

Here the board picture is inaccurate: cooks can agree out loud on who goes first. Threads do not see each other and wait for nothing until the program itself gives them a lock.

The synchronized lock

The cooks made a deal: a lock with one key hangs on the board, and only the cook holding the key may mark a dish. In Java every object has such a lock, and it is called a monitor. The word synchronized before a method tells it to take the lock on entering the method and give it back on leaving:

static synchronized void increment() {
    count++;
}
static void addMany() {
    for (int i = 0; i < 100_000; i++) {
        increment();
    }
}

What changed:

1. increment() is a static synchronized method. It takes the lock of the class Main, one for the whole program.
2. While one thread is inside increment(), the other waits at the entrance, and the three steps of count++ no longer mix.
3. In the loop of addMany, count++ is now replaced by a call to increment().
4. The program prints 200000 on every run.

An ordinary, non-static synchronized method takes the lock of its own object, this. The data is protected only if all threads take the same lock.

AtomicInteger

For a single counter there is a shorter way. The class AtomicInteger from the package java.util.concurrent.atomic holds an int and can increase it in one indivisible operation. The method incrementAndGet() reads, adds and writes so that no other thread can squeeze in between the steps:

static AtomicInteger count = new AtomicInteger();
static void addMany() {
    for (int i = 0; i < 100_000; i++) {
        count.incrementAndGet();
    }
}

Add import java.util.concurrent.atomic.AtomicInteger; at the top of the file. System.out.println(count) prints the number inside the AtomicInteger, and the program outputs 200000 on every run. Switch the widget above to AtomicInteger: each thread now has one step, and you cannot lose an increment.

synchronized fits when several actions must happen under the lock, and AtomicInteger when one number needs protecting.

Common mistake

synchronized was put on an ordinary method, while the field is shared by all objects:

class Board {
    static int marks = 0;
    synchronized void mark() { // ✗
        marks++;
    }
}

Each thread marks its own board: one calls mark() on one new Board(), the other on another. The program compiles, but increments still go missing: two boards have two locks, but the field marks is one (it is static). The fix is static synchronized void mark(): then both threads take one lock, the lock of the class Board.

Key points

• count++ is three steps: read, add, write; the steps of two threads mix, and increments are lost.
• A data race is access by two threads to one variable with nothing that decides who touches it when, where at least one writes; Java does not report it.
• synchronized lets one thread into a method at a time and protects the data only if all threads take one lock.
• AtomicInteger.incrementAndGet() increases the number in one indivisible operation.