Synchronization Problems

Operating-systems courses lean on three classic puzzles because each one distils a real concurrency hazard into a tiny, memorable story. Dining philosophers shows how shared resources can deadlock. Producer-consumer shows how to coordinate a fixed-size shared buffer so it never overflows or is read empty. Readers-writers shows shared-versus-exclusive access. Each is solved with the right semaphores plus one rule that rules out the bad interleaving.

The three classics

1. 1Dining philosophers — five philosophers around a table with one fork between each pair; each needs *both* neighbouring forks to eat. If all five grab their left fork at once, every right fork is taken — a circular wait, a deadlock.
2. 2Producer-consumer — a producer adds items to a fixed-size buffer and a consumer removes them. The producer must block when the buffer is full, the consumer when it's empty.
3. 3Readers-writers — many readers may share the data at once, but a writer needs exclusive access, since changing data mid-read would give inconsistent results.

Worked example — producer-consumer with semaphores

semaphore empty = N;   // count of free slots
semaphore full  = 0;   // count of filled slots
semaphore mutex = 1;   // lock for the buffer

// 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);

empty and full count the slots; mutex protects the buffer indices. A producer waits for a free slot (empty), takes the lock, inserts an item, then signals that one more slot is full. The consumer mirrors it: wait for a filled slot, take the lock, remove an item, then signal a slot is empty again.