Classic synchronization problems

Why it matters

Every queue, cache and resource pool is a textbook problem in production clothes. A Kafka consumer reading a partition is the bounded buffer; a feature-flag cache reloaded once a minute is readers-writers; a transfer locking two account rows is two dining philosophers; a thread pool parking idle workers is the sleeping barber. Interviewers use them because they expose the race, the deadlock and the starvation in five minutes.

The idea

Bounded-buffer producer-consumer

Producers put items into a buffer of capacity N and consumers take them out; nobody may put into a full buffer, take from an empty one, or touch it concurrently. Three semaphores solve it: empty (starts at N) counts free slots, full (starts at 0) counts items, mutex guards the buffer.

empty = N, full = 0, mutex = 1
producer:                 consumer:
  wait(empty)               wait(full)
  wait(mutex)               wait(mutex)
  put(item)                 item = take()
  signal(mutex)             signal(mutex)
  signal(full)              signal(empty)

The order of the two waits is the whole exam. Take mutex before empty and a producer facing a full buffer sleeps holding the mutex; the consumer that would free a slot cannot get in, and both wait for ever. The Monitors and condition variables lesson builds the same buffer with one mutex and two condition variables; the contrast is that a semaphore remembers signals as a count and a condition variable remembers nothing, so the monitor version must re-check in a loop. Every blocking queue, Go channel and Linux pipe is this buffer, and its gift is backpressure: a slow consumer slows the producer instead of growing memory.

Readers-writers

Many readers may read shared data together; a writer needs it alone. The first readers-writers solution gives readers preference: a readcount under a mutex, and a wrt semaphore that the first reader in takes and the last reader out releases, while a writer takes wrt directly. No reader waits unless a writer already holds the data, so a stream of readers keeps a writer out indefinitely: writer starvation. The second solution gives writers preference: once a writer is waiting, new readers queue behind it, and now readers can starve. The Mutexes and semaphores lesson warned about starvation; the other surprise is that rwlocks are often slower than a mutex. Every reader updates the shared count atomically, so that cache line bounces between every reading core; if a read takes 200 ns, the bookkeeping costs as much as the work. Rwlocks pay off when reads are long and writes rare; for short reads a mutex wins, and an immutable copy swapped by pointer (copy-on-write, RCU in the kernel) wins by more, because readers write nothing.

Dining philosophers

Five philosophers share five forks, one between each pair, and each needs both neighbouring forks to eat. If everyone picks up the left fork and then reaches for the right, all five hold one and wait for another: a circular wait, the textbook deadlock.

1. 1

   Order the resources

   Number the forks and always take the lower number first; the philosopher between forks 5 and 1 now reaches for 1 first and the cycle cannot close. This is global lock ordering, why a transfer locks account rows in ascending id order.
2. 2

   Add an arbitrator

   A waiter admits at most four to the table (a semaphore of N minus 1) or grants both forks atomically. A lock manager or transaction coordinator is the waiter: simple, and serialised on one point.
3. 3

   Chandy-Misra

   Forks are clean or dirty; a hungry philosopher requests the forks it lacks, and a holder yields a fork only if it is dirty, cleaning it first. No central party, deadlock-free and starvation-free, the basis of distributed resource allocation.

The sleeping barber

A barber sleeps when the shop is empty; a customer wakes him, waits in one of N chairs, or leaves if they are full. Semaphores customers and barber plus a mutex over the chair count solve it; the lesson is the race: if the barber checks for customers and then sleeps as two steps, a customer arriving between them waits for a barber who never wakes, the lost wakeup from the Monitors and condition variables lesson. The shop is a thread pool: parked workers, a bounded queue, rejection when full.

Trade-offs

Semaphore solutions are compact and brittle: swap two waits and you deadlock, miss a signal on an error path and the count drifts for ever. Monitors are harder to get wrong. Reader preference maximises read throughput and lets data go stale; writer preference keeps data fresh and makes readers wait. Lock ordering is free at runtime and demands that every caller know the order; an arbitrator is easy to reason about and one more thing to scale; Chandy-Misra needs no centre and pays in messages.

In an interview

Name the problem, then the real system: "A connection pool is the bounded buffer; the semaphore of 20 permits is empty, and callers that cannot get one within 100 ms fail fast instead of queuing without limit." For caches: "The routing table is read ten thousand times a second and reloaded once a minute, so we publish a new immutable table and swap a pointer; readers never lock."