Dining Philosophers Problem
AdvancedFive philosophers alternating between thinking and eating share five forks, demonstrating the deadlock problem and its solutions: ordered lock acquisition, arbitrator, and asymmetric strategies.
Overview
The dining philosophers problem (Dijkstra, 1965) illustrates deadlock and starvation. Five philosophers sit around a table with one fork between each adjacent pair. To eat, a philosopher needs both the fork to their left and the fork to their right. If every philosopher simultaneously picks up their left fork, all are waiting for their right fork — which is held by the next philosopher — and no one can eat: this is deadlock. The naive solution (each picks up left then right) deadlocks. Solutions: (1) Allow at most four philosophers to try eating simultaneously — guarantees at least one can always eat. (2) Asymmetric: odd-numbered philosophers pick left-then-right; even pick right-then-left — breaks the circular wait condition. (3) Arbitrator/waiter: a central coordinator grants permission — serialises but eliminates deadlock. (4) Chandy-Misra: message-passing solution. In Java, deadlock occurs when threads acquire multiple locks in inconsistent order — the dining philosophers is the canonical illustration.
Deadlock-Prone Version and Thread Dump Diagnosis
The deadlock scenario is created when all threads acquire their "left" lock and wait for their "right" lock, which is held by the next thread. Java's thread dump (jstack or VisualVM) shows the circular wait chain, labelled "Found one Java-level deadlock." This is the most powerful debugging tool for deadlocks in production.
// Deadlock-prone dining philosophers
ReentrantLock[] forks = new ReentrantLock[5];
for (int i = 0; i < 5; i++) forks[i] = new ReentrantLock();
Runnable deadlockPhilosopher(int id) {
return () -> {
int left = id;
int right = (id + 1) % 5;
while (true) {
// DEADLOCK: all pick up left fork, then wait for right
forks[left].lock(); // pick up left fork
System.out.println("P" + id + " has left fork " + left);
try { Thread.sleep(10); } catch (InterruptedException e) { return; }
// All 5 philosophers reach here simultaneously:
// P0 waits for fork1 (held by P1)
// P1 waits for fork2 (held by P2) → CIRCULAR WAIT = DEADLOCK
forks[right].lock();
try {
System.out.println("P" + id + " eating");
Thread.sleep(50);
} catch (InterruptedException e) {
forks[right].unlock(); return;
} finally {
forks[right].unlock();
}
forks[left].unlock();
}
};
}
// Detect: jstack <pid> → "Found one Java-level deadlock"
// Shows cycle: Thread-0 waiting for lock held by Thread-1 waiting for ... Thread-4 waiting for Thread-0Fix: Ordered Lock Acquisition (Asymmetric Solution)
The deadlock arises from circular wait — one of the four necessary deadlock conditions. Breaking circular wait by enforcing a global lock ordering prevents deadlock. Odd philosophers pick up the lower-numbered fork first; even philosophers pick up the higher-numbered fork first. This breaks the symmetry that enables circular waiting. This principle applies universally: always acquire multiple locks in a consistent global order.
// FIXED: Ordered lock acquisition — breaks circular wait
ReentrantLock[] forks = new ReentrantLock[5];
for (int i = 0; i < 5; i++) forks[i] = new ReentrantLock();
Runnable philosopher(int id) {
return () -> {
// Asymmetric: always acquire lower-numbered lock first
int first = Math.min(id, (id + 1) % 5); // lower index
int second = Math.max(id, (id + 1) % 5); // higher index
// Philosopher 0: forks 0,1 Philosopher 4: forks 0,4 (min=0,max=4)
for (int meal = 0; meal < 3; meal++) {
// Think
System.out.println("P" + id + " thinking");
try { Thread.sleep(10 + (int)(Math.random() * 40)); }
catch (InterruptedException e) { return; }
// Eat — acquire in consistent order (no circular wait possible)
forks[first].lock();
forks[second].lock();
try {
System.out.printf("P%d eating (forks %d,%d) meal %d%n",
id, first, second, meal + 1);
Thread.sleep(30);
} catch (InterruptedException e) { return; }
finally {
forks[second].unlock();
forks[first].unlock();
}
}
};
}
Thread[] philosophers = new Thread[5];
for (int i = 0; i < 5; i++) philosophers[i] = new Thread(philosopher(i), "P" + i);
for (Thread t : philosophers) t.start();
for (Thread t : philosophers) t.join();
System.out.println("All philosophers finished — no deadlock!");Key Points to Remember
- 1Deadlock requires all four conditions: mutual exclusion, hold and wait, no preemption, circular wait.
- 2Dining philosophers deadlock: all pick left fork, wait for right → circular wait.
- 3Breaking circular wait by enforcing global lock ordering prevents deadlock.
- 4Asymmetric solution: always acquire locks in lower-index-first order across all threads.
- 5Java thread dump (jstack) identifies deadlock cycles: "Found one Java-level deadlock."
- 6General rule: when acquiring multiple locks, always acquire them in the same global order across all threads.
Interview Questions
Sign in to ask AriaWhat are the four necessary conditions for deadlock?
Describe three solutions to the dining philosophers deadlock.
How does ordered lock acquisition break the circular wait condition?
In a Java application, two threads each hold one lock and wait for the other. How would you detect and fix this deadlock?
Ask Aria about Dining Philosophers Problem
Your personal AI tutor — ask anything about this concept
Revision Status
Personal Notes
Sign in to save personal notes for this topic.
Discussion
Sign in to join the discussion.