9.5.2 — The Synchronization Toolbox

The warehouse service has one job that keeps going wrong. When an order is picked, it decrements stock for each item and writes a pick record. Under load, stock numbers drift below zero, and the nightly count never matches.

class StockService {
  async pick(sku: Sku, qty: number): Promise<void> {
    const level = await this.repo.getLevel(sku);      // read
    if (level.onHand < qty) throw new OutOfStock(sku);
    await this.repo.setLevel(sku, level.onHand - qty); // write
    await this.repo.recordPick(sku, qty);
  }
}

This is the check-then-act shape from 9.5.1, and you already know the strongest fix is to make the decrement a single conditional write in the database. But suppose you cannot. Suppose onHand is derived from three tables, or the stock lives in a legacy system reachable only through a slow API that offers no atomic operation. Now you genuinely need to stop two pickers from being inside that function at the same time for the same SKU.

That is what this page is for. Every tool here answers one of two questions: how do I let only some threads through at a time, or how do I make one thread wait until another says it is safe to continue. Everything else is a variation.

1. The mutex: one at a time

A mutex, short for mutual exclusion, is the simplest tool. It has two operations, lock and unlock, and one rule: at most one thread can hold it. Anyone else who calls lock waits until the holder calls unlock.

Figure 1 — A mutex is a door with one key. The waiting threads are BLOCKED, so they cost memory and no CPU. The queue is what makes the wait orderly rather than a scramble.

Two properties are worth naming because interviewers ask about them.

A mutex has an owner. The thread that locked it is the only one allowed to unlock it. This sounds like a technicality and it is actually the main thing separating a mutex from a semaphore, which we get to next.

A mutex is usually not reentrant by default. If a thread that already holds the lock tries to lock it again, in most implementations it waits for itself forever. That sounds like an absurd mistake to make, but it happens constantly through indirection: pick() takes the lock and calls adjust(), and six months later somebody adds a lock to adjust() too. A reentrant mutex, sometimes called a recursive mutex, remembers its owner and a count, so the same thread may lock it repeatedly and must unlock the same number of times. Java's synchronized and ReentrantLock are reentrant. Most C++ and Rust mutexes are not, deliberately, on the argument that needing reentrancy is a sign your critical section is too large.

Writing one you can actually use in Node

JavaScript has no threads sharing objects, so it ships no mutex. But it very much has the await-gap race from 9.5.1, so a mutex over asynchronous sections is genuinely useful. Here is the whole thing:

class Mutex {
  #locked = false;                                        // (1)
  #waiting: Array<() => void> = [];                       // (2)

  async acquire(): Promise<void> {
    if (!this.#locked) {                                  // (3)
      this.#locked = true;
      return;
    }
    await new Promise<void>(resolve => this.#waiting.push(resolve));  // (4)
  }

  release(): void {
    const next = this.#waiting.shift();                   // (5)
    if (next) next();                                     // (6) hand ownership straight over
    else this.#locked = false;                            // (7) nobody waiting: door open
  }

  async withLock<T>(fn: () => Promise<T>): Promise<T> {   // (8)
    await this.acquire();
    try {
      return await fn();
    } finally {
      this.release();                                     // (9)
    }
  }
}

(1) One boolean is the entire state of the lock: is somebody inside?

(2) The waiting list holds resolve functions. Each parked caller left behind the switch that will wake it up. This is the deferred trick: create a promise, keep its resolver somewhere, and call the resolver later from completely different code.

(3) The fast path. If nobody holds the lock, take it and return immediately. Note that this returns without ever awaiting, which matters: an uncontended acquire costs nothing.

(4) The slow path. Create a promise that will never settle on its own, push its resolver onto the queue, and await it. The caller is now parked. It consumes no CPU and will resume only when somebody calls that resolver.

(5) On release, look for a waiter.

(6) If there is one, wake it and do not clear #locked. Ownership passes directly from the leaver to the next in line. If you cleared the flag first, a brand-new caller could arrive on the fast path at (3) and jump the entire queue.

(7) Only when nobody is waiting does the lock actually become free.

(8) withLock is the only method you should ever call from application code.

(9) The finally is the reason. If the work throws, the lock still gets released. A lock released only on the success path is a bug that lies dormant until the first exception, at which point the service wedges permanently and needs a restart. Every review of concurrency code should check this line first.

Applied to the warehouse:

class StockService {
  #locks = new Map<Sku, Mutex>();                        // (1) one lock PER SKU

  #lockFor(sku: Sku): Mutex {
    let m = this.#locks.get(sku);
    if (!m) { m = new Mutex(); this.#locks.set(sku, m); }  // (2)
    return m;
  }

  async pick(sku: Sku, qty: number): Promise<void> {
    await this.#lockFor(sku).withLock(async () => {        // (3)
      const level = await this.repo.getLevel(sku);
      if (level.onHand < qty) throw new OutOfStock(sku);
      await this.repo.setLevel(sku, level.onHand - qty);
      await this.repo.recordPick(sku, qty);
    });
  }
}

(1) One lock for the whole service would serialise every pick in the warehouse, including two pickers working on completely unrelated products. One lock per SKU means two pickers only wait when they are actually competing for the same item. This choice is called lock granularity, and section 7 is about how to pick it.

(2) Creating the lock lazily is fine here because Node runs this synchronously — there is no await between the get and the set, so no other request can interleave. In a threaded language, this exact if (!m) is itself a check-then-act race and would need a concurrent map's computeIfAbsent.

(3) Everything between the braces now runs for one SKU at a time.

And the honest limitation, which you must say out loud before anyone asks: this lock lives in one process's memory. Run two copies of the service and each has its own map of mutexes, so the two copies can be inside the critical section for the same SKU at the same moment. A process-local lock is a fairness and load tool at scale, and a correctness tool only in a single-process deployment. Correctness for real belongs at the database (9.5.1 section 6) or in a distributed lock service, which comes with its own long list of caveats covered in 10.7.2.

Try-lock and timed lock

Plain lock waits as long as it takes. Two variants let you decide otherwise.

tryLock takes the lock if it is free and returns false immediately if it is not. Use it when there is something better to do than wait: skip an optional refresh, return a cached answer, or tell the user the record is being edited by someone else.

tryLockFor(timeout) waits, but gives up after a while. This is the one that saves you in production. A lock with no timeout turns any slow holder into an unbounded queue of waiters, and then into an out-of-memory crash. A timeout converts a deadlock or a stuck holder from a total outage into a stream of clean, visible errors:

async acquireWithTimeout(ms: number): Promise<boolean> {
  if (!this.#locked) { this.#locked = true; return true; }
  return new Promise<boolean>(resolve => {
    const entry = () => { clearTimeout(timer); resolve(true); };   // (1)
    this.#waiting.push(entry);
    const timer = setTimeout(() => {                                // (2)
      const i = this.#waiting.indexOf(entry);
      if (i >= 0) this.#waiting.splice(i, 1);                       // (3) leave the queue
      resolve(false);
    }, ms);
  });
}

(1) If we get the lock first, cancel the timer. (2) If the timer wins, we give up. (3) And we must remove ourselves from the queue before resolving false, or the eventual release() will hand the lock to a caller that walked away — and then nobody will ever release it. That line is easy to forget and produces a lock that leaks one slot per timeout until the service wedges.

2. The semaphore: N at a time

A semaphore holds a count of permits. acquire takes one, waiting if none are left. release gives one back. If the count starts at 1, it behaves almost like a mutex. If it starts at 10, it lets ten threads through at once.

The difference from a mutex is not just the count:

	Mutex	Semaphore
How many inside	Exactly one	Up to N
Owner	The locker must unlock	Any thread may release
Typical use	Protect data	Limit a resource, or signal

That middle row is the important one. Because a semaphore has no owner, thread A can acquire and thread B can release. That is not sloppiness; it is a whole second use. It lets a semaphore be a signal between threads rather than a guard around data: a worker waits on a semaphore with zero permits, and whoever finishes the prerequisite work releases one, waking it.

So a semaphore has two jobs, and calling out which one you mean is good practice:

Job one, limiting a resource. You have 20 database connections, or a partner API that allows 5 concurrent calls, or enough memory for 4 image resizes at once. A semaphore sized to the real limit is the direct expression of that constraint.

Job two, signalling. One thread needs to tell another that something has happened. Start at zero permits so the waiter blocks immediately, and release when the event occurs.

class Semaphore {
  #permits: number;
  #waiting: Array<() => void> = [];
  constructor(permits: number) { this.#permits = permits; }

  async acquire(): Promise<void> {
    if (this.#permits > 0) { this.#permits--; return; }             // (1)
    await new Promise<void>(resolve => this.#waiting.push(resolve)); // (2)
  }

  release(): void {
    const next = this.#waiting.shift();
    if (next) next();                                                // (3) permit handed over
    else this.#permits++;                                            // (4)
  }
}

const partnerApi = new Semaphore(5);            // the partner allows 5 concurrent calls
async function callPartner(req: Request): Promise<Response> {
  await partnerApi.acquire();
  try { return await http.post(PARTNER_URL, req); }
  finally { partnerApi.release(); }             // (5)
}

(1) and (2) are the mutex's two paths with a count instead of a boolean. (3) hands the permit directly to a waiter rather than incrementing and letting a newcomer steal it. (4) only a permit nobody wants goes back on the shelf. (5) the same finally rule as before, for the same reason, and here the consequence of forgetting is that your allowance of 5 shrinks to 4, then 3, then 0 — a slow strangling that looks like the partner getting slower rather than like a bug in your code.

A warning that costs teams real money: limiting concurrency is not the same as limiting rate. A semaphore of 5 lets 5 calls run at once; if each takes 10 ms, that is 500 calls per second, which will get you rate-limited by a partner who allows 50. Concurrency limits protect your resources — sockets, memory, connections. Rate limits protect someone else's, and they need a token bucket, which is a different tool built in 9.7.5. Systems often need both, and confusing them is a standard interview probe.

3. Condition variables: waiting for something to become true

A mutex answers "may I go in?" A condition variable answers a different question: "I am in, but the thing I need has not happened yet — how do I wait without holding the door shut?"

The problem is real. A consumer holds the lock on a queue, finds the queue empty, and needs to wait for an item. If it just waits while holding the lock, no producer can ever get in to add one, and the program is stuck forever. What is needed is an atomic "release the lock and go to sleep", so there is no instant where the consumer is asleep and holding the lock.

That is exactly what a condition variable does. It has three operations:

• wait() — atomically release the lock and sleep. On waking, re-acquire the lock before returning.
• signal() — wake one sleeper.
• broadcast() — wake all sleepers.

And there is one rule that people get wrong so often it is worth putting on its own line:

Always wait in a while loop, never in an if.

// WRONG                                    // RIGHT
await mutex.acquire();                      await mutex.acquire();
if (queue.length === 0) {                   while (queue.length === 0) {   
  await notEmpty.wait();                      await notEmpty.wait();
}                                           }
const item = queue.shift();                 const item = queue.shift();
mutex.release();                            mutex.release();

There are two independent reasons the while is required, and knowing both is a genuine signal of experience.

Reason one: somebody may take it before you do. signal() wakes you, but waking is not the same as running. You become RUNNABLE and go into the scheduler's queue. Another thread that was not asleep at all can walk in, take the lock, and grab the item you were woken for. When you finally get the lock, the queue is empty again. With if, you proceed to queue.shift() on an empty queue and get undefined. With while, you check again, find it empty, and go back to sleep. This is called a spurious wakeup when it comes from the operating system waking you for no reason at all, which POSIX explicitly permits, and it is called a stolen wakeup when another thread beat you to it. The while handles both.

Reason two: broadcast wakes everyone. If ten consumers are asleep and one item arrives, broadcast wakes all ten. Exactly one can have the item. The other nine must discover that and go back to sleep, which only the loop does.

There is a matching hazard on the signalling side, the lost wakeup. If a producer signals at a moment when the consumer has checked the condition but has not yet started waiting, the signal hits nobody and evaporates, and the consumer sleeps forever even though an item is sitting there. The cure is to hold the mutex while you change the condition and signal, so the check-then-wait on the consumer side cannot interleave with the change-then-signal on the producer side. This is why condition variables are always paired with a mutex rather than being usable alone, and why every textbook signature is wait(mutex) rather than just wait().

The pattern to memorise, because it is the same six lines in every language:

// consumer                                    // producer
await lock.acquire();                          await lock.acquire();
while (!conditionIsTrue()) {                   makeConditionTrue();
  await cond.wait(lock);                       cond.signal();
}                                              lock.release();
useTheThing();
lock.release();

In Node you will rarely write this by hand, because a promise is a condition variable with a much nicer interface: awaiting a promise is "sleep until somebody says so", and resolving it is signal. The parked resolvers in the Mutex above are the same idea. But you should still recognise the shape, because wait in a while loop is one of the most reliable interview questions in this entire area.

4. Read-write locks: many readers, one writer

Most shared data is read far more often than it is written. A price table, a routing configuration, a permissions map. Serialising a thousand readers behind a mutex when none of them modify anything is pure waste, because two readers can never conflict.

A read-write lock has two modes. Any number of readers may hold it at once. A writer needs it exclusively, and waits for all current readers to leave.

const rw = new ReadWriteLock();

async function priceOf(sku: Sku): Promise<Money> {
  return rw.read(async () => table.get(sku)!);     // many of these run together
}

async function reloadPrices(next: PriceTable): Promise<void> {
  return rw.write(async () => { table = next; });  // this one runs alone
}

It looks like free performance and it is not, for three reasons you should be able to state before proposing one.

It is more expensive than a mutex when uncontended. The lock has to track a reader count as well as a writer flag, and both have to be updated atomically. For short critical sections the bookkeeping can cost more than the exclusion it replaces. The rule of thumb: a read-write lock pays off when reads greatly outnumber writes and the critical section is long enough for the overhead to disappear into it.

Writers can starve. If readers keep arriving and the lock lets them in whenever no writer is currently active, a steady stream of readers means the writer waits forever. Implementations solve this by making the lock write-preferring: once a writer is waiting, new readers queue behind it. Ask which behaviour yours has, because a read-preferring lock under read-heavy load is a config reload that never happens.

Upgrading is a deadlock trap. Taking a read lock, discovering you need to write, and trying to upgrade to the write lock without releasing the read lock is a classic. Two threads both holding read locks both try to upgrade, and each waits for the other to release its read lock. Most libraries simply forbid upgrading. If you need it, release, re-acquire in write mode, and re-check your assumption, because the world changed while you held nothing.

And the alternative that is usually better: if the data is replaced wholesale rather than edited in place — which is true of price tables, config, and routing maps — you do not need a lock at all. Build the new table off to the side and swap the reference in one assignment. Readers either see the old complete table or the new complete table, never a half-built one. This is copy-on-write, it makes reads completely free, and it is why immutability keeps showing up as the cheapest concurrency tool available.

5. Atomics and compare-and-swap: the thing all of them are built from

Every primitive above is built on a hardware instruction. A CPU that could only read and write memory could not build a mutex, because taking a lock is itself a check-then-act. What the hardware provides is a small set of atomic read-modify-write instructions that cannot be interleaved.

The most important is compare-and-swap, usually written CAS. Its meaning in one line: if this memory location still holds the value I expect, replace it with this new value, and tell me whether that worked. The comparison and the write are one indivisible instruction, guaranteed by the CPU.

In pseudocode, executed atomically:

function compareAndSwap(cell, expected, next): boolean {
  if (cell.value === expected) { cell.value = next; return true; }
  return false;                       // somebody changed it since you read it
}

From that one primitive you get everything. A lock is compareAndSwap(lockCell, UNLOCKED, LOCKED) in a loop. An atomic counter is a loop that reads, adds one, and swaps, retrying if somebody else got there first:

function atomicIncrement(cell: Cell): number {
  while (true) {                                     // (1)
    const current = cell.value;                      // (2) read
    const next = current + 1;                        // (3) compute
    if (compareAndSwap(cell, current, next)) {       // (4) publish, only if unchanged
      return next;
    }
    // (5) somebody else won; loop and try again with their value
  }
}

(1) The retry loop is the shape of every lock-free algorithm. (2)–(3) do the work optimistically, assuming no conflict. (4) is the one atomic step, which publishes the result only if nothing changed underneath you. (5) if it did change, you throw away your computed value and start over from the new one. Nothing is corrupted, because the swap either happened completely or not at all.

Two consequences worth understanding.

This is optimistic concurrency, and you have already met it. The retry-on-conflict shape is identical to an HTTP If-Match with an ETag (9.6.3) and to a database UPDATE ... WHERE version = 17. The version number is the "expected" value, and the 412 or the zero-rows-affected is the failed swap. Same idea at three wildly different scales, which is a connection worth making out loud in an interview.

Lock-free does not mean fast. It means no thread being descheduled can block the others, because there is no lock to be holding. Under heavy contention a CAS loop can spin many times, burning CPU, and can perform worse than a lock that puts waiters cleanly to sleep. Lock-free wins for very short operations under moderate contention. It loses for long critical sections.

The ABA problem, which interviewers love because it sounds impossible. CAS checks the value, not the history. If a thread reads A, gets descheduled while another thread changes the value to B and then back to A, the first thread's CAS succeeds even though the world it assumed no longer exists. For a plain counter this is harmless, since one value of an integer is as good as another. For a pointer it is a catastrophe: the A you are swapping in may be a node that has since been freed and reused. The standard cure is to tag the value with a counter that only ever increases, so what you compare is the pair (value, version) and a return trip to A is visible as (A, 7) versus (A, 5). Once again, that is a version number solving a concurrency problem.

6. What to hold a lock across, and what never to

A short list, and every item on it has cost somebody an outage.

Hold a lock for the shortest time that keeps the invariant. Everything that does not touch the shared state should happen outside. Compute first, then take the lock, then write, then release.

Never hold a lock across I/O. This is the big one. A lock held while you call an HTTP API means your critical section is now as long as somebody else's slowest response — and if their service hangs, your queue of waiters grows until you run out of memory. If you truly must, use a timed lock, and set the timeout below the point where the queue becomes fatal.

Never call unknown code while holding a lock. A callback, an event handler, a plugin, an overridden method. That code may take another lock, or call back into your object and try to take the same one. This is where deadlocks are born, and it is the subject of 9.5.3.

Always release in a finally. Said three times on this page, deliberately.

Do not make the lock public. A lock exposed as a public field is a lock that other people will take, in an order you cannot see, which is how deadlocks acquire a second participant. Keep it private and expose a withLock-style method instead.

7. Granularity: how much should one lock protect?

This is the design decision that separates a system that scales from one that does not, and there is a genuine trade-off with no universally right answer.

Coarse-grained means few locks, each protecting a lot. One lock for the whole warehouse. It is easy to reason about, it is nearly impossible to deadlock because there is only one lock to take, and it is trivially correct. It is also a bottleneck: every operation on anything waits behind every other.

Fine-grained means many locks, each protecting a little. One lock per SKU. Two pickers on different products never wait for each other, so throughput scales with the number of distinct items. But now an operation touching two SKUs must take two locks, and the moment you take two locks you have invented the possibility of deadlock.

The middle position that most real systems land on is lock striping: a fixed number of locks, say 16, with each key hashed to one of them. Two random keys usually get different locks, so you keep most of the concurrency, and the number of locks stays small and bounded so you never accumulate a lock object per key forever.

class StripedLocks {
  #stripes: Mutex[];
  constructor(count = 16) {
    this.#stripes = Array.from({ length: count }, () => new Mutex());   // (1)
  }
  for(key: string): Mutex {
    return this.#stripes[hash(key) % this.#stripes.length];             // (2)
  }
}

(1) A fixed set of locks, created once. (2) The key picks one by hash. Two different SKUs occasionally collide onto the same stripe and wait for each other unnecessarily, which is a small and bounded cost. In exchange, memory is fixed rather than growing with the number of keys ever seen — which is the actual bug in the per-SKU map from section 1, since that map never removes anything and grows forever in a long-lived process.

The practical way to choose: start coarse. A single lock is correct and simple, and correct-and-simple beats clever-and-broken by a wide margin. Split it only when a measurement shows contention on that lock is your bottleneck. Splitting locks without evidence buys you deadlock risk in exchange for throughput you did not need.

8. Choosing: the one-screen summary

You need	Use	Watch out for
One at a time	Mutex	Release in finally; keep it private
At most N at a time	Semaphore	Concurrency is not rate
Wait until a condition holds	Condition variable	while, never if
Many readers, rare writer	Read-write lock	Writer starvation; no upgrading
One tiny value updated often	Atomic + CAS	ABA; spinning under contention
Fixed rules, no waiting	Immutable value	Nothing — this is the free one
Per-entity ordering	One owner per key	Bounded mailbox

Read that table top to bottom and notice the shape of the advice. The tools get more powerful as you go up and safer as you go down. Reach downward first.

Next: 9.5.3 is about what happens when the tools on this page are used correctly and the program still stops forever.

Recall

• Mutex: one holder, owner must release, usually not reentrant. Always withLock with the release in a finally. A process-local mutex stops being a correctness tool the moment you run two replicas.
• Semaphore: N permits, no owner, so any thread may release — which makes it both a resource limiter and a signal. Concurrency limit ≠ rate limit.
• Condition variable: atomically release-and-sleep, then re-acquire on waking. Wait in a while loop because of spurious and stolen wakeups; signal while holding the mutex to avoid a lost wakeup.
• Read-write lock: many readers or one writer. Costs more uncontended, starves writers unless write-preferring, and upgrading deadlocks. Copy-on-write with a reference swap is often better.
• Compare-and-swap: if still the value I expect, replace it, as one hardware instruction. Every lock and atomic is built on it. Retry loop = optimistic concurrency = the same idea as an ETag or a version column. ABA: CAS compares values, not history — tag with a version.
• Never hold a lock across I/O or across a call into unknown code.
• Granularity: coarse is simple and a bottleneck; fine is fast and invites deadlock; striping is the bounded middle. Start coarse, split on evidence.

Self-test: What can a semaphore do that a mutex cannot, and why? Give both reasons the condition wait must be a while. What is a lost wakeup and what prevents it? Why does upgrading a read lock deadlock? Explain ABA and its cure. Why does a per-key lock map leak?

Quiz Bank

FoundationalWhat is the difference between a mutex and a binary semaphore, given that both allow one thread through at a time?

The count is the visible difference and the ownership is the real one.

A mutex has an owner. The thread that locked it is the only thread permitted to unlock it, and good implementations enforce that. This makes a mutex a statement about a critical section: I am inside, and I will come out.

A semaphore has no owner. Any thread may release a permit, including one that never acquired it. That is not an oversight, it is a second capability. It means a semaphore can carry a signal between two different threads: one waits on a semaphore that starts at zero permits, and a completely different thread releases one when the awaited work is done.

Three practical consequences follow.

Ownership enables reentrancy. Because a mutex knows who holds it, it can recognise a re-lock by the same thread and allow it with a count. A semaphore cannot, because it has no idea who you are.

Ownership enables priority inheritance. If a low-priority thread holds a mutex that a high-priority thread wants, the runtime can temporarily raise the holder's priority so it finishes and gets out of the way (2.3's priority inversion, the bug that nearly ended the Mars Pathfinder mission). A semaphore has nobody to promote.

Using a semaphore as a mutex loses the safety net. A binary semaphore protecting data works fine right up until somebody releases it twice by mistake, at which point the count becomes 2 and two threads are inside your critical section with no error reported anywhere. A mutex would have rejected the second unlock.

The short rule: mutex to protect data, semaphore to count a resource or to signal an event. Say the intent and the right tool is obvious.

FoundationalWhy must a condition variable wait always sit inside a while loop rather than an if?

Because being woken is not a promise that the condition is true. It is only a hint that it might be worth re-checking.

First reason, the stolen wakeup. signal() moves you from WAITING to RUNNABLE. Runnable is not running. Between the signal and the moment you actually get scheduled and re-acquire the mutex, any other thread may take the lock and consume the very thing you were woken for. You wake up, get the lock, and the queue is empty again. With an if, you fall straight through to queue.shift() and operate on nothing. With a while, you re-check, find it false, and go back to sleep, which is the correct behaviour.

Second reason, broadcast. broadcast() wakes every waiter. If ten consumers are asleep and one item arrives, all ten wake up, and nine of them must find the condition false and return to sleep. Only a loop does that.

Third reason, spurious wakeups. POSIX explicitly allows pthread_cond_wait to return without any signal having occurred, because permitting it makes the implementation dramatically faster on some platforms. Any code that assumes a wakeup implies a signal is wrong by specification, not merely unlucky.

The related hazard on the other side is the lost wakeup: the producer signals in the window after the consumer checked the condition but before it actually started waiting, so the signal hits an empty room and vanishes, and the consumer sleeps forever with work sitting right there. The cure is that the mutex must be held while you change the condition and signal it, which makes the consumer's check-then-wait and the producer's change-then-signal mutually exclusive. This is precisely why condition variables are always coupled to a mutex — the coupling is not bureaucracy, it is the thing that closes the window.

The rule in one line: the condition variable tells you when to look; the loop is what tells you whether it is true.

AppliedA team wraps every method of a shared cache in one mutex. Throughput collapses under load even though the cache is 99 percent reads. Diagnose it and give the fix, in order.

The diagnosis. A mutex is unconditionally exclusive. It does not know or care that a get only reads. So a thousand concurrent readers, none of whom conflict with each other in any way, are being processed strictly one at a time. The cache has been turned into a single-lane road, and worse, the lane is now the hottest object in the system, so every request in the service queues at the same point. Under load, the waiting queue grows faster than it drains, latency climbs, and each waiter is also occupying a thread or a request slot while it waits — so the collapse is nonlinear, not gradual.

Fix one, and try this before anything clever: make the value immutable and swap the reference. If the cache is refreshed as a whole — a price table, a config map, a routing table — then no lock is needed at all. Build the new map off to the side, and replace the reference in a single assignment. Every reader sees either the complete old map or the complete new one. Reads become as cheap as a field access, and the writer never blocks anyone. This is copy-on-write, and it removes the problem instead of managing it.

Fix two: a read-write lock. If entries genuinely have to be updated individually, this lets all readers in at once and only excludes them for the rare write. Two things to check before you propose it. It must be write-preferring, or a continuous stream of reads will starve the refresh forever. And it must be measured, because for very short critical sections the extra bookkeeping of a read-write lock can cost more than the exclusion it removes.

Fix three: shrink what the lock protects. Often the lock is being held far longer than necessary — across the expensive load that happens on a miss, for instance. Take the lock to read, release it, do the expensive work outside, then take it again to insert. That alone can move a system from serial to nearly parallel. Note the consequence you must handle: two threads can now miss simultaneously and both do the expensive load. If that is wasteful rather than wrong, accept it; if it must not happen, store an in-flight promise under the key so the second caller awaits the first caller's work (9.7.30 builds exactly this).

Fix four: stripe it. Sixteen locks, key hashed to one of them, so unrelated keys stop waiting for each other. This keeps memory fixed rather than growing a lock per key forever.

The ordering is the answer. Remove the need for the lock, then narrow what it covers, then split it. Every one of those is safer than the alternative of writing a cleverer lock, and the team's original mistake was reaching for the most exclusive tool by default rather than asking what actually conflicts with what.

InterviewExplain compare-and-swap, build an atomic counter from it, and say when a CAS loop is worse than a mutex.

What it is. Compare-and-swap is a single CPU instruction meaning: if this memory location still contains the value I expect, write this new value into it; either way tell me whether the write happened. The comparison and the write are indivisible — no other core can slip in between them. It is the primitive that makes multi-core programming possible at all, because a machine with only plain reads and writes cannot even implement a lock.

The counter.

function increment(cell: Cell): number {
  while (true) {
    const seen = cell.value;                          // read
    if (compareAndSwap(cell, seen, seen + 1)) {       // publish only if unchanged
      return seen + 1;
    }
    // lost the race: somebody incremented since our read. Loop with their value.
  }
}

The structure is: read a snapshot, compute a new value from it, and attempt to publish it conditionally on nothing having changed. When the attempt fails, no damage was done — the swap is all-or-nothing — so you simply discard your work and retry from the newer value. This is optimistic concurrency: assume no conflict, detect it if it happened, redo.

Why it is often better than a lock. No thread can block another by being descheduled at a bad moment, since there is no lock being held. A thread that is paused mid-loop simply retries later; everyone else keeps making progress. For a single counter or a single pointer swap, it is also much faster, because there is no queueing, no sleeping and no waking.

When it is worse, which is the part that shows real understanding.

Under heavy contention. Every failed attempt is wasted work, and with sixteen cores hammering one counter most attempts fail. You burn CPU spinning while achieving very little. A mutex would put the losers cleanly to sleep so the winner gets the whole core and finishes sooner. Counter-intuitively, a lock can beat lock-free at high contention precisely because it stops the losers from competing.

When the critical section is more than one word. CAS updates one location. Keeping two fields consistent with each other needs either a lock, or a redesign where the two fields live in one immutable object and you swap the pointer to it.

When retries are not free. The loop assumes recomputing is cheap. If the computation between the read and the swap is expensive, repeated failures can cost more than waiting would have.

And the trap to name unprompted: ABA. CAS compares values, not history. Read A, get descheduled while another thread makes it B and then A again, and your swap succeeds even though the state it assumed is gone. Harmless for an integer; disastrous for a pointer, where the reappeared A may be freed and reused memory. The standard cure is to CAS a (value, version) pair where the version only increments, so the round trip is visible. That is the same version-number trick as an ETag on an HTTP resource and a version column in a database row — one idea, three scales.

StaffA service holds a per-tenant lock while calling a downstream API. It runs fine for a year, then one tenant's downstream endpoint hangs and the entire service falls over, including for tenants that never touch that endpoint. Explain the chain, and redesign it.

The chain, link by link. The downstream call for tenant X stops responding, but the socket stays open, so nothing errors — the request simply never finishes. The thread or request holding tenant X's lock therefore never releases it. Every subsequent request for tenant X queues behind that lock, and the queue grows for as long as traffic continues.

Now the failure escapes tenant X, and this is the part teams do not anticipate. Each waiting request is not free. It occupies a request slot, an open socket to the caller, some memory, and in a threaded runtime an entire thread with its stack. When the shared pool of those things is exhausted, requests for every other tenant start failing too, because there is nothing left to serve them with. A single tenant's hang has become a total outage, and the mechanism was resource exhaustion rather than the lock itself.

There is usually a third link. The health check endpoint is served by the same pool, so it stops responding too. The orchestrator concludes the instance is unhealthy and restarts it. The restarted instance receives its share of the retry storm from every client that just got an error, and falls over faster than the original. Now the incident is self-sustaining.

The redesign, in the order the fixes should be applied.

First, remove the lock from the I/O path entirely. This is the root cause, and everything else is mitigation. A lock exists to protect state, and a downstream HTTP call is not your state. Restructure to: take the lock, read what you need, release; make the call with no lock held; take the lock again to apply the result. You must then handle the fact that the world may have changed while you held nothing — normally by making the final write conditional on the version you read, so a stale result is rejected rather than applied. That is optimistic concurrency replacing pessimistic locking, and it is the correct shape for any operation whose slow part is somebody else's system.

Second, put a timeout on every remote call. A call with no timeout is an unbounded commitment to another team's uptime. The value should be derived from your own latency budget, not from the downstream service's promises.

Third, make every lock acquisition timed. tryLockFor converts an unbounded queue into visible, countable, clean errors. An error you can see on a dashboard is enormously better than a queue you cannot.

Fourth, bulkhead the tenants. Give each tenant, or each stripe of tenants, its own bounded slice of the shared resources — a per-tenant concurrency semaphore in front of the handler (10.9). Now tenant X can consume its own slice and no more, so its failure is contained to itself by construction rather than by hope. Cap it well below the total, so no single tenant can ever exhaust the pool.

Fifth, add a circuit breaker per downstream endpoint. After N consecutive failures or timeouts, stop calling it and fail fast for a while. This stops you from queueing work for a service you already know is broken, and it gives that service room to recover instead of drowning it in retries.

Sixth, separate the health check. It must be served from a path that does not share the exhausted pool, or your orchestrator's restarts will make every incident worse.

The reviewable rule to leave the team with: a lock may be held across memory, never across a network. If you find yourself needing to, the design has put the guarantee in the wrong place, and the fix is a conditional write at the end rather than an exclusive hold throughout.

Flashcards

FlashMutex versus semaphore

Mutex: one holder, owner must release, supports reentrancy and priority inheritance, protects data. Semaphore: N permits, anyone may release, so it can also signal. Binary semaphore as a mutex silently allows a double release.

FlashCondition variable rules

wait atomically releases the lock and sleeps, re-acquires on wake. Always in a while — spurious and stolen wakeups. Signal while holding the mutex, or the wakeup is lost.

FlashCompare-and-swap in one line

If the location still holds what I read, write the new value; report whether it worked. Retry loop = optimistic concurrency. ABA: compare (value, version), not value alone.

FlashLock hygiene

Release in finally. Never across I/O. Never call unknown code while holding one. Keep it private. Prefer timed acquisition.

FlashGranularity ladder

Coarse = simple, bottleneck, no deadlock. Fine = fast, deadlock possible, lock objects can leak. Striped = fixed count, hash the key, bounded memory. Start coarse, split on measurement.

Scenario Drill

DrillDesign the concurrency control for a per-user wallet inside one service: deposits, withdrawals, and a transfer between two wallets. State every primitive you use and defend the granularity, then say what changes when the service runs on six instances.

Start by naming the contested resource. It is one wallet's balance. Two operations conflict only when they touch the same wallet, which immediately rules out a global lock: two unrelated users transacting are not in conflict, and serialising them would cap the whole service's throughput at one transaction at a time.

Deposits and withdrawals: one lock per wallet, or no lock at all. The invariant is that the balance never goes negative and no update is lost. The cheapest correct implementation is a conditional write with no lock in sight: UPDATE wallets SET balance = balance - ? WHERE user_id = ? AND balance >= ?, treating zero rows affected as "insufficient funds". The database is already good at exactly this, it holds for every writer including admin tools and future endpoints, and it does not care how many instances you run.

An in-process per-wallet mutex is then a supplement, not the guarantee. It is worth having when a single hot wallet — a merchant account receiving thousands of payments — would otherwise generate a stampede of conflicting writes and retries. Serialising per wallet in memory converts that stampede into an orderly line before it reaches the database. Say clearly which job each mechanism is doing, because a candidate who says "the lock is for load shaping and the conditional write is for correctness" has demonstrated the distinction that matters.

Granularity: per wallet, but stripe it. A Map<UserId, Mutex> that never removes entries grows forever in a long-running process, one small object per user who ever transacted. Sixteen or sixty-four striped locks with the user id hashed onto them keeps memory fixed and costs only the occasional unnecessary wait between two users who collide on a stripe, which is harmless.

The transfer is where it gets interesting, because it needs two wallets at once. The requirement is that money never appears or disappears: the debit and the credit must both happen or neither. Two hazards arrive together.

The first is atomicity, and the answer is a database transaction. Debit and credit in one transaction, so a crash between them cannot leave money in limbo.

The second is deadlock, and it is the reason this drill exists. If Alice sends to Bob at the same moment Bob sends to Alice, and each transaction locks the sender first, then Alice's transaction holds Alice's row and wants Bob's while Bob's holds Bob's and wants Alice's. Neither can proceed. This is a genuine, reproducible production deadlock that the database will eventually detect and resolve by killing one transaction.

The fix is a global ordering rule, and it is beautifully simple: always lock the two wallets in a fixed order, sorted by user id, regardless of which one is the sender. Now both transactions lock Alice first and then Bob, so one of them simply waits and both complete. This is the ordering discipline that 9.5.3 generalises, and it is the single most useful deadlock cure in existence.

const [first, second] = [fromId, toId].sort();          // (1) fixed order, always
await db.transaction(async tx => {                       // (2) both or neither
  await tx.lockWallet(first);                            // (3)
  await tx.lockWallet(second);
  const ok = await tx.debit(fromId, amount);             // (4) still conditional
  if (!ok) throw new InsufficientFunds(fromId);
  await tx.credit(toId, amount);
});

(1) removes the deadlock by construction. (2) removes the half-completed transfer. (3) locks in the sorted order even though the business operation has a direction. (4) the balance check stays conditional inside the transaction, because the lock and the invariant are separate concerns and you want the invariant enforced even if somebody later removes the lock.

Also worth stating: transfers must be idempotent. The client will retry on a timeout, and a retry must not move the money twice. A unique constraint on a client-supplied transfer id makes the second attempt fail at insert time, which is a correctness guarantee that survives every retry, every restart, and every future code path (9.6.3).

What changes at six instances. Everything that lives in process memory stops being a guarantee. Six copies of the striped mutex array mean six wallets can be "exclusively" held simultaneously. Three consequences follow.

The conditional writes and the unique constraint keep working unchanged, because they live in the database — which is exactly why the design put correctness there. The in-process locks degrade gracefully from a guarantee to an optimisation: they still reduce contention within each instance, which is still useful, just no longer sufficient on its own. And the lock-ordering rule keeps working, because the ordering is applied to the database row locks inside the transaction, and the database has one view of those regardless of how many application instances exist.

If you later find you need genuine cross-instance exclusion — for something that cannot be expressed as a conditional write, such as "only one instance may run this reconciliation job" — that is a distributed lock, and it brings a completely different failure model: a lock holder can pause for a garbage collection, lose its lease, and continue working while somebody else holds the lock. That problem, and the fencing token that solves it, is 10.7.2. Naming that difference before the interviewer does is the strongest possible ending to this answer.