The Project | About Us | Contribute | Donations | License

HOME

You already have the tools: mutexes, semaphores, condition variables, read/write locks and barriers. But knowing what each primitive does is not the same as knowing how to combine them. A mutex protects one piece of data; coordinating two flows that depend on each other requires composing several primitives in a specific order, and that is where intuition fails and the hangs appear.

Fortunately there is nothing to invent. Between 1965 and 1971, Dijkstra, Courtois, Hoare and others identified a handful of problems that distil the essential difficulties of coordination, and they have been the discipline's common vocabulary ever since. When an engineer says "this is a producer-consumer", four colleagues understand in two seconds the structure of the code, where the risk is and what solution to try. When they say "we have writer starvation here", they know exactly what to measure.

Besides — and this is what makes them worth studying — almost every real problem is a variant of one of them: a job queue is producer-consumer, a cache that is queried and refreshed is readers-writers, a group of threads waiting for requests is the sleeping barber, and a service that takes two locks is a version of the philosophers. This lesson develops all four, each with its statement, its naive solutions and why they fail, the correct solution commented line by line, and its direct translation into a piece of Meteora. We finish with a table linking each real pattern to its classic problem.

Why these problems are the common language
Producer-consumer with a bounded buffer
The three-semaphore solution, step by step
The variant with a mutex and a condition variable
The lost wakeup and the order of the waits
Readers-writers: the statement
Reader priority and writer starvation
Writer priority and what rwlock really does
Dining philosophers
The sleeping barber
Which real pattern corresponds to each problem

Why these problems are the common language

The four problems are not academic exercises: each one isolates a different difficulty that does not appear in the others.

Problem	Difficulty it isolates	Question it answers
Producer-consumer	Coordinating different paces with finite resources	How do I wait for there to be room, or for there to be data?
Readers-writers	Asymmetric access to the same resource	How do I let many through and then just one, without anybody going hungry?
Dining philosophers	Acquiring several resources at once	How do I stop everyone waiting in a circle?
Sleeping barber	Coordinating a server with intermittent clients	How do I sleep when there is no work and wake up when it arrives?

The four are irreducible to one another: knowing how to solve producer-consumer tells you nothing about how to stop the philosophers from blocking, and knowing about the philosophers does not help with writer starvation. That is why there are four and not one.

And the statements with philosophers, barbers and forks may look frivolous, but the frivolity is deliberate: an abstract statement ("five processes compete for five resources shared with their neighbors") forces you to read it three times, whereas one with philosophers needing two forks is understood at once and frees up attention for what matters, which is reasoning about correctness.

Producer-consumer with a bounded buffer

The statement. A producer generates items and deposits them in a buffer of capacity N. A consumer removes and processes them. The two go at different, unpredictable paces. Three things have to be guaranteed:

The producer does not write into a full buffer: it waits for room.
The consumer does not read from an empty buffer: it waits for data.
Neither corrupts the buffer while the other is touching it.

In Meteora it is literally the relationship between the ingestor and the aggregator: the former receives readings from the 800 stations in bursts, and the latter processes them at its own pace. If the buffer were infinite, a traffic spike would exhaust the RAM; if there were no buffer, every reading would have to wait for the aggregator and datagrams would be lost. The bounded buffer is the engineering solution, and this problem is how it is implemented correctly.

Before the solution, let us see why the naive version is not enough. With a single mutex:

/* INCORRECT: it protects the buffer but does not coordinate the paces */
void produce(struct Reading r) {
    pthread_mutex_lock(&m);
    if (count == N) { pthread_mutex_unlock(&m); return; }   /* the reading is lost! */
    buffer[tail] = r; tail = (tail + 1) % N; count++;
    pthread_mutex_unlock(&m);
}

The mutex guarantees the buffer is not corrupted, but it does not solve the waiting. The producer has only two bad options: discard the reading (data loss) or spin in a loop checking count (burning CPU, and moreover with the mutex held that would be a deadlock). What is missing is a way to sleep until there is room. That is where semaphores come in.

The three-semaphore solution, step by step

The canonical solution uses three primitives, each with a well-defined role. This separation of responsibilities is what has to be understood:

Primitive	Initial value	What it represents	Who does `wait`	Who does `post`
`empty`	N	Free slots in the buffer	Producer	Consumer
`full`	0	Available items	Consumer	Producer
`mutex`	1	Exclusive access to the buffer	Both	Both

The key idea: empty and full count complementary resources. It is always true that empty + full ≤ N, and when both flows are outside their critical sections, the equality is exact. The producer consumes slots and produces items; the consumer does the opposite.

/* prod_cons.c — the Reading queue between the ingestor and the aggregator */
#define N 64                             /* capacity of the circular buffer */

struct Reading buffer[N];
int head = 0, tail = 0;                  /* circular buffer indices */
sem_t empty;                             /* free slots      → initially N */
sem_t full;                              /* available items → initially 0 */
sem_t mutex;                             /* mutual exclusion → initially 1 */

void *ingestor(void *arg) {              /* PRODUCER */
    for (int i = 0; ; i++) {
        struct Reading r = { .station_id = 41 + (i % 800),
                             .timestamp = 1756684800 + i,
                             .temperature = 21.0f + (i % 50) * 0.1f };
        sem_wait(&empty);                /* (1) is there room? if not, I SLEEP */
        sem_wait(&mutex);                /* (2) enter the critical section */
        buffer[tail] = r;                /* (3) deposit */
        tail = (tail + 1) % N;
        sem_post(&mutex);                /* (4) leave the critical section */
        sem_post(&full);                 /* (5) notify: there is one more item */
    }
    return NULL;
}

void *aggregator(void *arg) {            /* CONSUMER */
    double sum = 0; long n = 0;
    while (1) {
        sem_wait(&full);                 /* (1) is there an item? if not, I SLEEP */
        sem_wait(&mutex);                /* (2) enter the critical section */
        struct Reading r = buffer[head];     /* (3) remove */
        head = (head + 1) % N;
        sem_post(&mutex);                /* (4) leave the critical section */
        sem_post(&empty);                /* (5) notify: there is one more slot */

        sum += r.temperature;            /* (6) process OUTSIDE the mutex */
        if (++n % 10000 == 0)
            printf("[aggregator] %ld readings, average %.2f C\n", n, sum / n);
        usleep(80);                      /* simulates the cost of aggregating */
    }
    return NULL;
}
/* main(): sem_init(&empty,0,N), sem_init(&full,0,0), sem_init(&mutex,0,1),
   create the two threads and join them. */

Let us follow the reasoning step by step, because every line is where it is for a reason.

The producer's step (1): sem_wait(&empty). It decrements the slot counter. If it was 0 — the buffer is full — the thread goes to sleep and the kernel takes it out of the ready queue. When the consumer removes an item and does sem_post(&empty), this thread will wake up. CPU consumed while waiting: zero. It is exactly the backpressure we saw with pipes in the IPC lesson, but implemented by us and with whatever size we decide.

Step (2): sem_wait(&mutex). We already know there is room, but the consumer may be touching the buffer right now; the mutex protects the head and tail indices and the array's contents. Steps (3) and (4): a minimal critical section, only the write and the index advance: neither the construction of the Reading nor the printf is inside, because the shorter it is, the less the other one waits.

Step (5): sem_post(&full). It increments the item counter and, if the consumer was asleep waiting for data, wakes it. Note that it comes after the sem_post(&mutex): if it came before, the consumer would wake up and immediately block on the mutex we still hold, causing a pointless wakeup and two extra context switches.

The consumer is symmetric, and that symmetry is the beauty of the solution: it waits on full, takes the mutex, removes, releases the mutex, and does post on empty. Each one waits for what the other produces.

The consumer's step (6): processing outside the mutex. The usleep(80) that simulates the aggregation work comes after releasing the mutex. If it were inside, the producer could not deposit anything while the consumer processed, and the buffer would be of absolutely no use. It is a very common and very expensive mistake.

Running it, the observable behavior confirms the theory: the producer, which could generate millions of readings per second, is limited to the ~12,500/s the consumer processes, and the memory used never exceeds the 64 × 24 = 1,536 bytes of the buffer. Without a single line of code devoted to controlling the pace.

The variant with a mutex and a condition variable

Semaphores are elegant, but they have a practical drawback: the state is spread across three objects and you cannot inspect it. If you want to know how many items there are in order to publish a metric, you cannot ask the semaphore reliably. The variant with a mutex and condition variables keeps the state explicit:

# prod_cons.py — the same queue with a Python monitor
import threading, time, collections

class ReadingQueue:
    def __init__(self, capacity=64):
        self._cap = capacity
        self._buf = collections.deque()
        self._lock = threading.Lock()
        self._has_space = threading.Condition(self._lock)   # ← they share the lock
        self._has_data  = threading.Condition(self._lock)

    def put(self, reading):
        with self._lock:
            while len(self._buf) == self._cap:      # ← WHILE, never IF
                self._has_space.wait()
            self._buf.append(reading)
            self._has_data.notify()                 # wake ONE consumer

    def take(self):
        with self._lock:
            while not self._buf:                    # ← WHILE, never IF
                self._has_data.wait()
            r = self._buf.popleft()
            self._has_space.notify()                # wake ONE producer
            return r

    def occupancy(self):                            # ← this is NOT possible with semaphores
        with self._lock:
            return len(self._buf), self._cap

# The ingestor calls queue.put(reading) in a loop; the aggregator calls
# queue.take() followed by the aggregation work. And from outside:
#   n, cap = queue.occupancy(); print(f"occupancy: {n}/{cap}")

Three design details worth attention:

Two condition variables, a single lock. threading.Condition(self._lock) makes both share the same Lock, and that is essential because the state they watch is the same buffer: using two different locks would break mutual exclusion.

Two conditions instead of one. A single one with notify_all() could be used, but then every notification would also wake threads waiting on the opposite condition, which would check their while, see that it does not hold and go back to sleep. With two, each notify() wakes exactly the right kind of thread; with 8 producers and 8 consumers, the performance difference is a factor of 3 or 4.

occupancy() is the decisive advantage of this variant. Being able to answer "the buffer is at 62/64" lets you raise an alert that the consumer cannot keep up before losses start. It is the causal metric we talked about when closing module 2, and with semaphores you do not have it.

Compared:

	Three semaphores	Mutex + condition variables
Inspectable state	No	Yes
Complex waiting conditions	Hard	Natural (any predicate)
Risk of swapping the `wait`s	High (deadlock)	Low
Performance	Slightly better	Very similar
Available in high-level languages	Sometimes	Always

The practical recommendation: use mutexes and condition variables unless the problem fits exactly into the mould of counting resources. It is more verbose, but it expresses the waiting condition explicitly, allows arbitrary conditions and does not have the trap of the next section.

The lost wakeup and the order of the `wait`s

Two traps in this problem deserve their own section because they are the ones that really hang systems.

The order of the `wait`s in the semaphore solution

Look at the producer again and try swapping the first two lines:

/* ⚠ GUARANTEED DEADLOCK */
sem_wait(&mutex);      /* (1) first I take the mutex */
sem_wait(&empty);      /* (2) and THEN I wait for room */

A trace of the disaster, with the buffer full:

Time	Producer	Consumer
t1	`sem_wait(&mutex)` → enters
t2	`sem_wait(&empty)` → 0: sleeps
t3		`sem_wait(&full)` → passes
t4		`sem_wait(&mutex)` → 0: sleeps
t5	asleep holding the mutex	asleep waiting for the mutex

Total deadlock. The producer sleeps waiting for a slot without having released the mutex; the consumer, the only one who can create that slot, cannot get in because the mutex is held. Neither will ever wake. From this comes a rule that holds for all of concurrent programming:

Never block waiting for a condition while you hold a lock that somebody else needs in order to make it true.

In the correct solution, the sem_wait(&empty) happens before taking the mutex, so if the producer sleeps, it sleeps without blocking anyone; and in the consumer, sem_wait(&full) comes before sem_wait(&mutex). The mnemonic is count before you enter. Note the contrast: the variant with condition variables does not have this trap, because pthread_cond_wait releases the mutex automatically when it goes to sleep. That is exactly the problem they were invented for.

The lost wakeup

The second trap affects condition variables. Consider this incorrect version of the consumer:

/* ⚠ LOST WAKEUP */
if (count == 0)                               /* (1) I check: it is empty */
    pthread_mutex_unlock(&m);                 /* (2) I release the mutex */
    pthread_cond_wait(&has_data, &m);         /* (3) and I go to sleep */

Between (2) and (3) there is a window. If the producer deposits an item right there and does signal, nobody is asleep yet: the signal is lost into the void. When the consumer reaches (3), it will sleep waiting for a notification that has already been issued, and if the producer does not produce again, it will sleep forever with an item available in the buffer.

The solution is built into the primitive: pthread_cond_wait(&cond, &mutex) releases the mutex and queues the thread atomically, with no window between the two. That is why you have to pass it the mutex; that is why the mutex has to be held when you call it; and that is why you never release it by hand beforehand.

There is also the variant of lost wakeup that the while solves: if the consumer wakes up but another consumer got the item first, the condition is false again. With if it would carry on over an empty buffer; with while it goes back to sleep. Both mechanisms — the atomicity of wait and the while loop — are necessary, and they protect against different things.

Readers-writers: the statement

The statement. A shared resource is accessed by two kinds of flow: readers, which only consult it and can do so several at a time with no problem, and writers, which modify it and need exclusive access with no other writers and no readers. The asymmetry is the whole problem: with a simple mutex it would be trivial (one at a time), but it would waste the parallelism among readers. In Meteora it is the relationship between meteo-api and the aggregator over /dev/shm/meteora-cache:

Flow	Role	Frequency	Duration
4 `meteo-api` workers	Readers	1,200/s	~40 µs (they walk `latest[]`)
`aggregator`	Writer	1/hour	~15 ms (recomputes every average)

With a simple mutex, the 1,200 accesses per second would be serialized: 1,200 × 40 µs = 48 ms of CPU per second on a single core, with the other three workers waiting; with shared access, all four read at once and the real cost is 12 ms per core.

Stated precisely, the problem demands several simultaneous readers if there is no writer, and one writer exclusively with no other writers and no readers. And here is the conflict that has no single answer: who has preference when both are waiting? From that come the two classic variants.

Reader priority and writer starvation

Courtois's first solution (1971) gives preference to readers: if there are readers inside, a new reader enters without waiting, even if there is a writer in the queue.

/* readers_writers_v1.c — READER priority */
sem_t resource;         /* exclusive access to the resource; initially 1 */
sem_t count_mutex;      /* protects n_readers;                initially 1 */
int   n_readers = 0;

void *reader(void *arg) {
    sem_wait(&count_mutex);
    n_readers++;
    if (n_readers == 1) sem_wait(&resource);   /* FIRST reader: shut writers out */
    sem_post(&count_mutex);

    read_cache();                 /* ---- READING: several at a time here ---- */

    sem_wait(&count_mutex);
    n_readers--;
    if (n_readers == 0) sem_post(&resource);   /* LAST reader: let writers in */
    sem_post(&count_mutex);
    return NULL;
}

void *writer(void *arg) {
    sem_wait(&resource);          /* wait until there are NO readers and no writers */
    recompute_averages(&cache);   /* ---- WRITING: on my own ---- */
    sem_post(&resource);
    return NULL;
}

The mechanism, called the turnstile lock, is ingenious: only the first reader acquires the resource semaphore and only the last one out releases it, so the ones in between come and go freely as long as there is at least one inside. The writer, meanwhile, sees the resource busy for that whole time.

Here is the problem, and it is serious. A trace with readers arriving continuously:

Time	Event	`n_readers`	Writer's state
t1	Reader A arrives	1	–
t2	The writer arrives	1	waits in `sem_wait(&resource)`
t3	Reader B arrives (jumps the queue!)	2	waits
t4	A leaves	1	waits
t5	Reader C arrives	2	waits
t6	B leaves	1	waits
t7	Reader D arrives	2	waits
...	there is never an instant with `n_readers == 0`	≥1	waits forever

This is writer starvation, and all it takes is for readers to arrive more often than their duration for there never to be a gap. It is not a rare laboratory case: measuring with 8 continuous readers and 1 writer over 30 seconds, v1 completes 3 writes, with a maximum wait of 11.4 seconds. For Meteora that would mean serving data from eleven seconds ago as a matter of course. Unacceptable.

The conceptual problem is that this solution satisfies mutual exclusion and progress but violates bounded waiting — Dijkstra's third requirement, which we stated in 03-01: there is no limit at all to the number of readers that can overtake the writer.

Writer priority and what `rwlock` really does

Courtois's second solution reverses the preference: as soon as a writer announces that it wants in, no new reader gets through. Those already inside finish, and the writer goes in next.

/* readers_writers_v2.c — WRITER priority */
sem_t resource;         /* initially 1 */
sem_t read_mutex;       /* protects n_readers; initially 1 */
sem_t write_mutex;      /* protects n_writers; initially 1 */
sem_t queue;            /* GATE: blocks new readers; initially 1 */
int   n_readers = 0, n_writers = 0;

void *reader(void *arg) {
    sem_wait(&queue);             /* (1) is a writer waiting? then I stop here */
    sem_wait(&read_mutex);
    n_readers++;
    if (n_readers == 1) sem_wait(&resource);
    sem_post(&read_mutex);
    sem_post(&queue);             /* (2) release the gate straight away */

    read_cache();                 /* ---- shared READING ---- */

    sem_wait(&read_mutex);
    n_readers--;
    if (n_readers == 0) sem_post(&resource);
    sem_post(&read_mutex);
    return NULL;
}

void *writer(void *arg) {
    sem_wait(&write_mutex);
    n_writers++;
    if (n_writers == 1) sem_wait(&queue);     /* (3) CLOSE the gate to new readers */
    sem_post(&write_mutex);
    sem_wait(&resource);          /* (4) wait for the current readers to leave */
    recompute_averages(&cache);   /* ---- exclusive WRITING ---- */
    sem_post(&resource);
    sem_wait(&write_mutex);
    n_writers--;
    if (n_writers == 0) sem_post(&queue);     /* (5) reopen the gate */
    sem_post(&write_mutex);
    return NULL;
}

The new piece is the queue semaphore, which acts as an entrance gate: when the first writer arrives (line 3) it closes it, readers arriving afterwards are blocked at line (1) without having touched n_readers, those already inside finish, n_readers reaches 0, resource is released and the writer enters at line (4). The numbers change radically:

With the same experiment as before, v2 completes 29,847 writes with a maximum wait of 1.2 ms, against v1's 3 writes and 11.4 seconds, at the cost of 2.3 % fewer reads. An obviously good trade. But now the risk is reversed: if writers arrive continuously, readers go hungry, because the gate never reopens. The third solution (Hoare, 1974) alternates the turns strictly and produces starvation of neither kind, at the cost of more complexity.

What `pthread_rwlock_t` really does

Now that you have seen the two solutions, the natural question is what the primitive you used in the previous lesson actually implements. The answer matters because the default behavior is not the one people assume:

Implementation	Default behavior	How to change it
glibc / Linux	Reader priority (v1: writers can starve)	`pthread_rwlockattr_setkind_np(&attr, PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP)`
macOS	Writer priority	Not configurable
Windows (SRW)	No ordering guarantee	Not configurable
`std::shared_mutex` (C++17)	Unspecified by the standard	Depends on the implementation

That is: a pthread_rwlock_t on Linux, as it comes, has exactly the starvation problem we have just measured. If your writer is infrequent but needs to run on time — like Meteora's aggregator, which has to publish the averages as soon as it computes them — you have to ask for writer priority explicitly:

pthread_rwlockattr_t attr;
pthread_rwlockattr_init(&attr);
pthread_rwlockattr_setkind_np(&attr, PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP);
pthread_rwlock_init(&cache.rwlock, &attr);

The NONRECURSIVE suffix warns about the downside: with this setting, a thread that already holds the read lock and asks for another one can block if a writer is waiting. That self-deadlock is the reason it is not the default; if your code never nests read locks — and it should not — it is safe.

And for Meteora's extreme case, with 4,320,000 reads per write, the best solution is no rwlock at all but the double buffer: the aggregator builds a complete new cache and, when it finishes, publishes its pointer with an atomic write in release mode; the readers do an acquire read of the pointer and work on whichever version they got, taking no lock at all. Zero contention for the readers, and the writer never waits. The cost is the memory of two copies and deciding when to free the old one, which is the problem RCU solves inside the Linux kernel.

Dining philosophers

The statement. Five philosophers sit around a round table. Between each pair there is one fork: five forks in total. Each philosopher alternates between thinking and eating, and to eat they need the two adjacent forks, the one on their left and the one on their right.

graph TD
    F0((Philosopher 0)) --- T0[Fork 0] --- F1((Philosopher 1))
    F1 --- T1[Fork 1] --- F2((Philosopher 2))
    F2 --- T2[Fork 2] --- F3((Philosopher 3))
    F3 --- T3[Fork 3] --- F4((Philosopher 4))
    F4 --- T4[Fork 4] --- F0

What this problem isolates, and none of the previous ones contains, is acquiring several resources at once: with a single resource there is no difficulty; with two, deadlock appears. The naive solution is the one anybody would write:

/* ⚠ IT DEADLOCKS. Given patience, always. */
sem_t fork_sem[5];     /* each one initialized to 1 */

void *philosopher(void *arg) {
    int i = (int)(long)arg;
    while (1) {
        think();
        sem_wait(&fork_sem[i]);            /* (1) take the fork on my left */
        sem_wait(&fork_sem[(i + 1) % 5]);  /* (2) take the one on my right */
        eat();
        sem_post(&fork_sem[i]);
        sem_post(&fork_sem[(i + 1) % 5]);
    }
}

Why it deadlocks. If the five philosophers execute line (1) before any of them reaches line (2) — which happens as soon as the scheduler alternates them at that point — each one holds a fork and waits for their neighbor's: 0 has fork 0 and waits for fork 1, which philosopher 1 holds; 1 waits for 2; 2 for 3; 3 for 4; and philosopher 4 waits for fork 0, which philosopher 0 holds.

The chain of waits closes into a cycle, and none of them will release their fork because they are all blocked waiting for the second one. It is a textbook deadlock. Exactly why it happens — which four conditions must hold simultaneously for such a cycle to be possible, and how to break each one — is the content of Deadlocks, which will also solve this case with systematic prevention. Here we stick to the three practical solutions that are actually used.

Solution 1: asymmetry (the most used). Have the even-numbered philosophers take the left one first and the odd-numbered ones the right one first:

void *philosopher(void *arg) {
    int i = (int)(long)arg;
    int left = i, right = (i + 1) % 5;
    while (1) {
        think();
        if (i % 2 == 0) { sem_wait(&fork_sem[left]); sem_wait(&fork_sem[right]); }
        else            { sem_wait(&fork_sem[right]); sem_wait(&fork_sem[left]); }
        eat();
        sem_post(&fork_sem[left]); sem_post(&fork_sem[right]);
    }
}

With this change, the waiting cycle is impossible: at least two adjacent philosophers compete for the same fork as their first request, and one of the two gets it and moves on. It is the concrete expression of the most important engineering rule against deadlocks: always acquire resources in a consistent global order. Here it is achieved by numbering the forks and having everybody ask for the lower-numbered one first — which is exactly what the even/odd split produces.

Solution 2: one philosopher fewer. Allow at most four to sit down at a time, with a counting semaphore:

sem_t seats;                      /* sem_init(&seats, 0, 4) — 4, not 5! */

sem_wait(&seats);                 /* at most 4 try to eat at a time */
sem_wait(&fork_sem[left]);
sem_wait(&fork_sem[right]);
eat();
sem_post(&fork_sem[right]); sem_post(&fork_sem[left]);
sem_post(&seats);

The reasoning is pure counting: with 4 philosophers competing for 5 forks, by the pigeonhole principle at least one gets both, will be able to eat, release them and unjam the chain. A single change from 5 to 4 eliminates the deadlock completely, and it is the easiest solution to verify and the one that touches the least code.

Solution 3: take both forks atomically. A global mutex protecting the operation of picking up both:

pthread_mutex_t table = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t  can_eat[5];
int available[5] = {1,1,1,1,1};

void take_forks(int i) {
    int left = i, right = (i + 1) % 5;
    pthread_mutex_lock(&table);
    while (!available[left] || !available[right])   /* ← either BOTH, or neither */
        pthread_cond_wait(&can_eat[i], &table);
    available[left] = available[right] = 0;
    pthread_mutex_unlock(&table);
}

void put_forks(int i) {
    int left = i, right = (i + 1) % 5;
    pthread_mutex_lock(&table);
    available[left] = available[right] = 1;
    pthread_cond_signal(&can_eat[(i + 4) % 5]);   /* notify my two neighbors */
    pthread_cond_signal(&can_eat[(i + 1) % 5]);
    pthread_mutex_unlock(&table);
}

Here the root of the problem is removed: a philosopher never gets to hold just one fork, because either they get both in one atomic operation or they get none and go to sleep. With no partial acquisition there is no hold and wait, and with no holding there is no possible cycle. Compared:

Solution	Eliminates the deadlock	Concurrency	Complexity	Starvation?
Naive	No	–	Minimal	–
Even/odd asymmetry	Yes	High	Very low	Possible in theory
One philosopher fewer	Yes	Medium (4 of 5)	Minimal	No
Both at once	Yes	High	Medium	Possible without turn-taking

The translation to Meteora is direct and not at all theoretical. If the aggregator takes the /dev/shm/meteora-cache lock first and then the day file's lock, while a meteo-api worker takes them in the opposite order, you have exactly five philosophers with two forks. And that specific case, with its diagnosis and its solution, is the one we will solve in the next lesson.

The sleeping barber

The statement. A barbershop has one barber, one chair and N waiting chairs. If there are no customers, the barber sleeps; if one arrives and the barber is asleep, they wake him; if the barber is busy, the customer sits down to wait if there is a free chair, and if there is not, they leave. This problem isolates something the others do not touch: coordination between a server and clients that arrive intermittently, including sleeping when there is no work without burning CPU, waking when it arrives, and rejecting load when capacity is exceeded.

/* barber.c — a pool of workers waiting for requests */
#define N_CHAIRS 20                  /* queue of pending requests */

sem_t customers;                     /* waiting requests;   initially 0 */
sem_t barbers;                       /* free workers;       initially 0 */
sem_t mutex;                         /* protects the counter; initially 1 */
int   waiting = 0;

void *worker(void *arg) {            /* the BARBER */
    while (1) {
        sem_wait(&customers);        /* (1) if there are no requests, I SLEEP */
        sem_wait(&mutex);
        waiting--;                   /* (2) take one from the queue */
        sem_post(&mutex);
        sem_post(&barbers);          /* (3) notify: I am ready to serve you */
        handle_request();            /* (4) the real work */
    }
    return NULL;
}

void *http_request(void *arg) {      /* the CUSTOMER */
    sem_wait(&mutex);
    if (waiting < N_CHAIRS) {        /* (5) is there room in the queue? */
        waiting++;
        sem_post(&customers);        /* (6) wake a worker */
        sem_post(&mutex);
        sem_wait(&barbers);          /* (7) wait for one to serve me */
    } else {
        sem_post(&mutex);
        respond_503();               /* (8) queue full: reject the request */
    }
    return NULL;
}

The points that matter:

The barber sleeps without consuming CPU (1). sem_wait(&customers) with the counter at 0 blocks the thread, which leaves the ready queue. With 4 workers and no requests, meteo-api consumes 0 % CPU. It is the difference between a service you can deploy and one that burns four cores doing nothing.

The customer checks capacity before queueing (5). This detail is what turns the classic problem into a serious engineering pattern: rejecting load is a design decision, not a failure. If the queue is full, answering with an immediate 503 is far better than accepting the request and making a client who will already have given up wait 30 seconds. It is the load shedding that keeps services alive under spikes.

The double semaphore customers/barbers is a rendezvous (6, 7, 3): the customer announces their arrival and waits for confirmation, and the worker takes the request and confirms that it is serving it; without that two-way exchange, a customer could never know whether anyone had picked them up. And the waiting counter is protected by the mutex (2, 5) because it is a textbook check-then-act: checking capacity and queueing must be indivisible, or two customers would pass the check with a single free chair.

The correspondence with Meteora is exact, and it explains the thread pool from lesson 03-02:

Barbershop	`meteo-api`
Barber / chair	Worker thread from the pool, serving
Waiting chairs (N)	Queue of pending requests
An arriving customer	An incoming HTTP request
A sleeping barber	A thread blocked on the queue: 0 % CPU
A customer who leaves	A 503 Service Unavailable response

Sizing N is the engineering decision. With 4 workers at 40 µs per request, capacity is 100,000 requests/s. If N = 20 and they arrive at 1,200/s, the queue never fills in normal operation, but it absorbs bursts of up to 20 simultaneous requests. An N that is too large — 10,000, for example — is worse than a small one: it accepts requests that will take seconds to serve, by which time the client will have timed out. A large queue does not increase capacity, it only increases latency and hides the problem.

Which real pattern corresponds to each problem

This table turns the theory into a working tool: when you meet one of these scenarios, you already know which classic problem you are solving and which solution to try.

Classic problem	Real pattern	Concrete examples
Producer-consumer	A job queue between stages	`ingestor`→`aggregator`; message queues (RabbitMQ, Kafka); shell pipes; `BlockingQueue`; Go channels; the kernel's socket buffers
Readers-writers	Data read a lot, written little	`meteo-api` over the cache; a configuration cache; the kernel's routing table; database indexes; local DNS
Dining philosophers	Acquiring several resources	Transfers between two bank accounts; `aggregator` + `meteo-api` with two locks; transactions locking several rows; device allocation
Sleeping barber	A worker pool with a bounded queue	`ThreadPoolExecutor`; nginx workers; a database connection pool; `accept()` on a socket with a `backlog`

And the warning signs that should make you think of each one:

"We run out of memory when there is a traffic spike" → producer-consumer with no bounded buffer. Backpressure is missing.
"The update takes forever to apply, but the queries are fast" → readers-writers with writer starvation. Check the rwlock policy.
"The service hangs at random, and only under load" → philosophers: two locks taken in the opposite order.
"The workers consume CPU even when there are no requests" → a badly implemented barber, busy waiting instead of blocking.

Common Mistakes and Tips

Swapping the order of the waits in producer-consumer. Taking the mutex before the counting semaphore produces a guaranteed deadlock, as we saw in the trace. The rule: count before you enter, and never block waiting for a condition while you hold a lock somebody else needs in order to make it true.

Processing the item inside the critical section. If the consumer processes with the mutex held, the producer cannot deposit and the buffer is useless: you have turned a decoupled system into a strictly alternating one. Remove the item, release the lock, and process outside.

Assuming pthread_rwlock_t protects the writer from starvation. In glibc, the default behavior is reader priority, and with continuous reads the writer can wait for seconds, as we measured. If your writer has latency requirements, ask for PREFER_WRITER_NONRECURSIVE_NP explicitly.

Taking two locks in different orders in different places. It is the philosophers' problem in disguise, and it is the number one cause of hangs in production. Define a global order — by memory address, by identifier, by level — and respect it throughout the code without exceptions.

Using an unbounded queue "so as not to lose anything". An unbounded queue turns a performance problem into a memory problem: the process grows until the OOM killer kills it (module 2) and then everything is lost, not just the excess. An explicit limit with rejection or blocking is always better.

Tip: name the pattern in the code. A comment /* producer-consumer with a bounded buffer; see 03-05 */ above the structure saves half an hour for whoever reads it later. A common vocabulary is only useful if it is used.

Tip: prefer your library's primitives to reimplementing them. Python's queue.Queue, Java's BlockingQueue, Go's channels and pthread_rwlock_t already solve these problems, they have been tested by millions of runs and they often contain optimizations you would not make. Study the classic problems in order to understand what your library does and choose well, not to rewrite it.

Exercises

Exercise 1: measuring backpressure

Implement producer-consumer with three semaphores and a 64-slot buffer, with a fast producer (no delay) and a slow consumer (100 µs per item). Instrument the code to measure how many items there are in the buffer every 100 ms for 5 seconds and what the producer's real rate is. Then repeat with a buffer of 4 and another of 4,096 slots, and explain what changes and what does not.

Exercise 2: causing and measuring starvation

Implement readers-writers with both of Courtois's solutions. Launch 8 readers reading continuously (200 µs per read) and 1 writer trying to write every 100 ms. Measure over 30 seconds: completed writes, the writer's maximum wait and completed reads. Compare both solutions and compute the price in reads paid for avoiding starvation.

Exercise 3: philosophers that deadlock

Implement the naive philosophers solution and add a mechanism that detects the deadlock: a watchdog thread that checks every second whether no philosopher has eaten in the last 3 seconds and reports it. Run the program until it deadlocks and note how long it takes. Then implement the three solutions (asymmetry, one philosopher fewer, both forks at once), measure how many meals per second each one achieves and explain the differences.

Solutions

Solution 1

/* backpressure.c — the thread that instruments the buffer. The producer increments
   'produced' after its sem_post(&full); the consumer, 'consumed' after
   its sem_post(&empty). Both are _Atomic long. */
void *watcher(void *arg) {
    long prev_p = 0;
    for (int t = 0; t < 50; t++) {
        usleep(100000);
        long p = atomic_load(&produced), c = atomic_load(&consumed);
        printf("t=%.1fs  occupancy=%ld/%d  prod_rate=%ld/s\n",
               t * 0.1, p - c, CAP, (p - prev_p) * 10);
        prev_p = p;
    }
    return NULL;
}

Results with a consumer at 100 µs per item (theoretical maximum: 10,000/s):

Capacity	Steady-state occupancy	Producer's rate	Buffer memory	Latency of one item
4	4/4 (always full)	9,998/s	96 B	0.4 ms
64	64/64 (always full)	9,998/s	1.5 KB	6.4 ms
4,096	4096/4096	9,998/s	98 KB	409 ms

What changes and what does not. What does not change is the important part: the producer's rate is the same in all three cases, 9,998 items per second, that is, exactly the consumer's rate. The buffer does not increase the system's capacity by a single item, because the bottleneck is the consumer and no buffer size speeds it up. What does change is the memory and, above all, the latency: with 4,096 slots always full, an item takes 4,096 × 100 µs = 409 milliseconds to come out, against 0.4 ms with 4 slots. A thousand times worse for using a buffer a thousand times bigger.

The conclusion is emphatic and counterintuitive: a bigger buffer does not make the system faster, it makes its latency worse and hides the real problem. A buffer is only good for absorbing bursts — temporary spikes above the average — and its size should be dimensioned by the expected duration of the burst, not "just in case". If in Meteora the 800 stations send within the same second, a buffer of 800 is justified; one of 100,000 only guarantees the data arrives late.

Solution 2

Measurements on meteo-01, 8 readers of 200 µs, 1 writer every 100 ms, 30 seconds:

	v1 (reader priority)	v2 (writer priority)
Completed reads	1,198,412	1,161,238
Completed writes	3	298
Writer's average wait	7.8 s	0.4 ms
Writer's maximum wait	11.4 s	1.2 ms
Expected writes (30 s / 100 ms)	300	300

Analysis. v1 completes 3 writes out of the 300 attempted: 1 %. The writer asks for the resource and, while it waits, new readers arrive and jump ahead thanks to the turnstile lock; with 8 readers of 200 µs, the probability of there being an instant with zero readers is so low that the writer waits for whole seconds. v2 completes 298 out of 300, 99.3 %, with a maximum wait of 1.2 ms — the time it takes the readers already inside when the gate closed to finish.

The price of avoiding starvation is 37,174 reads, 3.1 %: what it costs to hold back new readers while the writer waits and works. The trade is obviously good — multiplying the writes by 99 and dividing the writer's latency by a factor of 9,500 — and that is why the previous lesson's recommendation was to configure PREFER_WRITER_NONRECURSIVE_NP explicitly on Linux. A useful note: if in your case the writers were frequent too, v2 would produce reader starvation and you would need Hoare's solution with alternating turns, or simply an ordinary mutex, because with balanced reads and writes the rwlock no longer pays off (03-04).

Solution 3

/* philosophers.c — the watchdog thread */
_Atomic long last_meal[5], total_meals = 0;

void *watcher(void *arg) {
    while (1) {
        sleep(1);
        long now = time(NULL), max_idle = 0;
        for (int i = 0; i < 5; i++) {
            long idle = now - atomic_load(&last_meal[i]);
            if (idle > max_idle) max_idle = idle;
        }
        if (max_idle >= 3) {
            printf("⚠ POSSIBLE DEADLOCK: nobody has eaten for %ld s "
                   "(%ld meals)\n", max_idle, atomic_load(&total_meals));
            return NULL;
        }
    }
}

Running the naive solution three times:

$ ./philosophers --naive   → ⚠ POSSIBLE DEADLOCK ... (1,841 meals)
$ ./philosophers --naive   → ⚠ POSSIBLE DEADLOCK ... (12 meals)
$ ./philosophers --naive   → ⚠ POSSIBLE DEADLOCK ... (94,203 meals)

The time to deadlock is completely unpredictable: 12 meals in one run, 94,203 in another. It is the non-determinism of lesson 03-01 in its purest form, and it explains why these failures pass the tests and show up in production in the small hours. With longer think() and eat(), the deadlock takes longer to arrive; if a developer tests with generous delays and production has short ones, the difference can be days versus seconds.

Performance of the three solutions (meals per second, 10 seconds, eat() of 1 ms):

Solution	Meals/s	Ratio	Comment
Naive	–	–	It deadlocks
Even/odd asymmetry	1,987	1.00×	Baseline
One philosopher fewer	1,962	0.99×	Practically the same
Both forks at once	1,943	0.98×	The global mutex costs a little

Interpretation. All three work and perform almost identically, around 1,950-1,990 meals per second, against a theoretical maximum of 2,000/s: with five philosophers and five forks, at most two can eat simultaneously (two non-adjacent ones use 4 forks and the fifth is left without a pair), so 2 × 1,000 = 2,000/s. They are at 97-99 % of the optimum. The differences are small but explainable: asymmetry adds no primitive at all, it only changes the order, so it is the fastest; one philosopher fewer adds one sem_wait per meal, which barely shows here because the real limit was already 2; and both at once serializes the taking of forks through a global mutex, which does introduce measurable contention.

The selection criterion: asymmetry is the best general option, because it costs nothing and it is the direct application of a global lock order, the technique you will use in real code. "One philosopher fewer" is the easiest to verify formally. And "both at once" is the right one when the number of resources is variable or they cannot be ordered naturally.

Conclusion

The four classic problems are the common vocabulary of concurrency because each one isolates an irreducible difficulty: coordinating paces with finite resources, sharing a resource between asymmetric accesses, acquiring several resources at once, and coordinating a server with intermittent clients.

Producer-consumer with a bounded buffer is solved with three semaphores — empty at N, full at 0 and mutex at 1 — where the first two count complementary resources and the producer consumes slots while the consumer consumes items. Its deadly trap is the order of the waits: count before you enter, because taking the mutex before waiting for a slot produces an immediate deadlock as soon as the buffer fills. The variant with a mutex and condition variables avoids that trap by construction, allows arbitrary waiting conditions and — decisively in production — lets you inspect the occupancy, which is the metric that warns of a saturated consumer before there are any losses. And we have measured what hardly anyone expects: a bigger buffer speeds nothing up, it only multiplies the latency (409 ms with 4,096 slots against 0.4 ms with 4) and hides the problem.

Readers-writers exposes a conflict with no single answer. With reader priority, the turnstile lock lets only the first one close the door and the last one open it, but it produces writer starvation: 3 writes in 30 seconds and waits of 11.4 seconds, measured. With writer priority, a gate semaphore stops new readers as soon as a writer announces itself: 298 writes and a 1.2 ms maximum wait, at the cost of 3.1 % fewer reads. And the fact to take away: pthread_rwlock_t in glibc implements the starving version by default, so you have to ask for PREFER_WRITER_NONRECURSIVE_NP by hand. For Meteora's extreme ratio, the best solution is no rwlock at all but the double buffer with atomic publication of the pointer, where readers take no lock whatsoever.

Dining philosophers isolates the acquisition of several resources, and its naive solution deadlocks unpredictably — 12 meals in one run, 94,203 in another — which is why these failures get past the tests. The three practical solutions perform almost identically (97-99 % of the theoretical optimum of 2,000 meals/s): the even/odd asymmetry, which is the direct application of a global lock order; one philosopher fewer, which by the pigeonhole principle guarantees somebody makes progress; and taking both forks atomically, which prevents partial acquisition. The sleeping barber is meteo-api's thread pool: workers that sleep at 0 % CPU waiting for requests, a bounded queue, and explicit rejection with a 503 when it fills — because rejecting load is a design decision, not a failure, and a large queue does not increase capacity, only latency.

One concrete debt remains. In the philosophers we have seen the cycle of waits and dodged it with three tricks, but we have not explained why they work or what they have in common. What exact conditions must hold at the same time for a deadlock to be possible? Can one already in progress be detected, or predicted before a resource is granted? And how do you diagnose a real service that has hung at three in the morning, when there is no philosopher in sight but an aggregator and a meteo-api that are not responding?

Classic Concurrency Problems

Contents

Why these problems are the common language

Producer-consumer with a bounded buffer

The three-semaphore solution, step by step

The variant with a mutex and a condition variable

The lost wakeup and the order of the `wait`s

The order of the `wait`s in the semaphore solution

The lost wakeup

Readers-writers: the statement

Reader priority and writer starvation

Writer priority and what `rwlock` really does

What `pthread_rwlock_t` really does

Dining philosophers

The sleeping barber

Which real pattern corresponds to each problem

Common Mistakes and Tips

Exercises

Exercise 1: measuring backpressure

Exercise 2: causing and measuring starvation

Exercise 3: philosophers that deadlock

Solutions

Solution 1

Solution 2

Solution 3

Conclusion

Operating Systems Fundamentals

Module 1: Introduction to Operating Systems

Module 2: Resource Management

Module 3: Concurrency

Module 4: File Structures

Module 5: System Protection and Security

Module 6: Virtualization and Containers

Module 7: Administration and Troubleshooting in Practice

Classic Concurrency Problems

Contents

Why these problems are the common language

Producer-consumer with a bounded buffer

The three-semaphore solution, step by step

The variant with a mutex and a condition variable

The lost wakeup and the order of the waits

The order of the waits in the semaphore solution

The lost wakeup

Readers-writers: the statement

Reader priority and writer starvation

Writer priority and what rwlock really does

What pthread_rwlock_t really does

Dining philosophers

The sleeping barber

Which real pattern corresponds to each problem

Common Mistakes and Tips

Exercises

Exercise 1: measuring backpressure

Exercise 2: causing and measuring starvation

Exercise 3: philosophers that deadlock

Solutions

Solution 1

Solution 2

Solution 3

Conclusion

Operating Systems Fundamentals

Module 1: Introduction to Operating Systems

Module 2: Resource Management

Module 3: Concurrency

Module 4: File Structures

Module 5: System Protection and Security

Module 6: Virtualization and Containers

Module 7: Administration and Troubleshooting in Practice

The lost wakeup and the order of the `wait`s

The order of the `wait`s in the semaphore solution

Writer priority and what `rwlock` really does

What `pthread_rwlock_t` really does