SyntaxPilot
Courses/CS Fundamentals for Placements/Lesson 27
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

CS Fundamentals for Placements · Lesson 27 of 90

Classic synchronization problems

bounded-buffer producer-consumerreaders-writers (reader-preference and writer-preference)dining philosophers and its deadlock-free solutionssleeping barbercigarette smokers problemsemaphore-based solutions in code

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_create starts a thread running a function, pthread_join waits 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 atomic x++ (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_t from <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_wait to lock, sem_post to unlock) is a mutex (short for mutual exclusion).
  • A sleeping sem_wait does not busy-wait: the OS takes the thread off the CPU until a sem_post wakes 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

  1. count++ (cook) and count-- (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
  1. So while (count == N) { } and while (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.
  2. 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: protects readcount itself (it is shared, so readcount++ 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

  1. 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.
  2. 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.
  3. What is the readers-writers problem? Many readers may read together, a writer needs exclusive access.
  4. 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).
  5. How do you avoid starvation in readers-writers? A fair queue (one gate in arrival order), as in the no-starve solution.
  6. Why do the dining philosophers deadlock? Every philosopher holds one fork and waits for the next: a circular wait.
  7. Give deadlock-free solutions to the dining philosophers. Resource ordering, at most n - 1 at the table, odd/even asymmetry, an arbitrator (waiter).
  8. Is a deadlock-free solution always starvation-free? No; a philosopher can keep losing the race for forks.
  9. What is the sleeping barber problem modelling? A server that sleeps when idle and a limited waiting queue; customers who find it full leave.
  10. 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.
  11. What is a real-world readers-writers lock? pthread_rwlock_t in POSIX threads, ReentrantReadWriteLock in 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 on empty, consumer on full; 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, barber and a mutex guarding the waiting count; 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.