The moment two threads touch the same data, correctness stops being obvious. This article covers why race conditions happen, the tools that tame them, and how deadlock arises and is prevented — the concurrency triad every interview revisits.
Race conditions and the critical section
A race condition occurs when the result of a computation depends on the timing of interleaved operations on shared state. The canonical example is an unguarded increment:
// Two threads run counter++ ; final value should be 2 but can be 1
load r, counter // T1 reads 0
// T2 reads 0
add r, 1 // both compute 1
store counter, r // both write 1 -> lost update
counter++ looks atomic but compiles to load–modify–store. If a context switch lands between the load and the store, one update is lost. The block of code that accesses shared state is the critical section, and any correct solution must satisfy three properties:
- Mutual exclusion: at most one thread in the critical section at a time.
- Progress: if no thread is inside and some want in, one that is not spinning in remainder code must be selected to enter (no needless blocking).
- Bounded waiting: a thread cannot be starved indefinitely; there is a bound on how many others can enter first.
The synchronization toolkit
Mutex (lock)
A mutex enforces mutual exclusion: lock() before the critical section, unlock() after. It has an owner — only the thread that locked it should unlock it. A spinlock busy-waits (good for very short critical sections on multicore); a blocking mutex parks the thread (better when the wait may be long).
Semaphore
A semaphore is an integer with two atomic operations: wait/P (decrement; block if it would go negative) and signal/V (increment; wake a waiter).
- A binary semaphore (0/1) acts like a lock.
- A counting semaphore admits up to N threads — perfect for a pool of N identical resources (e.g., database connections).
Unlike a mutex, a semaphore has no ownership: any thread can signal it, which makes it ideal for signaling between threads (producer signals consumer) but easier to misuse.
Condition variables and monitors
A condition variable lets a thread wait (atomically release a mutex and sleep) until another thread signals a state change, then reacquire the mutex. Always re-check the predicate in a while loop, not an if, to guard against spurious wakeups. A monitor bundles shared data, a mutex, and condition variables into one language construct (Java's synchronized, C#'s lock) so mutual exclusion is automatic.
Producer–consumer sketch
semaphore empty = N; // free slots
semaphore full = 0; // filled slots
mutex m;
producer: consumer:
wait(empty); wait(full);
wait(m); wait(m);
buffer.add(item); item = buffer.remove();
signal(m); signal(m);
signal(full); signal(empty);
Note the ordering: acquire the counting semaphore before the mutex. Acquiring the mutex first and then blocking on empty/full while holding it would deadlock.
Deadlock
Deadlock is a state where a set of threads are each waiting for a resource held by another in the set, so none can proceed. Coffman identified four conditions that must all hold simultaneously:
- Mutual exclusion — resources are non-shareable.
- Hold and wait — a thread holds one resource while requesting another.
- No preemption — resources cannot be forcibly taken.
- Circular wait — a cycle exists: T1 waits on T2 waits on ... waits on T1.
Break any one and deadlock cannot occur.
The four strategies
| Strategy | Idea | Trade-off | |----------|------|-----------| | Prevention | Structurally negate a Coffman condition | May waste resources / limit concurrency | | Avoidance | Grant only if the system stays safe (Banker's algorithm) | Needs max-claims in advance; costly | | Detection & recovery | Let deadlock happen, find cycles, recover | Recovery kills/rolls back victims | | Ostrich | Ignore it; reboot if it happens | Common in general-purpose OSes |
Prevention examples: eliminate hold-and-wait by requiring all resources up front; allow preemption by making a blocked holder release what it has; eliminate circular wait by imposing a global lock ordering — always acquire locks in a fixed, agreed order. The lock-ordering rule is the single most practical technique in real code.
Banker's algorithm (avoidance)
The Banker's algorithm admits a request only if, afterward, there exists a sequence in which every process can obtain its declared maximum and finish — a safe state. It tracks Available, Max, Allocation, and Need = Max − Allocation. It is theoretically clean but rarely used in practice because maximum resource claims are seldom known ahead of time.
Deadlock vs starvation vs livelock
- Deadlock: processes are blocked forever, waiting on each other; nothing runs.
- Starvation: a process is runnable but perpetually passed over (e.g., low priority).
- Livelock: processes are active, changing state in response to each other, but make no progress — like two people stepping side to side in a hallway. Retrying transactions that keep colliding is a real-world livelock.
Classic problems interviewers cite
- Dining philosophers: five philosophers, five forks, each needs two neighbors' forks — a textbook circular-wait scenario. Fixes: pick up both forks atomically, impose fork ordering, or make one philosopher left-handed.
- Readers–writers: many readers may share, but a writer needs exclusive access; naive solutions starve writers.
Common follow-ups and gotchas
- "Mutex vs semaphore?" A mutex has an owner and is for mutual exclusion; a counting semaphore has no owner and is for counting/signaling resources. Use the least powerful tool that fits.
- "Why while, not if, around a condition-variable wait?" Spurious wakeups and the fact that another thread may have changed the state before you reacquire the lock.
- Deadlock needs all four conditions. If an interviewer asks how to prevent it, name the condition you're negating and how (lock ordering is the crispest answer).
- Atomicity ≠ visibility. Even a lock-free atomic operation must consider memory ordering; volatile in C/Java is about visibility, not mutual exclusion.