Every programming subject has its "standard exercises". In data structures you reverse a linked list; in algorithms you sort an array. In process synchronization, the standard exercises are a small set of puzzles known as the classical synchronization problems.
They are not just academic games. Each one is a tiny model of a pattern that appears everywhere in real systems:
Bounded-Buffer (Producer–Consumer) – one part of a program produces data, another consumes it, with a limited queue in between. Think of a web server's request queue, a print spooler, or a shell pipe like
cat file | grep x.Readers–Writers – many threads read shared data, a few update it. Think of a database table, a cache, or a configuration file.
Dining Philosophers – several processes each need more than one shared resource at the same time. It is the classic way to show how deadlock and starvation happen.
In Mutex Locks & Semaphores we learned the three ways to use a semaphore: initial value 1 for mutual exclusion, 0 for ordering, and n for counting resources. In this chapter we combine those three uses to solve each problem, run real C programs on Linux, and look at exactly what goes wrong when one line is changed. These solutions are asked again and again in GATE, university exams and interviews.
1. The Bounded-Buffer (Producer–Consumer) Problem
The problem
A producer creates items and puts them into a shared buffer. A consumer takes items out of the buffer and uses them. The buffer has room for only n items.
Producer ──put──▶ [ slot 0 | slot 1 | ... | slot n-1 ] ──get──▶ Consumer
(circular buffer of size n)Three rules must hold:
If the buffer is full, the producer must wait (not overwrite an item that has not been consumed).
If the buffer is empty, the consumer must wait (not read garbage).
Producer and consumer must not modify the buffer and its indexes at the same time (that would be a race condition, as in Process Synchronization & Race Conditions).
The idea: one semaphore per rule
Each rule maps to one of the three semaphore uses:
Semaphore | Initial value | Meaning | Which use? |
|---|---|---|---|
| n | Number of empty slots. The producer must take one before putting an item. | Counting |
| 0 | Number of filled slots. The consumer must take one before removing an item. | Counting (and ordering: a consumer cannot run before something is produced) |
| 1 | Lock for the buffer and its | Mutual exclusion |
Notice the invariant: at any moment when nobody is in the middle of an operation, empty + full = n.
The solution
semaphore empty = n, full = 0, mutex = 1;
/* Producer */ /* Consumer */
while (true) { while (true) {
item = produce(); wait(full); /* any item? */
wait(empty); /* free slot? */ wait(mutex);
wait(mutex); item = remove_from_buffer();
add_to_buffer(item); signal(mutex);
signal(mutex); signal(empty); /* slot freed */
signal(full); /* new item */ consume(item);
} }Read it as a conversation. The producer says "give me a free slot" (wait(empty)), locks the buffer, adds the item, unlocks, and announces "one more item" (signal(full)). The consumer does the mirror image. Notice that produce() and consume() are outside the lock, so the slow work happens in parallel and only the buffer update is serialized.
Running it in C
Here is the solution with POSIX semaphores, a buffer of 3 slots, and 8 items:
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
#define BUF_SIZE 3
#define ITEMS 8
int buffer[BUF_SIZE];
int in = 0, out = 0; /* next slot to fill / to empty */
sem_t empty; /* counts empty slots, starts at BUF_SIZE */
sem_t full; /* counts filled slots, starts at 0 */
sem_t mutex; /* binary semaphore guarding buffer/in/out */
void *producer(void *arg)
{
(void)arg;
for (int item = 1; item <= ITEMS; item++) {
sem_wait(&empty); /* wait for a free slot */
sem_wait(&mutex); /* lock the buffer */
buffer[in] = item;
printf("Produced %d into slot %d\n", item, in);
in = (in + 1) % BUF_SIZE;
sem_post(&mutex); /* unlock the buffer */
sem_post(&full); /* one more full slot */
}
return NULL;
}
void *consumer(void *arg)
{
(void)arg;
long sum = 0;
for (int k = 0; k < ITEMS; k++) {
sem_wait(&full); /* wait for an item */
sem_wait(&mutex);
int item = buffer[out];
printf(" Consumed %d from slot %d\n", item, out);
out = (out + 1) % BUF_SIZE;
sem_post(&mutex);
sem_post(&empty); /* one more empty slot */
sum += item;
}
printf("Sum of consumed items = %ld (expected %d)\n", sum, ITEMS * (ITEMS + 1) / 2);
return NULL;
}
int main(void)
{
pthread_t p, c;
sem_init(&empty, 0, BUF_SIZE);
sem_init(&full, 0, 0);
sem_init(&mutex, 0, 1);
pthread_create(&p, NULL, producer, NULL);
pthread_create(&c, NULL, consumer, NULL);
pthread_join(p, NULL);
pthread_join(c, NULL);
return 0;
}One run on Linux:
$ gcc -std=c17 -Wall -pthread boundedbuf.c -o boundedbuf
$ ./boundedbuf
Produced 1 into slot 0
Produced 2 into slot 1
Produced 3 into slot 2
Consumed 1 from slot 0
Consumed 2 from slot 1
Consumed 3 from slot 2
Produced 4 into slot 0
Produced 5 into slot 1
Produced 6 into slot 2
Consumed 4 from slot 0
Consumed 5 from slot 1
Consumed 6 from slot 2
Produced 7 into slot 0
Produced 8 into slot 1
Consumed 7 from slot 0
Consumed 8 from slot 1
Sum of consumed items = 36 (expected 36)The exact interleaving of the "Produced" and "Consumed" lines depends on the scheduler and can be different on your machine. What can never change:
The producer is never more than 3 items ahead of the consumer (it blocks in
sem_wait(&empty)after filling all three slots).The consumer never takes an item before it is produced, and items come out in the order they went in (1, 2, 3, ...).
The sum is always 36 – no item is lost or read twice.
Step-by-step trace (buffer size 2)
Let us trace a small scenario by hand with n = 2. (We show values the way POSIX reports them, never below 0; in the textbook blocking implementation from the previous chapter, empty would read −1 at step 3.) The producer runs three times in a row, then the consumer runs once, then the producer finishes its third item.
Step | Action | empty | full | Items in buffer |
|---|---|---|---|---|
0 | Start | 2 | 0 | 0 |
1 | Producer adds item 1 | 1 | 1 | 1 |
2 | Producer adds item 2 | 0 | 2 | 2 |
3 | Producer: | 0 | 2 | 2 |
4 | Consumer removes item 1, | 0 (the unit goes straight to the woken producer) | 1 | 1 |
5 | Producer adds item 3 | 0 | 2 | 2 |
Does the order of the wait calls matter? Yes!
This is the single most asked question about this problem. Suppose the producer is written with the two waits swapped:
/* WRONG producer */
wait(mutex); /* lock first ... */
wait(empty); /* ... then wait for a slot */
add_to_buffer(item);
signal(mutex);
signal(full);Now imagine the buffer is full (empty = 0):
The producer takes
mutex(it becomes 0), then blocks onwait(empty)– while still holding the lock.The consumer passes
wait(full), then blocks onwait(mutex), because the producer holds it.The producer waits for the consumer to free a slot; the consumer waits for the producer to release the lock. Nobody can move. Deadlock.
The same thing happens if the consumer swaps its waits and the buffer is empty. We checked all of this by exploring every possible interleaving of a producer and a consumer (buffer size 2) with a small Python model checker:
Version | Result of exploring all interleavings |
|---|---|
Correct solution | No deadlock, buffer count always between 0 and n |
Producer: | Deadlock when the buffer is full |
Consumer: | Deadlock when the buffer is empty |
Producer: | Still correct (only slightly less efficient) |
Rule: never block waiting for a condition (a counting semaphore) while holding the lock (the mutex). Wait for the "slot" or "item" first, then lock. The order of the two
signalcalls does not matter, becausesignalnever blocks.
Variations
Multiple producers and consumers: the same code works unchanged.
mutexensures two producers never write the same slot.Unbounded buffer: drop
empty; the producer never waits.In real life: a Linux pipe is a kernel-managed bounded buffer (64 KiB by default).
write()blocks when the pipe is full andread()blocks when it is empty, exactly like our producer and consumer (see Inter-Process Communication).
2. The Readers–Writers Problem
The problem
A shared object (a file, a database record, an in-memory table) is accessed by two kinds of threads:
Readers only look at the data.
Writers change the data.
Two readers at the same time are harmless, because neither changes anything. But a writer must have exclusive access: no other writer, and no reader (a reader could see a half-updated record).
Already inside → | Nobody | Readers | A writer |
|---|---|---|---|
Reader | Allowed | Allowed | Must wait |
Writer | Allowed | Must wait | Must wait |
Why not simply put one mutex around every access? It would be correct, but readers would have to queue one by one even though they could safely work together. In a read-heavy system (most web apps read far more than they write) that throws away a lot of parallelism.
First readers–writers problem (readers' preference)
The classic solution lets readers in as long as at least one reader is already reading. It uses:
rw_mutex = 1– held by a writer, or by the group of readers as a whole.read_count = 0– how many readers are inside right now.mutex = 1– protectsread_count(it is shared data too!).
semaphore rw_mutex = 1, mutex = 1;
int read_count = 0;
/* Writer */ /* Reader */
wait(rw_mutex); wait(mutex);
/* write */ read_count++;
signal(rw_mutex); if (read_count == 1) /* first reader */
wait(rw_mutex); /* lock out writers */
signal(mutex);
/* read (many readers together) */
wait(mutex);
read_count--;
if (read_count == 0) /* last reader */
signal(rw_mutex); /* let writers in */
signal(mutex);The clever part: only the first reader competes with writers for rw_mutex. Later readers just increment the count and walk in. The last reader to leave releases rw_mutex. Note that the reader that releases it may be a different thread from the one that acquired it – this is fine for a semaphore, but would be wrong for a mutex, which has an owner (see Mutex vs Semaphore in the previous chapter).
What if a writer is inside and readers arrive? The first reader blocks on wait(rw_mutex) while holding mutex, so all other readers queue up on mutex. When the writer leaves and does signal(rw_mutex), the scheduler decides who goes next: either the waiting readers (the first one gets rw_mutex, releases mutex, and the rest follow it in) or another waiting writer.
Running it in C
Writer 1 starts first; then three readers and a second writer are created. Reading and writing each take one second:
#define _DEFAULT_SOURCE /* for usleep() */
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>
sem_t rw_mutex; /* 1: held by a writer, or by the group of readers */
sem_t mutex; /* 1: protects read_count */
int read_count = 0; /* how many readers are reading right now */
int shared_data = 0;
void *reader(void *arg)
{
int id = *(int *)arg;
sem_wait(&mutex);
read_count++;
if (read_count == 1) /* first reader locks out writers */
sem_wait(&rw_mutex);
int inside = read_count; /* copy it while we hold mutex */
sem_post(&mutex);
printf("Reader %d reads %d (readers inside: %d)\n", id, shared_data, inside);
sleep(1); /* reading takes time */
sem_wait(&mutex);
read_count--;
if (read_count == 0) /* last reader lets writers in */
sem_post(&rw_mutex);
sem_post(&mutex);
return NULL;
}
void *writer(void *arg)
{
int id = *(int *)arg;
sem_wait(&rw_mutex);
shared_data += 10;
printf("Writer %d wrote %d\n", id, shared_data);
sleep(1); /* writing takes time */
sem_post(&rw_mutex);
return NULL;
}
int main(void)
{
pthread_t r[3], w[2];
int rid[3] = {1, 2, 3}, wid[2] = {1, 2};
sem_init(&rw_mutex, 0, 1);
sem_init(&mutex, 0, 1);
pthread_create(&w[0], NULL, writer, &wid[0]);
usleep(100000); /* let writer 1 get in first */
for (int i = 0; i < 3; i++)
pthread_create(&r[i], NULL, reader, &rid[i]);
pthread_create(&w[1], NULL, writer, &wid[1]);
for (int i = 0; i < 3; i++) pthread_join(r[i], NULL);
for (int i = 0; i < 2; i++) pthread_join(w[i], NULL);
return 0;
}$ gcc -std=c17 -Wall -pthread readers_writers.c -o readers_writers
$ ./readers_writers
Writer 1 wrote 10
Reader 1 reads 10 (readers inside: 1)
Reader 2 reads 10 (readers inside: 2)
Reader 3 reads 10 (readers inside: 3)
Writer 2 wrote 20The three readers are inside at the same time (the count goes 1, 2, 3), and Writer 2 gets in only after the last of them leaves. The order shown here is controlled with sleep/usleep, so you will usually see this same output, but strictly speaking it is still up to the scheduler.
The catch: writer starvation
Look at the reader code again. As long as at least one reader is inside, new readers keep walking in. If readers arrive continuously, with their reading times overlapping, read_count never drops to 0 and the writer waits forever:
time ─────────────────────────────────────────────▶
R1 ███████████
R2 ███████████
R3 ███████████
R4 ███████████ ... and so on
W waiting ..................................... (starves)This is starvation, not deadlock: the system as a whole makes progress (readers keep reading), but one process never does.
Second readers–writers problem (writers' preference)
The second version says: once a writer is waiting, no new reader may start. Readers already inside finish, then the writer goes. One common solution adds a "turnstile" semaphore read_try that writers close while any writer is waiting:
semaphore resource = 1; /* the shared data itself */
semaphore read_try = 1; /* readers must pass this turnstile */
semaphore rmutex = 1, wmutex = 1;
int read_count = 0, write_count = 0;
/* Reader */ /* Writer */
wait(read_try); wait(wmutex);
wait(rmutex); write_count++;
read_count++; if (write_count == 1)
if (read_count == 1) wait(read_try); /* block new readers */
wait(resource); signal(wmutex);
signal(rmutex);
signal(read_try); wait(resource);
/* write */
/* read */ signal(resource);
wait(rmutex); wait(wmutex);
read_count--; write_count--;
if (read_count == 0) if (write_count == 0)
signal(resource); signal(read_try); /* readers may go */
signal(rmutex); signal(wmutex);We verified both versions with the same model checker (two readers + two writers, and three readers + one writer, every possible interleaving): no reader is ever inside together with a writer, no two writers are ever inside together, and there is no deadlock.
But now the problem flips: if writers keep arriving, readers can starve. There is no free lunch; a fully fair version needs a FIFO queue that serves readers and writers in arrival order (sometimes called the "third readers–writers problem").
First (readers' preference) | Second (writers' preference) | |
|---|---|---|
New reader arrives while readers inside and a writer waits | Reader goes in | Reader waits |
Who can starve? | Writers | Readers |
Semaphores used | 2 (+ 1 counter) | 4 (+ 2 counters) |
Good when | Writes are rare and can be delayed | Data must be fresh; updates should not be held back |
Readers–writer locks in practice
You rarely build this by hand. Most systems provide a reader–writer lock:
POSIX:
pthread_rwlock_twithpthread_rwlock_rdlock(),pthread_rwlock_wrlock()andpthread_rwlock_unlock(). On Linux (glibc) the default prefers readers; a non-portable attribute can ask for writer preference.Java:
ReentrantReadWriteLock; C++17:std::shared_mutex; the Linux kernel:rwlock_tandrw_semaphore.Databases use the same idea as shared (S) and exclusive (X) locks on rows and tables.
Reader–writer locks have more bookkeeping than a plain mutex, so they only pay off when reads are frequent, reasonably long, and much more common than writes.
3. The Dining Philosophers Problem
The problem
Five philosophers sit at a round table. Between each pair of neighbours lies a single chopstick (some books say "fork"), so there are 5 chopsticks in total. A philosopher alternates between thinking and eating. To eat, she needs both chopsticks next to her: the one on her left and the one on her right. She can pick up only one at a time.
P0
c0 c1
P4 P1
c4 c2
P3 c3 P2
Philosopher i uses chopstick i (left) and chopstick (i+1) mod 5 (right)The chopsticks are resources that each process needs two of, shared with its neighbours. The challenge is to let philosophers eat without deadlock (everyone stuck forever) and without starvation (one philosopher never gets to eat).
The obvious solution – and why it deadlocks
Represent each chopstick with a semaphore initialised to 1. Each philosopher picks up the left one, then the right one:
semaphore chopstick[5] = {1, 1, 1, 1, 1};
/* Philosopher i */
while (true) {
wait(chopstick[i]); /* left */
wait(chopstick[(i + 1) % 5]); /* right */
/* eat */
signal(chopstick[(i + 1) % 5]);
signal(chopstick[i]);
/* think */
}Two neighbours can never eat at the same time, because they share a chopstick. But suppose all five get hungry at the same moment and each picks up her left chopstick. Every chopstick is now taken, and every philosopher waits for her right chopstick, which her neighbour holds and will never put down. Deadlock.
To show this really happens, here is a C version in which each philosopher pauses for one second between picking up the two chopsticks. That widens the dangerous window so the bad interleaving occurs every time. (Compile with -DFIXED to get the fixed version we look at next.)
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>
#define N 5
sem_t chopstick[N]; /* each starts at 1 */
void *philosopher(void *arg)
{
int i = *(int *)arg;
int left = i, right = (i + 1) % N;
#ifdef FIXED
/* Fix: always pick up the LOWER-numbered chopstick first */
int first = left < right ? left : right;
int second = left < right ? right : left;
#else
int first = left, second = right; /* everybody: left, then right */
#endif
for (int meal = 1; meal <= 2; meal++) {
printf("P%d is hungry\n", i);
sem_wait(&chopstick[first]);
sleep(1); /* widen the window: forces the bad case */
sem_wait(&chopstick[second]);
printf("P%d is EATING (meal %d)\n", i, meal);
sem_post(&chopstick[second]);
sem_post(&chopstick[first]);
}
return NULL;
}
int main(void)
{
pthread_t t[N];
int id[N];
for (int i = 0; i < N; i++)
sem_init(&chopstick[i], 0, 1);
for (int i = 0; i < N; i++) {
id[i] = i;
pthread_create(&t[i], NULL, philosopher, &id[i]);
}
for (int i = 0; i < N; i++)
pthread_join(t[i], NULL);
printf("All philosophers finished\n");
return 0;
}$ gcc -std=c17 -Wall -pthread dining.c -o dining
$ timeout 5 ./dining
P0 is hungry
P1 is hungry
P2 is hungry
P3 is hungry
P4 is hungry
$ echo $?
124All five philosophers became hungry and nobody ever ate. The program hung until timeout killed it after 5 seconds (exit status 124 means "killed by timeout"). Without the sleep(1) the program would usually finish, and the deadlock would appear only once in a while. That is exactly what makes such bugs so dangerous in real software. (If you redirect the output to a file or a pipe, you may see no lines at all: stdout is then fully buffered, and the buffer is lost when timeout kills the process.)
A deadlock like this needs four conditions to hold at the same time, known as the Coffman conditions (the chapter Deadlocks later studies them in detail). All four hold here: chopsticks are used exclusively (mutual exclusion), each philosopher holds one and waits for another (hold and wait), nobody snatches a chopstick away (no preemption), and P0 waits for P1, who waits for P2, ..., who waits for P0 (circular wait). Each fix below breaks one of these conditions.
Fix 1: Allow at most four philosophers at the table
Add a counting semaphore room = 4. A philosopher does wait(room) before picking up chopsticks and signal(room) after putting them down. With only 4 philosophers competing for 5 chopsticks, by the pigeonhole principle at least one of them can get both chopsticks, eat, and release them. The cycle can never close. (In general: with N philosophers, allow at most N − 1.)
Fix 2: Break the symmetry (resource ordering)
Number the chopsticks and make every philosopher pick up the lower-numbered chopstick first. Philosophers 0–3 still pick left then right, but philosopher 4 (whose chopsticks are 4 and 0) now picks chopstick 0 first. A circular chain of waiting would need someone to wait for a lower-numbered chopstick while holding a higher-numbered one, which this rule forbids. This is the general deadlock-prevention technique of ordering resources, which we will meet again in the deadlock chapters. Here is the same program built with -DFIXED:
$ gcc -std=c17 -Wall -pthread -DFIXED dining.c -o dining_fixed
$ ./dining_fixed
P0 is hungry
P1 is hungry
P2 is hungry
P3 is hungry
P4 is hungry
P3 is EATING (meal 1)
P3 is hungry
P3 is EATING (meal 2)
P2 is EATING (meal 1)
P2 is hungry
P2 is EATING (meal 2)
P1 is EATING (meal 1)
P1 is hungry
P1 is EATING (meal 2)
P0 is EATING (meal 1)
P0 is hungry
P0 is EATING (meal 2)
P4 is EATING (meal 1)
P4 is hungry
P4 is EATING (meal 2)
All philosophers finishedEveryone ate twice and the program finished, even with the one-second pause that made the naive version deadlock every time. (The exact order of the lines varies from run to run.) A popular variant of the same idea: odd-numbered philosophers pick left first, even-numbered pick right first.
Fix 3: Pick up both chopsticks or none
Let a philosopher pick up chopsticks only if both are free, checking and taking them inside one critical section. This breaks hold and wait. It is awkward to write with raw semaphores, but very natural with a monitor; the full solution appears in the next chapter, Monitors.
We checked the naive version and Fixes 1 and 2 with the model checker, exploring every interleaving of 5 philosophers: the naive version reaches the state where all five hold their left chopstick and nobody can move; the "room = 4", "lowest number first" and "odd/even" versions never deadlock, and in no version do two neighbours eat at the same time.
Solution | Deadlock-free? | Coffman condition broken | Starvation-free? |
|---|---|---|---|
Naive (left then right) | No | None | No |
At most N − 1 at the table | Yes | Circular wait (cannot form) | Depends on fair (FIFO) semaphores |
Lower-numbered chopstick first / odd–even | Yes | Circular wait | Depends on fair semaphores |
Both or none (monitor) | Yes | Hold and wait | No – two neighbours can keep a philosopher hungry |
Two facts worth remembering: with 5 philosophers, at most 2 can eat at the same time (in general ⌊N/2⌋), and deadlock-freedom does not imply starvation-freedom.
4. A Quick Look: The Sleeping Barber Problem
A barber shop has one barber, one barber chair, and k waiting chairs. If there are no customers, the barber sleeps. An arriving customer wakes the barber if he is asleep, sits in a waiting chair if one is free, or leaves if all chairs are taken. It models a server thread with a limited waiting queue that rejects extra requests.
semaphore customers = 0; /* customers waiting (barber sleeps on this) */
semaphore barber = 0; /* barber ready to cut */
semaphore mutex = 1; /* protects waiting */
int waiting = 0;
/* Barber */ /* Customer */
while (true) { wait(mutex);
wait(customers); /* sleep */ if (waiting < k) {
wait(mutex); waiting++;
waiting--; signal(customers); /* wake barber */
signal(barber); /* call one */ signal(mutex);
signal(mutex); wait(barber); /* wait my turn */
cut_hair(); get_haircut();
} } else {
signal(mutex); /* shop full: leave */
}It is the bounded buffer again in a different costume: customers counts items in the queue, waiting < k is the "buffer full" check (but a full shop makes customers leave instead of block), and barber is an ordering semaphore that tells one customer to come to the chair.
Solved Problems (GATE Style)
Problem 1
In the bounded-buffer solution with a buffer of size 10, what are the initial values of empty, full and mutex?
Answer: empty = 10, full = 0, mutex = 1.
Problem 2
Buffer size 5. At some instant full = 3 and nobody is inside a wait/signal pair. What is empty?
Answer: empty = 5 − 3 = 2, since empty + full = n at rest.
Problem 3
In the producer, wait(empty) and wait(mutex) are interchanged. What can happen?
Answer: deadlock. When the buffer is full, the producer holds mutex and blocks on empty; the consumer then blocks on mutex and can never free a slot.
Problem 4
In the first readers–writers solution, which process executes wait(rw_mutex), and which executes signal(rw_mutex), among the readers?
Answer: only the first reader to enter (when read_count becomes 1) waits on it, and only the last reader to leave (when read_count becomes 0) signals it.
Problem 5
With N = 7 dining philosophers using the "limit the table" fix, what is the largest number of philosophers that may be allowed to try at once, and how many can eat simultaneously?
Answer: at most N − 1 = 6 may try; at most ⌊7/2⌋ = 3 can eat at the same time.
Common Mistakes
Locking before waiting for space or data. Swapping
wait(empty)/wait(full)withwait(mutex)causes deadlock. Always wait on the counting semaphore first.Forgetting to protect
read_count. It is a shared variable; withoutmutex, two readers can both see "I am the first" or both miss "I am the last".Thinking the first readers–writers solution is fair. It can starve writers. The second can starve readers.
Using a mutex for
rw_mutex. The thread that releases it may not be the one that acquired it, which a mutex does not allow.Saying "deadlock-free" means "starvation-free". The monitor solution of dining philosophers is deadlock-free but not starvation-free.
Testing once and concluding "no deadlock". The naive dining philosophers usually completes when you run it; the bad interleaving is rare but real.
Interview Questions
Explain the producer–consumer problem and its semaphore solution.
A producer and a consumer share a buffer of n slots. Use empty = n (free slots), full = 0 (filled slots) and mutex = 1 (buffer lock). The producer does wait(empty), wait(mutex), add, signal(mutex), signal(full); the consumer does wait(full), wait(mutex), remove, signal(mutex), signal(empty).
Why must wait(empty) come before wait(mutex)?
If the producer locks first and the buffer is full, it sleeps holding the lock, so the consumer can never enter to free a slot: deadlock.
Why are three semaphores needed and not just one?
They solve three different problems: mutex gives mutual exclusion on the buffer, empty makes the producer wait when the buffer is full, and full makes the consumer wait when it is empty.
What is the readers–writers problem?
Many readers may access shared data at the same time, but a writer needs exclusive access. The first variant gives readers priority (writers may starve); the second gives waiting writers priority (readers may starve).
Where are reader–writer locks used in practice?
Caches, in-memory indexes, configuration data, file systems and databases (shared/exclusive locks). POSIX offers pthread_rwlock_t, Java ReentrantReadWriteLock, C++ std::shared_mutex.
Why does the naive dining philosophers solution deadlock?
If all philosophers pick up their left chopstick at once, each holds one and waits for the next, forming a cycle of waits. All four Coffman conditions hold.
Give three ways to avoid deadlock in dining philosophers.
Allow at most N − 1 philosophers to compete; make philosophers pick up the lower-numbered chopstick first (or odd/even asymmetry); or pick up both chopsticks only when both are free, inside a critical section (monitor solution).
Is a deadlock-free solution always starvation-free?
No. In the monitor solution of dining philosophers, two neighbours can alternate eating so that the philosopher between them never gets both chopsticks.
Summary
The classical problems are small models of real patterns: queues between workers (bounded buffer), shared read-mostly data (readers–writers), and processes needing multiple resources (dining philosophers).
Bounded buffer:
empty = n,full = 0,mutex = 1. Wait on the counting semaphore before the mutex, or you get deadlock. Signal order does not matter.Readers–writers: the first reader locks writers out and the last reader lets them in. Readers' preference can starve writers; writers' preference can starve readers. Real systems use reader–writer locks.
Dining philosophers: the naive solution deadlocks (we saw it hang in C). Fix it by limiting the table to N − 1, ordering the chopsticks, or taking both at once. Deadlock-free is not the same as starvation-free.
The sleeping barber is a bounded queue that turns customers away when full.
Getting these right with raw semaphores requires care with every line. The next chapter, Monitors, shows a higher-level construct that makes such code easier to get right.