Skip to content
wannacode

Race condition

In short: A race condition is a bug where the result depends on how threads interleave: left-- is three steps (read, subtract, write), so two threads can lose a sale.

Problem

The sale counts wrong

Friday, flash sale. Headphones are half price and the orders pour in. Two tills sell from one warehouse: each sale subtracts 1 from the stock.

The tills are two threads. Each sells 100,000 items and calls sell() for each one:
class Stock {
    private int left;


    Stock(int left) {
        this.left = left;
    }


    void sell() {
        left--;   // read, subtract 1, write
    }


    int left() {
        return left;
    }
}
Stock stock = new Stock(200_000);
Runnable checkout = () -> {
    for (int i = 0; i < 100_000; i++) {
        stock.sell();
    }
};
Thread a = new Thread(checkout);
Thread b = new Thread(checkout);
a.start();
b.start();
a.join();
b.join();
System.out.println("Orders: " + 2 * 100_000);
System.out.println("Sold according to the stock:");
System.out.println(200_000 - stock.left());

Customers have paid for 200,000 orders. Here is how many sales the warehouse counts over five runs:

Output of five runs (the third line)
Sold according to the stock: 108435
Sold according to the stock: 129196
Sold according to the stock: 117263
Sold according to the stock: 118496
Sold according to the stock: 118057
The warehouse counts tens of thousands fewer. Those items are gone, but the warehouse thinks it "has" them: tomorrow the shop will sell them to someone and then refund the money.

The idea

left-- is three steps

In the code left-- is one line. The processor does it in three steps, as if you wrote them out:

class Stock {
    private int left;


    Stock(int left) {
        this.left = left;
    }


    void sell() {
        int seen = left;       // 1. read
        int after = seen - 1;  // 2. subtract 1
        left = after;          // 3. write
    }


    int left() {
        return left;
    }
}
Step by step, in words
  1. 5 items are left. Till A and till B each sell one at the same moment.
  2. Till A reads the stock: 5.
  3. Till B reads before A has written: also 5.
  4. Till A subtracts 1 in its own variable: 4.
  5. Till B does the same from its own 5: also 4.
  6. Till A writes 4. One sale, 4 left: correct so far.
  7. Till B writes 4 too, over the 4 of A. Two sales, and the stock is 4, not 3.
  8. One sale is lost: both read the same number before either wrote. That is a race condition, and the stock now shows one item that is already sold.
  1. Read the stock into your own variable.
  2. Subtract 1 from your copy.
  3. Write the copy back.

Two threads can take turns between any two steps. If both read 5 before either writes, both write 4. Two sales, and the stock goes down by one.

When the result depends on which thread does which step first, that is a race condition. The three steps "read, change, write" on shared data are its most common form.

More precisely, if you are curious
The compiler turns left-- into JVM instructions: getfield, iconst_1, isub, putfield (read the field, compute, write the field). javap -c Stock shows them. The JIT compiler may later replace them with machine instructions, but the read and the write stay separate.

Try it

Three tills, 5 in stock

Here are three tills, interleaved by hand in one of the possible orders. Each reads into its own variable, then writes 1 less:

int left = 5;
int seenA = left;      // A reads
int seenB = left;      // B reads
left = seenA - 1;      // A writes
int seenC = left;      // C reads
left = seenB - 1;      // B writes
left = seenC - 1;      // C writes
System.out.println("Sales: 3");
System.out.println("In stock: " + left);
Answer

The idea

"It works on my machine"

The same program, with fewer sales per till:

Stock stock = new Stock(2_000);
Runnable checkout = () -> {
    for (int i = 0; i < 1_000; i++) {
        stock.sell();
    }
};
Thread a = new Thread(checkout);
Thread b = new Thread(checkout);
a.start();
b.start();
a.join();
b.join();
System.out.println("Orders: " + 2 * 1_000);
System.out.println("Sold according to the stock:");
System.out.println(2_000 - stock.left());
Output of five runs (the third line)
Sold according to the stock: 2000
Sold according to the stock: 2000
Sold according to the stock: 2000
Sold according to the stock: 2000
Sold according to the stock: 2000
Right five times. Starting a thread takes longer than 1000 sales: the first till finishes before the second has started. The race condition is there, it just does not happen.

That is what makes a race condition treacherous:

  • the test passes on the laptop and fails on the server with 64 cores and thousands of customers;
  • the bug comes "sometimes" and does not repeat when you look for it;
  • add a print line, the order of the threads changes and the bug goes away.

A test without a loss proves nothing. Safety is proven by how the code is written: which data is shared and who protects it.

Problem

The last item

One item is left. Two buyers click "Buy" at the same moment. buy checks whether there is one, charges the card (about 100 ms) and only then takes the item:

class Stock {
    private int left;


    Stock(int left) {
        this.left = left;
    }


    boolean buy() {
        if (left > 0) {      // check: is there one?
            pause(100);      // the card is charged, ~100 ms
            left--;          // act: take the item
            return true;
        }
        return false;
    }


    int left() {
        return left;
    }


    private static void pause(int ms) {
        try {
            Thread.sleep(ms);
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
    }
}
Stock stock = new Stock(1);
boolean[] bought = new boolean[2];
Thread first = new Thread(() -> bought[0] = stock.buy());
Thread second = new Thread(() -> bought[1] = stock.buy());
first.start();
second.start();
first.join();
second.join();
int sold = (bought[0] ? 1 : 0) + (bought[1] ? 1 : 0);
System.out.println("In stock before: 1");
System.out.println("Sold:");
System.out.println(sold);
System.out.println("In stock after:");
System.out.println(stock.left());
Output of five runs
Sold: 2, in stock after: -1
Sold: 2, in stock after: -1
Sold: 2, in stock after: -1
Sold: 2, in stock after: -1
Sold: 2, in stock after: -1

Both pass the check: while the first one pays, the second sees the same 1. Both paid, and the stock is at -1. Here the race condition happens every time, because there are a whole 100 ms between the check and the action.

This is the second form of a race condition: check, then act (check-then-act). The decision is made on a value that someone else can change before the decision is carried out. It is everywhere: "is there a free room", "is the username free", "is there money in the account".

Try it

Order numbers

Every order gets a number: 1001, 1002, 1003… The tills are threads and call take() at the same time. Sometimes two orders get the same number. After which line does the other thread have to come in for that to happen?

Pick the line with the bug.

The idea

When there can be a race condition

It takes three things at once:

  1. Shared data: something several threads can see (the stock, the counter, the number).
  2. At least one thread changes it. If everyone only reads, there is nothing to get wrong.
  3. Nothing orders the access: threads go into their steps whenever their turn comes.

Take away one of the three and there is no race condition:

  • Don't share. Each thread counts in its own variable, and at the end the results are added up. That is how the 1000 invoices worked in "Why threads": each part computes its own.
  • Don't change. An object nobody changes can be read by as many threads as you like. That is the lesson "Atomic operations and immutable objects".
  • Order the access. Only one thread at a time in the three steps. That is the lock, the next lesson: "Locking".
More precisely, if you are curious

There is also a quieter problem: visibility. Without synchronized or volatile the JVM does not promise that a thread will ever see a value written by another. A loop while (!done) { } may never stop, because the JIT read done once. The lock solves this too: whatever one thread wrote before releasing it, the next one sees after taking it.

How it is in other languages: in Java and C# count++ loses just like here. In Python it loses less often because of the GIL, but it loses. In JavaScript it loses between Workers on a SharedArrayBuffer, and on one thread a race condition exists only between two awaits.

Exercise

The sale's revenue

Solve the task in your editor.

The revenue. Two tills sell 50,000 headphones each at €3. Each till counts its sales in its own variable, and the revenue is shared: a Revenue object with a method add(euros) that does total += euros. Print each till's sales and the revenue. Run the program several times.

Expect
Till 1: 50000 sales
Till 2: 50000 sales
Revenue (€):
300000

The tills' sales are right on every run: each counts in its own variable. The revenue is smaller and different every time. The fix is in the next lesson.

More tasks

  • How much is lost. Run the sale with 2, 4 and 8 tills. Is more lost with more tills?
  • Find what is shared. Take a program with threads you have written and list the data that more than one thread touches. Which of them does some thread change? - Free room. Write a hotel with a method "book room 12 if it is free" and run two guests at once, with a 100 ms pause between the check and the write. How many guests get the room?

Test

Test yourself

1. Two threads each call left-- once on a shared field that is 5. What can it be at the end?
2. The test with two threads of 1000 sales each passes 100 times out of 100. What does that tell you?
3. There is 1 item in stock. The code checks "left > 0", charges the card for 100 ms and only then subtracts 1. Two people buy at once. What happens?
4. Which of these can NOT have a race condition?

Made by Ivo Gergov as part of Evo Tech's campaign for accessible programming education ·