Classic Concurrency Problems

Producer-consumer, readers-writers and dining philosophers: each problem run as real threads, the failure reproduced, and the standard fixes compared.

Overview

Three problems from the 1960s and early 1970s still carry most concurrency interviews. Each one isolates a single hazard. Producer-consumer is about waiting: a buffer that can be full or empty. Readers-writers is about fairness: sharing without starving anyone. Dining philosophers is about deadlock: several threads each holding one resource and wanting another.

Interviewers use them because the solutions are short and the mistakes are specific. Knowing the problem is not enough; you are expected to write the solution, explain which condition for deadlock or starvation it breaks, and test it.

Producer-consumer

Producers put items into a fixed-size buffer; consumers take them out. A producer must wait when the buffer is full, a consumer when it is empty, and the buffer itself must never be changed by two threads at once.

The semaphore solution uses three objects. empty counts free slots (starts at the capacity), full counts filled slots (starts at 0), and a mutex guards the buffer.

The order matters. If a producer took the mutex first and then waited on empty while the buffer was full, it would sleep holding the mutex, and no consumer could get in to make room.

1 — takes the mutex — buffer is full
2 — waits on empty, still holding the mutex
3 — waits for the mutex to pop an item
4 — waits forever — waits forever — deadlock

In practice, a blocking queue (queue.Queue(maxsize), Java's ArrayBlockingQueue) gives you this behavior, packaged (built from a lock and conditions rather than semaphores); the Thread-Safe Queue topic builds one from a lock and two condition variables.

Readers-writers

Many threads read shared data and a few write it. Readers may share; a writer needs the data to itself. Courtois, Heymans and Parnas stated the problem in 1971 with two solutions: one that favors readers and one that lets writers in as early as possible. The choice is the whole problem, because each favors one side at the cost of the other.

Readers first — A reader enters whenever no writer is writing, even if a writer waits — Writers, under a steady stream of readers
Writers first — Once a writer waits, new readers wait too — Readers, under a steady stream of writers
Fair — Arrival order, with consecutive readers let in together — Nobody, at some cost in throughput

The readers-first version, built the classic way: a counter of active readers guarded by its own mutex, and a room lock that the first reader takes and the last reader releases (sometimes called a lightswitch).

Note that room is released by whichever reader is last, not the one that acquired it. That is legal for Python's Lock, which has no owner; with an owned lock such as RLock or Java's ReentrantLock you would use a semaphore instead. For the writer-preferring version, see Synchronization Primitives; Java's ReentrantReadWriteLock offers a fair mode.

Dining philosophers

Dijkstra's version (1971): five philosophers sit around a table with one fork between each pair; a philosopher needs both neighboring forks to eat. If all five pick up their left fork at the same moment, each waits for a right fork that its neighbor holds, and nobody eats again. Dijkstra called this the deadly embrace.

The program first reproduces the deadlock (with a timeout, so it ends), then fixes it by numbering the forks and having everyone pick up the lower-numbered one first. P4's forks are 4 and 0, so P4 reaches for fork 0 first, the same fork P0 wants first; the cycle cannot form.

What you will be able to do

Write producer-consumer with two semaphores and a mutex, and explain why the semaphore wait comes before the mutex.
Explain the readers-first and writers-first variants and who starves in each.
Reproduce the dining philosophers deadlock and fix it with fork ordering, a limit on diners, or an arbitrator.
Say which deadlock condition each fix breaks.

Interview questions

Walk through the producer-consumer solution with a bounded buffer.
How do you solve the dining philosophers problem without deadlock?
In readers-writers, how do you stop writers from starving?
Make two threads print in strict alternation: ping, pong, ping, pong.