SETUP: a producer adds items to a fixed-size buffer; a consumer removes them. THE THREE CONSTRAINTS: 1. the producer must WAIT when the buffer is FULL 2. the consumer must WAIT when the buffer is EMPTY 3. only one process may touch the indices at a time SOLUTION — three semaphores, one per constraint: semaphore empty = N; /* free slots */ semaphore full = 0; /* items present */ semaphore mutex = 1; /* index protection */ producer: consumer: wait(empty); wait(full); wait(mutex); wait(mutex); buffer[in] = item; item = buffer[out]; in = (in+1) % N; out = (out+1) % N; signal(mutex); signal(mutex); signal(full); signal(empty); THE ORDER RULE — verified experimentally in the semaphore topic: wait(empty) MUST come before wait(mutex). Reversed, the producer blocks on `empty` while HOLDING the mutex, the consumer cannot acquire the mutex to signal `empty`, and both block forever. Measured: neither thread ever finished. MEASURED CORRECT BEHAVIOUR (BUF=5, 20 items): produced : 20 consumed : 20 max occupancy observed : 5 ← never exceeded the buffer final occupancy : 0 ← nothing lost or duplicated MEASURED WITHOUT THE SEMAPHORES (5,000 items, 5 slots): final count = -5000 The counter went to minus five thousand — the invariant is not bent, it is meaningless. The consumer "consumed" items that were never produced, repeatedly re-reading stale slots. THE INVARIANT WORTH STATING: empty + full + (in flight) = N A semaphore pair like this is really one resource count split in two directions, which is why they always move in opposite directions.

SETUP: a shared data structure. MANY readers may read simultaneously (reading does not conflict with reading), but a WRITER needs exclusive access. reader–reader compatible reader–writer CONFLICT writer–writer CONFLICT This is exactly the lock compatibility matrix from the database locking topic — the same problem at a different layer. FIRST READERS-WRITERS PROBLEM (readers have priority) No reader waits unless a writer already holds the resource. semaphore mutex = 1; /* protects readcount */ semaphore wrt = 1; /* the resource lock */ int readcount = 0; writer: wait(wrt); ... write ... signal(wrt); reader: wait(mutex); readcount++; if (readcount == 1) wait(wrt); /* FIRST reader locks out writers */ signal(mutex); ... read ... wait(mutex); readcount--; if (readcount == 0) signal(wrt); /* LAST reader releases */ signal(mutex); THE MECHANISM: only the first reader acquires `wrt` and only the last releases it. Readers in between simply increment and proceed, so many read concurrently. ✗ WRITERS CAN STARVE. With a steady stream of readers, readcount never reaches 0, so `wrt` is never signalled and the writer waits forever. SECOND READERS-WRITERS PROBLEM (writers have priority) Once a writer is waiting, no NEW reader may start. ✗ now READERS can starve. THIRD (fair) VERSION — nobody starves. Add a queue semaphore that everyone must pass through in arrival order: semaphore queue = 1; reader: wait(queue); wait(mutex); readcount++; if (readcount==1) wait(wrt); signal(mutex); signal(queue); ... read ... writer: wait(queue); wait(wrt); signal(queue); ... write ... signal(wrt); The `queue` semaphore serialises ENTRY, so a writer that arrives is ahead of every later reader — bounded waiting for both. REAL-WORLD FORM: this is a READ-WRITE LOCK. pthread_rwlock_rdlock / pthread_rwlock_wrlock Java ReentrantReadWriteLock Go sync.RWMutex WHEN IT IS WORTH IT: only when reads dominate AND the critical section is long. A read-write lock has more bookkeeping than a plain mutex, so for short sections a plain mutex is often faster. Measure rather than assume — Go's documentation explicitly warns that RWMutex is slower than Mutex for short critical sections.

SETUP: five philosophers around a table, five forks between them. Each needs BOTH adjacent forks to eat. P0 F0 F1 P4 P1 F4 F2 P3 F3 P2 THE NAIVE SOLUTION, and why it fails: philosopher i: wait(fork[i]); /* left */ wait(fork[(i+1) % 5]); /* right */ ... eat ... signal(fork[i]); signal(fork[(i+1) % 5]); If all five pick up their LEFT fork simultaneously, every fork is held and every philosopher waits for a right fork that will never be released. DEADLOCK. MEASURED ON THIS MACHINE (5 philosophers, 3 meals each, expected 15 meals total): NAIVE (all left-first), three runs: meals = [0,0,0,0,0] total = 0/15 DEADLOCKED meals = [0,0,0,0,0] total = 0/15 DEADLOCKED meals = [0,0,0,0,0] total = 0/15 DEADLOCKED Not a single philosopher ate, in any run. This is one of the few concurrency bugs that is reliably reproducible — because the circular wait forms almost immediately. All four Coffman conditions are present: mutual exclusion a fork is held exclusively hold and wait each holds the left, waits for the right no preemption a fork cannot be taken away circular wait P0→P1→P2→P3→P4→P0 FOUR SOLUTIONS, each breaking one condition: 1. ALLOW AT MOST 4 AT THE TABLE (breaks hold-and-wait) semaphore seats = 4; wait(seats); ... take both forks, eat, release ... ; signal(seats); With 4 competing for 5 forks, at least one gets both. 2. PICK UP BOTH FORKS ATOMICALLY (breaks hold-and-wait) wait(mutex); if both free: take both signal(mutex); Requires checking both under one lock — a monitor does this naturally. 3. ASYMMETRY — ODD/EVEN ORDERING (breaks circular wait) odd philosophers: left then right even philosophers: right then left Or simply: ONE philosopher reverses the order. MEASURED, with only the LAST philosopher reversed: meals = [3,3,3,3,3] total = 15/15 ALL ATE meals = [3,3,3,3,3] total = 15/15 ALL ATE meals = [3,3,3,3,3] total = 15/15 ALL ATE Three runs, all successful, and perfectly fair — every philosopher ate exactly three times. ONE reversed acquisition order eliminated the deadlock completely. 4. RESOURCE ORDERING — number the forks and always acquire the LOWER-NUMBERED one first (breaks circular wait) This is solution 3 generalised, and it is the standard industrial answer: impose a total order on all locks and acquire in that order everywhere. STARVATION vs DEADLOCK — a distinction this problem shows well: solutions 1–4 all prevent DEADLOCK. None of them alone guarantees no STARVATION: a philosopher could in principle be perpetually unlucky. Preventing that needs a fairness mechanism (a queue, or aging) on top.

SLEEPING BARBER A barber shop with one barber, one barber chair and N waiting chairs. · no customers → the barber SLEEPS · a customer arrives → wakes the barber, or takes a waiting chair, or LEAVES if all chairs are full · the barber finishes → takes the next waiting customer, or sleeps semaphore customers = 0; /* waiting customers */ semaphore barbers = 0; /* barbers ready */ semaphore mutex = 1; int waiting = 0; barber: customer: while (true) { wait(mutex); wait(customers); if (waiting < N) { wait(mutex); waiting++; waiting--; signal(customers); signal(mutex); signal(mutex); signal(barbers); wait(barbers); cut_hair(); get_haircut(); } } else { signal(mutex); leave(); /* balk */ } THE INTERESTING PART is the BALKING — a customer who finds the shop full leaves rather than waiting. That models a BOUNDED QUEUE WITH REJECTION, which is exactly what a web server does when its connection backlog is full (it returns 503 rather than queueing forever). Real systems must balk; unbounded queues are how they die. CIGARETTE SMOKERS Three smokers, each with an infinite supply of ONE ingredient (tobacco, paper, matches). An agent places two random ingredients on the table; the smoker with the third can smoke. · illustrates that a naive semaphore solution DEADLOCKS because a smoker may grab an ingredient it cannot use · the lesson: signal the specific waiter that can proceed, which is what condition variables (one per case) give you MAPPING THE PROBLEMS TO REALITY: producer/consumer → work queues, thread pools, Kafka readers/writers → caches, database tables, config reload dining philosophers → lock ordering, database deadlocks sleeping barber → bounded queues with rejection, 503s cigarette smokers → precise signalling, one condition per predicate