ExampleDifficulty: Intermediate1 min

Race Condition Example: A Counter Incremented Ten Million Times

Eight of nine runs are right, and the code is broken in every one of them.

The smallest program that loses updates is two threads incrementing one unsynchronised counter. Running it at three sizes shows both the race and how hard it is to catch.

java

Counter counter = new Counter();

Runnable job = () -> {
    for (int i = 0; i < n; i++) {
        counter.increment();
    }
};

Thread a = new Thread(job);
Thread b = new Thread(job);
a.start(); b.start();
a.join(); b.join();

System.out.println(counter.count);

Run with n at a thousand, then at a hundred thousand, then at ten million, three times each. On a machine with two cores this is what comes back.

The same program at three sizes, three runs each
Increments each	Expected	Run 1	Run 2	Run 3
1,000	2,000	2,000	2,000	2,000
100,000	200,000	200,000	200,000	200,000
10,000,000	20,000,000	20,000,000	20,000,000	10,238,769

Eight of those nine runs are correct, and the code is broken in every one of them. The two join calls wait for both threads to finish before the total is read, so nothing was missed by reading too early: the increments really were lost.

Almost half of them went, on the run that failed. That is what a lost update looks like: not a small drift, but one thread spending a long stretch writing values it computed from a number the other thread had already moved past.

So a test cannot show this code is correct; it can only fail to show that it is wrong. That is what makes shared state that changes worth removing, rather than worth testing.

← → move through sections and cards