Concurrency & Synchronization
Race conditions, critical sections, mutexes and semaphores — why tests pass but production corrupts data.
The Core Problem
When two threads touch shared data and at least one writes, the interleaving of their operations decides the result — a race condition. The classic example: two threads each run count++, which is really read → add → write. Interleave them and one update is lost.
count = 0 // shared Thread A: read 0 → add 1 → write 1 Thread B: read 0 → add 1 → write 1 // A's update lost! // Expected 2, got 1.
Mutexes & Semaphores
| Primitive | What it is | Use for |
|---|---|---|
| Mutex | A lock — one holder at a time | Protecting a critical section |
| Binary semaphore | 0/1 counter with wait/signal | Similar to a mutex, no ownership |
| Counting semaphore | Counter ≥ 0 | Limiting N concurrent users of a resource |
| Condition variable | Wait until a predicate holds | Producer/consumer signaling |
lock.acquire() try: count += 1 # critical section finally: lock.release()
Rules of a Correct Solution
- Mutual exclusion — one thread in the critical section
- Forgetting to release the lock (leak → deadlock)
Any mutual-exclusion solution must provide three properties: mutual exclusion (at most one in the critical section), progress (if it’s free, someone waiting gets in), and bounded waiting (no one waits forever).
Producer–Consumer
The canonical synchronization problem: producers add items to a bounded buffer, consumers remove them. You need a mutex for the buffer plus two counting semaphores — empty slots and full slots — so producers block when full and consumers block when empty.
empty = Semaphore(N) # free slots full = Semaphore(0) # filled slots mutex = Lock() # Producer empty.acquire(); mutex.acquire() buffer.put(item) mutex.release(); full.release() # Consumer full.acquire(); mutex.acquire() item = buffer.get() mutex.release(); empty.release()
Interview Questions
What is a race condition?
A bug where the result depends on the nondeterministic timing of threads accessing shared data, with at least one writer. Fix by making the critical section mutually exclusive.
Mutex vs semaphore?
A mutex is a lock with ownership — only the thread that locked it should unlock it — used for mutual exclusion. A semaphore is a signaling counter with no ownership; a counting semaphore limits N concurrent accesses.
Why is count++ not atomic?
It compiles to read-modify-write (load, increment, store). A thread can be preempted between those steps, so two threads can both read the old value and one increment is lost.
What three properties must a mutual-exclusion solution guarantee?
Mutual exclusion, progress, and bounded waiting.