The Dining Philosophers problem, introduced by Edsger Dijkstra in 1971, models synchronization challenges in concurrent systems. Originally conceived as five computers attempting to access five shared tape drives, it was later reformulated by C.A.R. Hoare into the classic version involving philosophers and forks.
The problem involves five philosophers seated at a circular table, with one fork between each pair. Philosophers alternate between thinking and eating, but must adhere to these rules:
- A philosopher can only pick up adjacent forks
- Fork acquisition follows a specific order (left fork first, then right fork)
- Both forks must be held simultaneously to eat
- Forks are released in reverse order after eating
Deadlock Emergence
Deadlock occurs when all five philosophers simultaneously pick up their left forks and then wait indefinitely for their right forks. Each philosopher holds one fork while waiting for another, creating a circular wait condition where no progress is possible.
Four necessary conditions for deadlock apply here: mutual exclusion (forks can only be held by one philosopher), hold-and-wait (philosophers hold while requesting), no preemption (forks cannot be forcibly taken), and circular wait (each philosopher waits for another in a cycle).
Solution Strategies
Two fundamental approaches address synchronization problems: mutual exclusion and ordering. Mutual exclusion ensures that when one thread holds a resource lock, others cannot acquire it. Ordering mandates a consistent acquisition sequence for multiple locks, preventing circular dependencies.
Dijkstra's Semaphore Solution
Dijkstra's original solution assigns each philosopher one of three states: THINKING, HUNGRY, or EATING. A semaphore controls when both forks become available, enabling philosophers to communicate thier redainess through state changes.
import java.util.Random;
import java.util.concurrent.Semaphore;
import java.util.concurrent.TimeUnit;
public class PhilosopherTable {
private static final int PHILOSOPHER_COUNT = 5;
private enum Activity {THINKING, HUNGRY, EATING}
private static final Activity[] philosopherState = new Activity[PHILOSOPHER_COUNT];
private static final Object[] forkLocks = new Object[PHILOSOPHER_COUNT];
private static final Semaphore[] forkSemaphores = new Semaphore[PHILOSOPHER_COUNT];
static {
for (int i = 0; i < PHILOSOPHER_COUNT; i++) {
philosopherState[i] = Activity.THINKING;
forkLocks[i] = new Object();
forkSemaphores[i] = new Semaphore(0);
}
}
private static int getLeftNeighbor(int index) {
return (index - 1 + PHILOSOPHER_COUNT) % PHILOSOPHER_COUNT;
}
private static int getRightNeighbor(int index) {
return (index + 1) % PHILOSOPHER_COUNT;
}
private static int generateWaitTime(int min, int max) {
Random generator = new Random();
return generator.nextInt(max - min + 1) + min;
}
private static void checkAvailability(int index) {
if (philosopherState[index] == Activity.HUNGRY &&
philosopherState[getLeftNeighbor(index)] != Activity.EATING &&
philosopherState[getRightNeighbor(index)] != Activity.EATING) {
philosopherState[index] = Activity.EATING;
forkSemaphores[index].release();
}
}
private static void contemplate(int index) throws InterruptedException {
int waitDuration = generateWaitTime(400, 800);
System.out.println(index + " contemplates for " + waitDuration + "ms");
TimeUnit.MILLISECONDS.sleep(waitDuration);
}
private static void acquireUtensils(int index) throws InterruptedException {
synchronized (forkLocks[index]) {
philosopherState[index] = Activity.HUNGRY;
System.out.println("\t\t" + index + " becomes HUNGRY");
checkAvailability(index);
}
forkSemaphores[index].acquire();
}
private static void consume(int index) throws InterruptedException {
int eatDuration = generateWaitTime(400, 800);
System.out.println("\t\t\t\t" + index + " consumes food for " + eatDuration + "ms");
TimeUnit.MILLISECONDS.sleep(eatDuration);
}
private static void releaseUtensils(int index) {
synchronized (forkLocks[index]) {
philosopherState[index] = Activity.THINKING;
checkAvailability(getLeftNeighbor(index));
checkAvailability(getRightNeighbor(index));
}
}
private static void lifecycle(int index) {
while (true) {
try {
contemplate(index);
acquireUtensils(index);
consume(index);
releaseUtensils(index);
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}
}
public static void main(String[] args) {
System.out.println("Starting Dining Philosophers Simulation");
Thread[] participants = new Thread[PHILOSOPHER_COUNT];
for (int i = 0; i < PHILOSOPHER_COUNT; i++) {
participants[i] = new Thread(() -> lifecycle(i), "Philosopher-" + i);
participants[i].start();
}
}
}
Resource Hierarchy Approach
This solution assigns priority levels to forks (0 through 4), requiring philosophers to acquire the lower-priority fork before the higher-priority one. This eliminates circular wait conditions—when four philosophers simultaneously grab their left forks, the fifth philosopher cannot proceed because the fork numbered 0 is already taken, preventing the deadlock cascade.
This approach has limitations: resources must be released and re-acquired when priorities change, and fairness issues may arise where slow philosophers starve.
import java.util.Random;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
public class PriorityForkSolution {
private static final Random randomGenerator = new Random();
private static int randomDuration(int min, int max) {
return randomGenerator.nextInt(max - min + 1) + min;
}
private static void runPhilosopher(int id, Lock lowerPriority, Lock higherPriority, Lock output) {
while (true) {
int waitTime = randomDuration(200, 800);
synchronized (output) {
System.out.println("Philosopher " + id + " thinks for " + waitTime + "ms");
}
sleep(waitTime);
synchronized (output) {
System.out.println("\t\tPhilosopher " + id + " is hungry");
}
lowerPriority.lock();
try {
higherPriority.lock();
try {
waitTime = randomDuration(200, 800);
synchronized (output) {
System.out.println("\t\t\t\tPhilosopher " + id + " eats for " + waitTime + "ms");
}
sleep(waitTime);
} finally {
higherPriority.unlock();
}
} finally {
lowerPriority.unlock();
}
}
}
private static void sleep(int milliseconds) {
try {
Thread.sleep(milliseconds);
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}
public static void main(String[] args) {
System.out.println("Dining Philosophers - Resource Hierarchy Solution");
Lock forkA = new ReentrantLock();
Lock forkB = new ReentrantLock();
Lock forkC = new ReentrantLock();
Lock forkD = new ReentrantLock();
Lock forkE = new ReentrantLock();
Lock consoleLock = new ReentrantLock();
Thread p1 = new Thread(() -> runPhilosopher(1, forkA, forkB, consoleLock));
Thread p2 = new Thread(() -> runPhilosopher(2, forkB, forkC, consoleLock));
Thread p3 = new Thread(() -> runPhilosopher(3, forkC, forkD, consoleLock));
Thread p4 = new Thread(() -> runPhilosopher(4, forkD, forkE, consoleLock));
Thread p5 = new Thread(() -> runPhilosopher(5, forkE, forkA, consoleLock));
p1.start();
p2.start();
p3.start();
p4.start();
p5.start();
joinAll(p1, p2, p3, p4, p5);
}
private static void joinAll(Thread... threads) {
for (Thread t : threads) {
try {
t.join();
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}
}
}
Chandy-Misra Algorithm
This solution uses dirty/clean states for forks and request messages between philosophers. Initially, all forks are dirty. When a philosopher requests a fork from a neighbor, the neighbor cleans and passes it if dirty, or ignores the request if already clean. After eating, forks become dirty and are cleaned upon request.
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
public class ChandyMisraSolution {
private final int philosopherCount;
private final Lock[] forkLocks;
private final boolean[] forkCondition;
private final boolean[] hungerState;
public ChandyMisraSolution(int count) {
this.philosopherCount = count;
this.forkLocks = new Lock[count];
this.forkCondition = new boolean[count];
this.hungerState = new boolean[count];
for (int i = 0; i < count; i++) {
hungerState[i] = true;
forkLocks[i] = new ReentrantLock();
forkCondition[i] = true; // Start dirty
}
}
private int leftForkOf(int philosopher) {
return philosopher;
}
private int rightForkOf(int philosopher) {
return (philosopher + 1) % philosopherCount;
}
private int leftNeighborOf(int philosopher) {
return (philosopher - 1 + philosopherCount) % philosopherCount;
}
private int rightNeighborOf(int philosopher) {
return (philosopher + 1) % philosopherCount;
}
private void think(int philosopher) {
System.out.println(Thread.currentThread().getName() +
": Philosopher " + philosopher + " is thinking.");
hungerState[philosopher] = true;
}
private void eat(int philosopher) {
System.out.println(Thread.currentThread().getName() +
": Philosopher " + philosopher + " is eating.");
forkLocks[leftForkOf(philosopher)].unlock();
forkLocks[rightForkOf(philosopher)].unlock();
hungerState[philosopher] = false;
}
private boolean tryAcquireForks(int philosopher) {
boolean acquiredLeft = forkLocks[leftForkOf(philosopher)].tryLock();
boolean acquiredRight = forkLocks[rightForkOf(philosopher)].tryLock();
if (acquiredLeft && acquiredRight) {
return true;
}
if (acquiredLeft) {
forkLocks[leftForkOf(philosopher)].unlock();
} else {
sendRequest(philosopher, true);
}
if (acquiredRight) {
forkLocks[rightForkOf(philosopher)].unlock();
} else {
sendRequest(philosopher, false);
}
return false;
}
private void sendRequest(int philosopher, boolean requestingRightFork) {
int forkIndex = requestingRightFork ?
rightForkOf(philosopher) : leftForkOf(philosopher);
if (!forkCondition[forkIndex]) {
return; // Fork is clean, ignore request
}
forkCondition[forkIndex] = false; // Clean the fork
if (forkLocks[forkIndex].tryLock()) {
forkLocks[forkIndex].unlock();
}
}
public void beginSimulation() {
Thread[] participants = new Thread[philosopherCount];
for (int i = 0; i < philosopherCount; i++) {
final int id = i;
participants[i] = new Thread(() -> {
while (true) {
if (tryAcquireForks(id) && hungerState[id]) {
eat(id);
} else {
think(id);
}
}
}, "Philosopher-" + i);
participants[i].start();
}
}
public static void main(String[] args) {
int participantCount = 5;
ChandyMisraSolution simulation = new ChandyMisraSolution(participantCount);
simulation.beginSimulation();
}
}
Waiter-Mediated Solution
Entroducing a central coordinator (waiter) who grants permission before fork acquisition prevents deadlock entirely. The waiter maintains awareness of current fork availability and can delay philosopher requests until both required forks are free. When philosophers 0 and 2 are eating, philosopher 1 cannot proceed because forks are unavailable. Philosopher 3 must wait even for a single fork, as the waiter recognizes this could lead to deadlock.
Limiting Concurrent Diners
A simpler approach restricts the number of philosophers who can attempt to eat simultaneously. With n-1 philosophers allowed to eat at once, at least one philosopher remains waiting, breaking the circular dependency. When a waiting philosopher finishes, another can proceed, ensuring continuous system progress.
These solutions demonstrate how proper synchronization primitives and coordination patterns eliminate deadlock conditions in concurrent systems.