3.1Race conditions and the critical-section problem
The idea
A race condition happens when the result depends on the exact interleaving of operations on shared data. The critical-section problem asks for rules that prevent it.
Think of it like this: Two people editing the same cell of a shared spreadsheet from stale copies: whoever saves last silently erases the other's change.
Why it exists
counter++ is three machine steps, so even a simple increment is not atomic. Without control, updates are lost.
How it works
- Identify the shared data and the code that touches it (the critical section).
- Demand mutual exclusion: one process at a time.
- Demand progress: only interested processes decide who enters, without endless postponement.
- Demand bounded waiting: no one waits forever while others repeatedly enter.
Worked example: counter = 0, two threads run counter++
Both LOAD 0, both ADD to 1, both STORE 1. The final value is 1, not 2. Minimum possible over all interleavings is 1 (for one increment per thread).
Now play with it
- →Run T1 LOAD, T2 LOAD, T1 ADD, T1 STORE, T2 ADD, T2 STORE and get 1.
- →Run all of T1 then all of T2 and get 2.
Two threads each run counter++, compiled to three steps. Counter starts at 0, so the correct result is 2. Click to choose which thread runs the next step, and try to produce 1.
Try T1 LOAD, T2 LOAD, T1 ADD, T1 STORE, T2 ADD, T2 STORE: both loaded 0, so the final value is 1. The outcome depends on the interleaving, which is what makes it a race condition.
| Requirement | Meaning | Typical way to break it |
|---|---|---|
| Mutual exclusion | at most one process in the critical section | checking a flag before setting it |
| Progress | only processes wanting in take part in choosing, and the choice is not postponed forever | strict alternation: a process that does not want in still blocks the other |
| Bounded waiting | a limit on how often others may enter ahead of a waiting process | a spinlock that always favours the same fast process |
Check yourself
Which is NOT one of the three requirements of a critical-section solution?
Exam notes (the dense version)
A race condition is when the result depends on the interleaving of operations on shared data, e.g. counter++ is load, add, store, so two threads can lose an update. The critical section is code touching shared data. A correct solution needs three things: mutual exclusion (one at a time), progress (a process outside the critical section cannot block others from entering; the decision cannot be postponed forever) and bounded waiting (no process waits indefinitely while others repeatedly enter).
Previous year questions: Synchronization & Concurrency (10)
PYQs are grouped by topic, so this is the full set for Synchronization & Concurrency; try the ones that match this subtopic. Open all 10 on the topic page.