Race condition

Code in:JavaC#PythonJavaScript

In short: A race condition is a bug where the result depends on the order of execution: two Workers lose a sale, and an await between the check and the purchase lets two buyers in even on one thread.

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 Workers (the lesson "Async, await and threads"). The stock lives in a SharedArrayBuffer, shared memory that both can see. Each sells 1,000,000 items:

// stock is an Int32Array in a SharedArrayBuffer:
// memory shared by the Workers.
function sell(stock) {
  stock[0]--;   // read, subtract 1, write
}

if (isMainThread) {
  const stock = new Int32Array(new SharedArrayBuffer(4));
  stock[0] = 2_000_000;
  const checkouts = [1, 2].map(
    () => new Worker(new URL(import.meta.url), { workerData: stock }),
  );
  await Promise.all(checkouts.map((worker) => once(worker, "exit")));
  console.log(`Orders: ${2 * 1_000_000}`);
  console.log("Sold according to the stock:");
  console.log(2_000_000 - stock[0]);
} else {
  for (let i = 0; i < 1_000_000; i++) {
    sell(workerData);
  }
}

Customers have paid for 2,000,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: 2000000
Sold according to the stock: 1003506
Sold according to the stock: 994022
Sold according to the stock: 1004855
Sold according to the stock: 1018607

Usually the warehouse counts about half. In one of the five runs it counts right: that time one Worker finished before the other started. The items that are gone, the warehouse thinks it "has": tomorrow the shop will sell them to someone and then refund the money.

The idea

stock[0]-- is three steps

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

// stock is an Int32Array in a SharedArrayBuffer:
// memory shared by the Workers.
function sell(stock) {
  const seen = stock[0];     // 1. read
  const after = seen - 1;    // 2. subtract 1
  stock[0] = after;          // 3. write
}

Step by step, in words

1. 5 items are left. Worker A and Worker B each sell one at the same moment.
2. Worker A reads the stock: 5.
3. Worker B reads before A has written: also 5.
4. Worker A subtracts 1 in its own variable: 4.
5. Worker B does the same from its own 5: also 4.
6. Worker A writes 4. One sale, 4 left: correct so far.
7. Worker 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

stock[0]-- on an Int32Array reads from the shared memory, subtracts in a register and writes. In between, the other Worker, running on another core, can read the same number. With an ordinary JavaScript object this cannot happen: objects are not shared between Workers, they are copied.

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:

let left = 5;
const seenA = left;    // A reads
const seenB = left;    // B reads
left = seenA - 1;      // A writes
const seenC = left;    // C reads
left = seenB - 1;      // B writes
left = seenC - 1;      // C writes
console.log("Sales: 3");
console.log(`In stock: ${left}`);

Answer

Sales: 3
In stock: 2

Sales: 3
In stock: 4

Sales: 3
In stock: 3

Check

The idea

"It works on my machine"

The same program, with fewer sales per till:

if (isMainThread) {
  const stock = new Int32Array(new SharedArrayBuffer(4));
  stock[0] = 2_000;
  const checkouts = [1, 2].map(
    () => new Worker(new URL(import.meta.url), { workerData: stock }),
  );
  await Promise.all(checkouts.map((worker) => once(worker, "exit")));
  console.log(`Orders: ${2 * 1_000}`);
  console.log("Sold according to the stock:");
  console.log(2_000 - stock[0]);
} else {
  for (let i = 0; i < 1_000; i++) {
    sell(workerData);
  }
}

Output of five runs (the third line)

Sold according to the stock: 2000
Sold according to the stock: 2000
Sold according to the stock: 1929
Sold according to the stock: 2000
Sold according to the stock: 2000

Right four times and one loss. A Worker starts slowly, so usually one finishes its 1000 sales before the other has begun. Usually.

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 {
  constructor(left) {
    this.left = left;
  }

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

const stock = new Stock(1);
const bought = await Promise.all([stock.buy(), stock.buy()]);
console.log("In stock before: 1");
console.log("Sold:");
console.log(bought.filter((ok) => ok).length);
console.log("In stock after:");
console.log(stock.left);

Output

In stock before: 1
Sold:
2
In stock after:
-1

There is one thread here, and the bug is the same. await sleep(100) lets the other call run while the first waits for the bank. It reaches the check while left is still 1. On one thread the order is the same every time, so the bug happens every time too. There is more on this in the lesson "async is not a thread".

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(next) 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.

1// next is an Int32Array in a SharedArrayBuffer.2function take(next) {3 const number = next[0];4 next[0] = number + 1;5 return number;6}

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. In a SharedArrayBuffer an ordinary read may not see another Worker's write in time. Atomics.load and Atomics.store guarantee it. 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 500,000 headphones each at €3. Each till counts its sales in its own variable, and the revenue is shared: an Int32Array in a SharedArrayBuffer, where each Worker does revenue[0] += 3. Print each till's sales and the revenue. Run the program several times.

Expect

Till 1: 500000 sales
Till 2: 500000 sales
Revenue (€):
3000000

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 an async method "book room 12 if it is free" with await sleep(100) between the check and the write, and run two guests with Promise.all. How many guests get the room?

Test

Test yourself

1. Two Workers each call stock[0]-- once on a SharedArrayBuffer where it is 5. What can it be at the end?

Always 33, 4 or 53 or 4

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. An async function checks this.left > 0, then await sleep(100), then this.left--. Two calls with Promise.all, 1 in stock. What happens?

Both pass the check: the stock goes to -1, on every runThe second waits for the first, because there is one threadSometimes -1, sometimes 0

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: Arrays: push, splice and sort · Arrow functions · Async, await and threads · Why threads
• Continues in: Locking · Atomic operations and immutable objects · Deadlock · Producer and consumer
• Tasks on this topic: Concurrency and race conditions