Skip to content
Tutorials Center
My learning

Topics

Lesson 22 of 66 ยท Synchronization

Race Conditions and Why Synchronization Exists

See how two threads that share data can corrupt it, why counter++ is not atomic, and how to explore every interleaving with a small Python simulation.

Two processes or threads that only touch their own data never need to coordinate. The trouble starts when they share something: a counter, a linked list, a bank balance, a file. If the final result depends on the exact order in which their steps happen to interleave, you have a race condition.

Race conditions are among the nastiest bugs in computing. The program works a thousand times, then fails once, and the failure disappears when you add a print statement. This chapter is about the tools the operating system and the hardware give you to prevent them. First, you need to see the problem clearly.

Why counter += 1 is not one step

In a high-level language, incrementing a shared counter looks like a single action. The CPU does not see it that way. It turns the statement into three instructions:

  1. LOAD: copy the value from memory into a register.
  2. ADD: add one to the register.
  3. STORE: write the register back to memory.

The scheduler can interrupt a thread between any two instructions. Suppose counter is 5 and two threads each run the increment:

sequenceDiagram
    participant A as Thread A
    participant M as counter (memory)
    participant B as Thread B
    A->>M: LOAD (reads 5)
    B->>M: LOAD (reads 5)
    A->>A: ADD (register = 6)
    B->>B: ADD (register = 6)
    A->>M: STORE 6
    B->>M: STORE 6
    Note over M: Two increments, final value 6, not 7

Both threads read the old value, so one update is lost.

This is called a lost update. Nothing crashed; the answer is just silently wrong.

Simulating threads with generators

Pyodide cannot run real parallel threads, but we do not need them. We can model a thread as a Python generator: every yield marks a point where the scheduler is allowed to switch to another thread. That lets us choose the interleaving ourselves and replay it exactly, which is something real threads never allow.

Python A lost update, on purpose

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The serial schedule gives 2, the interleaved one gives 1. The code is identical; only the timing differs. That is the heart of every race.

Counting every possible outcome

Instead of hoping to hit the bad schedule, a simulation can try all of them. Two threads with three steps each have 20 distinct interleavings (the number of ways to choose which 3 of 6 slots belong to thread A). Let us run each one and tally the final counter value.

Python Every interleaving of two increments

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Only 2 of the 20 schedules (the two fully serial ones) give the correct answer 2; the other 18 lose an update. Real hardware does not pick uniformly at random, so the actual failure rate depends on timing, which is exactly why the bug looks random in practice.

The general definition

A race condition exists when:

  • two or more threads or processes access the same shared data,
  • at least one of them writes, and
  • the result depends on the order of the accesses, which the programmer does not control.

The section of code that touches the shared data is called the critical section. The next lesson defines that precisely and shows the rules a correct solution must obey.

Where races hide

  • Shared counters and statistics: hit counters, reference counts, the "number of free slots".
  • Check-then-act: if (file does not exist) create it. Another process can create the file between the check and the act (a TOCTOU bug, time of check to time of use).
  • Linked lists and queues: two threads inserting at the same head can lose a node.
  • Kernel structures: the process table, the ready queue, the free-memory list. The kernel itself must protect these, even on a single CPU, because an interrupt can arrive at any instruction.

A race condition is not the same as a deadlock. In a race, programs finish with a wrong answer. In a deadlock, they never finish. You will meet deadlocks in the next chapter.

Fixing it: make the section run alone

The cure is mutual exclusion: only one thread at a time may be inside the critical section. Here is the same simulation with a simple lock flag. A thread that finds the lock taken yields without making progress and tries again on its next turn.

Python The same race, guarded

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Across 2,000 random schedules, every run now ends with 2. But look at the comment: acquiring the lock is itself a "check, then set" and could race in real life. The next lessons show how to build a lock that is correct, first in software and then with hardware help.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why can two threads executing counter++ lose an update?

    The statement compiles to several instructions. If both threads load the old value before either stores, both write back the same new value and one increment disappears.
  2. 2. Which of these is a race condition?

    A race needs shared data, at least one writer, and an outcome that depends on the order of accesses.
  3. 3. What is a TOCTOU bug?

    Time of check to time of use: the state you checked may no longer be true when you act on it.
  4. 4. What does the cure for a race condition aim to guarantee?

    Mutual exclusion on the critical section removes the interleavings that cause the wrong result.

Summary

  • A race condition means the result depends on the unpredictable interleaving of accesses to shared data.
  • Simple statements such as counter += 1 are several machine instructions, so they can be interrupted halfway.
  • Lost updates are silent: no crash, just a wrong answer that appears rarely.
  • A generator-based simulation lets you replay or enumerate every interleaving.
  • The cure is mutual exclusion around the critical section.

Next: The Critical-Section Problem and Peterson's Solution