Synchronization: Mutex, Semaphore & Spinlock

1. What is a race condition?

A race condition is when the outcome of concurrent execution depends on the timing or interleaving of threads. The classic example is two threads incrementing a shared counter: counter++ is not atomic — it is a read, an increment, and a write. Thread A reads 5, Thread B reads 5, both write 6 — one increment is lost, and the final value is 6 instead of 7.

The danger is that the code looks correct in isolation but produces wrong, non-deterministic results depending on scheduling. Any access to shared state that isn’t synchronized is a potential race.

2. What is a critical section and what are the three requirements for a solution?

A critical section is a piece of code that accesses shared resources — variables, files, or data structures — that must not be entered by two threads simultaneously. The critical section problem is to guarantee that when one thread is inside its critical section, no other thread is inside its critical section for the same resource.

Any correct solution must satisfy three requirements:

• Mutual exclusion — only one process can be in its critical section at a time.
• Progress — if no process is in its critical section, a waiting process must be able to enter without indefinite delay; a process that isn’t in its critical section must not block others.
• Bounded waiting — a process shouldn’t wait forever; there is a limit on how many times others can enter ahead of it.

All three must hold for a correct solution.

3. What is a mutex and how does it work?

A mutex (mutual exclusion lock) is a locking mechanism that ensures only one thread can access a resource at a time. It has a binary state — locked or unlocked — and enforces ownership: the thread that locks a mutex must be the one to unlock it.

The thread that can’t acquire a mutex sleeps (yields the CPU) rather than busy-waiting, which makes it efficient under contention. The typical use is protecting a shared data structure — a linked list or hash table — from concurrent modification. Unlocking from a different thread is undefined behavior on most implementations, typically a crash or deadlock, which is exactly why ownership is enforced.

4. What is a semaphore?

A semaphore is an integer with two atomic operations: wait() (P, decrement — block if the value is 0) and signal() (V, increment — wake a blocked thread). Unlike a mutex, it has no ownership: any thread can signal a semaphore, not just the one that waited on it.

There are two kinds. A binary semaphore ranges over 0 and 1 and is used for signaling between threads. A counting semaphore ranges from 0 to N and is used to manage a pool of identical resources — for example, controlling access to N database connections or N buffer slots. A semaphore is a signaling mechanism; a mutex is an ownership mechanism.

5. What’s the difference between a mutex and a binary semaphore?

The critical difference is ownership. A mutex must be unlocked by the same thread that locked it; a binary semaphore can be signaled by any thread. Mutexes are for mutual exclusion; semaphores are for signaling.

A mutex also typically supports priority inheritance and recursive locking (the same thread can lock again), while semaphores do not. You should not safely use a binary semaphore as a mutex — without ownership tracking, a thread can accidentally signal on behalf of another, leading to race conditions. The analogy interviewers like: a mutex is a locked room with one key; a semaphore is a parking lot with N spaces.

6. When would you use a counting semaphore instead of a mutex?

When you have multiple identical resources to manage: a pool of N database connections, N buffer slots, or N printers. A mutex only allows one thread in at a time; a counting semaphore initialized to N allows up to N threads to hold a slot simultaneously.

Each thread does wait() before using a resource and signal() after. The counter tracks how many slots are free, so the limit is enforced by the kernel/primitive itself rather than by application logic.

7. What is a spinlock and when is it better than a mutex?

A spinlock makes the waiting thread busy-wait — it spins in a loop checking the lock instead of sleeping. The CPU is burned the entire time, but the latency when the lock is released is immediate because the waiter is already running.

Use a spinlock when the critical section is very short (under ~100 CPU cycles, shorter than a context switch), when you’re in an interrupt handler or atomic context where sleeping is illegal, and when you have multiple CPU cores. A spinlock on a single-core CPU is a deadlock — the lock holder can’t yield the CPU if the spinner never yields. For long critical sections, I/O waits, or high contention, use a mutex, which sleeps and lets other threads run.

8. Why is a spinlock bad on a single-core CPU?

If the thread holding the lock is the only thread that can release it, and it’s been preempted or hasn’t run, the spinning thread will spin forever — it can never make progress. On a single core, only one thread runs at a time, so a spinner starves the holder.

The fix is to use a mutex (which sleeps and lets other threads, including the lock holder, be scheduled) or to disable preemption around the critical section. That’s why the Linux decision tree says: single-core CPU → disable preemption; spinlocks are pointless there.

9. What is busy-waiting and when is it acceptable?

Busy-waiting is when a thread keeps executing — checking the lock in a loop — without making progress or yielding the CPU. It wastes CPU cycles doing nothing useful.

It’s acceptable only when the wait is guaranteed to be extremely short: shorter than a context switch would cost. That’s the spinlock trade-off — spinning wastes CPU but avoids the scheduler overhead of sleeping and waking. Linux bridges the gap with an adaptive mutex: it spins for a short while, and only if the lock isn’t released quickly does it sleep.

10. What is an atomic operation?

An atomic operation appears to execute in a single indivisible step from the perspective of other threads — no thread can observe it partially complete. The hardware guarantees this at the instruction level (for example, cmpxchg or __sync_fetch_and_add on x86).

Atomic operations are the foundation for all synchronization primitives. Instead of counter++ (three non-atomic steps), an atomic increment like __sync_fetch_and_add(&counter, 1) guarantees the final value is correct even under contention, without any lock.

11. How does Compare-and-Swap (CAS) work?

CAS(address, expected, new) checks whether *address == expected; if so, it sets *address = new and returns true, otherwise it returns false. The check-and-set is atomic — no other thread can interleave between the comparison and the store.

The key property is that CAS succeeds only if the memory hasn’t changed since you last read it. If another thread modified it, CAS fails and you retry in a loop. That’s how lock-free increments work: read the old value, compute the new one, attempt CAS, retry on failure — no lock needed, just a loop.

12. What is the ABA problem and how is it solved?

The ABA problem: CAS can’t detect if a value changed from A to B and back to A. Thread 1 reads value A. Thread 2 changes it to B and back to A (the structure changed — e.g., a freed node was reused). Thread 1’s CAS succeeds because it compares against A, but the underlying state is not what it expects.

It is solved with tagged pointers — add a version counter to the pointer so each modification bumps the tag and A-with-tag-1 differs from A-with-tag-2 — or by using Load-Linked/Store-Conditional (LL/SC) instructions, which detect any intervening modification rather than comparing values.

13. What is lock-free programming and why use it?

Lock-free programming uses atomic operations (CAS, fetch-and-add) instead of locks to synchronize shared data. No thread can block another — progress is guaranteed even if a thread is suspended in the middle of an operation.

It eliminates deadlocks, priority inversion, and lock contention entirely. The cost is that it’s much harder to write correctly: you must reason about retry loops, the ABA problem, and memory ordering. A data structure built this way is called lock-free if at least one thread always makes progress.

14. What is a monitor?

A monitor is a high-level synchronization construct that encapsulates shared data together with the procedures that operate on it. Only one thread can be active inside a monitor at a time — mutual exclusion is automatic. Java’s synchronized is the canonical example.

Monitors use condition variables for signaling: a thread that can’t proceed does wait(), releasing the monitor lock; another thread does signal() when the condition might be satisfied. This gives the safety of a lock with a structured way to wait for a predicate, which raw mutexes don’t provide.

15. What is Peterson’s algorithm?

Peterson’s algorithm is a software-only solution to the two-process critical-section problem — it needs no hardware support, just shared variables. Two processes share two flags and a turn variable:

// shared
int flag[2] = {0, 0};
int turn;

// process P_i (i = 0 or 1)
flag[i] = 1;
turn = 1 - i;
while (flag[1 - i] && turn == 1 - i);  // busy wait
// critical section
flag[i] = 0;                            // exit

The idea: a process declares it wants in (flag[i] = 1), then graciously yields by setting turn to the other process. It waits only if the other process also wants in and it’s the other’s turn. Because turn can only be one value at a time, only one process can pass the while at once.

It satisfies all three requirements — mutual exclusion (only one passes), progress (a waiting process isn’t blocked forever), and bounded waiting. Its limitation: it only works for two processes and still uses busy waiting, so modern systems prefer hardware primitives like test-and-set or CAS.