Synchronization primitives
Locks, semaphores and atomics create the ordering edges that make shared state safe — each with a different cost and a different failure mode.
The fix for a race is not a cleverer schedule; it is an object that the
scheduler cannot violate. A mutex is exactly that: a lock with two
operations, lock() and unlock(), and one guarantee — at most one thread is
between them at a time. Whatever the OS does with your threads, it cannot place
two of them inside the same critical section. That is the ordering edge that
makes the lost-update program correct: the load, add and store become one
indivisible unit.
Everything else is a variation on that theme. A counting semaphore is a lock that admits N holders instead of one. A condition variable lets a thread wait for a predicate rather than spinning. Atomics do away with locks for simple operations by asking the hardware for a read-modify-write that cannot be split. Each is the right tool for a different shape of problem, and each has its own way of biting you.
A permit, not a barrier
A mutex does not stop other threads from running — it stops them from entering. Threads outside the critical section continue freely while one holds the permit. The job is to keep the protected region as small as possible, so the time serialised is a fraction of the time parallel.
Request and release permits below. Switch between a mutex and a semaphore and watch the waiter queue form.
Mutex — one thread at a time
critical section · 0 / 1 permits held
waiter queue · FIFO · 0 blocked
idle threads · click to request
Request is the fast path when a permit is free and the slow path — park in the queue — when it is not. Release returns the permit and hands it directly to the head of the queue, which is what stops a hot thread from stealing it back and starving the others. A mutex is just this with one permit; a read-write lock admits many readers but one writer. The queue is illustrative FIFO, not a real scheduler's fairness policy.
Mutex
lock() blocks until the permit is free, then takes it; unlock() returns it
and wakes the next waiter. The contract is strict:
- Every
lock()must be matched by exactly oneunlock(), on every path including exceptions. RAII — a scoped guard object — is what makes this reliable in C++. - Do not hold a lock across a blocking call, a network request, or user code you do not control. Long critical sections serialise the whole program.
- Lock ordering must be consistent across the program, or you invite deadlock.
The cost of a mutex is not just the instruction to set a flag; it is the cache-line bouncing and the potential context switch when a waiter sleeps. Uncontended, it is tens of nanoseconds. Contended, it can be thousands of nanoseconds and reorder your performance entirely. That gap is why lock-free designs exist.
Semaphores and condition variables
A counting semaphore holds a non-negative integer. wait() decrements if
positive, otherwise blocks; post() increments and wakes a waiter. A mutex is
the special case of one permit. Semaphores are the natural fit for
resource pools — N database connections, N worker slots — and for
signalling between threads.
A condition variable is different in kind: it lets a thread sleep until a
predicate becomes true, with wait(lock), notify_one() and notify_all().
The canonical pattern is always a loop, never an if:
cv.wait(lock, [] { return !queue.empty(); });
auto item = queue.front();
queue.pop();
The predicate loop guards against spurious wakeups and against the window
between wakeup and reacquiring the lock in which another thread may have
consumed the condition. An if here is a classic bug.
Atomics and compare-and-swap
Some updates are single machine instructions. A fetch-and-add or a
compare-and-swap (CAS) — "if the value is still expected, set it to
desired, and tell me whether you succeeded" — completes atomically without a
lock. The standard lock-free loop is optimistic:
do {
old = load(v);
new = f(old); // compute from the value you read
} while (!compare_exchange(v, old, new));
You compute a new value from the snapshot, then try to install it only if
nobody changed the snapshot in the meantime; if they did, you retry. This is
fast under low contention and can live-lock under high contention, which is
why lock-free structures often use a CAS loop with backoff. In C++, std::atomic
also lets you choose a memory order (relaxed, acquire, release,
seq_cst); the default seq_cst is the easiest to reason about and the
slowest, and the others are a topic in their own right.
When things go wrong
- Deadlock — two threads each hold what the other wants. The classic fix is a global lock ordering: everyone acquires A before B.
- Starvation — one thread never wins the lock because others keep barging. Fair locks cost throughput; unfair locks cost tail latency.
- Priority inversion — a high-priority thread waits behind a low-priority one that is itself preempted. Priority inheritance (as on Mars Pathfinder) is the standard remedy.
- False sharing — two threads write different variables that happen to share a cache line, so the line ping-pongs. Padding the variables apart fixes it.
Careful
Locks are not composable in the way you would like: two individually thread-safe operations, called in sequence without the lock held across both, are not together atomic. "Check then act" — test a condition, then act on it — must happen inside one critical section, or another thread can change the world between the two steps. Prefer holding the lock across the whole invariant.
Illustrative vs real
The queue here is an idealised FIFO and the cost of a permit is not modelled. Real mutexes may be unfair (barging), spin before sleeping, or use futexes with kernel fallback; real atomics have architecture-specific ordering and performance. The semantics shown are the concepts, not any particular standard-library implementation.
Check yourself
Eduspheria wiki · Systems for AI, Concurrent programming
0 / 5 answered
From the exam paper
Modeled on NITJ AI-619, End-Sem June 2025
0 / 5 answered
Where next: the parallel patterns — map, reduce, scan — that turn these primitives into scalable structure.