Classic Synchronization Problems

A handful of small, carefully designed puzzles capture almost every coordination pattern real concurrent programs need. Producer-consumer is every job queue and message buffer. Readers-writers is every cache and configuration store that is read far more than it is written. Dining philosophers is every program that needs more than one lock at a time. Solving these teaches you to reason about mutual exclusion, signaling, deadlock and starvation together.

Interviewers commonly ask you to code a bounded buffer (often in Java or C, with semaphores or with a lock and condition variables), explain the starvation trade-off in readers-writers, show how dining philosophers deadlocks and give two or three fixes, and then extend a solution: multiple producers, timeouts, fairness, or a related puzzle like printing odd and even numbers from two threads. This lesson assumes the primitives from synchronization: mutexes, semaphores (wait/signal) and condition variables.

Throughout, wait(S) decrements semaphore S and blocks if it would go below zero, and signal(S) increments it and wakes a waiter. C code uses POSIX names: sem_wait and sem_post.

The producer-consumer (bounded-buffer) problem

The problem

One or more producer threads create items and put them into a shared buffer of fixed size N. One or more consumer threads take items out. The buffer is usually a circular array: an in index where the next item goes and an out index where the next item is taken, both wrapping around modulo N.

   circular buffer, N = 4
   +-------+-------+-------+-------+
   | item  | item  |       |       |
   +-------+-------+-------+-------+
     ^out            ^in
   consumers take    producers put
   at out            at in

Requirements:

1. A producer must wait if the buffer is full.
2. A consumer must wait if the buffer is empty.
3. Producers and consumers must not corrupt the buffer or the indexes: updates to them need mutual exclusion.

Real examples: a web server's request queue between an acceptor thread and worker threads; a logging library buffering lines for a writer thread; Unix pipes, which are a kernel bounded buffer between two processes; and message brokers, on a much larger scale.

Solution 1: semaphores

Use three synchronization objects:

• empty, a counting semaphore initialized to N: the number of free slots.
• full, a counting semaphore initialized to 0: the number of filled slots.
• mutex, a lock protecting the buffer and the indexes.

producer:                          consumer:
    item = produce()                   wait(full)       // any items?
    wait(empty)      // any space?     lock(mutex)
    lock(mutex)                        item = buffer[out]
    buffer[in] = item                  out = (out + 1) % N
    in = (in + 1) % N                  unlock(mutex)
    unlock(mutex)                      signal(empty)    // one more free slot
    signal(full)     // one more item  consume(item)

Here it is as a complete C program with two producers and two consumers. It uses unnamed POSIX semaphores, which are available on Linux; macOS only supports named semaphores (sem_open), so on a Mac use the condition-variable version below.

#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>

#define SIZE 4          /* buffer slots */
#define ITEMS 10        /* items each producer makes */

static int buffer[SIZE];
static int in = 0, out = 0;           /* next slot to fill / to empty */

static sem_t empty;                   /* free slots, starts at SIZE */
static sem_t full;                    /* filled slots, starts at 0 */
static pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

static void *producer(void *arg) {
    int id = *(int *)arg;
    for (int i = 0; i < ITEMS; i++) {
        int item = id * 100 + i;
        sem_wait(&empty);             /* wait for a free slot */
        pthread_mutex_lock(&mutex);
        buffer[in] = item;
        in = (in + 1) % SIZE;
        pthread_mutex_unlock(&mutex);
        sem_post(&full);              /* one more item available */
    }
    return NULL;
}

static void *consumer(void *arg) {
    long *sum = arg;
    for (int i = 0; i < ITEMS; i++) {
        sem_wait(&full);              /* wait for an item */
        pthread_mutex_lock(&mutex);
        int item = buffer[out];
        out = (out + 1) % SIZE;
        pthread_mutex_unlock(&mutex);
        sem_post(&empty);             /* one more free slot */
        *sum += item;
    }
    return NULL;
}

int main(void) {
    sem_init(&empty, 0, SIZE);        /* 0 = shared between threads only */
    sem_init(&full, 0, 0);

    pthread_t p[2], c[2];
    int ids[2] = {1, 2};
    long sums[2] = {0, 0};
    for (int i = 0; i < 2; i++) {
        pthread_create(&p[i], NULL, producer, &ids[i]);
        pthread_create(&c[i], NULL, consumer, &sums[i]);
    }
    for (int i = 0; i < 2; i++) {
        pthread_join(p[i], NULL);
        pthread_join(c[i], NULL);
    }
    printf("consumed total = %ld\n", sums[0] + sums[1]);

    sem_destroy(&empty);
    sem_destroy(&full);
    return 0;
}

Producer 1 makes items 100 to 109 and producer 2 makes 200 to 209. Their sum is 1045 + 2045 = 3090, and the program prints consumed total = 3090 every run, whichever consumer happens to take which item.

Why each piece is needed:

• empty blocks producers when all N slots are full. full blocks consumers when nothing is there. Together, empty + full always equals N plus however many threads are between their wait and signal.
• mutex stops two producers from writing the same slot (both read the same in), and two consumers from taking the same item.

The ordering trap

Swap the first two lines of the producer so it locks the mutex before waiting on empty:

producer (WRONG):
    lock(mutex)
    wait(empty)     // buffer is full: sleeps while holding mutex
    ...

When the buffer is full, the producer goes to sleep holding the mutex. Every consumer then blocks on the mutex and can never remove an item and signal empty. Nobody can proceed: a deadlock. The rule: wait on the counting semaphore first, then take the lock; never sleep on a condition while holding a lock that the thread who would wake you needs. The order of the two signal calls at the end does not matter for correctness.

Solution 2: a mutex and two condition variables

The monitor-style solution keeps an explicit count of items and uses two condition variables, one for each reason to wait. This version runs on Linux and macOS.

#include <pthread.h>
#include <stdio.h>

#define SIZE 4
#define ITEMS 10

static int buffer[SIZE];
static int in = 0, out = 0, count = 0;

static pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
static pthread_cond_t not_full = PTHREAD_COND_INITIALIZER;
static pthread_cond_t not_empty = PTHREAD_COND_INITIALIZER;

static void put(int item) {
    pthread_mutex_lock(&m);
    while (count == SIZE)                     /* buffer full: wait */
        pthread_cond_wait(&not_full, &m);
    buffer[in] = item;
    in = (in + 1) % SIZE;
    count++;
    pthread_cond_signal(&not_empty);          /* a consumer may proceed */
    pthread_mutex_unlock(&m);
}

static int get(void) {
    pthread_mutex_lock(&m);
    while (count == 0)                        /* buffer empty: wait */
        pthread_cond_wait(&not_empty, &m);
    int item = buffer[out];
    out = (out + 1) % SIZE;
    count--;
    pthread_cond_signal(&not_full);           /* a producer may proceed */
    pthread_mutex_unlock(&m);
    return item;
}

static void *producer(void *arg) {
    int id = *(int *)arg;
    for (int i = 0; i < ITEMS; i++)
        put(id * 100 + i);
    return NULL;
}

static void *consumer(void *arg) {
    long *sum = arg;
    for (int i = 0; i < ITEMS; i++)
        *sum += get();
    return NULL;
}

int main(void) {
    pthread_t p[2], c[2];
    int ids[2] = {1, 2};
    long sums[2] = {0, 0};
    for (int i = 0; i < 2; i++) {
        pthread_create(&p[i], NULL, producer, &ids[i]);
        pthread_create(&c[i], NULL, consumer, &sums[i]);
    }
    for (int i = 0; i < 2; i++) {
        pthread_join(p[i], NULL);
        pthread_join(c[i], NULL);
    }
    printf("consumed total = %ld\n", sums[0] + sums[1]);
    return 0;
}

It also prints consumed total = 3090.

Points to call out:

• pthread_cond_wait releases the mutex while sleeping, so there is no deadlock even though the thread waits "inside" the lock. That is the difference from the semaphore trap above.
• The waits are in while loops, because of spurious wakeups and because with several consumers another one may take the item first.
• Two condition variables, not_full and not_empty, mean a signal wakes the right kind of thread. With a single condition variable shared by producers and consumers, a consumer's signal might wake another consumer instead of a producer; that consumer finds the buffer still empty and goes back to sleep, and the wakeup the producer needed is lost. With one condition variable you would have to use broadcast everywhere, which works but wakes many threads needlessly.

In Java

Java's java.util.concurrent package already contains production-quality bounded buffers: ArrayBlockingQueue and LinkedBlockingQueue, with blocking put and take, and offer/poll with timeouts. In an interview, write the monitor version first if asked to implement it, then mention that real code should use BlockingQueue.

import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;

public class BoundedBuffer<T> {
    private final Object[] items;
    private int in = 0, out = 0, count = 0;
    private final ReentrantLock lock = new ReentrantLock();
    private final Condition notFull = lock.newCondition();
    private final Condition notEmpty = lock.newCondition();

    public BoundedBuffer(int capacity) { items = new Object[capacity]; }

    public void put(T item) throws InterruptedException {
        lock.lock();
        try {
            while (count == items.length) notFull.await();
            items[in] = item;
            in = (in + 1) % items.length;
            count++;
            notEmpty.signal();
        } finally {
            lock.unlock();      // always unlock, even if an exception is thrown
        }
    }

    @SuppressWarnings("unchecked")
    public T take() throws InterruptedException {
        lock.lock();
        try {
            while (count == 0) notEmpty.await();
            T item = (T) items[out];
            items[out] = null;  // let the garbage collector reclaim it
            out = (out + 1) % items.length;
            count--;
            notFull.signal();
            return item;
        } finally {
            lock.unlock();
        }
    }
}

The readers-writers problem

The problem

A shared resource, such as a database table, a configuration object or a cache, is accessed by two kinds of threads:

• Readers only read. Any number of readers can safely read at the same time.
• Writers modify. A writer needs exclusive access: no other writer and no reader may be active.

A plain mutex would work but wastes the opportunity: readers would queue up one by one even though they could share. The goal is to allow concurrent readers while keeping writers exclusive. The difficulty is deciding who goes first when both are waiting, which creates a starvation trade-off.

First readers-writers problem: readers' preference

No reader is kept waiting unless a writer has already obtained access. In other words, a new reader can join existing readers even if a writer is waiting.

semaphore rw_mutex = 1     // held by the writer, or by the reader group
semaphore mutex = 1        // protects read_count
int read_count = 0         // number of active readers

writer:
    wait(rw_mutex)
        ... write ...
    signal(rw_mutex)

reader:
    wait(mutex)
    read_count = read_count + 1
    if read_count == 1:        // first reader locks out writers
        wait(rw_mutex)
    signal(mutex)
        ... read ...
    wait(mutex)
    read_count = read_count - 1
    if read_count == 0:        // last reader lets writers in
        signal(rw_mutex)
    signal(mutex)

How it works: the readers act as a group. The first reader to arrive acquires rw_mutex on behalf of all of them, and the last to leave releases it. Readers in between just bump the counter. mutex protects read_count from racing updates. Note that rw_mutex is acquired by one reader and released by a different one, which is why this is written with a semaphore (no ownership), not a mutex.

The flaw: writers can starve. If readers keep arriving so that read_count never drops to zero, the waiting writer never gets rw_mutex.

time --->
R1 [=======]
R2     [========]
R3          [=========]
R4                [========]      read_count never reaches 0
W  waiting.......................  writer starves

Second readers-writers problem: writers' preference

Once a writer is waiting, no new reader may start. The writer gets in as soon as the current readers finish.

int read_count = 0, write_count = 0
semaphore r_mutex = 1      // protects read_count
semaphore w_mutex = 1      // protects write_count
semaphore read_try = 1     // writers close this gate to stop new readers
semaphore resource = 1     // the shared resource

reader:
    wait(read_try)             // blocked here if a writer is waiting
    wait(r_mutex)
    read_count = read_count + 1
    if read_count == 1: wait(resource)
    signal(r_mutex)
    signal(read_try)
        ... read ...
    wait(r_mutex)
    read_count = read_count - 1
    if read_count == 0: signal(resource)
    signal(r_mutex)

writer:
    wait(w_mutex)
    write_count = write_count + 1
    if write_count == 1: wait(read_try)   // first waiting writer closes the gate
    signal(w_mutex)
    wait(resource)
        ... write ...
    signal(resource)
    wait(w_mutex)
    write_count = write_count - 1
    if write_count == 0: signal(read_try) // last writer reopens it
    signal(w_mutex)

The flaw is now reversed: readers can starve if writers keep arriving.

Third variant: fairness

A fair solution serves threads roughly in arrival order. A common construction adds a service_queue semaphore that every reader and writer must pass through first, in FIFO order (assuming the semaphore wakes waiters in FIFO order). A writer that arrives while readers are active waits for them to finish, but readers who arrive after the writer queue up behind it. Neither side starves, at the cost of some reader concurrency.

Read-write locks in practice

You rarely write this by hand. Libraries provide read-write locks:

• POSIX: pthread_rwlock_t with pthread_rwlock_rdlock, pthread_rwlock_wrlock and pthread_rwlock_unlock. Whether readers or writers are preferred is implementation-defined; glibc offers a non-portable attribute to choose.
• Java: ReentrantReadWriteLock (with an optional fair mode) and StampedLock, which adds an optimistic read: read without locking, then check that no write happened meanwhile, and retry with a real lock if one did.
• Linux kernel: rwlock_t, and RCU (read-copy-update), where readers take no lock at all and writers publish a new copy, freeing the old one only after all pre-existing readers are done.

A read-write lock only helps when reads are frequent, critical sections are long enough to matter, and contention is real. For tiny critical sections, the extra bookkeeping can make it slower than a plain mutex.

The dining philosophers problem

The problem

Five philosophers sit at a round table. Between each pair of neighbors lies a single fork, so there are five forks. Each philosopher alternates between thinking and eating, and to eat needs both the fork on the left and the fork on the right. A philosopher picks forks up one at a time and puts them down after eating.

                 P0
           F0          F4
        P1                P4
           F1          F3
             P2  F2  P3

   Philosopher i uses fork i (left) and fork (i+1) mod 5 (right):
   P0: F0,F1   P1: F1,F2   P2: F2,F3   P3: F3,F4   P4: F4,F0

Each fork is a shared resource that only one philosopher can hold, so it is modeled as a mutex or a binary semaphore. The problem represents any program where threads need several locks at once, such as transferring money between two accounts, each with its own lock.

The naive solution and its deadlock

philosopher(i):
    loop:
        think()
        wait(fork[i])               // pick up left
        wait(fork[(i + 1) % 5])     // pick up right
        eat()
        signal(fork[(i + 1) % 5])
        signal(fork[i])

Suppose all five get hungry at the same moment and each picks up the left fork. Now every fork is held, and each philosopher waits for the right fork, which the neighbor holds and will never release. Deadlock.

 P0 holds F0, waits for F1 (held by P1)
 P1 holds F1, waits for F2 (held by P2)
 P2 holds F2, waits for F3 (held by P3)
 P3 holds F3, waits for F4 (held by P4)
 P4 holds F4, waits for F0 (held by P0)   <- cycle closes

All four deadlock conditions from the deadlocks lesson hold: forks are exclusive (mutual exclusion), each philosopher holds one while waiting for another (hold and wait), nobody can grab a fork from a neighbor (no preemption), and the waits form a cycle (circular wait). Every fix breaks one of them.

There is also a subtler problem, starvation: even without deadlock, a philosopher whose neighbors eat in alternating, overlapping turns might never find both forks free. And a "fix" where everyone puts down the left fork if the right one is busy and retries can produce livelock: all five pick up, put down, pick up again in lockstep forever.

Fix 1: resource ordering (break circular wait)

Number the forks and require every philosopher to pick up the lower-numbered fork first. Philosophers 0 to 3 are unchanged (left is lower), but philosopher 4 now reaches for F0 before F4. A cycle would need someone to hold a higher-numbered fork while waiting for a lower one, which the rule forbids, so circular wait is impossible.

#include <pthread.h>
#include <stdio.h>

#define N 5
#define MEALS 1000

static pthread_mutex_t fork_lock[N];
static int meals[N];

static void *philosopher(void *arg) {
    int i = *(int *)arg;
    int left = i;
    int right = (i + 1) % N;
    /* Resource ordering: always pick up the lower-numbered fork first.
       Philosopher 4 therefore takes fork 0 before fork 4, which breaks
       the circular wait. */
    int first = left < right ? left : right;
    int second = left < right ? right : left;

    for (int k = 0; k < MEALS; k++) {
        /* think */
        pthread_mutex_lock(&fork_lock[first]);
        pthread_mutex_lock(&fork_lock[second]);
        meals[i]++;                                   /* eat */
        pthread_mutex_unlock(&fork_lock[second]);
        pthread_mutex_unlock(&fork_lock[first]);
    }
    return NULL;
}

int main(void) {
    pthread_t t[N];
    int ids[N];
    for (int i = 0; i < N; i++)
        pthread_mutex_init(&fork_lock[i], NULL);
    for (int i = 0; i < N; i++) {
        ids[i] = i;
        pthread_create(&t[i], NULL, philosopher, &ids[i]);
    }
    for (int i = 0; i < N; i++)
        pthread_join(t[i], NULL);
    for (int i = 0; i < N; i++)
        printf("philosopher %d ate %d times\n", i, meals[i]);
    return 0;
}

Every run finishes with each philosopher having eaten 1000 times. This is exactly the lock ordering rule used in real code: if threads may need locks A and B together, always take them in one global order (for example, by account ID or memory address).

A related variant is the asymmetric solution: odd-numbered philosophers pick up left then right, even-numbered ones pick up right then left. It also prevents the cycle.

Fix 2: the waiter, or limit the diners (break hold and wait at the table level)

Allow at most four philosophers (N - 1) to try to eat at once, using a counting semaphore room initialized to 4, sometimes described as a waiter who seats at most four people.

semaphore room = 4

philosopher(i):
    wait(room)
    wait(fork[i])
    wait(fork[(i + 1) % 5])
    eat()
    signal(fork[(i + 1) % 5])
    signal(fork[i])
    signal(room)

Why it works: with at most four philosophers holding forks among five forks, by the pigeonhole principle at least one of them can get both forks, eat and release them, so the system always makes progress.

Another version of the waiter idea: a philosopher picks up both forks or neither, checking and taking them atomically under a single mutex, with a condition variable to wait until both neighbors are not eating. This is the textbook monitor solution. It is deadlock-free, but without extra care an individual philosopher can still starve.

Fix 3: Chandy-Misra (brief)

The Chandy-Misra solution (1984) works for any number of philosophers competing for arbitrary resources, without a central waiter. Each fork is either clean or dirty and is always held by one of the two philosophers who share it. Initially, every fork is dirty and is given to the lower-numbered of its two philosophers, which makes the "who has priority over whom" graph acyclic. When a philosopher wants a fork, it sends a request to its neighbor. A holder who is not eating must give up a dirty fork when asked, cleaning it before handing it over, but keeps a clean one. After eating, a philosopher's forks become dirty. This rule ensures that a philosopher who just ate yields to a hungry neighbor, which prevents both deadlock and starvation. It is a good name to mention; interviewers rarely expect the full algorithm.

The sleeping barber problem

The problem

A barbershop has one barber, one barber chair and a waiting room with N chairs.

• If there are no customers, the barber sleeps in the barber chair.
• A customer who arrives and finds the barber asleep wakes him up.
• A customer who arrives while the barber is busy sits in a free waiting chair, or leaves if all waiting chairs are full.

The challenge is to coordinate without race conditions, for example a customer deciding to wait at the moment the barber decides to sleep, so both wait for each other forever. It models a server with a bounded queue of requests that rejects work when the queue is full, which is how real systems shed load.

Semaphore solution

const CHAIRS = N
semaphore customers = 0      // number of waiting customers (barber sleeps on it)
semaphore barber_ready = 0   // barber signals a waiting customer to sit down
semaphore mutex = 1          // protects 'waiting'
int waiting = 0

barber:
    loop:
        wait(customers)          // sleep until a customer arrives
        wait(mutex)
        waiting = waiting - 1    // take one customer from the waiting room
        signal(barber_ready)     // invite them to the chair
        signal(mutex)
        cut_hair()

customer:
    wait(mutex)
    if waiting < CHAIRS:
        waiting = waiting + 1
        signal(customers)        // wake the barber if asleep
        signal(mutex)
        wait(barber_ready)       // wait to be called
        get_haircut()
    else:
        signal(mutex)            // shop full: leave
        leave()

Why it works:

• customers counts waiting customers, so the barber sleeps exactly when it is zero and is woken by each arrival.
• waiting is checked and incremented under mutex, so two customers cannot both take the last chair.
• The customer increments waiting and signals customers inside the same critical section, so the barber can never observe an inconsistent state, and because semaphores remember signals, a signal(customers) sent before the barber calls wait is not lost. This is the lost-wakeup race that a naive version with plain flags suffers from.

Extensions interviewers use: several barbers (make the barber code run in several threads; the same semaphores work), and making sure customers are served in arrival order (use a FIFO queue of per-customer semaphores).

The cigarette smokers problem (brief)

Proposed by Suhas Patil in 1971. Making a cigarette needs three ingredients: tobacco, paper and matches. Three smokers each have an unlimited supply of one ingredient. An agent repeatedly places two random ingredients on the table and waits. The smoker with the missing third ingredient should take them, smoke, and signal the agent to continue.

The naive approach, one semaphore per ingredient with each smoker waiting on its two missing ingredients one after the other, can deadlock: if the agent puts out tobacco and paper, the matches-holder may take the tobacco while the tobacco-holder grabs the paper, and each now waits forever for an ingredient that will not come.

Patil used it to argue that semaphores were not expressive enough, under the restrictions that the agent code cannot be changed and that conditional statements are not allowed. The well-known practical solution adds three pusher threads, one per ingredient. Each pusher wakes when its ingredient appears, updates shared flags under a mutex (is_tobacco, is_paper, is_match), and, seeing which pair is present, signals the one correct smoker. The lesson for interviews: when a thread needs a combination of events, collect the events in shared state under a lock and decide in one place, rather than waiting on each event separately.

How interviewers extend these problems

Once you have a working solution, expect variations. Here are the common ones and how to approach them.

Multiple producers and consumers. The semaphore and condition-variable solutions above already support them. Be ready to explain why the mutex is needed even though the semaphores count correctly: two producers that both passed wait(empty) could otherwise write the same slot.

Timeouts and non-blocking operations. Add try_put and try_get or versions with a timeout: sem_timedwait, pthread_cond_timedwait, Java's offer(item, timeout, unit) and poll(timeout, unit). With condition variables, loop until either the condition holds or the deadline passes.

Graceful shutdown. How do consumers know there will be no more items? Options: a closed flag checked in the wait loop with a broadcast on close, or a special "poison pill" item that tells each consumer to exit.

Priorities and fairness. A priority queue instead of a FIFO buffer, or a guarantee that waiting producers are served in order (Java's ArrayBlockingQueue has a fairness option).

Batching. Consumers take up to K items at once to reduce locking overhead, a common trick in loggers and network stacks.

Ordering puzzles. A family of commonly asked puzzles where threads must run in a fixed order: print odd and even numbers alternately from two threads, print "foo" and "bar" alternately, make three threads print in order first-second-third, or form H2O molecules from hydrogen and oxygen threads (two H, one O per molecule). They all use the same tools: a shared state variable under a mutex with a condition variable, or one semaphore per "turn".

Here is the odd-even printer with one mutex and one condition variable:

#include <pthread.h>
#include <stdio.h>

#define MAX 10

static pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
static pthread_cond_t cv = PTHREAD_COND_INITIALIZER;
static int next = 1;                 /* the next number to print */

static void *printer(void *arg) {
    int parity = *(int *)arg;        /* 1 = odd thread, 0 = even thread */
    for (;;) {
        pthread_mutex_lock(&m);
        while (next <= MAX && next % 2 != parity)
            pthread_cond_wait(&cv, &m);
        if (next > MAX) {
            pthread_mutex_unlock(&m);
            return NULL;
        }
        printf("%s %d\n", parity ? "odd" : "even", next);
        next++;
        pthread_cond_broadcast(&cv);
        pthread_mutex_unlock(&m);
    }
}

int main(void) {
    pthread_t odd, even;
    int one = 1, zero = 0;
    pthread_create(&odd, NULL, printer, &one);
    pthread_create(&even, NULL, printer, &zero);
    pthread_join(odd, NULL);
    pthread_join(even, NULL);
    return 0;
}

Output: odd 1, even 2, odd 3, and so on up to even 10. The next <= MAX check in the wait loop matters: without it, after the last number the other thread would wait forever for a turn that never comes. Shutdown conditions are where many otherwise correct answers hang.

Turn the deadlock question around. "Here is a solution; find the bug." Look for: waiting on a semaphore or condition while holding a lock the waker needs; if instead of while around a condition wait; a signal that can happen before the corresponding wait with a primitive that does not remember signals (a condition variable without a state check); locks taken in different orders on different paths; and missing unlocks on error paths (use try/finally in Java).

Interview questions

Q1. Explain the producer-consumer problem and its semaphore solution.

Producers add items to a fixed-size buffer and consumers remove them; producers must wait when it is full, consumers when it is empty, and buffer updates must be mutually exclusive. The solution uses a counting semaphore empty initialized to N, a counting semaphore full initialized to 0, and a mutex. A producer waits on empty, locks, inserts, unlocks and signals full; a consumer does the mirror image.

Q2. What happens if the producer locks the mutex before waiting on the empty semaphore?

If the buffer is full, the producer sleeps on empty while holding the mutex. Consumers then block trying to acquire the mutex, so no one can remove an item and signal empty, and the system deadlocks. Always wait on the counting semaphore before acquiring the mutex.

Q3. Why use two condition variables in the bounded buffer instead of one?

With one shared condition variable, a signal intended for a producer might wake another consumer, which finds the buffer still empty and goes back to sleep, so the needed wakeup is effectively lost and threads can stall. Separate not_full and not_empty variables ensure each signal wakes a thread that can actually proceed. With a single variable you would have to use broadcast, which is correct but wasteful.

Q4. What is the readers-writers problem?

Many threads share a resource; readers can safely access it simultaneously, but a writer needs exclusive access. The challenge is to let readers share while keeping writers exclusive, and to decide priority when both are waiting. The first variant favors readers and can starve writers; the second favors writers and can starve readers.

Q5. How does the first readers-writers solution work?

A read_count counter, protected by a mutex, tracks active readers. The first reader acquires the resource semaphore on behalf of all readers, and the last one to leave releases it, while writers acquire that semaphore directly. As long as readers keep overlapping, the count never reaches zero, so a waiting writer can starve.

Q6. How would you prevent writer starvation?

Give writers priority: once a writer is waiting, block new readers from starting, for example with a read_try gate that the first waiting writer closes and the last writer reopens. Or use a fair scheme where every thread passes through a FIFO service queue so arrival order is respected. In practice, use a read-write lock with a fair or writer-preferring policy.

Q7. Explain the dining philosophers problem and why the naive solution deadlocks.

Five philosophers share five forks placed between them, and each needs both adjacent forks to eat. If each picks up the left fork and then waits for the right, all five can hold one fork while waiting for a neighbor's, forming a cycle. That satisfies mutual exclusion, hold and wait, no preemption and circular wait, so it deadlocks.

Q8. Give three solutions to dining philosophers.

Resource ordering: always pick up the lower-numbered fork first, which makes a circular wait impossible. Limit the diners: a semaphore lets at most four of the five try at once, so by pigeonhole at least one can eat. Atomic acquisition: take both forks or none under a monitor. Chandy-Misra provides a distributed, starvation-free alternative.

Q9. Can dining philosophers have starvation without deadlock?

Yes. With the "both forks or none" solution, for example, two neighbors of a philosopher can alternate eating so that both of that philosopher's forks are never free at the same moment, and it waits indefinitely while the system as a whole keeps making progress. Fairness needs extra rules, such as priority for the longest-waiting philosopher or the Chandy-Misra clean and dirty forks.

Q10. How does the lock-ordering fix apply to real code?

Whenever a thread must hold several locks at once, such as two bank accounts in a transfer, everyone acquires them in one global order, for example by account ID. A cycle of waits would require some thread to hold a higher lock while waiting for a lower one, which the rule forbids. This is the most common way production systems prevent deadlock.

Q11. Explain the sleeping barber problem.

A barber sleeps when there are no customers; arriving customers wake him, wait in one of N chairs if he is busy, or leave if the chairs are full. The solution uses a customers semaphore the barber sleeps on, a barber_ready semaphore customers wait on, and a mutex protecting the count of waiting customers. It models a server with a bounded queue that rejects excess load, and it shows how semaphores avoid the lost-wakeup race.

Q12. What is the cigarette smokers problem meant to show?

Each of three smokers needs the two ingredients the agent places on the table, and waiting on each ingredient separately can deadlock when two smokers each grab one of the pair. It was originally used to argue about the limits of semaphores under certain restrictions. The practical solution uses helper "pusher" threads that record which ingredients are present under a lock and wake exactly the right smoker, illustrating how to wait for a combination of events.

Q13. How would you implement a blocking queue in Java?

Use a circular array with a ReentrantLock and two conditions, notFull and notEmpty. put locks, waits in a while loop while the queue is full, inserts, signals notEmpty and unlocks in a finally block; take mirrors it. In production you would simply use ArrayBlockingQueue or LinkedBlockingQueue.

Q14. How do you shut down consumers cleanly in producer-consumer?

Either set a closed flag under the mutex and broadcast, with consumers' wait loops checking both "not empty" and "closed", or enqueue one poison-pill item per consumer that tells it to exit. Without one of these, consumers block forever on an empty buffer after producers finish.

Key takeaways

• Producer-consumer needs counting for space and items plus mutual exclusion for the buffer: semaphores empty = N, full = 0 and a mutex, or a mutex with not_full and not_empty condition variables.
• Never sleep on a semaphore while holding a lock the waker needs; condition variables avoid this by releasing the mutex while waiting.
• Readers-writers trades concurrency against starvation: readers' preference starves writers, writers' preference starves readers, and FIFO queuing is fair.
• Use library read-write locks (pthread_rwlock_t, ReentrantReadWriteLock), and consider RCU or copy-on-write for read-mostly data.
• Dining philosophers deadlocks because all four Coffman conditions hold; fix it by lock ordering, limiting diners to N - 1, or acquiring both forks atomically.
• The sleeping barber models a bounded queue that rejects excess load; semaphores remember signals and so avoid lost wakeups.
• Interview extensions (timeouts, shutdown, ordering puzzles like odd-even printing) are solved with the same recipe: shared state, one condition per reason to wait, while loops, and a designed shutdown path.

Next lesson

Continue with Deadlocks.