// the one-minute version
When threads share data, interleaving their steps can corrupt it — a race condition. The fix is to make the dangerous code a critical section only one thread enters at a time. This chapter is the toolbox: atomic instructions at the bottom, mutex locks and semaphores in the middle, and monitors as the high-level, harder-to-misuse wrapper. Even correct locking can hit deadlock, starvation, and priority inversion.
Two threads both run count = count + 1. You'd expect count to rise by two. Sometimes it rises by one — and the bug shows up once in a million runs, on the customer's machine, never in your tests. Welcome to concurrency.
01 The race condition
count = count + 1 isn't one step — it's three: read count, add one, write back. If two threads interleave those steps, both can read the same old value, both add one, both write the same result. One increment vanishes. A race condition is exactly this: the outcome depends on the unpredictable timing of threads.
02 The critical-section problem
The code touching shared data is the critical section. The goal: only one thread inside at a time. A correct solution needs three properties:
Mutual exclusion
If one thread is in its critical section, no other can be in theirs. The core guarantee.
Progress
If no one is inside and some threads want in, one must be allowed in — no needless stalling.
Bounded waiting
A thread can't wait forever while others repeatedly jump ahead. No starvation.
03 A software-only solution: Peterson's algorithm
Before hardware help, you can solve it in pure software. Peterson's solution (for two threads) uses a shared turn variable and a flag[] array: each thread signals it wants in and politely yields the turn to the other, guaranteeing all three properties. It's mostly of teaching value today — modern CPUs reorder memory operations, which can break naive software solutions — but it proves correct mutual exclusion is possible without special instructions.
04 Atomic hardware instructions
Real systems lean on the CPU. Modern processors provide atomic instructions — operations that complete as one indivisible step — such as test-and-set and compare-and-swap (CAS). These are the bedrock every higher-level tool is built on.
count = count + 1 lacks and what hardware atomics provide. CAS — "if this value is still X, set it to Y" — also underpins lock-free data structures.05 Mutex locks
The simplest tool: a mutex (mutual-exclusion lock). A thread acquire()s before the critical section and release()s after; if the lock is taken, others wait. Built on atomic instructions underneath.
06 Semaphores
A semaphore is a counter with two atomic operations: wait() (decrement, block if it would go negative) and signal() (increment, wake a waiter). A binary semaphore (0 or 1) acts like a mutex. A counting semaphore tracks a pool of N identical resources — say 5 database connections — letting exactly five threads through at once. Semaphores also coordinate ordering: one thread can wait() for another to signal() that a step is done.
07 Monitors and condition variables
Semaphores are powerful but easy to misuse: forget a signal(), or order wait()s wrong, and you get deadlock or corruption. A monitor bundles shared data with the procedures that touch it and automatically ensures only one thread is active inside at a time. Condition variables let a thread inside wait for some state to become true and be woken (signal) when it does. This is what languages expose as synchronized methods or lock objects.
08 Liveness hazards
Synchronization fixes races but can introduce new troubles: deadlock (threads wait on each other in a cycle — Chapter 8), starvation (a thread never gets the lock), and priority inversion (a high-priority thread stuck waiting on a lock held by a low-priority one). The classic fix for inversion is priority inheritance — temporarily boost the lock-holder's priority. Correct locking is necessary but not sufficient; you must also avoid these.
common catches & gotchas
- Increment is not atomic —
x++is read-modify-write — three steps that can interleave. The #1 source of races. - Forgetting to release — Return early or throw inside a critical section without releasing the lock and you deadlock everyone. Use scoped/RAII locks.
- Spinlock for a long wait — Spinning burns a whole core doing nothing. Only spin for waits shorter than a context switch.
- Semaphore ordering bugs — Swap a
waitandsignal, or mismatch counts, and you silently deadlock or corrupt. Monitors exist to prevent exactly this. - Priority inversion — A low-priority thread holding a lock can block a high-priority one indefinitely. Famous for nearly killing the Mars Pathfinder mission; fixed with priority inheritance.
09 Questions students actually ask
What exactly causes a race condition?
Shared data plus unsynchronized access where the result depends on timing. Operations that look atomic in source (like incrementing a counter) are several machine steps that can interleave.
Mutex vs semaphore?
A mutex enforces single ownership of one resource (one thread in, one out). A counting semaphore tracks N interchangeable resources and lets up to N threads proceed. A binary semaphore behaves like a mutex.
When is a spinlock a bad idea?
When the wait might be long — spinning burns CPU doing nothing. For very short waits (or briefly holding a lock on a multiprocessor) it's fine; otherwise block the thread.
Why prefer monitors over raw semaphores?
Monitors automate locking and keep shared data with its operations, so it's much harder to forget a release or order operations wrong. Fewer footguns, fewer bugs.
What is priority inversion?
A high-priority thread is blocked waiting on a lock held by a low-priority thread that itself can't run. Priority inheritance fixes it by temporarily raising the holder's priority.
10 Key takeaways
- A race condition = shared data + unsynchronized, timing-dependent access.
- Protect the critical section so only one thread enters at a time (mutual exclusion, progress, bounded waiting).
- Peterson's solves it in software; real systems use atomic instructions (test-and-set, CAS).
- Mutexes guard one resource; semaphores count a pool and coordinate ordering; monitors wrap it all safely.
- Spin vs block is a real choice with real costs.
- Even correct locking can hit deadlock, starvation, priority inversion.
11 Wrapping up
These are the tools; the next chapter puts them to work on the famous problems every OS course drills — bounded buffer, readers-writers, dining philosophers. Next up: Synchronization Examples.