Classical Synchronization Problems

Three classic problems (Silberschatz 7.1) are the standard test bed for any new synchronization primitive. The bounded-buffer (producer-consumer) problem is about counting and waiting for space or data. The readers-writers problem is about letting many readers share while writers get exclusive access, and about who gets starved. The dining philosophers problem is about acquiring several resources at once without deadlock or starvation.

The standard semaphore solution of each problem works for the reasons given in its section; small changes break it, such as swapping two wait calls or letting every philosopher pick up the same side first, and the readers-writers section adds the priority variants.

Producers put items into a buffer of $n$ slots; consumers take them out. A producer must wait when the buffer is full, a consumer when it is empty, and buffer updates must be mutually exclusive.

Before starting any producer or consumer, require n >= 1, allocate buffer[0..n-1], and initialize in <- 0 and out <- 0; retain the semaphore initial values below.

Invariant. At every moment, empty + full equals $n$ minus the number of producers and consumers between their first wait and their final signal. When nobody is in the middle of an operation, empty + full $= n$ and full is the number of items. All $n$ slots can be used, unlike the busy-waiting in/out buffer of Inter-Process Communication, which can fill only $n - 1$.

IMPERATIVE RULE. Wait on the counting semaphore (empty or full) before mutex, never after. If a producer runs wait(mutex) first and then blocks on wait(empty) because the buffer is full, it sleeps while holding mutex; no consumer can ever enter to make space, and the system deadlocks. The order of the two signal calls does not matter for correctness.

With several producers and consumers the same code works unchanged, because mutex serializes all index updates.

Many processes read a shared object; some write it. Any number of readers may read together, but a writer needs exclusive access (no other writer, no reader).

Once a writer is waiting, no new reader may start. This needs an extra semaphore that readers must pass (often called read_try) and a writer count; the first waiting writer locks readers out. Now readers can starve under a stream of writers. A fair solution queues readers and writers in arrival order.

Readers-writers locks. Many systems provide them directly (POSIX pthread_rwlock_t). They pay off when reads far outnumber writes; otherwise the bookkeeping costs more than a plain mutex.

Five philosophers sit round a table with one chopstick between each pair (five in all). A philosopher alternates thinking and eating, and needs both neighbouring chopsticks to eat.

Deadlock. If all five pick up their left chopstick at once, every right chopstick is taken and all five wait forever. All four Coffman conditions hold: chopsticks are exclusive, each holds one and waits for one, none can be taken away, and the waits form a cycle.

Remedies (each breaks one condition):

Deadlock-free is not starvation-free. In the monitor solution (a philosopher eats only if neither neighbour is eating), two neighbours can alternate so that the philosopher between them never finds both free. Preventing starvation needs extra fairness, such as a queue or priorities.

How many can eat at once? With five chopsticks and two per meal, at most $\lfloor 5/2 \rfloor = 2$ philosophers eat simultaneously, and they cannot be neighbours.

With $n = 1$, one producer making 3 items and one consumer taking 3: the standard order (counting semaphore first) never deadlocks and never puts the item count outside 0 to 1. Swapping the producer's two waits allows this sequence: the producer fills the slot, loops, takes mutex, blocks on empty (still 0); the consumer blocks on mutex. Deadlock. The same check with $n = 2$, four items, or with two producers and two consumers, finds no error in the standard order.

With two readers and one writer under the first solution: both readers can be reading at the same time, a reader and the writer are never active together, and two writers are never active together. Suppose reader A is reading, so read_count $= 1$ and rw_mutex $= 0$, and a writer is blocked on rw_mutex. A new reader B passes mutex, makes read_count $= 2$, skips wait(rw_mutex) and starts reading. If readers keep overlapping like this, the writer never runs.

For 3, 4 and 5 philosophers, the plain left-then-right program can deadlock, while the asymmetric version (the last philosopher takes right first) and the version with a room semaphore of $n - 1$ cannot.

A five-slot buffer ($n = 5$) starts empty. The producer tries to put in 7 items before the consumer starts; then the consumer takes 3 items while the producer finishes. Blocking semaphores are used, so a wait decrements first and a negative value counts the blocked processes. The mutex operations always succeed here and are left out.

At the end, 7 items were produced and 3 consumed, so full $= 7 - 3 = 4$ and empty $= 5 - 4 = 1$, whatever the interleaving, as the invariant requires once nobody is inside an operation. The $-1$ at step 6 appears only with blocking semaphores; with the busy-waiting definition the producer spins at empty = 0 and the value never goes negative.

Common misconceptions.