Locks, condition variables, atomics and memory ordering

Why it matters

Thread-coordination problems are a standard way to test whether you can reason about all interleavings rather than the one you imagined. Beyond puzzles, every backend with a worker pool, cache, connection pool or batching queue relies on these primitives, and many production bugs come from a missing re-check, a flag read without synchronization, or a lock held across slow I/O. Low-level and systems-research interviews go further and ask what ordering an atomic operation guarantees.

Core ideas

Mutexes give exclusion and visibility. Unlocking a mutex and later locking the same mutex creates a happens-before edge: everything the first thread wrote inside its critical section is visible to the next owner. That is why reading a shared variable "just to check" without the lock is a bug, not an optimization. Keep critical sections short, avoid blocking I/O inside them, and choose granularity deliberately: one coarse lock is simple and correct, while finer locks add parallelism and deadlock risk.

How locks are built. Spin locks loop on an atomic test-and-set or compare-and-swap; ticket locks add FIFO fairness. Spinning wastes CPU when the holder has been descheduled, so practical mutexes spin briefly and then sleep. On Linux, a futex-based mutex handles the uncontended case entirely in user space with one atomic instruction and enters the kernel only to sleep or to wake waiters.

Condition variables are waiting rooms, not state. The condition lives in shared variables protected by a mutex; the condition variable only lets a thread sleep until someone says "re-check". wait atomically releases the mutex and sleeps, then re-acquires it before returning. Always re-check in a loop: POSIX allows spurious wakeups, and under the usual Mesa semantics another thread may consume the state between the signal and your wakeup.

lock(m)
while queue is empty: wait(not_empty, m)
item = pop(queue)
signal(not_full)
unlock(m)

Use signal when any single waiter can make progress and all waiters wait for the same condition; use broadcast when waiters wait for different conditions or you cannot tell which one should run.

Semaphores hold a count: wait decrements it or blocks, post increments it and may wake a waiter. They express mutual exclusion (initial count 1), ordering (initial count 0: one thread posts, another waits) and resource counting, such as free slots in a bounded buffer. They have no owner, so misuse is harder to detect than with mutexes.

Atomics and memory order. Compilers and CPUs reorder memory operations whenever a single thread could not tell the difference: x86 lets a later load pass an earlier store through the store buffer, and ARM reorders more. Two unsynchronized conflicting accesses form a data race, which is undefined behavior in C and C++. Atomics provide atomicity, and their memory order provides visibility:

• Release/acquire: a release store publishes every earlier write; an acquire load that reads the stored value sees them. Write data, then ready.store(true, release); a reader that sees ready through an acquire load can safely read data.
• Sequentially consistent: all such operations appear in one global order consistent with each thread's program order. It is the default for C++ atomics and the semantics of Java volatile, and the easiest to reason about, but it can require extra fences (even x86 needs one for a sequentially consistent store).
• Relaxed: atomicity only, suitable for statistics counters whose value does not guard other data.

Common misconceptions

• "if is fine if I only signal when the condition is true." Spurious wakeups and competing consumers make the while loop mandatory.
• "Reading a shared variable without the lock is safe." It is a data race; the compiler may cache the value and you may see stale or torn data.
• "Atomic variables make my operation atomic." Each operation is atomic; check-then-act across two of them is still a race.
• "volatile makes C or C++ code thread-safe." It provides neither atomicity nor inter-thread ordering; Java's volatile is a different, stronger concept.
• "x86 is sequentially consistent, so ordering does not matter." x86 allows store-to-load reordering, and the compiler reorders regardless; portable code must follow the language memory model.
• "A semaphore is just a mutex." It has no owner and counts, which suits signaling and resource limits rather than protecting invariants with clear ownership.

How to approach it

Solve each coordination problem twice, once with a mutex and condition variables and once with semaphores, and explain why every wait sits in a loop. Then write the message-passing example with release/acquire and explain what relaxed ordering would allow. Graduate interviews look for correct waiting without busy loops; mid-level ones for clean producer/consumer designs and awareness of contention; senior and low-level ones for memory-order reasoning and lock implementation tradeoffs.