When sharing is not symmetric
The producer-consumer problem from the last guide treated everyone the same: every thread touched the shelf, so a single mutex around every access was the right idea. But a lot of real data is read far more often than it is changed. Picture a wall-mounted train timetable in a station. A hundred travelers can stand in front of it and read it at once with no trouble at all — they are not interfering with one another, because reading does not change anything. The only dangerous moment is when a worker climbs up to repaint a departure time. While that worker is mid-stroke, nobody should be reading (they might see half the old time and half the new), and no second worker should be painting the same board.
This is the readers-writers problem, and the whole point is that the two kinds of access are not symmetric. Readers do not conflict with other readers, so it would be wasteful to force them to take turns one at a time the way a plain mutex would. Writers conflict with everyone — with other writers and with readers alike. So the rule we actually want is: any number of readers may be inside at once, OR exactly one writer may be inside alone, but never both. Letting many readers share simultaneously is the speedup; guaranteeing a writer total exclusivity is the safety.
The first solution — and the writer who starves
The textbook 'readers-preference' solution is clever and worth tracing. We keep a counter, readcount, of how many readers are currently inside, guarded by its own small mutex. Crucially, only the FIRST reader to arrive does wait on a second semaphore called rw (the one a writer must also hold), and only the LAST reader to leave does signal on it. So a whole crowd of readers acquires the writer-blocking lock exactly once between them, and any reader arriving while others are already inside just bumps the counter and walks straight in. Writers, by contrast, must each grab rw alone, which a present crowd of readers is holding shut.
READER WRITER
------ ------
wait(mutex) wait(rw) // exclusive
readcount += 1 ... write the data ...
if readcount == 1: wait(rw) signal(rw)
signal(mutex)
... read the data ... mutex starts at 1
wait(mutex) rw starts at 1
readcount -= 1 readcount starts at 0
if readcount == 0: signal(rw)
signal(mutex)Now read that last sentence again, because it hides a serious flaw. As long as at least one reader is always inside, readcount never drops back to zero, so rw is never released, so a waiting writer waits forever. In a read-heavy system this is not hypothetical — a fresh reader arrives before the previous crowd has fully drained, and the writer is locked out indefinitely. That is writer starvation: a thread that is ready and able to run, but is perpetually overtaken by others. Recall starvation from the scheduling rung — it is the same disease here, caused by our policy rather than by any deadlock. The system as a whole makes progress; one unlucky thread never does.
Curing starvation by being fair
The cure is to stop giving readers automatic priority. A 'writers-preference' variant flips the bias: once a writer is waiting, new readers are made to queue behind it, so the writer gets in as soon as the current readers drain. But that just moves the starvation onto the readers in a write-heavy burst. The genuinely fair fix is a turnstile: place one extra semaphore in front of the whole entrance that every newcomer — reader or writer — must pass through one at a time. Because it preserves arrival order, a writer that arrives is never jumped by readers who came after it, yet a run of readers already past the turnstile still share happily inside.
Notice the deeper idea, because it recurs all over operating systems: starvation is almost always cured by introducing fairness, and fairness usually means respecting arrival order or, more generally, bounded waiting — a guarantee that once you ask, only a finite number of others can go ahead of you before your turn comes. It is exactly the same move as aging in CPU scheduling, where a job's effective priority slowly rises the longer it waits so it cannot be ignored forever. Whenever a design lets one class of request indefinitely overtake another, look for a fairness mechanism that puts a ceiling on how long anyone can be skipped.
Five philosophers, five forks, one disaster
The second great puzzle is the dining philosophers, and it is the canonical picture of deadlock. Five philosophers sit around a round table. Between each pair of neighbors lies a single fork — five forks for five people. A philosopher only ever does two things: think, and eat. To eat the (slippery) spaghetti, a philosopher needs BOTH the fork on the left and the fork on the right. The natural, obvious code is: pick up the left fork, then pick up the right fork, eat, then put both down. Each fork is a shared resource — model it as a mutex or a binary semaphore, one per fork.
Here is the catastrophe. Suppose all five philosophers get hungry at the same instant and each one picks up the fork on their left. Now every fork on the table is held, and every philosopher is sitting there holding one fork, waiting for the fork on their right — which is the LEFT fork of their neighbor, who is also waiting and will never let go. Nobody can eat, nobody will put a fork down, and the table freezes forever. That is a deadlock you can see with your own eyes: a perfect ring of waiting.
Breaking the ring: the cures
Here is where the abstract theory from the deadlock rung pays off. Recall that a deadlock needs ALL FOUR of the necessary conditions to hold at once: mutual exclusion, hold-and-wait, no-preemption, and circular wait. They are necessary together, which is wonderful news — you do not have to fix all of them. Break ANY single one and deadlock becomes impossible. The dining philosophers is the perfect lab for this, because each classic cure corresponds to attacking one specific condition.
- Limit the diners: allow at most four philosophers to sit at the table at once (use a counting semaphore starting at 4). With one empty seat, at least one philosopher can always get both forks. This attacks hold-and-wait by ensuring the resources are never all simultaneously claimed.
- Pick up both forks or neither: a philosopher acquires the pair atomically, inside a single critical section, taking both only if both are free and otherwise taking none. This directly forbids hold-and-wait — you never hold one fork while waiting for the other.
- Break the symmetry with a global fork order: number the forks and require every philosopher to pick up the lower-numbered fork first. Now one philosopher reaches for the same fork as a 'first' grab as their neighbor reaches for as a 'second', so the circular wait cannot close. This is exactly lock ordering.
The lock-ordering cure is the most important one to internalize, because it generalizes to every multi-lock program you will ever write. The deadlock arose from a circular wait: a cycle where each thread holds a resource the next one needs. If every thread always acquires locks in the same global order, you literally cannot form a cycle — a cycle would require some thread to grab a higher-numbered lock before a lower-numbered one, which the rule forbids. The whole symmetric ring breaks because, with consistent ordering, at least one philosopher (the one whose left fork has the higher number) reaches for their forks in the opposite sequence from everyone else.
What these puzzles are really teaching
Step back and notice what these toy stories actually drill into you. The readers-writers problem teaches that not all shared access is equal, and that a correct solution can still be a bad one if it starves a whole class of threads — correctness and fairness are separate goals you must check independently. The dining philosophers teaches that deadlock is not magic: it is the four conditions, and you defeat it by surgically breaking one, usually with a consistent lock order. A close cousin, the sleeping barber, dresses the same machinery in yet another scene — a barber who sleeps when there are no customers and customers who leave when all the waiting chairs are full — to drill the handoff of signalling someone awake without losing a notification.
Be honest, though, about how the real world handles deadlock. The dining-philosophers cures show prevention is possible, but the heavyweight runtime alternatives — detecting cycles in a wait-for graph and aborting victims, or running the banker's algorithm to avoid unsafe states — are expensive and need to know resource demands in advance. So most general-purpose operating systems quietly use the ostrich algorithm: they ignore deadlock entirely, betting it is rare enough that a reboot is cheaper than the machinery to prevent it. That is not laziness; it is a real engineering trade-off, honestly named. You prevent deadlock in your own code with discipline like lock ordering, and you accept that the OS underneath mostly will not save you.
So far every tool in this rung — semaphores, mutexes, condition variables — has been a lock: a way to make threads take turns. They are powerful but brittle, as the writer starvation and the philosophers' ring both showed. In the next guide we go beyond locks entirely, to atomic operations and the compare-and-swap loop, and to lock-free data structures that let threads make progress without anyone ever holding a lock at all — a different and surprising way to tame the very same shared data.