These are the notes for CS Fundamentals for Placements, episode 27. Last episode gave us semaphores. Today we use them on the five classic puzzles that every operating-systems exam and interview asks about: the bounded-buffer (producer-consumer) problem, the readers-writers problem (with reader preference and writer preference), the dining philosophers problem and its deadlock-free solutions, the sleeping barber problem and the cigarette smokers problem. For each one you will see the obvious code fail live, understand why, and build the semaphore-based solution in C. Every term is explained in plain words the first time it appears, and there is a full glossary at the end.
All program outputs below are real: every C program was compiled with gcc 13.3 -O2 (the SyntaxPilot compiler's flags: gcc -O2 -Wno-unused-result main.c -o main -lm; on Linux, glibc has the pthread and semaphore functions built in) and run on Linux x86-64 with 2 CPUs on 3 November 2026. Programs with a race print different numbers on every run; the numbers shown are from one run, and the text says so.
Refresher: the tools we need
- A thread is one flow of execution inside a program; threads of one program share global variables.
pthread_createstarts a thread running a function,pthread_joinwaits for it to finish (episode 20). - A race condition is a bug where the result depends on the timing of threads;
count++is really three steps (load, add, store), so two threads can overwrite each other's update (episode 24). - A critical section is code that touches shared data; only one thread should be inside at a time. That rule is mutual exclusion (episode 24).
- Busy waiting (spinning) means waiting in a loop that keeps checking a condition, like
while (count == 0) { }. It burns CPU time doing nothing useful. - An atomic operation happens as one indivisible step; no other thread can see it half-done.
__sync_fetch_and_add(&x, 1)is an atomicx++(episode 25). - A semaphore is a shared integer counter that threads may change only through two atomic operations (episode 26). In C it is the type
sem_tfrom<semaphore.h>:
| Operation | Other names | What it does |
|---|---|---|
sem_wait(&s) |
wait, P, down | If s is 0, sleep until it is positive; then subtract 1 |
sem_post(&s) |
signal, V, up | Add 1; if a thread is sleeping on s, wake one |
sem_init(&s, 0, n) |
— | Set the starting value to n (the 0 means "shared between threads of this process") |
- A counting semaphore can hold any value 0, 1, 2, ...: it counts free things, like 5 free seats. A binary semaphore only takes 0 or 1. A binary semaphore used as a lock (start at 1,
sem_waitto lock,sem_postto unlock) is a mutex (short for mutual exclusion). - A sleeping
sem_waitdoes not busy-wait: the OS takes the thread off the CPU until asem_postwakes it.
The five problems
| Problem | Real-life story | What it teaches |
|---|---|---|
| Bounded buffer (producer-consumer) | A dhaba cook and waiter share a counter that holds 5 plates | Counting semaphores for "free" and "full", a mutex for the shelf, and the order of waits |
| Readers-writers | Students read the exam results board; a clerk updates it | Sharing between readers; reader vs writer preference; starvation |
| Dining philosophers | Five friends, five chopsticks, a round table | Deadlock from circular wait, and four ways to prevent it |
| Sleeping barber | One barber, one chair, 3 waiting chairs | Waking a sleeping server, turning customers away, a counter guarded by a mutex |
| Cigarette smokers | Three people making chai, each with one ingredient | Why naive "grab what you need" deadlocks; helper threads that match the pair |
Problem 1: the bounded buffer (producer-consumer)
The story
At a busy dhaba the cook makes plates and puts them on the pass counter; the waiter takes them to the tables. The counter holds only 5 plates.
- A producer is anything that creates data for someone else (the cook).
- A consumer is anything that uses that data up (the waiter).
- A buffer is a storage area between them; a bounded buffer has a fixed size (5 plates). Real ones: a printer queue, a keyboard buffer, a pipe between two programs (
ls | sort), a video player's download buffer. - Two rules: if the buffer is full, the producer must wait; if it is empty, the consumer must wait. This is the bounded-buffer problem, also called the producer-consumer problem.
The obvious attempt: a shared count (fails)
#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
#define N 5 // the counter holds 5 plates
volatile int count = 0, cooked = 0, taken = 0; // count: plates now
void *cook(void *a) { // producer: puts plates
while (cooked < 1000000) {
while (count == N) { } // counter full: wait
count++; cooked++; // put one plate
}
return NULL;
}
void *waiter(void *a) { // consumer: takes plates
while (1) {
while (count == 0) { } // counter empty: wait
count--; taken++; // take one plate
}
}
int main(void) {
pthread_t c, w;
pthread_create(&c, NULL, cook, NULL); pthread_create(&w, NULL, waiter, NULL);
sleep(2); // give them 2 seconds
printf("cooked %d, taken %d, on counter %d\n", cooked, taken, count);
}
One real run (it differs every run):
cooked 1000000, taken 941020, on counter 0
Over several runs we saw three kinds of wrong answer: plates vanished (taken < cooked, counter 0), phantom plates (taken > cooked: the waiter took plates that were never cooked), and both threads stuck early (cooked and taken stop far below a million). The only consistent thing is that it's wrong.
Why it fails
count++(cook) andcount--(waiter) race. Each is load, add, store:
count = 3
cook: load 3 waiter: load 3
cook: store 4 waiter: store 2
→ count = 2, but 3 plates are really there
- So
while (count == N) { }andwhile (count == 0) { }check a number that can be wrong: the cook may think the counter is full when it isn't, the waiter may take a plate that isn't there, or both may wait forever. - And while waiting they busy-wait, burning a whole CPU core.
We need three things: a count of free places the cook can sleep on, a count of plates the waiter can sleep on, and a lock on the shelf itself. Three semaphores.
The semaphore solution
| Semaphore | Meaning | Starts at |
|---|---|---|
empty |
free places on the counter | N (5) |
full |
plates ready to take | 0 |
mutex |
lock on the shelf (the buffer's in/out positions) | 1 |
producer: consumer:
sem_wait(&empty); // a free place sem_wait(&full); // a plate
sem_wait(&mutex); sem_wait(&mutex);
put item in buffer take item from buffer
sem_post(&mutex); sem_post(&mutex);
sem_post(&full); // one more plate sem_post(&empty); // one more free place
Live, first without the header:
main.c:3:1: error: unknown type name ‘sem_t’
3 | sem_t empty, full, mutex; pthread_t c, w; int cooked = 0, taken = 0;
| ^~~~~
main.c: In function ‘cook’:
main.c:6:9: warning: implicit declaration of function ‘sem_wait’ [-Wimplicit-function-declaration]
6 | sem_wait(&empty); // wait for a free place
| ^~~~~~~~
main.c:7:37: warning: implicit declaration of function ‘sem_post’ [-Wimplicit-function-declaration]
7 | sem_wait(&mutex); cooked++; sem_post(&mutex); // put a plate
| ^~~~~~~~
main.c: In function ‘main’:
main.c:19:5: warning: implicit declaration of function ‘sem_init’ [-Wimplicit-function-declaration]
19 | sem_init(&empty, 0, 5); sem_init(&full, 0, 0); sem_init(&mutex, 0, 1);
| ^~~~~~~~
sem_t, sem_wait, sem_post and sem_init are declared in <semaphore.h>. Without it the compiler doesn't know the type (an error) and guesses that the functions return int (the "implicit declaration" warnings). With the include:
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
sem_t empty, full, mutex; pthread_t c, w; int cooked = 0, taken = 0;
void *cook(void *a) { // producer
for (int i = 0; i < 1000000; i++) {
sem_wait(&empty); // wait for a free place
sem_wait(&mutex); cooked++; sem_post(&mutex); // put a plate
sem_post(&full); // one more plate
}
return NULL; }
void *waiter(void *a) { // consumer
for (int i = 0; i < 1000000; i++) {
sem_wait(&full); // wait for a plate
sem_wait(&mutex); taken++; sem_post(&mutex); // take a plate
sem_post(&empty); // one more free place
}
return NULL; }
int main(void) { // empty = 5 free places, full = 0 plates, mutex = 1
sem_init(&empty, 0, 5); sem_init(&full, 0, 0); sem_init(&mutex, 0, 1);
pthread_create(&c, NULL, cook, NULL); pthread_create(&w, NULL, waiter, NULL);
pthread_join(c, NULL); pthread_join(w, NULL);
printf("cooked %d, taken %d\n", cooked, taken);
}
Output (3 of 3 runs):
cooked 1000000, taken 1000000
Every plate is accounted for. When the counter is full, sem_wait(&empty) puts the cook to sleep; when it is empty, sem_wait(&full) puts the waiter to sleep. No busy waiting, and the counts are changed atomically by the semaphores, so no update is lost.
With one producer and one consumer touching only their own counters, the mutex is not strictly needed; with several producers or consumers sharing a real array with in and out positions, it is essential (see the mini project).
The trap: the order of the waits
Swap the cook's two waits:
sem_wait(&mutex); // lock FIRST (wrong order)
sem_wait(&empty); cooked++; sem_post(&mutex); // put a plate
The program hangs forever (we stopped it after 5 seconds with timeout, exit code 124). When the counter is full, the cook sleeps inside sem_wait(&empty) while holding the mutex. The waiter needs the mutex to take a plate, so it sleeps too. Each waits for the other: a deadlock. Rule: wait on the counting semaphore first, take the mutex last. (The order of the two sem_post calls does not matter.)
Problem 2: readers-writers
The story
Exam results are pinned on the college notice board. Fifty students can read it at once; that's harmless. But when the clerk pins a correction, nobody should read a half-changed sheet.
- A reader is a thread that only reads shared data.
- A writer is a thread that changes it, and needs it all to itself.
- The rule: any number of readers together, or exactly one writer, never both. This is the readers-writers problem, published by P. J. Courtois, F. Heymans and D. L. Parnas in Communications of the ACM in October 1971. Their paper gave two solutions: one that keeps readers' delay small, and one that lets writers write as early as possible. Databases, file systems and in-memory caches face this all the time.
The obvious attempt: one lock for everyone (correct, but slow)
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>
#include <time.h>
sem_t board; // 1 = the notice board is free
double now(void) { struct timespec t; clock_gettime(CLOCK_MONOTONIC, &t);
return t.tv_sec + t.tv_nsec / 1e9; }
void *reader(void *a) {
sem_wait(&board); // lock the board
sleep(1); // read it for 1 second
sem_post(&board); // unlock
return NULL; }
int main(void) {
sem_init(&board, 0, 1);
pthread_t t[5]; double start = now();
for (int i = 0; i < 5; i++) pthread_create(&t[i], NULL, reader, NULL);
for (int i = 0; i < 5; i++) pthread_join(t[i], NULL);
printf("5 readers took %.1f s\n", now() - start);
}
Output:
5 readers took 5.0 s
Correct, but the five readers queued one at a time, although reading together is harmless. (now() returns the time in seconds from a steady clock; clock_gettime comes from <time.h>.)
Reader preference: the first reader locks, the last reader unlocks
readcount: how many readers are reading right now.board: locked while a writer writes, or while any reader reads.mutex: protectsreadcountitself (it is shared, soreadcount++could race).
reader: writer:
sem_wait(&mutex); sem_wait(&board);
if (++readcount == 1) sem_wait(&board); write
sem_post(&mutex); sem_post(&board);
read
sem_wait(&mutex);
if (--readcount == 0) sem_post(&board);
sem_post(&mutex);
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>
#include <time.h>
sem_t board, mutex; int readcount = 0; // readers reading right now
double now(void) { struct timespec t; clock_gettime(CLOCK_MONOTONIC, &t);
return t.tv_sec + t.tv_nsec / 1e9; }
void *reader(void *a) {
sem_wait(&mutex);
if (++readcount == 1) sem_wait(&board); // first reader locks writers out
sem_post(&mutex);
sleep(1); // read it for 1 second
sem_wait(&mutex);
if (--readcount == 0) sem_post(&board); // last reader lets writers in
sem_post(&mutex);
return NULL; }
int main(void) {
sem_init(&board, 0, 1); sem_init(&mutex, 0, 1);
pthread_t t[5]; double start = now();
for (int i = 0; i < 5; i++) pthread_create(&t[i], NULL, reader, NULL);
for (int i = 0; i < 5; i++) pthread_join(t[i], NULL);
printf("5 readers took %.1f s\n", now() - start);
}
Output:
5 readers took 1.0 s
The catch: writer starvation
Three readers keep coming back (10 reads each, 0.3 s per read, started 0.1 s apart), then one writer arrives:
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>
sem_t board, mutex; int readcount = 0, reads = 0;
void *reader(void *a) {
for (int k = 0; k < 10; k++) { // each reader reads 10 times
sem_wait(&mutex); reads++;
if (++readcount == 1) sem_wait(&board); // first reader locks
sem_post(&mutex);
usleep(300000); // read for 0.3 s
sem_wait(&mutex); if (--readcount == 0) sem_post(&board); sem_post(&mutex);
}
return NULL; }
void *writer(void *a) {
printf("writer arrives after %d reads\n", reads);
sem_wait(&board); printf("writer gets the board after %d reads\n", reads);
sem_post(&board); return NULL; }
int main(void) { // 3 readers, 0.1 s apart, then one writer
sem_init(&board, 0, 1); sem_init(&mutex, 0, 1); pthread_t r, w;
for (int i = 0; i < 3; i++) { pthread_create(&r, NULL, reader, NULL); usleep(100000); }
pthread_create(&w, NULL, writer, NULL); pthread_join(w, NULL);
}
Output (5 of 5 runs):
writer arrives after 4 reads
writer gets the board after 30 reads
There was always at least one reader on the board, so readcount never fell to 0 and board was never released until every reader had finished. With readers that never stop, the writer would wait forever. Waiting forever while other threads keep making progress is starvation. This is why the first solution is called reader preference (the "first readers-writers problem"): readers never wait for each other, even if a writer is waiting.
Writer preference: a gate a waiting writer closes
Add a semaphore gate that every new reader must pass on the way in. A writer that wants the board closes the gate first, so readers already inside finish but no new reader starts:
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>
sem_t board, mutex, gate; int readcount = 0, reads = 0;
void *reader(void *a) {
for (int k = 0; k < 10; k++) { // each reader reads 10 times
sem_wait(&gate); sem_wait(&mutex); reads++; // pass the gate
if (++readcount == 1) sem_wait(&board); // first reader locks
sem_post(&mutex); sem_post(&gate);
usleep(300000); // read for 0.3 s
sem_wait(&mutex); if (--readcount == 0) sem_post(&board); sem_post(&mutex);
}
return NULL; }
void *writer(void *a) {
printf("writer arrives after %d reads\n", reads);
sem_wait(&gate); // close the gate: no NEW readers
sem_wait(&board); printf("writer gets the board after %d reads\n", reads);
sem_post(&board); sem_post(&gate); return NULL; }
int main(void) { // 3 readers, 0.1 s apart, then one writer
sem_init(&board, 0, 1); sem_init(&mutex, 0, 1); sem_init(&gate, 0, 1); pthread_t r, w;
for (int i = 0; i < 3; i++) { pthread_create(&r, NULL, reader, NULL); usleep(100000); }
pthread_create(&w, NULL, writer, NULL); pthread_join(w, NULL);
}
Output (5 of 5 runs):
writer arrives after 4 reads
writer gets the board after 4 reads
No new read started while the writer waited.
With many writers, the full writer-preference solution (the second solution in the 1971 paper) keeps a writecount: the first waiting writer closes the gate (readtry), the last writer reopens it, so a stream of writers keeps readers out:
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>
// Writer preference (Courtois, Heymans, Parnas 1971, second solution)
sem_t board, rmutex, wmutex, readtry;
int readcount = 0, writecount = 0, reads = 0;
void *reader(void *a) {
for (int k = 0; k < 10; k++) {
sem_wait(&readtry); // blocked while writers wait
sem_wait(&rmutex); reads++;
if (++readcount == 1) sem_wait(&board);
sem_post(&rmutex);
sem_post(&readtry);
usleep(300000); // read for 0.3 s
sem_wait(&rmutex);
if (--readcount == 0) sem_post(&board);
sem_post(&rmutex);
}
return NULL;
}
void *writer(void *arg) {
int id = *(int *)arg;
sem_wait(&wmutex);
if (++writecount == 1) sem_wait(&readtry); // first writer shuts readers out
sem_post(&wmutex);
printf("writer %d waits after %d reads\n", id, reads);
sem_wait(&board);
printf("writer %d writes after %d reads\n", id, reads);
usleep(200000); // write for 0.2 s
sem_post(&board);
sem_wait(&wmutex);
if (--writecount == 0) sem_post(&readtry); // last writer lets readers in
sem_post(&wmutex);
return NULL;
}
int main(void) {
sem_init(&board, 0, 1); sem_init(&rmutex, 0, 1);
sem_init(&wmutex, 0, 1); sem_init(&readtry, 0, 1);
pthread_t r[3], w[2]; int wid[2] = {1, 2};
for (int i = 0; i < 3; i++) { pthread_create(&r[i], NULL, reader, NULL); usleep(100000); }
for (int i = 0; i < 2; i++) pthread_create(&w[i], NULL, writer, &wid[i]);
for (int i = 0; i < 3; i++) pthread_join(r[i], NULL);
for (int i = 0; i < 2; i++) pthread_join(w[i], NULL);
printf("total reads %d\n", reads);
}
Output (the two writers' order differs between runs):
writer 1 waits after 4 reads
writer 2 waits after 4 reads
writer 1 writes after 4 reads
writer 2 writes after 4 reads
total reads 30
Both writers wrote before any new read began. The trade-off: now readers can starve if writers keep arriving. A fair (no-starvation) version makes readers and writers pass one shared gate in arrival order: a reader passes and immediately reopens it, a writer holds it until it gets the board (exactly the single-writer gate program above).
| Solution | Readers share? | Who can starve? |
|---|---|---|
| One lock for everyone | No | Nobody (but slow) |
| Reader preference | Yes | Writers |
| Writer preference | Yes | Readers |
| Fair (one queue/gate in arrival order) | Yes | Nobody |
Problem 3: the dining philosophers
The story
Five friends sit at a round table with a big plate of Hakka noodles and only five chopsticks, one between each pair. To eat, a friend needs both the chopstick on the left and the one on the right. If everyone gets hungry together and picks up the left chopstick, everyone then waits for the right one, which the neighbour is holding. Nobody eats, and nobody ever puts a chopstick down.
A deadlock is a set of threads each waiting for something that another thread in the set is holding, so none of them can ever continue. Here the waits form a closed circle: a circular wait.
History: Edsger Dijkstra first formulated the problem in 1965 as a student exam exercise about computers competing for access to tape drives; Tony Hoare soon gave it its present form, with five philosophers alternating between thinking and eating with forks.
The obvious code: left first, then right (deadlock)
Each chopstick is a binary semaphore that starts at 1 (free).
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>
sem_t chop[5]; int ate = 0; // chopstick i: left of friend i
void *diner(void *arg) {
int i = *(int *)arg, left = i, right = (i + 1) % 5;
sem_wait(&chop[left]); // pick up the left chopstick
usleep(100000); // look around for 0.1 s
sem_wait(&chop[right]); // pick up the right chopstick
printf("friend %d eats\n", i);
__sync_fetch_and_add(&ate, 1); // atomic ate++ (episode 25)
sem_post(&chop[right]); sem_post(&chop[left]);
return NULL; }
int main(void) {
pthread_t t[5]; int id[5];
for (int i = 0; i < 5; i++) sem_init(&chop[i], 0, 1);
for (int i = 0; i < 5; i++) {
id[i] = i; pthread_create(&t[i], NULL, diner, &id[i]); }
sleep(2); // wait 2 seconds, then check
printf("after 2 s: %d of 5 friends ate\n", ate);
}
Output (3 of 3 runs):
after 2 s: 0 of 5 friends ate
Not a single "eats" line: every thread holds its left chopstick and sleeps waiting for its right one. (The 0.1 s pause makes the bad timing happen every time; without it the deadlock is rarer, which is worse, because it then appears only in production.)
F0 holds 0, wants 1 → F1 holds 1, wants 2 → F2 holds 2, wants 3 → F3 holds 3, wants 4 → F4 holds 4, wants 0 → (back to F0)
Fix 1: resource ordering (resource hierarchy)
Number the chopsticks and always pick up the lower-numbered one first. Friends 0 to 3 are unchanged, but friend 4 (chopsticks 4 and 0) must pick up 0 first, so friend 4 competes with friend 0 for chopstick 0 and holds nothing while waiting. The circle can't close.
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>
sem_t chop[5]; int ate = 0; // chopstick i: left of friend i
void *diner(void *arg) {
int i = *(int *)arg, left = i, right = (i + 1) % 5;
int first = left < right ? left : right; // lower number
int second = left < right ? right : left; // higher number
sem_wait(&chop[first]); // ALWAYS the lower number first
usleep(100000); // look around for 0.1 s
sem_wait(&chop[second]);
printf("friend %d eats\n", i);
__sync_fetch_and_add(&ate, 1); // atomic ate++ (episode 25)
sem_post(&chop[right]); sem_post(&chop[left]);
return NULL; }
int main(void) {
pthread_t t[5]; int id[5];
for (int i = 0; i < 5; i++) sem_init(&chop[i], 0, 1);
for (int i = 0; i < 5; i++) {
id[i] = i; pthread_create(&t[i], NULL, diner, &id[i]); }
sleep(2); // wait 2 seconds, then check
printf("after 2 s: %d of 5 friends ate\n", ate);
}
Output (the eating order differs between runs):
friend 3 eats
friend 2 eats
friend 1 eats
friend 0 eats
friend 4 eats
after 2 s: 5 of 5 friends ate
Fix 2: at most n - 1 at the table
A counting semaphore seats starts at 4: a friend must take a seat before touching a chopstick. With at most 4 friends holding chopsticks and 5 chopsticks, at least one of them can always get both.
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>
sem_t chop[5], seats; int ate = 0; // seats: at most 4 sit at once
void *diner(void *arg) {
int i = *(int *)arg, left = i, right = (i + 1) % 5;
sem_wait(&seats); // take one of 4 seats
sem_wait(&chop[left]); // pick up the left chopstick
usleep(100000); // look around for 0.1 s
sem_wait(&chop[right]); // pick up the right chopstick
printf("friend %d eats\n", i);
__sync_fetch_and_add(&ate, 1); // atomic ate++ (episode 25)
sem_post(&chop[right]); sem_post(&chop[left]); sem_post(&seats);
return NULL; }
int main(void) {
pthread_t t[5]; int id[5];
for (int i = 0; i < 5; i++) sem_init(&chop[i], 0, 1);
sem_init(&seats, 0, 4); // 4 seats for 5 friends
for (int i = 0; i < 5; i++) {
id[i] = i; pthread_create(&t[i], NULL, diner, &id[i]); }
sleep(2); // wait 2 seconds, then check
printf("after 2 s: %d of 5 friends ate\n", ate);
}
Output:
friend 3 eats
friend 2 eats
friend 1 eats
friend 0 eats
friend 4 eats
after 2 s: 5 of 5 friends ate
Fix 3: the asymmetric solution
Even-numbered friends pick up the left chopstick first, odd-numbered friends the right one first. Neighbours then compete for the same first chopstick, so nobody can hold one while the neighbour holds the other in a full circle.
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>
sem_t chop[5]; int ate = 0;
void *diner(void *arg) {
int i = *(int *)arg, left = i, right = (i + 1) % 5;
int first = (i % 2 == 0) ? left : right; // even: left first
int second = (i % 2 == 0) ? right : left; // odd: right first
sem_wait(&chop[first]);
usleep(100000);
sem_wait(&chop[second]);
printf("friend %d eats\n", i);
__sync_fetch_and_add(&ate, 1);
sem_post(&chop[second]); sem_post(&chop[first]);
return NULL; }
int main(void) {
pthread_t t[5]; int id[5];
for (int i = 0; i < 5; i++) sem_init(&chop[i], 0, 1);
for (int i = 0; i < 5; i++) {
id[i] = i; pthread_create(&t[i], NULL, diner, &id[i]); }
sleep(2);
printf("after 2 s: %d of 5 friends ate\n", ate);
}
Output (order differs):
friend 1 eats
friend 3 eats
friend 0 eats
friend 2 eats
friend 4 eats
after 2 s: 5 of 5 friends ate
Fix 4: a waiter (arbitrator)
A central arbitrator (the waiter, for example a single mutex) hands out chopsticks: you get both or none. Simple and deadlock-free, but only one friend picks up at a time, which reduces parallelism.
Deadlock-free is not starvation-free
All four fixes prevent deadlock, but a slow friend can still keep losing the race for chopsticks and stay hungry: starvation. Resource ordering in particular is not fair. (A fully distributed answer, the Chandy/Misra solution of 1984, uses "clean" and "dirty" chopsticks passed by request messages to avoid starvation too.)
| Fix | Breaks the circle by | Downside |
|---|---|---|
| Resource ordering | Everyone takes the lower number first | Needs all resources known and numbered in advance; can be unfair |
| At most n - 1 seated | One extra semaphore | Limits how many try at once |
| Asymmetric (odd/even) | Neighbours pick in opposite orders | Specific to the ring shape |
| Waiter (arbitrator) | Both chopsticks or none | Central bottleneck, less parallel |
Problem 4: the sleeping barber
The story
A barber shop has one barber, one barber chair and N waiting chairs (here 3). When there are no customers, the barber naps in his chair. An arriving customer wakes the barber if he is asleep, sits in a waiting chair if one is free, and leaves if all waiting chairs are taken. Dijkstra described this problem in 1965, in his report Cooperating Sequential Processes (EWD-123). It models a server (a support agent, a print server, a web server thread) that sleeps when idle and a waiting room of limited size.
What can go wrong without care
- A customer checks the room, decides to wait, but before sitting the barber checks the room, finds it empty and falls asleep: the barber sleeps while a customer waits (a race).
- Two customers both see one free chair and both sit (a race on the chair count).
The semaphore solution
| Name | Kind | Meaning | Starts at |
|---|---|---|---|
customers |
counting semaphore | customers waiting (the barber sleeps on it) | 0 |
barber |
semaphore | the barber is ready to cut (the customer waits on it) | 0 |
mutex |
binary semaphore | protects waiting |
1 |
waiting |
int | occupied waiting chairs | 0 |
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>
#define CHAIRS 3 // waiting chairs
sem_t customers, barber, mutex; // waiting customers, barber ready, lock
int waiting = 0, served = 0, left_shop = 0;
void *barber_fn(void *a) {
while (1) {
sem_wait(&customers); // sleep until a customer arrives
sem_wait(&mutex); waiting--; sem_post(&mutex);
sem_post(&barber); // call the customer to the chair
usleep(50000); // cut hair for 0.05 s
__sync_fetch_and_add(&served, 1);
}
}
void *customer(void *a) {
sem_wait(&mutex);
if (waiting < CHAIRS) { // a free chair: sit and wake the barber
waiting++; sem_post(&customers); sem_post(&mutex);
sem_wait(&barber); // wait to be called
} else { // shop full: leave
left_shop++; sem_post(&mutex);
}
return NULL;
}
int main(void) {
sem_init(&customers, 0, 0); sem_init(&barber, 0, 0); sem_init(&mutex, 0, 1);
pthread_t b, c[20];
pthread_create(&b, NULL, barber_fn, NULL);
for (int i = 0; i < 20; i++) { // 20 customers, one every 0.02 s
pthread_create(&c[i], NULL, customer, NULL); usleep(20000);
}
for (int i = 0; i < 20; i++) pthread_join(c[i], NULL);
usleep(100000); // let the last haircut finish
printf("served %d, left because the shop was full %d\n", served, left_shop);
}
Output (one run; 3 of 3 runs gave the same numbers, but they depend on timing):
served 11, left because the shop was full 9
Customers arrive every 0.02 s, a haircut takes 0.05 s, so the 3 chairs fill up and some customers leave. Everyone who sat down got a haircut, and the barber never slept while someone waited. This solution is deadlock-free; customers are not served in strict arrival order, which a FIFO queue would add.
Problem 5: the cigarette smokers (told with chai)
The story
The textbook version, described by Suhas Patil in 1971, has three smokers and the ingredients tobacco, paper and matches. Our version: making chai needs tea leaves, milk and sugar. Three people sit at a table; each has an endless supply of one ingredient. A supplier, the agent, repeatedly puts two different ingredients on the table. The person who has the third should take both, make chai, and signal the agent to put out the next pair. Rule of the puzzle: the agent's code may not be changed (just as an operating system can't be rewritten for each new application).
The naive solution deadlocks
Each person waits on the two ingredient semaphores they need:
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>
// 0 = tobacco, 1 = paper, 2 = matches. The agent posts INGREDIENTS.
sem_t item[3], agent; int rounds = 0;
void *agent_fn(void *a) {
for (int r = 0; r < 100; r++) {
sem_wait(&agent);
int m = r % 3; // missing ingredient
sem_post(&item[(m + 1) % 3]); sem_post(&item[(m + 2) % 3]);
}
return NULL;
}
void *smoker_fn(void *arg) { // I have ingredient i
int i = *(int *)arg;
while (1) {
sem_wait(&item[(i + 1) % 3]); // grab the first one I need
usleep(1000);
sem_wait(&item[(i + 2) % 3]); // grab the second one I need
rounds++; sem_post(&agent);
}
}
int main(void) {
sem_init(&agent, 0, 1); pthread_t a, s[3]; int id[3] = {0, 1, 2};
for (int i = 0; i < 3; i++) sem_init(&item[i], 0, 0);
for (int i = 0; i < 3; i++) pthread_create(&s[i], NULL, smoker_fn, &id[i]);
pthread_create(&a, NULL, agent_fn, NULL);
sleep(2);
printf("after 2 s: %d of 100 rounds\n", rounds);
}
Output (3 of 3 runs):
after 2 s: 0 of 100 rounds
The agent put out, say, paper and matches. The person who needs paper + matches grabbed paper, but meanwhile the person who needs matches + tobacco grabbed matches. Each holds one ingredient and waits for one that will never come: deadlock.
The fix: helper threads ("pushers")
Add one helper thread per ingredient. A helper wakes when its ingredient lands on the table, checks under a mutex what else is already there, and then wakes exactly the one person who can use the pair (or records that its ingredient is waiting). The agent is unchanged.
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>
// 0 = tobacco, 1 = paper, 2 = matches. The agent code is unchanged.
const char *name[3] = {"tobacco", "paper", "matches"};
sem_t item[3], agent, mutex, smoker[3];
int on_table[3] = {0, 0, 0}, rounds = 0, id[3] = {0, 1, 2};
void *agent_fn(void *a) {
for (int r = 0; r < 100; r++) {
sem_wait(&agent);
int m = r % 3; // missing ingredient
sem_post(&item[(m + 1) % 3]); sem_post(&item[(m + 2) % 3]);
}
return NULL;
}
void *pusher(void *arg) { // one helper per ingredient
int i = *(int *)arg;
while (1) {
sem_wait(&item[i]); // ingredient i was put down
sem_wait(&mutex);
int a = (i + 1) % 3, b = (i + 2) % 3;
if (on_table[a]) { on_table[a] = 0; sem_post(&smoker[b]); }
else if (on_table[b]) { on_table[b] = 0; sem_post(&smoker[a]); }
else on_table[i] = 1; // first of the pair: remember it
sem_post(&mutex);
}
}
void *smoker_fn(void *arg) { // I have ingredient i
int i = *(int *)arg;
while (1) { sem_wait(&smoker[i]); rounds++; sem_post(&agent); }
}
int main(void) {
sem_init(&agent, 0, 1); sem_init(&mutex, 0, 1); pthread_t t;
for (int i = 0; i < 3; i++) { sem_init(&item[i], 0, 0); sem_init(&smoker[i], 0, 0); }
for (int i = 0; i < 3; i++) {
pthread_create(&t, NULL, pusher, &id[i]);
pthread_create(&t, NULL, smoker_fn, &id[i]);
}
pthread_create(&t, NULL, agent_fn, NULL);
sleep(2);
printf("after 2 s: %d of 100 rounds\n", rounds);
}
Output (3 of 3 runs):
after 2 s: 100 of 100 rounds
History: Patil argued, using a Petri-net proof, that the problem cannot be solved with Dijkstra's semaphores alone and that a more powerful primitive was needed (his rules also banned conditional statements). David Parnas later showed the proof is inadequate once arrays of semaphores are allowed, and gave a solution with helper processes. Our helpers use if statements, which the strict original rules forbid; the lesson is the same: don't let consumers grab resources one at a time when they need a matching pair.
If the agent may be changed, the simplest answer is to let the agent post the semaphore of the one person who has the missing ingredient:
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
// ingredients: 0 = tobacco, 1 = paper, 2 = matches
const char *name[3] = {"tobacco", "paper", "matches"};
sem_t agent, smoker[3]; // smoker[i] has ingredient i forever
int rounds = 0;
void *agent_fn(void *a) {
for (int r = 0; r < 6; r++) {
sem_wait(&agent); // wait until the table is empty
int missing = r % 3; // put the OTHER two on the table
printf("agent puts everything except %s\n", name[missing]);
sem_post(&smoker[missing]); // wake exactly the smoker who has it
}
return NULL;
}
void *smoker_fn(void *arg) {
int i = *(int *)arg;
while (1) {
sem_wait(&smoker[i]); // wait for my two missing ingredients
printf(" smoker with %s rolls and smokes\n", name[i]);
rounds++;
sem_post(&agent); // table is empty again
}
}
int main(void) {
sem_init(&agent, 0, 1);
pthread_t a, s[3]; int id[3] = {0, 1, 2};
for (int i = 0; i < 3; i++) { sem_init(&smoker[i], 0, 0); pthread_create(&s[i], NULL, smoker_fn, &id[i]); }
pthread_create(&a, NULL, agent_fn, NULL);
pthread_join(a, NULL);
sem_wait(&agent); // wait for the last smoker to finish
printf("%d rounds, no deadlock\n", rounds);
}
agent puts everything except tobacco
smoker with tobacco rolls and smokes
agent puts everything except paper
smoker with paper rolls and smokes
agent puts everything except matches
smoker with matches rolls and smokes
agent puts everything except tobacco
smoker with tobacco rolls and smokes
agent puts everything except paper
smoker with paper rolls and smokes
agent puts everything except matches
smoker with matches rolls and smokes
6 rounds, no deadlock
The whole chain
| Puzzle | Obvious attempt | What broke | Fix |
|---|---|---|---|
| Bounded buffer | Shared count + busy-wait loops |
Race on count; wrong numbers |
empty = N, full = 0, mutex = 1 |
| Bounded buffer (order) | mutex before empty |
Sleeps holding the lock: deadlock | Counting semaphore first, mutex last |
| Readers-writers | One lock for everyone | Readers queue (5.0 s) | readcount: first locks, last unlocks (1.0 s) |
| Readers-writers (fairness) | Reader preference | Writer starves (30 reads) | Writer preference gate (4 reads) or a fair queue |
| Dining philosophers | Left, then right | Circular wait: 0 of 5 ate | Ordering, n - 1 seats, asymmetry, waiter |
| Sleeping barber | Check, then sleep | Barber sleeps on a waiting customer | customers, barber, mutex + waiting |
| Cigarette smokers | Grab each needed ingredient | Two people each hold one: deadlock | Helper threads that match the pair |
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
sem_t without the header |
error: unknown type name 'sem_t' (+ implicit declaration of function 'sem_wait' warnings) |
Semaphores are declared in <semaphore.h> |
#include <semaphore.h> |
sem_wait(&mutex) before sem_wait(&empty) |
The program hangs forever | The producer sleeps holding the lock | Counting semaphore first, mutex last |
Wrong starting values, e.g. mutex = 0 |
Hangs at the first sem_wait(&mutex) |
A lock that starts locked | empty = N, full = 0, mutex = 1 |
| Every philosopher picks the left chopstick first | after 2 s: 0 of 5 friends ate |
Circular wait | Ordering, n - 1 seats, asymmetry or a waiter |
| Calling reader preference fair | writer gets the board after 30 reads |
readcount never reaches 0 |
Writer preference or a fair gate |
Updating readcount without its mutex |
Writers and readers inside together (rarely, so hard to find) | readcount++ is a race |
Guard it with mutex |
Forgetting a sem_post on one path (e.g. the "shop full" branch) |
Everyone else hangs | The lock is never released | Every path that waits must post |
A shared counter updated with plain ++ from several threads |
Counts slightly off | Race | Atomic add or a mutex |
Mini project: two cooks and two waiters
Change the bounded-buffer program to use a real array int buf[5] with in and out positions, and run two cook threads and two waiter threads (each cook makes 500,000 numbered plates, each waiter takes 500,000). Each waiter adds up the plate numbers it takes; print the total and compare with the sum of all plate numbers. Then delete the sem_wait(&mutex) / sem_post(&mutex) pairs and run it again: two cooks can now write to the same in slot, and the totals go wrong. This shows why the mutex is needed once there is more than one producer or consumer.
Practice
1. Two cooks and two waiters share the bounded buffer. Is one mutex still enough?
Solution
Yes. empty and full already work for any number of producers and consumers. The single mutex makes sure only one thread at a time changes buf, in and out. (You could use two mutexes, one for producers on in and one for consumers on out, to let a producer and a consumer work at once; with one mutex it is simpler and still correct.)
2. Trace readcount and board for: reader R1 arrives, R2 arrives, writer W arrives, R1 leaves, R2 leaves (reader preference).
Solution
R1: readcount 0 → 1, it is the first reader, so it takes board (1 → 0). R2: readcount → 2, no wait on board. W: sem_wait(&board) finds 0 and sleeps. R1 leaves: readcount → 1, not the last. R2 leaves: readcount → 0, last reader, sem_post(&board) wakes W, which writes.
3. Prove that with 4 seats, 5 dining philosophers can't deadlock.
Solution
In a deadlock, every philosopher at the table holds their left chopstick and waits for their right one, which their right-hand neighbour holds. So the right-hand neighbour must also be seated and stuck, and so must their right-hand neighbour, all the way round the table: a circular wait needs all 5 philosophers. With only 4 seats, one philosopher is always missing from the circle, so the circle can't close. Concretely: the seated philosopher whose right-hand neighbour is the one standing finds that right chopstick free, eats, and releases both.
4. In the sleeping barber, what changes with 0 waiting chairs?
Solution
CHAIRS = 0: a customer gets a haircut only if they arrive exactly when the barber is free and the waiting count is 0 (the customer who is called in is no longer "waiting"); otherwise they leave immediately. The code still works; the shop just turns away many more customers.
5. A bounded buffer of size 3 starts empty. The producer runs 5 times in a row without the consumer running. What happens, and what are empty and full?
Solution
The first 3 puts succeed: empty goes 3 → 0 and full goes 0 → 3. The 4th sem_wait(&empty) finds 0 and the producer sleeps until the consumer takes an item. The 5th put hasn't started.
6. Why is the asymmetric solution deadlock-free?
Solution
A deadlock needs a circle where every philosopher holds one chopstick and waits for the next. In the asymmetric scheme, two neighbours (an even and an odd one) reach for the same chopstick first. Whichever loses waits holding nothing, so at least one link of the circle is missing.
Quick quiz
sem_t empty, full, mutex;
// buffer holds 8 items, starts empty
sem_init(&empty, 0, ?);
sem_init(&full, 0, ?);
sem_init(&mutex, 0, ?);
A. empty = 0, full = 8, mutex = 1 B. empty = 8, full = 0, mutex = 1 C. empty = 8, full = 8, mutex = 0 D. empty = 1, full = 1, mutex = 1
Answer
B. An empty buffer has 8 free places (empty = 8) and 0 items (full = 0). The mutex starts at 1 (unlocked); with mutex = 0 nobody could ever enter.
Interview questions
- Explain the producer-consumer problem and its semaphore solution. Three semaphores:
empty(free slots, N),full(filled slots, 0),mutex(1). Producer: wait(empty), wait(mutex), put, signal(mutex), signal(full); consumer mirrors it. - What happens if the producer waits on the mutex before
empty? When the buffer is full it sleeps holding the mutex, and the consumer can never take an item: deadlock. - What is the readers-writers problem? Many readers may read together, a writer needs exclusive access.
- Reader preference vs writer preference? Reader preference lets readers in while any reader is reading (writers can starve); writer preference blocks new readers once a writer waits (readers can starve).
- How do you avoid starvation in readers-writers? A fair queue (one gate in arrival order), as in the no-starve solution.
- Why do the dining philosophers deadlock? Every philosopher holds one fork and waits for the next: a circular wait.
- Give deadlock-free solutions to the dining philosophers. Resource ordering, at most n - 1 at the table, odd/even asymmetry, an arbitrator (waiter).
- Is a deadlock-free solution always starvation-free? No; a philosopher can keep losing the race for forks.
- What is the sleeping barber problem modelling? A server that sleeps when idle and a limited waiting queue; customers who find it full leave.
- What is the cigarette smokers problem about? A supplier provides two of three resources; naive consumers deadlock by grabbing one each; helper threads (or signalling the right consumer) fix it. Patil (1971) claimed semaphores alone couldn't solve it; Parnas showed otherwise with arrays of semaphores.
- What is a real-world readers-writers lock?
pthread_rwlock_tin POSIX threads,ReentrantReadWriteLockin Java.
Glossary
| Term | Meaning in plain words | Example |
|---|---|---|
| Thread | One flow of execution inside a program, sharing its globals | cook, waiter |
| Shared data | Data more than one thread reads or writes | count |
| Race condition | The result depends on the timing of threads | plates vanish |
| Critical section | Code that touches shared data | putting a plate on the shelf |
| Mutual exclusion | At most one thread in the critical section at a time | one hand on the shelf |
| Busy waiting | Waiting in a loop that keeps checking, burning CPU | while (count == 0) { } |
| Atomic operation | One indivisible step no thread can see half-done | __sync_fetch_and_add |
| Semaphore | A shared counter changed only by atomic wait and signal | sem_t empty |
sem_wait (wait, P) |
If 0, sleep; then subtract 1 | take a free place |
sem_post (signal, V) |
Add 1 and wake a sleeper | one more plate |
sem_init |
Set a semaphore's starting value | sem_init(&empty, 0, 5) |
<semaphore.h> |
The C header that declares sem_t and its functions |
#include <semaphore.h> |
| Counting semaphore | Holds 0, 1, 2, ...: counts free things | empty = 5 |
| Binary semaphore | Holds only 0 or 1 | a chopstick |
| Mutex | A lock: one holder at a time (a binary semaphore used as a lock) | mutex = 1 |
| Producer | A thread that creates data for others | the cook |
| Consumer | A thread that uses data up | the waiter |
| Buffer | Storage between a producer and a consumer | the pass counter |
| Bounded buffer | A buffer with a fixed size | 5 plates |
| Bounded-buffer / producer-consumer problem | Synchronizing producers and consumers on a bounded buffer | dhaba counter |
empty / full |
Semaphores counting free slots / filled slots | 5 / 0 at start |
| Reader | A thread that only reads shared data | a student at the board |
| Writer | A thread that changes shared data, needs it alone | the clerk |
| Readers-writers problem | Many readers together or one writer alone | exam results board |
readcount |
Number of readers reading right now | first locks, last unlocks |
| Reader preference | Readers never wait while other readers read; writers can starve | first readers-writers problem |
| Writer preference | A waiting writer blocks new readers; readers can starve | the gate / readtry |
writecount |
Number of writers waiting or writing | first closes, last opens the gate |
| Fair (no-starve) solution | Everyone passes one gate in arrival order | no one starves |
| Starvation | A thread waits forever while others keep making progress | writer after 30 reads |
| Deadlock | Threads each wait for something another holds; none can continue | 0 of 5 ate |
| Circular wait | The waits form a closed circle | F0 → F1 → ... → F4 → F0 |
| Dining philosophers problem | n philosophers, n forks, each needs both neighbours' forks | five friends, five chopsticks |
| Resource ordering (hierarchy) | Always take resources in increasing number order | lower chopstick first |
| Asymmetric solution | Odd and even philosophers pick in opposite orders | even left, odd right |
| Arbitrator (waiter) | A central party that grants both resources or none | the waiter |
| Deadlock-free solution | One that can never deadlock | the four fixes |
| Sleeping barber problem | A barber sleeps when idle; limited waiting chairs; full → leave | barber shop |
| Cigarette smokers problem | An agent supplies 2 of 3 ingredients; the holder of the 3rd must get them | chai makers |
| Agent | The supplier thread in the smokers problem, whose code can't change | puts milk + sugar |
| Pusher (helper thread) | A helper that sees an ingredient and wakes the right smoker | one per ingredient |
| Semaphore-based solution | Synchronization built only from semaphores (wait/signal) | all of today's fixes |
pthread_rwlock_t |
The POSIX threads library's built-in readers-writer lock | real code |
Summary
- Bounded buffer (producer-consumer):
empty = N,full = 0,mutex = 1; producer waits onempty, consumer onfull; always wait on the counting semaphore before the mutex, or it deadlocks. - Readers-writers: readers share via
readcount(first in locks the board, last out unlocks it). Reader preference can starve writers (live: the writer waited for all 30 reads); writer preference closes a gate to new readers (live: after 4 reads) and can starve readers; a fair queue starves nobody. - Dining philosophers: everyone taking the left fork first gives a circular wait and deadlock (live: 0 of 5 ate). Deadlock-free fixes: resource ordering, at most n - 1 seated, asymmetric order, an arbitrator. Deadlock-free does not mean starvation-free.
- Sleeping barber:
customers,barberand amutexguarding thewaitingcount; turn customers away when the chairs are full. - Cigarette smokers: naive smokers deadlock by grabbing one ingredient each; helper threads that match the pair fix it without changing the agent.
Next episode: Deadlocks 1: conditions, resource allocation graphs and prevention: the four Coffman conditions, resource allocation graphs, wait-for graphs, prevention by breaking each condition, and livelock.