Classic Synchronization Problems

When people first learn locks and semaphores, they can explain each primitive perfectly and still write broken concurrent code. The reason is that correctness lives in the interleavings — the astronomically many orders in which threads can run — and you cannot hold all of them in your head. What you can do is learn a small library of coordination patterns so thoroughly that when a real problem arrives, you match it to a pattern you already trust, and reuse a solution whose corner cases someone else already suffered through.

These three problems earned their place because between them they cover an enormous fraction of real coordination. They are famous partly because Edsger Dijkstra and Tony Hoare used them decades ago to test the very primitives you now use, but they survive because the shapes are timeless. If you can solve these three cleanly, you can reason about most of the concurrency you will meet in production.

Producer–Consumer

Threads that create work hand it to threads that process it, through a shared buffer of bounded size. The shape behind every queue and pipeline.

Readers–Writers

Many threads may safely read shared data at once, but a writer needs exclusive access. The shape behind caches, config, and database locks.

Dining Philosophers

Several threads each need two shared resources at once to make progress. The shape that teaches deadlock and lock ordering.

The setup: one or more producer threads generate items and put them into a shared buffer; one or more consumer threads take items out and process them. The buffer is bounded — it holds at most N items — because memory is finite and unbounded queues are how systems quietly die. Three things must never happen. A producer must never write into a full buffer, a consumer must never read from an empty one, and no two threads may touch the buffer’s internal state (the pointers, the count) at the same time.

Notice there are two completely different kinds of coordination hiding here. The buffer’s internal bookkeeping needs mutual exclusion — that is a job for a mutex. But "wait until there is a free slot" and "wait until there is an item" are not mutual exclusion at all; they are counting and waiting. That is exactly what a counting semaphore is for. Trying to solve the whole thing with one mutex is the classic beginner mistake; the elegance is in using the right tool for each of the two jobs.

So we use two counting semaphores and one mutex. The semaphore empty counts how many free slots remain and starts at N; the semaphore full counts how many filled slots exist and starts at 0. A producer waits on empty (blocking if the buffer is full), and after inserting, it signals full. A consumer is the mirror image: it waits on full (blocking if the buffer is empty), and after removing, it signals empty. The mutex is held only for the brief moment of actually touching the shared indices.

#define N 8
int    buffer[N];
int    in = 0, out = 0;      /* next write / next read slot */

sem_t  empty;                /* free slots  — init to N     */
sem_t  full;                 /* used slots  — init to 0     */
pthread_mutex_t m;           /* guards in, out, buffer      */

/* setup: sem_init(&empty, 0, N); sem_init(&full, 0, 0); */

void producer(void) {
    for (;;) {
        int item = produce_item();
        sem_wait(&empty);                 /* one fewer free slot; blocks if full  */
        pthread_mutex_lock(&m);           /* enter critical section               */
        buffer[in] = item;
        in = (in + 1) % N;
        pthread_mutex_unlock(&m);
        sem_post(&full);                  /* one more item to consume             */
    }
}

void consumer(void) {
    for (;;) {
        sem_wait(&full);                  /* one fewer item; blocks if empty      */
        pthread_mutex_lock(&m);
        int item = buffer[out];
        out = (out + 1) % N;
        pthread_mutex_unlock(&m);
        sem_post(&empty);                 /* one more free slot                   */
        consume_item(item);
    }
}

The single most important detail is the ordering: the semaphore wait happens outside the mutex, never inside it. Picture the alternative. A consumer grabs the mutex first and then waits on full while the buffer is empty — it now sleeps holding the lock, so no producer can ever get in to add an item and wake it. That is a self-inflicted deadlock. Wait for the resource first, then take the lock to touch the data; release the lock, then signal. Get that order right and the solution is bulletproof.

empty (counting semaphore)

How many free slots remain; producers wait on it, consumers signal it. Starts at N.

full (counting semaphore)

How many filled slots exist; consumers wait on it, producers signal it. Starts at 0.

mutex

Guards the buffer indices during the tiny insert/remove step so two threads never corrupt them.

The golden rule

wait(semaphore) before lock(mutex); unlock(mutex) before signal(semaphore). Never block on a semaphore while holding the lock.

Producer–Consumer is not an exercise; it is arguably the most common concurrency pattern in all of software. The instant you have work being generated at one rate and processed at another, you reach for a queue between them, and that queue is a bounded buffer whether you call it that or not. Recognising the pattern tells you immediately what can go wrong and what the knobs mean.

• ▸Thread pools: a fixed set of worker threads (consumers) pull tasks off a shared work queue that your application code (producers) submits to. The pool’s queue is the buffer; its size is a real capacity decision.
• ▸Message brokers: Kafka, RabbitMQ, and SQS are Producer–Consumer scaled to a network, with the buffer durably stored so producers and consumers need not even be alive at the same time.
• ▸Go channels: a buffered channel, ch := make(chan T, N), is literally a bounded buffer with the semaphores built in — sending blocks when full, receiving blocks when empty, exactly like our code.
• ▸Buffered I/O and logging: your program produces log lines fast; a background thread consumes and flushes them to disk slowly. The in-memory buffer between them is the same structure.

The word that turns this from trivia into engineering wisdom is backpressure. The buffer is bounded on purpose. When it fills, the producer blocks on the empty semaphore — and that blocking is a feature, not a bug. It is the system telling fast producers "slow down, the consumers cannot keep up." Remove the bound to stop the blocking and you have not fixed anything; you have moved the failure. An unbounded queue absorbs the mismatch by growing without limit until the machine runs out of memory and the whole process dies — usually under exactly the peak load where you needed it most.

This is also why tuning a thread pool is subtle. Too small a queue and you reject or block work you could have absorbed; too large and you hide a chronic capacity shortfall behind a growing backlog and rising latency, until the buffer is a queue of stale work nobody wants anymore. The classic problem gave you the mechanism; production teaches you that the buffer size encodes a policy about how your system should behave when it is overloaded.

The setup: many threads share a piece of data. Threads that only read it do not interfere with one another, so it would be wasteful to force them to take turns — we want any number of readers active at once. But a writer changes the data, so a writer must have it entirely to itself: no other writer, and no reader, at the same time. This asymmetry — reads share, writes are exclusive — is the whole problem, and it is everywhere data is read far more often than it is written.

The trick is to make the readers, as a group, behave like a single user of the data with respect to writers. We keep a counter, read_count, of how many readers are currently active, protected by its own small mutex. The first reader to arrive acquires the write lock on behalf of all readers; the last reader to leave releases it. In between, readers come and go freely without touching the write lock at all. Writers simply grab that one write lock exclusively.

int read_count = 0;
sem_t rw_lock;          /* exclusive data access — init 1 */
sem_t count_mtx;        /* guards read_count     — init 1 */

void writer(void) {
    sem_wait(&rw_lock);              /* full exclusive access */
    write_data();
    sem_post(&rw_lock);
}

void reader(void) {
    sem_wait(&count_mtx);
    if (++read_count == 1)           /* first reader in... */
        sem_wait(&rw_lock);          /* ...locks out writers */
    sem_post(&count_mtx);

    read_data();                     /* many readers here at once */

    sem_wait(&count_mtx);
    if (--read_count == 0)           /* last reader out... */
        sem_post(&rw_lock);          /* ...lets writers back in */
    sem_post(&count_mtx);
}

Trace it once and the elegance is clear. Reader A arrives, bumps read_count to 1, and takes rw_lock. Reader B arrives, bumps it to 2, and — because it is not the first — walks straight in without touching rw_lock. Both read concurrently. A writer that shows up must wait on rw_lock until read_count falls to 0. Correct and efficient for the read-heavy case we wanted.

But this version has a nasty flaw that its own cleverness creates: writer starvation. As long as at least one reader is always active, read_count never returns to 0, so rw_lock is never released, so a waiting writer waits forever even though it may be an urgent update. Under a steady stream of readers, this solution is correct on safety but broken on liveness — the writer’s work never happens.

The fix is to change the priority policy. A writer-priority variant adds bookkeeping so that once a writer is waiting, new readers are held back until that writer has had its turn — protecting writers at the risk of starving readers instead. Better still are fair (or "no-starvation") solutions that serve threads in roughly arrival order, so neither side is locked out indefinitely. There is no single right answer: the correct policy depends on whether stale reads or delayed writes hurt your application more. That judgement call is the real lesson.

read_count

How many readers are active right now; the first reader acquires the write lock and the last releases it.

rw_lock

The exclusive gate on the data. Held by an active writer, or held on behalf of the whole reader group.

Reader priority

Readers never wait for a waiting writer; maximises read concurrency but can starve writers.

Writer priority / fair

Holds back new readers once a writer is waiting, or serves in arrival order, to bound how long either side waits.

You almost never hand-roll the semaphore dance from the previous section, because the pattern is so common that it has been packaged into a primitive of its own: the read-write lock. POSIX gives you pthread_rwlock_t with rdlock and wrlock; Java has ReentrantReadWriteLock; Go has sync.RWMutex; Rust’s RwLock is in the standard library. Each one is exactly the Readers–Writers solution, hardened and given a name, with a documented policy about fairness and starvation you should actually read.

• ▸Databases: this is the beating heart of concurrency control. A shared (S) lock lets many transactions read a row at once; an exclusive (X) lock lets exactly one write it, blocking all readers. SELECT versus UPDATE is Readers–Writers at the row and table level, and the engine’s starvation policy determines whether a long-running report can starve an urgent write.
• ▸Read-heavy caches and config: an in-process cache, a routing table, a feature-flag map — read on nearly every request, written only when something changes. A read-write lock lets the hot read path run fully concurrently and pays the exclusive cost only on the rare refresh.
• ▸Copy-on-write and snapshots: some systems dodge the writer entirely by letting readers see an immutable snapshot while the writer prepares a new version and swaps a single pointer. It is the same asymmetry, solved by never blocking readers at all.

Knowing this pattern changes how you debug production. When a database grinds to a halt under load, "who holds the exclusive lock and who is queued behind it" is the first question — and it is the Readers–Writers picture in your head that makes the question obvious. When a service’s tail latency spikes on writes, you suspect readers are starving the writer; when reads slow down, you suspect a writer is holding the exclusive lock too long. The classic problem is not academic; it is the mental model you debug with.

The setup is deliberately whimsical so the mechanics stay clear. Five philosophers sit around a round table. Between each pair of neighbours lies a single fork — five forks for five philosophers. A philosopher alternates between thinking and eating, and to eat they need both the fork on their left and the fork on their right. A fork is shared by two neighbours, so it is a shared resource, and each philosopher is a thread that needs two of them at once to make progress.

The obvious solution is the trap. "Pick up your left fork, then pick up your right fork, eat, put both down." Model each fork as a mutex and it reads perfectly reasonable:

philosopher(i):
    while true:
        think()
        lock(fork[i])                 # my left fork
        lock(fork[(i + 1) % 5])       # my right fork
        eat()
        unlock(fork[i])
        unlock(fork[(i + 1) % 5])

Now imagine the interleaving that nature will eventually hand you. Every philosopher gets hungry at once. Each one successfully picks up their left fork — philosopher 0 takes fork 0, philosopher 1 takes fork 1, and so on around the table. Now every philosopher is holding one fork and reaching for the right-hand fork, which is the left fork of their neighbour, who is holding it and will not let go. Nobody can proceed, nobody will release, and the table sits frozen forever. That is a textbook deadlock, and the fact that it needs a specific timing to appear is exactly what makes it so dangerous — the code passes every casual test and then hangs in production at 3 a.m.

The deadlock arises because all four of the necessary conditions line up: each fork gives mutual exclusion, philosophers hold one fork while waiting for another (hold-and-wait), nobody can be forced to drop a fork (no preemption), and the "everyone waits for their neighbour" arrangement forms a circular wait around the table. Break any one condition and the deadlock cannot form. Each classic solution is precisely an attack on one of those conditions.

Resource ordering (break circular wait)

Number the forks and require every philosopher to pick up the lower-numbered fork first. Now the last philosopher reaches for the shared low fork before their own, so the cycle cannot close.

Limit the diners (break hold-and-wait pressure)

Allow at most four philosophers at the five-seat table at once (a counting semaphore of value 4). With one seat always spare, at least one philosopher can always get both forks.

Arbitrator / waiter (break the free-for-all)

A central waiter must grant permission before anyone picks up forks, handing out forks only in combinations that cannot deadlock. Simple and correct, but the waiter is a bottleneck.

Try-and-back-off (break hold-and-wait directly)

Take the first fork, then try the second; if it is unavailable, put the first back down and think again. Avoids deadlock but risks livelock — everyone politely retrying forever — unless you add randomness.

The resource-ordering fix is the one worth burning into memory, because it generalises far beyond forks. Impose a single global order on your locks and always acquire them in that order, and a circular wait becomes impossible — there is no cycle when everyone climbs the same ladder in the same direction. This is not a philosophers’ trick; it is the number-one deadlock-prevention rule in real multithreaded code, from kernels to database engines. We will make this rigorous in the deadlock chapters, but Dining Philosophers is where you feel in your bones why lock ordering matters.

Strip away the costumes and each problem leaves you with one transferable idea you will use for the rest of your career. These are not three party tricks; they are three lenses for looking at any concurrent system, and the engineers who see through them reason about production incidents that leave others guessing.

From Producer–Consumer: backpressure

Decouple producers from consumers with a bounded buffer, and treat the bound as policy. When it fills, you must choose consciously between blocking, dropping, and (dangerously) growing forever.

From Readers–Writers: exploit asymmetry

When one operation dominates, optimise its path. Let reads share and isolate only the rare write — but always ask which side your fairness policy is quietly starving.

From Dining Philosophers: order your locks

Circular wait is the deadlock you can design away for free. Acquire every set of locks in one consistent global order and cycles become impossible.

Underneath all three runs a single distinction that is worth naming explicitly, because you will use it every time you evaluate a concurrent design. Safety means nothing bad ever happens — no two threads corrupt the buffer, no reader sees a half-written value, no fork is held by two philosophers. Liveness means something good eventually happens — producers eventually proceed, writers eventually get their turn, philosophers eventually eat. Almost every concurrency bug is a violation of one or the other: a race condition breaks safety, while deadlock and starvation break liveness. A solution is only correct when it delivers both, and the classic problems are so instructive precisely because the naive answers nail one and quietly betray the other.

• ▸Producer–Consumer: safe with the mutex, live only if the buffer is bounded and backpressure is handled deliberately.
• ▸Readers–Writers: safe with the write lock, live only if the priority policy does not starve one side.
• ▸Dining Philosophers: safe with per-fork mutexes, live only once you break the circular wait.