Race condition

Code in:JavaC#PythonJavaScript

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;

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

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

    public int Left => left;
}

Stock stock = new Stock(200_000);
ThreadStart 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();
Console.WriteLine($"Orders: {2 * 100_000}");
Console.WriteLine("Sold according to the stock:");
Console.WriteLine(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: 107415
Sold according to the stock: 104427
Sold according to the stock: 108645
Sold according to the stock: 107147
Sold according to the stock: 130643

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;

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

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

    public int Left => 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 a separate read (ldfld), subtraction (sub) and write (stfld) in IL. You can see them in sharplab.io or with ILSpy. The JIT compiler later turns them into 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
Console.WriteLine("Sales: 3");
Console.WriteLine($"In stock: {left}");

Answer

Sales: 3
In stock: 4

Sales: 3
In stock: 2

Sales: 3
In stock: 3

Check

The idea

"It works on my machine"

The same program, with fewer sales per till:

Stock stock = new Stock(2_000);
ThreadStart 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();
Console.WriteLine($"Orders: {2 * 1_000}");
Console.WriteLine("Sold according to the stock:");
Console.WriteLine(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;

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

    public bool Buy()
    {
        if (left > 0)        // check: is there one?
        {
            Thread.Sleep(100);   // the card is charged, ~100 ms
            left--;              // act: take the item
            return true;
        }
        return false;
    }

    public int Left => left;
}

Stock stock = new Stock(1);
bool[] bought = new bool[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.Count(b => b);
Console.WriteLine("In stock before: 1");
Console.WriteLine("Sold:");
Console.WriteLine(sold);
Console.WriteLine("In stock after:");
Console.WriteLine(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.

1class OrderNumbers2{3 private int next = 1001;45 public int Take()6 {7 int number = next;8 next = number + 1;9 return number;10 }11}

Check

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 lock or Volatile.Read the JIT may read a field once and never read it again. A loop while (!done) { } may never stop. 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?

3 or 4Always 33, 4 or 5

2. The test with two threads of 1000 sales each passes 100 times out of 100. What does that tell you?

That you need more cores to checkThat the code is thread-safeNothing about a race condition: with 1000 the first thread often finishes before the second starts

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?

Both pass the check, both pay, and the stock goes to -1The second waits for the first, because there is one checkThe program throws an exception

4. Which of these can NOT have a race condition?

One thread writes to a shared counter, and another reads it and decides by itTwo threads write to a shared counterEach thread counts its sales in its own local variable

Check

Start the lesson over

Related lessons

• Builds on: Lists · Lambdas and delegates · Threads · Why threads
• Continues in: Locking · Atomic operations and immutable objects · Deadlock · Producer and consumer
• Tasks on this topic: Concurrency and race conditions