Mediumproducer-consumerdining philosopherssemaphoresbounded bufferdeadlocksynchronization

Step 10 of 14 in Operating SystemsIntermediateRead first: Mutexes, Semaphores and Monitors, Deadlocks: Conditions and Prevention

Producer-Consumer and Dining Philosophers

Two classic synchronization problems solved with semaphores and lock ordering. Python code was run: a bounded buffer moved 100,000 items safely and naive philosophers deadlocked.

Nikhila Reddy

NLP, Cloud, Testing, Operating Systems, DBMS, Java, Python

Published 13 Oct 2026 · Updated 23 Oct 2026

Short answer

The producer-consumer problem is solved with a bounded buffer guarded by one mutex plus two counting semaphores: empty counts free slots and full counts items. Dining philosophers deadlocks when all five grab their left fork at once. Interviewers expect the fixes to name the deadlock condition they break, such as resource ordering breaking circular wait.

Producer-consumer asks how threads hand work through a fixed-size buffer without losing items or overrunning it, and the answer is one mutex plus two counting semaphores. Dining philosophers asks how five threads sharing five forks avoid deadlock, and the answers all break one of the four deadlock conditions.

Key facts

A bounded buffer uses a mutex to protect the queue, an empty semaphore starting at the capacity, and a full semaphore starting at 0.
A producer that takes the mutex before waiting on the empty semaphore can sleep holding the lock on a full buffer and deadlock the system.
A Python bounded buffer with 4 producers and 4 consumers moved 100,000 items with none lost or duplicated, taking 5.02 s with capacity 1 and 0.39 s with capacity 64 in one run.
The four deadlock conditions are mutual exclusion, hold and wait, no preemption and circular wait; naive dining philosophers have all four.
Dining philosophers is fixed by always taking the lower-numbered fork first, or by a semaphore allowing only N-1 philosophers to compete; both let all five eat 200 meals.
Lock ordering prevents deadlock but not starvation; fairness needs a fair lock or queue.

The Little Book of Semaphores, Allen Downey Dining philosophers problem, Wikipedia Semaphores, Operating Systems: Three Easy Pieces

01Why these two problems keep appearing

These two problems are small models of real hazards: producer-consumer is a work queue, dining philosophers is several threads each needing two locks at once.

Almost every concurrency bug in a real system is a version of one of these two shapes. A web server that puts requests in a queue for worker threads is producer-consumer. A transfer function that locks the source account and then the destination account is dining philosophers with two forks.

Interviewers like them because the naive solution looks fine, passes a quick test, and fails under load. The skill being tested is knowing which primitive guards which invariant, and being able to say why the fix works. This article uses Python threads so the code is short, but the reasoning is the same in C, Java or Go.

02Producer-consumer: the bounded buffer

A bounded buffer needs one mutex for the queue and two semaphores, one counting free slots and one counting filled slots, so producers wait when full and consumers wait when empty.

Producers add items to a buffer of fixed capacity. Consumers remove them. Three rules must hold: a producer must wait when the buffer is full, a consumer must wait when it is empty, and the queue itself must not be corrupted by two threads touching it at once.

The standard solution uses three objects. A mutex protects the queue. A semaphore called empty starts at the capacity and counts free slots. A semaphore called full starts at 0 and counts items. A producer does empty.acquire, then the locked append, then full.release. A consumer does the mirror image. The semaphores do the waiting; the mutex only guards the few lines that touch the deque.

import threading, collections, time
class BoundedBuffer:
    def __init__(self, cap):
        self.q = collections.deque()
        self.mutex = threading.Lock()
        self.empty = threading.Semaphore(cap)   # free slots
        self.full = threading.Semaphore(0)      # filled slots
        self.max_len = 0
    def put(self, x):
        self.empty.acquire()
        with self.mutex:
            self.q.append(x); self.max_len = max(self.max_len, len(self.q))
        self.full.release()
    def get(self):
        self.full.acquire()
        with self.mutex:
            x = self.q.popleft()
        self.empty.release()
        return x

Order matters. If the producer took the mutex before waiting on empty, a full buffer would make it sleep while holding the lock, and no consumer could ever get in to free a slot. That is a deadlock built from two perfectly legal primitives.

03Testing the buffer: what I ran and what came out

With 4 producers, 4 consumers and 100,000 items the buffer never exceeded its capacity and lost or duplicated nothing, and larger buffers ran faster because threads blocked less.

The test harness starts 4 producers that each push 25,000 tagged items and 4 consumers that each pull a quarter of the total. After all threads finish it asserts that exactly 100,000 distinct items arrived and that each consumer saw each producer's items in order.

def run(P, C, per_producer, cap):
    buf = BoundedBuffer(cap)
    total = P * per_producer
    got = [[] for _ in range(C)]
    def prod(p):
        for i in range(per_producer): buf.put((p, i))
    def cons(c):
        for _ in range(total // C): got[c].append(buf.get())
    ts = [threading.Thread(target=prod, args=(p,)) for p in range(P)] + \
         [threading.Thread(target=cons, args=(c,)) for c in range(C)]
    t0 = time.perf_counter(); [t.start() for t in ts]; [t.join() for t in ts]
    dt = time.perf_counter() - t0
    allv = [x for g in got for x in g]
    assert len(allv) == total and len(set(allv)) == total
    # per-producer FIFO inside each consumer
    for g in got:
        for p in range(P):
            seq = [i for (pp, i) in g if pp == p]
            assert seq == sorted(seq)
    return buf.max_len, dt
for cap in (1, 8, 64):
    m, dt = run(4, 4, 25_000, cap)
    print(f"cap={cap:3d} items=100000 max queue length seen={m} time={dt:.2f}s")

Output on Python 3.13 in this environment:

cap=  1 items=100000 max queue length seen=1 time=5.02s
cap=  8 items=100000 max queue length seen=8 time=1.24s
cap= 64 items=100000 max queue length seen=64 time=0.39s

The assertions passed every time, and the queue length never went above the capacity. The timing shows why buffer size matters: with one slot, each handoff forces a thread switch, so it took 5.02 s. With 64 slots, 0.39 s. These are wall-clock times from one run on a shared cloud machine, and Python's global interpreter lock affects them, so treat the ratio as indicative and the absolute numbers as specific to this run.

04Dining philosophers: the setup and the deadlock

If every philosopher grabs the left fork and then waits for the right one, all five can hold one fork each and wait forever: circular wait, hold-and-wait, no preemption, mutual exclusion.

Five philosophers sit at a round table with one fork between each pair, so five forks in total. To eat, a philosopher needs both adjacent forks. They think, pick up the left fork, pick up the right, eat, put both down.

If all five pick up their left fork at the same moment, each now holds one fork and waits for a neighbour who is also waiting. All four deadlock conditions are present: forks are exclusive, each philosopher holds one while waiting for another, nobody takes a fork away, and the waits form a circle.

I reproduced it with five threads and a short sleep between the two grabs to make the unlucky timing certain. The function is below; the three strategies are explained in the next section.

import threading, time

def dine(n, strategy, meals, patience=2.0):
    forks = [threading.Lock() for _ in range(n)]
    seats = threading.Semaphore(n - 1)          # used by the "limit" strategy
    eaten = [0] * n

    def philosopher(i):
        first, second = i, (i + 1) % n
        if strategy == "ordered" and first > second:
            first, second = second, first       # always take the lower-numbered fork first
        for _ in range(meals):
            if strategy == "limit":
                seats.acquire()
            forks[first].acquire()
            time.sleep(0.001)                   # widen the gap between the two grabs
            forks[second].acquire()
            eaten[i] += 1
            forks[second].release()
            forks[first].release()
            if strategy == "limit":
                seats.release()

    threads = [threading.Thread(target=philosopher, args=(i,), daemon=True) for i in range(n)]
    start = time.time()
    for t in threads: t.start()
    for t in threads: t.join(patience)
    finished = not any(t.is_alive() for t in threads)
    return finished, eaten, round(time.time() - start, 2)

for strategy, meals in (("naive", 200), ("ordered", 200), ("limit", 200)):
    print(f"{strategy:8s}", dine(5, strategy, meals))

The naive strategy printed (False, [0, 0, 0, 0, 0], 10.0). Nobody finished, nobody ate a single meal, and the 10 seconds are just five 2-second join timeouts, not the time to solve anything. The program would have waited forever.

05Three ways out and what each breaks

Lock ordering breaks circular wait, and seating at most four at once also removes it; both let all 200 meals finish, but they trade simplicity against some lost parallelism.

Each fix removes one of the four deadlock conditions.

Resource ordering: number the forks 0 to 4 and always take the lower-numbered fork first. The philosopher between fork 4 and fork 0 reaches for fork 0 first, which breaks the circle. This is the cheapest fix and the one to prefer for locks in real code.

Limit the diners: allow at most four philosophers to try at once, using a semaphore initialised to 4. With five forks and four diners, at least one diner can always get both forks.

Try-lock with back-off: take one fork, try the other without waiting, and put both down if it fails. This breaks hold-and-wait but can livelock, with everyone repeatedly picking up and putting down in step, unless you add random delays.

Results of running the first two, 200 meals each:

ordered  (True, [200, 200, 200, 200, 200], 0.68)
limit    (True, [200, 200, 200, 200, 200], 0.59)

Both finished, each philosopher ate exactly 200 times, in about 0.6 seconds. Neither fix guarantees fairness in general. A philosopher could in principle be starved by faster neighbours, which is a separate problem called starvation. I did not run the try-lock variant.

06Where this shows up in real code

Bounded queues give back-pressure between pipeline stages, and always acquiring multiple locks in one global order is the practical lesson from dining philosophers.

Producer-consumer appears as thread pools, log writers, message brokers and the pipe between two shell commands. The bounded part matters: an unbounded queue hides a slow consumer until memory runs out, while a bounded one pushes back on producers. In Python use queue.Queue(maxsize=n), in Java a BlockingQueue, which do the mutex and semaphore work for you.

The dining philosophers lesson is about order. When code must hold two locks, say two bank accounts, sort by account id and lock in that order. If two locks cannot be ordered, take them with a timeout and be ready to retry. The same reasoning appears in database deadlock handling, where the engine kills a victim instead.

07Common interview questions

Expect questions on why two semaphores are needed, what goes wrong if the mutex is taken first, the four deadlock conditions, and a working fix for the philosophers.

Q: Why does the bounded buffer need two semaphores and a mutex?
A: The semaphores count free slots and filled slots to make threads wait at the boundaries. The mutex protects the queue structure while one thread changes it.

Q: What happens if a producer acquires the mutex before waiting on the empty semaphore?
A: On a full buffer it sleeps holding the mutex, consumers cannot enter to free a slot, and the system deadlocks.

Q: Which deadlock conditions are present in the naive philosophers solution?
A: All four: mutual exclusion, hold and wait, no preemption, and circular wait.

Q: Give a fix for dining philosophers.
A: Order the forks and always take the lower-numbered one first, or allow only N-1 philosophers to compete at once.

Q: Does lock ordering prevent starvation?
A: No. It prevents deadlock only. Fairness needs a fair lock or queue.

Q: How is a monitor version different?
A: A monitor bundles the mutex with condition variables, so producers wait on not_full and consumers on not_empty inside one critical section.

Up next · step 11 of 14

Containers vs Virtual Machines: Namespaces and cgroups

A container is a normal process with a restricted view (namespaces) and budget (cgroups); a VM brings its own kernel. Real runs show PID 1 isolation, an OOM kill at 50 MiB and CPU throttling.

Previous: Memory Allocation: First Fit, Best Fit and Fragmentation