Bounded Buffers and Deadlock

The second half of LeetCode’s concurrency set moves from ordering to capacity and contention: a queue that blocks when full, groups that must form before anyone proceeds, and five philosophers who can genuinely deadlock.

This page has the only measured deadlock in the course. If you have not read Thread Ordering and Signalling, start there — the semaphore-versus-lock distinction is assumed here.

The cue

You are looking at capacity or contention when…

• A buffer has a maximum size and producers must block when it is full, consumers when it is empty. LC 1188.
• Threads must form a group before any of them proceeds — n arrive, n continue. LC 1117.
• Each thread needs two or more resources at once, which is where deadlock lives. LC 1226.
• The condition to wait on is a predicate over shared state (“until the queue is non-empty”) rather than a single event — that is a Condition, not a Semaphore.
• The problem hints at starvation or fairness, not just correctness.

When it is not this. If the requirement is a fixed order or an alternation, that is the previous page and a chain of Semaphore(0) gates. And if you are reaching for threads to make CPU work faster, the GIL means you measured 0.68× — use processes.

Producer–consumer: Condition, not a busy-wait

LC 1188 asks for a queue with a capacity where enqueue blocks when full and dequeue blocks when empty. The primitive is a Condition, because the thing being waited on is a predicate over shared state:

bounded_queue.py

import threading
from collections import deque
 
 
class BoundedBlockingQueue:
    def __init__(self, capacity):
        self.cap = capacity
        self.q = deque()
        self.cv = threading.Condition()      # a Lock plus a waiting room
 
    def enqueue(self, x):
        with self.cv:
            # wait_for re-checks the predicate on every wake-up, which is what
            # makes spurious wake-ups and lost races harmless.
            self.cv.wait_for(lambda: len(self.q) < self.cap)
            self.q.append(x)
            self.cv.notify_all()
 
    def dequeue(self):
        with self.cv:
            self.cv.wait_for(lambda: len(self.q) > 0)
            x = self.q.popleft()
            self.cv.notify_all()
            return x
 
    def size(self):
        with self.cv:
            return len(self.q)

Verified with capacity 2, one producer pushing 0..9 and one consumer draining:

Check	Result
Items consumed	[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Order preserved	yes
Maximum size ever observed	2 — never exceeded the capacity
Threads stuck at the end	none

sketch A capacity-2 queue: the producer blocks rather than overflowing p5.js Pause Restart

One producer pushing 0..9, one consumer draining, capacity 2. Watch the producer go BLOCKED whenever both slots are full -- that is the whole point of a bounded buffer, and it is why the depth trace below never crosses the dashed capacity line. Measured on the page: order preserved, maximum size ever observed exactly 2, nothing stuck at the end.

Three details carry it:

• wait_for(predicate) rather than wait(). wait_for loops until the predicate holds, so a wake-up that turns out to be premature just waits again. A bare wait() assumes the condition is true on waking, which is the classic bug.
• notify_all, not notify. With producers and consumers on the same condition, notify can wake a producer when only a consumer can make progress — and then nothing moves. Two separate Conditions sharing one lock let you use notify; one shared condition needs notify_all.
• The lock is held while checking the predicate. with self.cv acquires it; wait_for releases it while blocked and reacquires before returning. That is what makes “check then act” atomic, and it is why you must not check len(self.q) outside the with.

In real code, use queue.Queue

Python ships this: queue.Queue(maxsize=n) is a bounded blocking queue, written in C, with put/get and timeouts. Hand-rolling it is a LeetCode exercise and an interview exercise, not a production decision.

Saying that out loud is worth marks — as is knowing why the stdlib version exists: getting notify_all, the predicate loop and the lock scope right is fiddly enough that everyone should use the tested one.

Barrier: forming groups

LC 1117 (Building H2O) needs threads to leave in groups of exactly three — two hydrogen, one oxygen — with no partial molecules. A semaphore caps how many at once; a Barrier makes them leave together:

h2o.py

import threading
 
 
class H2O:
    def __init__(self):
        self.h = threading.Semaphore(2)          # at most 2 H inside a molecule
        self.o = threading.Semaphore(1)          # at most 1 O
        self.bar = threading.Barrier(3)          # nobody leaves until all 3 arrive
 
    def hydrogen(self, out):
        self.h.acquire()
        out.append("H")
        self.bar.wait()                          # blocks until 2 H and 1 O are here
        self.h.release()
 
    def oxygen(self, out):
        self.o.acquire()
        out.append("O")
        self.bar.wait()
        self.o.release()

Verified for 1 and 3 molecules: HHO and HHOHHOHHO, with every group of three being exactly HHO and nothing stuck.

The two primitives are doing different jobs and both are needed:

• The semaphores enforce the ratio. Without Semaphore(2) on hydrogen, three H threads could get in and the barrier would trip with the wrong mixture.
• The barrier enforces the grouping. Without it, an H could release its permit and let the next molecule’s H in before this molecule was complete, interleaving them.

A Barrier also resets automatically after tripping, which is what lets the same object serve molecule after molecule with no bookkeeping.

Dining philosophers: a real deadlock

Five philosophers, five forks, each needs the two beside them. The naive solution — take the left fork, then the right — deadlocks, and here it is actually happening:

Strategy	Meals eaten (of 5)	Threads still stuck	Verdict
Naive (left then right)	0	5	DEADLOCK
Resource ordering (lowest index first)	5	0	ok
Waiter (cap diners at n − 1)	5	0	ok

Measured with a 1.5-second timeout and a small sleep between the two acquires to make the window reliable. Zero meals — not “slow”, not “unfair”. Every philosopher holds their left fork and waits forever for a right fork their neighbour is holding.

sketch Dining philosophers: click to break the cycle p5.js Pause Restart

Five philosophers, five forks. Left-then-right closes a cycle of five and nothing ever completes -- measured 0 meals, 5 threads stuck. Click the canvas to switch to resource ordering, where every philosopher takes the LOWER-numbered fork first. Only philosopher 4 changes behaviour, and that one reversal is enough: the cycle cannot close, and all five eat. Deadlock needs a cycle, so removing the cycle is sufficient.

philosophers.py

import threading
 
 
def naive(forks, i, n):
    left, right = i, (i + 1) % n
    forks[left].acquire()                  # everyone gets their left fork...
    forks[right].acquire()                 # ...and nobody ever gets a right one
    return left, right
 
 
def resource_ordering(forks, i, n):
    """Break the CYCLE: always take the lower-numbered fork first."""
    left, right = i, (i + 1) % n
    a, b = min(left, right), max(left, right)
    forks[a].acquire()
    forks[b].acquire()
    return a, b
 
 
def waiter(forks, i, n, permits):
    """Break HOLD-AND-WAIT: at most n-1 philosophers may try to eat at once."""
    permits.acquire()                      # a Semaphore(n - 1)
    left, right = i, (i + 1) % n
    forks[left].acquire()
    forks[right].acquire()
    return left, right                     # caller releases forks, then permits

Why resource ordering works is the part to be able to say: philosopher 4’s “left” is fork 4 and “right” is fork 0, so under the ordering rule philosopher 4 takes fork 0 first. That one philosopher reaching in the opposite direction breaks the cycle — and a cycle is required for deadlock, so removing it is sufficient.

Why the waiter works is different: with at most four philosophers competing for five forks, at least one can always complete a pair. It removes hold-and-wait rather than circular wait.

The four conditions, and which fix removes which

Deadlock needs all four Coffman conditions simultaneously. Remove any one and it cannot happen — which turns “avoid deadlock” from a vague instruction into a checklist:

Condition	In the philosophers	How to remove it
Mutual exclusion	a fork is held by one philosopher at a time	Not removable — it is the point of a fork
Hold and wait	holds left while waiting for right	Waiter: cap concurrent diners at n − 1
No preemption	a fork is never taken back	acquire(timeout=…), then drop both and retry
Circular wait	0 waits on 1 waits on … waits on 0	Resource ordering: always take the lower index first

This is the answer to “how would you avoid deadlock in general?” — name the four conditions, then say which one your fix removes. It generalises far beyond philosophers: always acquire locks in a globally consistent order is resource ordering, and it is the single most useful deadlock rule in real systems.

The timeout fix trades deadlock for livelock

acquire(timeout=0.1), and on failure release everything and retry, does remove no-preemption. But if every philosopher times out and retries in lockstep, they can loop forever making no progress — livelock: all running, none advancing.

The standard mitigation is a randomised backoff before retrying, which makes lockstep unlikely rather than impossible. Resource ordering has no such caveat, which is why it is the default recommendation.

Dry run

The queue, with capacity 2

Producer pushing 0..9, consumer draining, capacity 2:

Moment	Queue	Producer	Consumer
start	[]	running	blocked — non-empty is false
after enqueue(0)	[0]	running	wakes, predicate now true
after enqueue(1)	[0, 1]	blocked — room-available is false	draining
consumer takes 0	[1]	wakes	—
…	…	…	…
end	[]	done	got [0..9] in order

Both sides block, on the same condition object. That is why notify_all is required: a notify after enqueue might wake the producer that is waiting for space, which cannot proceed, and the consumer stays asleep. With one shared Condition, waking everyone and letting each re-check its own predicate is the correct and simple choice.

Verified: max observed size was exactly 2, and order was preserved — a consumer never saw a value out of sequence, because deque is FIFO and the lock makes each pop atomic.

The deadlock, philosopher by philosopher

Five philosophers, all executing acquire-left then acquire-right:

Step	State
all five acquire their left fork	P0 holds F0, P1 holds F1, P2 holds F2, P3 holds F3, P4 holds F4
all five request their right fork	P0 wants F1 (P1 has it), P1 wants F2 (P2 has it), … P4 wants F0 (P0 has it)
result	a cycle of five threads, each holding one resource and waiting for the next

Measured: 0 meals, 5 threads alive after the timeout. Nothing recovers on its own, and no amount of retrying inside that structure helps, because every thread is blocked inside its acquire call.

Now the ordering fix, on the same five:

Philosopher	left / right	Under ordering, takes first
P0	0 / 1	F0
P1	1 / 2	F1
P2	2 / 3	F2
P3	3 / 4	F3
P4	4 / 0	F0 — not F4

P4 is the only one whose behaviour changes, and that is enough. P4 and P0 now contend for F0 first; whichever loses does not hold anything, so the chain never closes. 5 meals, nothing stuck.

Why waiting without a predicate is a bug

wrong_wait.py

# WRONG — do not copy this
import threading
from collections import deque
 
cv, q = threading.Condition(), deque()
 
 
def broken_dequeue():
    with cv:
        if len(q) == 0:
            cv.wait()          # assumes the queue is non-empty on waking
        return q.popleft()     # may raise IndexError

Two ways this fails. A spurious wake-up — permitted by the API and real on some platforms — returns from wait() with nothing changed. And with notify_all, several consumers wake, the first takes the only item, and the rest proceed into an empty queue.

Using wait_for with a predicate re-checks after every wake and loops if it is still false. The rule: always wait in a loop on a predicate, never on a bare notification.

Complexity

Operation	Cost	Note
enqueue / dequeue	$O(1)$	deque at both ends, plus lock acquire/release
Blocked enqueue	one context switch	not a spin — the thread sleeps
notify_all	$O(w)$ in waiters	wakes all, each re-checks; fine for small w
Barrier(n).wait()	$O(1)$ amortised	the n-th arrival releases all
Philosopher meal	2 lock acquires	plus the waiter’s semaphore, if used
Naive philosophers	never completes	measured 0 meals in 1.5 s

Two honest notes:

• notify_all is $O(w)$ wake-ups where notify would be $O(1)$, and with many waiters that is the “thundering herd”. The fix is two separate Condition objects sharing one Lock — one for “not full”, one for “not empty” — so each notify wakes a thread that can actually proceed. For LC 1188’s scale, notify_all on a single condition is simpler and correct, and saying you know the upgrade path is the better answer.
• None of this is about throughput. The GIL serialises bytecode, so a Python bounded queue is a correctness exercise. queue.Queue is the same design in C.

The variant map

Problem	The primitive	The trap
1188 Bounded Blocking Queue	Condition + wait_for	Bare wait(); notify instead of notify_all
1117 Building H2O	2 semaphores + Barrier(3)	Semaphores alone let molecules interleave
1226 Dining Philosophers	Resource ordering, or a waiter semaphore	Left-then-right deadlocks — measured 0 meals
1195 Fizz Buzz Multithreaded	4 semaphores, or Condition on a counter	Four-way ordering — previous page
“At most k concurrent”	Semaphore(k)	—
“Wait for all workers”	Barrier(n), or join each thread	A barrier resets; join does not
Readers–writers	Condition with reader count + writer flag	Writer starvation under continuous readers
Unbounded producer–consumer	queue.Queue() with no maxsize	Memory growth if consumers fall behind
Real production code	queue.Queue, concurrent.futures	Hand-rolling is the exercise, not the answer

Readers–writers is the natural next question

Many readers may hold the lock simultaneously; a writer must be alone. The naive version starves writers: while any reader holds the lock, new readers keep arriving and the writer waits forever.

The fix is the same shape as the elevator’s SCAN-over-SSTF and the library’s FIFO hold queue — once a writer is waiting, block new readers. That converts unbounded writer starvation into bounded waiting for everyone, at the cost of some reader throughput. Recognising starvation as a distinct failure from deadlock is the point: nothing is blocked in a cycle, yet one thread never progresses.

Pitfalls

• Waiting without a predicate loop. Spurious wake-ups are permitted, and notify_all wakes several consumers for one item. Always use wait_for(predicate), or a while loop around wait().
• notify on a shared condition with both producers and consumers. It can wake a thread that cannot make progress, and everything stalls. Use notify_all, or two conditions on one lock.
• Checking the predicate outside the lock. Testing the queue’s length before entering the with block is a check-then-act race — the item can vanish between the two.
• Left-then-right fork acquisition. Measured 0 meals, 5 threads stuck. It is a textbook deadlock and it reproduces reliably with a small sleep between the acquires.
• Believing a deadlock is a hang you can retry out of. Every thread is blocked inside its acquire; nothing times out and nothing recovers. It needs a structural fix.
• Timeout-and-retry without backoff. Removes no-preemption and introduces livelock — all threads running, none progressing. Randomise the backoff, or prefer resource ordering.
• Acquiring locks in different orders in different functions. This is the general form of the philosophers’ bug and the most common real-world deadlock. Pick a global order and document it.
• Semaphores without a barrier for grouping. In H2O, permits alone let the next molecule’s hydrogen in before the current one completes. The barrier is what makes the group atomic.
• Forgetting a Barrier resets. It trips and rearms, which is what makes it reusable — but it also means a stray extra thread joins the next group.
• Confusing deadlock with starvation. Deadlock is a cycle where nothing moves; starvation is one thread never getting a turn while others progress. Different diagnoses, different fixes.
• Hand-rolling a queue in production. queue.Queue(maxsize=n) is this, in C, tested.
• Testing concurrency once. Use repetitions and a timeout, so a deadlock fails the test instead of hanging the suite.

Try it yourself

Drill 1 — the bounded blocking queue

pch.exerciseTag pch.exerciseTitle

Drill 2 — deadlock, then break the cycle

pch.exerciseTag pch.exerciseTitle

Drill 3 — a Barrier makes groups

pch.exerciseTag pch.exerciseTitle

Interview follow-ups

They ask	What they’re checking	The answer
“Implement a bounded blocking queue.”	The right primitive	A Condition with wait_for on a predicate, notify_all after mutating, everything inside the with. And say that queue.Queue(maxsize=n) is this in C
“Why wait_for rather than wait?”	The classic bug	Spurious wake-ups are permitted, and notify_all wakes several consumers for one item — so a bare wait() proceeds on a false predicate and pops an empty deque. Always wait in a loop on a predicate
“Why notify_all rather than notify?”	Whether you see the stall	Producers and consumers share one condition, so notify can wake a thread that cannot proceed while the one that could stays asleep. The upgrade is two Conditions on one Lock, which makes notify safe and avoids the thundering herd
“Where must the predicate be checked?”	Check-then-act	Inside the lock. wait_for releases the lock while blocked and reacquires before returning, which is what makes check-and-act atomic
“Five philosophers, left fork then right. What happens?”	Whether you can state it as deadlock	It deadlocks — measured 0 meals and 5 threads stuck. All five hold their left fork and wait on a right fork a neighbour holds: a cycle of five
“Fix it.”	Two valid answers	Resource ordering — always take the lower-numbered fork first, so philosopher 4 reaches for fork 0 and the cycle breaks. Or a waiter semaphore capping diners at n − 1, so someone can always complete a pair. Both measured 5 meals, nothing stuck
“Which deadlock condition does each fix remove?”	The general framework	Ordering removes circular wait; the waiter removes hold and wait; timeouts remove no preemption; mutual exclusion is not removable. All four must hold at once, so killing one is sufficient
“What about timeout and retry?”	The trap in the obvious fix	It removes no-preemption but risks livelock — everyone timing out and retrying in lockstep, all running and none progressing. Needs randomised backoff; resource ordering has no such caveat
“Deadlock or starvation?”	Distinguishing failures	Deadlock is a cycle where nothing moves. Starvation is one thread never getting a turn while others progress — like writers under continuous readers. Different diagnosis, different fix
“Build H2O in groups of three.”	Barrier versus semaphore	Two semaphores for the ratio, a Barrier(3) for the grouping. Semaphores alone let the next molecule’s hydrogen in before this one completes
“How do you avoid deadlock in real code?”	The one transferable rule	Acquire locks in a globally consistent order, and document it. That is resource ordering, and it is the most useful deadlock rule there is
“How do you test for deadlock?”	Practical	join(timeout) and assert the threads finished — a deadlock then fails the test instead of hanging the suite. Plus many repetitions, because interleavings vary

Self-check

pch.quizTag pch.quizDefaultTitle

1. Why does the bounded queue use a predicate-checking wait rather than a bare `cv.wait()`?

   A wait_for is faster B Spurious wake-ups are permitted and notify_all wakes several consumers for one item, so a bare wait() can proceed with a false predicate and pop from an empty deque C wait() does not release the lock D wait() cannot be used inside a with-block
   pch.quizShowAnswer

   B — Spurious wake-ups are permitted and notify_all wakes several consumers for one item, so a bare wait() can proceed with a false predicate and pop from an empty deque — wait_for loops until the predicate holds, so a premature wake-up simply waits again. Note that wait() does release the lock while blocked — that part is fine. The bug is the assumption that the condition is true on waking, which neither spurious wake-ups nor notify_all respect.

2. The queue uses one Condition for both producers and consumers. Why is `notify_all` required?

   A notify only works with Locks B notify could wake a producer waiting for space when only a consumer can make progress — and then nothing moves C notify_all is faster with few waiters D notify does not exist on Condition
   pch.quizShowAnswer

   B — notify could wake a producer waiting for space when only a consumer can make progress — and then nothing moves — With a single condition object you cannot choose who to wake, so waking one thread risks waking the wrong one and stalling. notify_all wakes everyone and lets each re-check its own predicate. The upgrade path is two Condition objects sharing one Lock, which makes notify safe and avoids the thundering herd — worth naming as the next step.

3. Five philosophers each take their left fork then their right. What was measured over 1.5 seconds?

   A All five ate, slowly B Zero meals, five threads still stuck — a genuine deadlock C Three ate and two starved D It varied between runs
   pch.quizShowAnswer

   B — Zero meals, five threads still stuck — a genuine deadlock — Measured 0 meals and 5 alive. Every philosopher holds their left fork and waits on a right fork their neighbour holds, forming a cycle of five. It is not slowness or unfairness — nothing will ever complete, and no thread can time out because all five are blocked inside their acquire.

4. How does resource ordering break the philosophers' deadlock?

   A It makes each philosopher wait a random time first B Taking the lower-numbered fork first means philosopher 4 reaches for fork 0 before fork 4 — that one philosopher going the other way breaks the cycle C It gives each philosopher their own pair of forks D It serialises the philosophers completely
   pch.quizShowAnswer

   B — Taking the lower-numbered fork first means philosopher 4 reaches for fork 0 before fork 4 — that one philosopher going the other way breaks the cycle — P4's left is fork 4 and right is fork 0, so the ordering rule inverts only P4's behaviour. P4 and P0 then contend for fork 0 first, and whoever loses holds nothing — so the chain never closes. Deadlock requires a cycle, so removing the cycle is sufficient. Note it does not serialise anything: 5 meals were eaten with nothing stuck.

5. The waiter fix caps concurrent diners at n − 1. Which Coffman condition does it remove?

   A Circular wait B Hold and wait — with four philosophers competing for five forks, at least one can always complete a pair C Mutual exclusion D No preemption
   pch.quizShowAnswer

   B — Hold and wait — with four philosophers competing for five forks, at least one can always complete a pair — It is a different fix from resource ordering, which is what makes the pair worth knowing. Ordering attacks circular wait; the waiter attacks hold-and-wait by guaranteeing spare capacity. Both measured 5 meals and nothing stuck, and being able to say which condition each one removes is the general framework the question is really after.

6. You fix deadlock by acquiring with a timeout and retrying on failure. What is the risk?

   A It is a complete fix with no downside B Livelock — all philosophers timing out and retrying in lockstep, everything running and nothing progressing. Needs randomised backoff C It reintroduces circular wait D The timeout leaks locks
   pch.quizShowAnswer

   B — Livelock — all philosophers timing out and retrying in lockstep, everything running and nothing progressing. Needs randomised backoff — Timeouts genuinely remove the no-preemption condition, so this is a real fix rather than a wrong one — but it trades a stopped system for a busy one that makes no progress. Randomised backoff makes lockstep unlikely rather than impossible, which is why resource ordering, with no such caveat, is the default recommendation.

7. In Building H2O, why are semaphores alone insufficient?

   A Semaphores cannot count to 2 B Semaphores enforce the RATIO but not the GROUPING — a hydrogen could release its permit and let the next molecule's hydrogen in before the current molecule completed C Semaphores are not thread-safe for three threads D They are sufficient; the barrier is an optimisation
   pch.quizShowAnswer

   B — Semaphores enforce the RATIO but not the GROUPING — a hydrogen could release its permit and let the next molecule's hydrogen in before the current molecule completed — The two primitives answer different questions: how many of each kind may be inside a molecule, and when may they leave. Verified — with a Barrier(3), every consecutive group of three is exactly HHO across 1 and 3 molecules. The barrier also rearms after tripping, which is what lets one object serve molecule after molecule with no bookkeeping.

8. What is the difference between deadlock and starvation?

   A They are two names for the same failure B Deadlock is a cycle in which nothing moves; starvation is one thread never getting a turn while others progress — such as writers under continuous readers C Deadlock affects two threads, starvation more D Starvation is always caused by deadlock
   pch.quizShowAnswer

   B — Deadlock is a cycle in which nothing moves; starvation is one thread never getting a turn while others progress — such as writers under continuous readers — The distinction drives the diagnosis. In a deadlock every involved thread is blocked and the system is stopped; under starvation the system is making progress and one participant is being passed over. The fixes differ too: break a cycle versus introduce fairness — which is the same judgement as FIFO hold queues and SCAN over SSTF elsewhere in this course.

9. What is the single most useful deadlock-avoidance rule in real code?

   A Use timeouts on every lock B Acquire locks in a globally consistent order, and document that order C Never use more than one lock D Prefer processes to threads
   pch.quizShowAnswer

   B — Acquire locks in a globally consistent order, and document that order — This is resource ordering generalised, and the philosophers are its canonical illustration. Most real deadlocks are two functions taking the same two locks in opposite orders — a global order makes that impossible by construction rather than unlikely. Timeouts are a fallback that risks livelock, and a single lock is often not an option.

10. How should a concurrency test be written so a deadlock does not hang the suite?

    A Run it once and inspect the output B join(timeout) and assert the threads finished, plus many repetitions — a deadlock then fails the test rather than hanging C Use a debugger D Reduce the thread count to two
    pch.quizShowAnswer

    B — join(timeout) and assert the threads finished, plus many repetitions — a deadlock then fails the test rather than hanging — That is exactly how the numbers on this page were produced: a 1.5-second timeout turned the philosophers' deadlock into a reportable result (0 meals, 5 alive) instead of a stalled process. Repetitions matter because interleavings vary, and no number of passes proves a race absent — the reasoning still has to come from the invariant.

Recall card

• Capacity and grouping, not ordering. Ordering is the previous page.
• Bounded queue = Condition. wait_for(predicate) never a bare wait(); notify_all after every mutation; predicate checked inside the lock. Verified: order preserved, max size exactly 2, nothing stuck.
• A bare wait() is a bug — spurious wake-ups are legal and notify_all wakes several consumers for one item. Always loop on a predicate.
• notify on a shared condition can stall everything by waking a thread that cannot proceed. Upgrade: two Conditions on one Lock.
• Barrier(n) for grouping, semaphores for ratio. H2O needs both — permits alone let the next molecule interleave. A barrier rearms after tripping.
• Left-then-right forks deadlock: measured 0 meals, 5 threads stuck. Not slow — stopped.
• Resource ordering breaks it by making philosopher 4 take fork 0 first, destroying the cycle. Waiter semaphore (n − 1 diners) also works. Both: 5 meals, nothing stuck.
• Four Coffman conditions, all required: mutual exclusion (not removable) · hold-and-wait (waiter) · no-preemption (timeouts) · circular wait (ordering). Kill one and deadlock cannot happen.
• Timeout-and-retry risks livelock — running, not progressing. Randomise backoff.
• Deadlock is not starvation. A cycle with nothing moving, versus one thread never served while others progress.
• The real-world rule: acquire locks in a globally consistent order and document it.
• In production use queue.Queue(maxsize=n) — this design, in C, tested.
• Test with join(timeout) so a deadlock fails instead of hanging.