Race conditions

Intuition

You and a flatmate share a jar for the electricity money. You both count it (£10), each go to the cash machine, each add £5 to your own count, and each write “£15” on the label. Two people added money, but the label says one did. Neither of you did anything wrong on your own; the problem is that you both read the jar before either of you updated it.

That’s a race condition. Whoever writes last “wins,” and the other person’s update is lost.

How it works

counter = counter + 1 looks like one step, but the computer does three:

1. Read counter into a private copy (tmp = counter).
2. Add one to the copy (tmp = tmp + 1).
3. Write the copy back (counter = tmp).

If a second thread reads between the first thread’s read and write, both start from the same old value and one increment is lost. The figure lets you choose exactly when each thread runs, so you can make that happen on purpose.

A lock (also called a mutex) fixes it by making the three lines a critical section: a thread must acquire the lock before reading and release it after writing. While A holds the lock, B waits, so B always reads the value A wrote.

The fix in code

Each program starts several workers that add 1 to a shared counter many times, guarded by a lock. The counter lives on the heap, where every thread can see it. Remove the lock and the total comes out short, by a different amount on each run.

import threading


def count_up(times, workers):
    counter = 0
    lock = threading.Lock()

    def work():
        nonlocal counter
        for _ in range(times):
            with lock:  # only one thread at a time past here
                tmp = counter
                counter = tmp + 1

    threads = [threading.Thread(target=work) for _ in range(workers)]
    for t in threads:
        t.start()
    for t in threads:
        t.join()  # wait for every thread to finish
    return counter

// JavaScript runs one task at a time, but an await lets other tasks in
// between a read and a write, so async code can lose updates too.
const pause = () => new Promise((resolve) => setTimeout(resolve, 0));

async function countUp(times, workers) {
  let counter = 0;
  let queue = Promise.resolve(); // a simple lock: wait your turn

  async function work() {
    for (let i = 0; i < times; i++) {
      let release;
      const ahead = queue;
      queue = new Promise((resolve) => (release = resolve));
      await ahead; // take the lock
      const tmp = counter;
      await pause(); // other tasks run here, but none can touch counter
      counter = tmp + 1;
      release(); // let the next task in
    }
  }

  await Promise.all(Array.from({ length: workers }, work));
  return counter;
}

import "sync"

func countUp(times, workers int) int {
	counter := 0
	var mu sync.Mutex
	var wg sync.WaitGroup
	for w := 0; w < workers; w++ {
		wg.Add(1)
		go func() {
			defer wg.Done()
			for i := 0; i < times; i++ {
				mu.Lock() // only one goroutine at a time past here
				tmp := counter
				counter = tmp + 1
				mu.Unlock()
			}
		}()
	}
	wg.Wait() // wait for every goroutine to finish
	return counter
}

use std::sync::{Arc, Mutex};
use std::thread;

fn count_up(times: usize, workers: usize) -> usize {
    // Rust won't compile shared, unguarded writes: the counter
    // has to live inside a Mutex that every thread shares.
    let counter = Arc::new(Mutex::new(0));
    let mut handles = Vec::new();
    for _ in 0..workers {
        let counter = Arc::clone(&counter);
        handles.push(thread::spawn(move || {
            for _ in 0..times {
                let mut value = counter.lock().unwrap(); // take the lock
                let tmp = *value;
                *value = tmp + 1;
            } // the lock is released when `value` goes out of scope
        }));
    }
    for h in handles {
        h.join().unwrap(); // wait for every thread to finish
    }
    let total = *counter.lock().unwrap();
    total
}

In each language

Race condition or data race?

A data race is two threads touching the same memory at the same time, at least one writing, with no synchronization. Tools like Go’s race detector and ThreadSanitizer find these.

A race condition is any bug that depends on timing. Every data race can cause one, but you can also have a race condition without a data race: lock, read, unlock, lock, write, unlock is free of data races and still loses updates, because the read and the write aren’t in the same critical section.

Common mistakes

1. Trusting that it passed the tests. Most orders are fine; a race shows up under load, on a different machine, or once a week.
2. Locking only the write. The read and the write must be inside the same critical section.
3. Holding a lock while waiting for something slow, such as a network call. Other threads stall behind it.
4. Taking two locks in different orders in different threads. Each can end up waiting for the other forever: a deadlock.

Check yourself

Sources

• Maurice Herlihy and Nir Shavit, The Art of Multiprocessor Programming, chapter 2, “Mutual Exclusion”.
• The Go blog, “Introducing the Go Race Detector”.
• Python documentation, threading.Lock; PEP 703, “Making the Global Interpreter Lock Optional in CPython”.