Dining Philosophers Problem
Five philosophers, five forks, and a rule that guarantees deadlock if nobody's careful. Dijkstra's 1965 thought experiment is the cleanest possible model of circular-wait deadlock, and this topic implements it, breaks it on purpose, and fixes it three genuinely different ways.
Learning objectives
- Explain why the naive dining philosophers solution deadlocks
- Apply resource ordering to break circular wait in the dining philosophers setting
- Apply tryLock with timeout and backoff as an alternative fix
- Apply the arbitrator (semaphore) pattern to bound concurrent resource attempts
- Recognize that deadlock-freedom and fairness are different guarantees
Edsger Dijkstra posed a thought experiment in 1965 that has outlived every specific system it was meant to illustrate, because the model underneath it shows up everywhere: five philosophers sit around a round table. Between each adjacent pair sits exactly one fork - five forks total. Each philosopher alternates between two activities: thinking, which needs no resources at all, and eating, which needs both the fork to their left and the fork to their right, held at the same time.
The problem appears the moment you write the obvious solution: each philosopher picks up their left fork, then their right fork, eats, and puts both down. If every philosopher happens to pick up their left fork at roughly the same moment, no philosopher has a right fork available - every single one is now holding one fork and waiting on a neighbor who is, in turn, waiting on them. Nobody can ever eat again. This is deadlock, and it's worth naming precisely why: it's a five-way version of the exact circular-wait condition from the classic two-lock deadlock, just drawn as a ring instead of a pair.
The reason this toy problem earns a permanent place in concurrency curricula is that it forces the full range of standard deadlock-prevention techniques onto one small, visualizable setup, and it exposes a subtlety that a two-lock example can hide: even a solution that provably never deadlocks can still be unfair - some philosopher can, in principle, keep losing every race to eat while the table as a whole stays busy and productive. Deadlock-freedom and fairness turn out to be two separate guarantees, and this topic builds toward both.
Every philosopher and every fix in this topic shares one building block: a Chopstick, a lock-guarded resource wrapping a ReentrantLock rather than plain synchronized, chosen specifically so that a later fix has a timed acquire method to call. This is deliberately the unsafe building block on its own - nothing about it prevents two chopsticks from being acquired in an inconsistent order across threads, which is exactly what makes deadlock possible once naive philosopher logic sits on top of it.
Layer the naive strategy on top: every philosopher picks up its left chopstick, then its right chopstick, with no ordering discipline at all. For four of the five seats this looks harmless in isolation. The problem is systemic: if every philosopher's thread happens to reach "pick up left" before any of them reaches "pick up right," all five now hold exactly one chopstick each and block forever trying to acquire the other. A thread dump at that point would show all five threads BLOCKED, each one waiting on a lock currently held by its neighbor - a five-node cycle, the direct generalization of the two-thread circular wait from a simple lock-ordering bug.
💻 Code example
package concurrency.diningphilosophers; import java.util.concurrent.locks.ReentrantLock; import java.util.concurrent.TimeUnit; public class Chopstick { private final int id; private final ReentrantLock lock = new ReentrantLock(); public Chopstick(int id) { this.id = id; } // Blocking acquire: the calling philosopher thread parks here until no // other philosopher holds this chopstick. public void pickUp() { lock.lock(); } // Non-blocking, timed acquire - used by the tryLock-based fix. public boolean tryPickUp(long timeout, TimeUnit unit) throws InterruptedException { return lock.tryLock(timeout, unit); } public void putDown() { lock.unlock(); } public int getId() { return id; } } /* * Naive philosopher - always deadlock-prone. Not wired up to run in this * chapter's demos; shown to make the failure mode concrete. * * class NaivePhilosopher implements Runnable { * private final Chopstick left, right; * NaivePhilosopher(Chopstick left, Chopstick right) { this.left = left; this.right = right; } * public void run() { * while (true) { * left.pickUp(); // All 5 philosophers pick up left first... * right.pickUp(); // ...and all block here, forever. * right.putDown(); * left.putDown(); * } * } * } * If all 5 threads grab their left chopstick before any grabs a right one, * every thread blocks inside right.pickUp() permanently - a five-way circular * wait, exactly what jstack would show as five BLOCKED threads. */
The canonical fix lives entirely in how each philosopher decides which chopstick to grab first: always acquire the lower-numbered chopstick before the higher-numbered one, regardless of which one is physically "left" or "right" for that seat.
For philosophers 0 through 3, the left chopstick already has the lower ID, so this matches the naive left-then-right order - no visible change for those four seats. The interesting case is the last philosopher, seat 4: its right chopstick wraps around to chopstick 0, so naive left-then-right would grab the higher ID first and the lower ID second - exactly the reversal that completes the circular chain around the whole table. The ID comparison catches this one asymmetric seat and flips its order, so philosopher 4 also reaches for chopstick 0 first, same as philosopher 0 does.
That single flip turns what was a cycle - philosopher 0 waits on chopstick 1, held by philosopher 1, who waits on chopstick 2, and so on around to philosopher 4 waiting on chopstick 0 - into a strict total order with no cycle at all. Whichever philosopher is contending for the globally lowest-numbered chopstick they need can always get it without waiting on anyone further around the ring, and from there the whole system keeps unwinding. This is the same fix from the two-lock deadlock example, generalized from two locks to five: pick a consistent global order for every resource, and a cycle becomes structurally impossible to form.
💻 Code example
package concurrency.diningphilosophers; public class OrderedPhilosopher implements Runnable { private final int id; private final Chopstick firstChopstick; private final Chopstick secondChopstick; public OrderedPhilosopher(int id, Chopstick left, Chopstick right) { this.id = id; // Always acquire the LOWER-numbered chopstick first. This is the // entire fix - it breaks circular wait structurally. if (left.getId() < right.getId()) { firstChopstick = left; secondChopstick = right; } else { firstChopstick = right; secondChopstick = left; } } @Override public void run() { try { for (int i = 0; i < 3; i++) { // A few meals, for demo purposes. Thread.sleep(50); firstChopstick.pickUp(); secondChopstick.pickUp(); System.out.println("Philosopher " + id + " is eating."); Thread.sleep(100); secondChopstick.putDown(); firstChopstick.putDown(); } } catch (InterruptedException e) { Thread.currentThread().interrupt(); } } public static void main(String[] args) throws InterruptedException { int n = 5; Chopstick[] chopsticks = new Chopstick[n]; for (int i = 0; i < n; i++) chopsticks[i] = new Chopstick(i); Thread[] threads = new Thread[n]; for (int i = 0; i < n; i++) { // Philosopher i's "left" is chopsticks[i]; "right" wraps around // via modulo, so philosopher 4's right is chopstick 0. threads[i] = new Thread(new OrderedPhilosopher(i, chopsticks[i], chopsticks[(i + 1) % n])); threads[i].start(); } for (Thread t : threads) t.join(); System.out.println("Resource-ordering simulation complete - no hang."); } }
Instead of reordering which chopstick gets acquired first - fix 1's approach, which breaks circular wait - this fix attacks a different one of the four Coffman conditions directly: hold-and-wait. A philosopher never holds one chopstick while waiting indefinitely for another. It locks the first chopstick normally, since nothing else is held yet, then attempts the second with a timed tryLock(). If that times out, it immediately releases the first chopstick and backs off before retrying the whole attempt from scratch.
The first chopstick's acquisition is always safe to block on, because at that point in the attempt nothing else is held. The second chopstick's acquisition is where the timeout matters: if a neighbor is holding it, the timed tryPickUp() returns false after the timeout instead of blocking forever, and the finally block guarantees the first chopstick gets released regardless of which branch was taken - success or timeout. That unconditional release is the entire fix: this philosopher is never caught holding a partial set of chopsticks while parked waiting.
As with the general tryLock pattern from earlier in this course, a naive fixed retry delay after a failed attempt risks livelock - multiple philosophers backing off and retrying in lockstep, all busy, none making progress. A small random backoff before the next attempt breaks that symmetry.
💻 Code example
package concurrency.diningphilosophers; import java.util.Random; import java.util.concurrent.TimeUnit; public class TryLockPhilosopher implements Runnable { private final int id; private final Chopstick left; private final Chopstick right; private final Random rnd = new Random(); public TryLockPhilosopher(int id, Chopstick left, Chopstick right) { this.id = id; this.left = left; this.right = right; } @Override public void run() { try { int eaten = 0; while (eaten < 3) { Thread.sleep(50); while (!tryEat()) { // Random backoff (1-10ms) stops every philosopher from // retrying in lockstep, which would otherwise livelock. Thread.sleep(1 + rnd.nextInt(10)); } eaten++; } } catch (InterruptedException e) { Thread.currentThread().interrupt(); } } private boolean tryEat() throws InterruptedException { left.pickUp(); // Safe to block: nothing else is held yet. try { // Timed, non-blocking attempt on the second chopstick. if (right.tryPickUp(50, TimeUnit.MILLISECONDS)) { try { System.out.println("Philosopher " + id + " is eating."); Thread.sleep(100); } finally { right.putDown(); } return true; } return false; } finally { // ALWAYS release the first chopstick, whether we ate or not - // this is the entire fix. Breaks the hold-and-wait condition. left.putDown(); } } public static void main(String[] args) throws InterruptedException { int n = 5; Chopstick[] chopsticks = new Chopstick[n]; for (int i = 0; i < n; i++) chopsticks[i] = new Chopstick(i); Thread[] threads = new Thread[n]; for (int i = 0; i < n; i++) { threads[i] = new Thread(new TryLockPhilosopher(i, chopsticks[i], chopsticks[(i + 1) % n])); threads[i].start(); } for (Thread t : threads) t.join(); } }
The third fix attacks the problem indirectly, without touching lock ordering or acquisition timeouts at all. A single shared Semaphore, initialized with N-1 permits - 4 for 5 philosophers - acts as a gatekeeper: a philosopher must acquire a permit from this "waiter" before attempting to pick up any chopstick. The chopstick-acquisition order underneath is still the naive left-then-right - this fix does not rely on ordering at all; it relies purely on limiting how many philosophers can attempt to eat at once.
Deadlock requires all five philosophers to simultaneously hold one chopstick each while blocked waiting for a second. Capping the number of philosophers who can even attempt this at four guarantees that at least one chopstick always stays free, so at least one philosopher can always complete a meal and release its permit, letting the next one through. Naive left-then-right acquisition is safe here only because the semaphore already guarantees at most four of five philosophers attempt it concurrently - the "everyone grabs left simultaneously" scenario that would deadlock five philosophers is structurally impossible once a fifth is always waiting at the door.
Two specific changes silently reintroduce a hang. Raising the permit count from 4 (N-1) to 5 (N) stops the semaphore from restricting anyone - all five could pass the gate and grab their left chopstick simultaneously, right back to the original deadlock. And releasing the permit outside a finally block means an exception mid-meal leaks a permit; eventually every philosopher permanently blocks on acquiring one, a different kind of hang - starvation via exhausted permits, not a lock cycle.
💻 Code example
package concurrency.diningphilosophers; import java.util.concurrent.Semaphore; public class WaiterPhilosopher implements Runnable { // Shared across every philosopher instance - max N-1 (4) can attempt to // eat at once, out of 5 total philosophers. private static final Semaphore WAITER = new Semaphore(4); private final int id; private final Chopstick left; private final Chopstick right; public WaiterPhilosopher(int id, Chopstick left, Chopstick right) { this.id = id; this.left = left; this.right = right; } @Override public void run() { try { for (int i = 0; i < 3; i++) { Thread.sleep(50); WAITER.acquire(); // Ask the waiter for permission. try { // Naive left-then-right is safe here ONLY because the // semaphore above already caps concurrent attempters at 4. left.pickUp(); right.pickUp(); System.out.println("Philosopher " + id + " is eating."); Thread.sleep(100); right.putDown(); left.putDown(); } finally { WAITER.release(); } } } catch (InterruptedException e) { Thread.currentThread().interrupt(); } } public static void main(String[] args) throws InterruptedException { int n = 5; Chopstick[] chopsticks = new Chopstick[n]; for (int i = 0; i < n; i++) chopsticks[i] = new Chopstick(i); Thread[] threads = new Thread[n]; for (int i = 0; i < n; i++) { threads[i] = new Thread(new WaiterPhilosopher(i, chopsticks[i], chopsticks[(i + 1) % n])); threads[i].start(); } for (Thread t : threads) t.join(); System.out.println("Waiter-regulated simulation complete."); } }
None of the three fixes above guarantee fairness - only that the system as a whole keeps making progress. A specific philosopher could, in principle, keep losing every race to its neighbors and never get to eat, even though the table as a whole is busy and no deadlock has occurred. That's starvation: individually unlucky, but systemically invisible, since nothing crashes and no metric at the system level looks wrong.
Each fix has its own fairness gap. Resource ordering guarantees no deadlock but says nothing about turn order - a philosopher could theoretically keep losing the race for its first chopstick to faster neighbors indefinitely. The tryLock fix has the same gap plus a subtler one: random backoff reduces the odds of any one philosopher losing repeatedly, but doesn't eliminate it. The waiter fix is the most exposed of the three: a plain new Semaphore(4) defaults to non-fair, meaning waiting threads aren't served in FIFO order - a philosopher parked on WAITER.acquire() could keep losing to newer arrivals indefinitely. The fix, when it matters, is usually cheap: new Semaphore(4, true) constructs a fair semaphore, serving waiters in strict arrival order, at the cost of some throughput from the added scheduling overhead. ReentrantLock carries the same fairness flag for the same reason. There's no equivalent one-line fix for the resource-ordering or tryLock approaches - real fairness there would need an explicit queue or ticket system layered on top.
This toy problem maps directly onto production concurrency. A philosopher is a thread, a transaction, or a microservice. A chopstick is a database row lock, a file lock, a mutex, or a pooled connection. Eating is the critical section - reading or writing shared state. The classic "all grab left first" deadlock is exactly thread A holding lock A while waiting on lock B, and thread B holding lock B while waiting on lock A. Resource ordering maps to a team-wide convention of always acquiring locks in a consistent, agreed order - alphabetical, numeric, whatever - across every service that touches them. The waiter pattern maps directly onto a connection pool: a bounded number of permits limiting how many callers can hold a database connection at once, which is exactly why connection pools are sized deliberately rather than left unbounded.
Why does the naive solution deadlock? : Every philosopher picks up its left chopstick first, then its right. If all five reach for their left chopstick at once, all five hold exactly one chopstick and wait forever for a second - a five-way circular wait, the same root cause as the classic two-lock deadlock.
Fix 1 - resource ordering : Always acquire the lower-numbered chopstick first, regardless of which is physically "left." This turns the circular dependency into a strict total order, so at least one philosopher can always get both chopsticks it needs.
Fix 2 - tryLock with backoff : Lock the first chopstick normally, but attempt the second with a timeout; release the first immediately on failure and retry after a random delay. This breaks hold-and-wait instead of circular wait, and needs random backoff to avoid livelock.
Fix 3 - the waiter (semaphore) : Cap concurrent eating attempts at N-1 permits so at least one chopstick always stays free. Left-then-right acquisition order becomes safe again, because the semaphore already makes the "all five grab left" scenario impossible.
Do any of the fixes guarantee fairness?
: No - all three guarantee deadlock-freedom, not fairness. A specific philosopher can still starve under any of them. new Semaphore(4, true) or a fair ReentrantLock closes that gap for the waiter pattern specifically, at some cost to throughput.
Want a visual for this concept?
Generate a diagram tailored to “Dining Philosophers Problem” — the AI picks whichever visual (flowchart, comparison, sequence, etc.) best fits.
Sign in to generate a visual →