Dining Philosophers Problem
Formulated by Edsger Dijkstra in 1965, the Dining Philosophers Problem remains one of the most well known examples used to teach process synchronization. It captures a surprisingly common real-world scenario: multiple processes competing for a limited set of shared resources.
Understanding the Problem
Six philosophers are seated around a circular table. Each one alternates between two activities: thinking and eating. To eat, a philosopher needs both a fork and a spoon at the same time. The catch is that only three forks and three spoons are available, each placed between two neighboring philosophers.
A philosopher can only reach the utensils directly beside them. So the question becomes: how do we let everyone eat eventually, without the system getting stuck?
Dining Philosophers: philosophers seated around a circular table with shared utensils between them.
How Deadlock Happens Here
Say all six philosophers get hungry at the same moment and each one grabs the cutlery on their left side first. Now everyone is holding one utensil and waiting for the one on their right, which is already taken by their neighbor. Nobody can move forward.
P1 -> Picks Spoon on left -> Needs Fork on right (held by P6)
P2 -> Picks Fork on left -> Needs Spoon on right (held by P1)
P3 -> Picks Spoon on left -> Needs Fork on right (held by P2)
P4 -> Picks Fork on left -> Needs Spoon on right (held by P3)
P5 -> Picks Spoon on left -> Needs Fork on right (held by P4)
P6 -> Picks Fork on left -> Needs Spoon on right (held by P5)
Result: Circular wait. DEADLOCK. Nobody eats.Solving It with Semaphores
Each fork and spoon gets represented as a binary semaphore starting at 1, meaning it is available. A philosopher must successfully acquire both before eating, and must release both once done.
semaphore fork[3] = {1, 1, 1};
semaphore spoon[3] = {1, 1, 1};
void philosopher(int i) {
while (true) {
think();
wait(fork[i]); // Pick up fork
wait(spoon[i]); // Pick up spoon
eat(); // Critical section
signal(spoon[i]); // Put down spoon
signal(fork[i]); // Put down fork
}
}This ensures no two philosophers hold the same utensil simultaneously. However, the circular wait scenario can still occur if everyone grabs their left utensil at the exact same time.
Breaking the Deadlock
Several strategies exist to prevent the circular wait from forming in the first place:
| Strategy | How It Works | Tradeoff |
|---|---|---|
| Limit to N-1 | Allow at most N-1 philosophers to attempt eating at any given time. A "waiter" semaphore initialized to N-1 controls this. | Simple and effective. Slightly reduces parallelism since one philosopher is always blocked. |
| Asymmetric Pickup | Odd-numbered philosophers pick up the left utensil first. Even-numbered pick up the right first. This breaks the uniform ordering that creates the cycle. | No extra semaphore needed. Slightly harder to reason about correctness. |
| Resource Hierarchy | Number all utensils. Every philosopher always picks up the lower-numbered utensil first. Since the ordering is global, a cycle is impossible. | General-purpose strategy that works for any resource allocation problem. |
| Central Arbitrator | A single coordinator grants permission to pick up both utensils atomically. Philosophers request permission before picking up anything. | Eliminates deadlock entirely but the arbitrator becomes a bottleneck. |
Full Implementation in C++
This implementation uses the "Limit to N-1" strategy with a waiter semaphore to prevent deadlock:
#include <iostream>
#include <thread>
#include <semaphore>
#include <chrono>
#include <vector>
const int N = 5;
std::counting_semaphore<1> forks[N] = {
std::counting_semaphore<1>(1),
std::counting_semaphore<1>(1),
std::counting_semaphore<1>(1),
std::counting_semaphore<1>(1),
std::counting_semaphore<1>(1)
};
std::counting_semaphore<N> waiter(N - 1); // At most N-1 can try
void philosopher(int i) {
for (int round = 0; round < 3; round++) {
// Thinking
std::cout << "Philosopher " << i << " is thinking." << std::endl;
std::this_thread::sleep_for(std::chrono::milliseconds(500));
waiter.acquire(); // Ask the waiter for permission
forks[i].acquire(); // Pick up left fork
forks[(i + 1) % N].acquire(); // Pick up right fork
// Eating
std::cout << "Philosopher " << i << " is eating (round "
<< round << ")." << std::endl;
std::this_thread::sleep_for(std::chrono::milliseconds(300));
forks[(i + 1) % N].release(); // Put down right fork
forks[i].release(); // Put down left fork
waiter.release(); // Leave the table
std::cout << "Philosopher " << i << " finished eating." << std::endl;
}
}
int main() {
std::cout << "Dining Philosophers Simulation" << std::endl;
std::cout << "-------------------------------" << std::endl;
std::vector<std::thread> threads;
for (int i = 0; i < N; i++)
threads.emplace_back(philosopher, i);
for (auto& t : threads)
t.join();
std::cout << "-------------------------------" << std::endl;
std::cout << "All philosophers done." << std::endl;
return 0;
}Output:
Dining Philosophers Simulation
-------------------------------
Philosopher 0 is thinking.
Philosopher 1 is thinking.
Philosopher 2 is thinking.
Philosopher 3 is thinking.
Philosopher 4 is thinking.
Philosopher 0 is eating (round 0).
Philosopher 2 is eating (round 0).
Philosopher 0 finished eating.
Philosopher 1 is eating (round 0).
Philosopher 2 finished eating.
Philosopher 3 is eating (round 0).
...
-------------------------------
All philosophers done.Notice that multiple philosophers can eat at the same time, as long as they are not neighbors competing for the same fork. The waiter semaphore (initialized to N-1) guarantees at least one philosopher is blocked from trying, which breaks the circular wait.
The Four Deadlock Conditions
The Dining Philosophers problem is a perfect lens for understanding the four necessary conditions for deadlock. All four must hold simultaneously for a deadlock to occur. Breaking any one of them prevents it:
| Condition | In Dining Philosophers | How the Solution Breaks It |
|---|---|---|
| Mutual Exclusion | Each utensil can only be held by one philosopher at a time. | Not broken (this is a fundamental requirement). |
| Hold and Wait | A philosopher holds one utensil while waiting for the other. | Can be broken by requiring philosophers to request both utensils atomically. |
| No Preemption | A utensil cannot be forcibly taken from a philosopher. | Can be broken by allowing a philosopher to drop utensils if the second is unavailable. |
| Circular Wait | Each philosopher waits for the utensil held by their neighbor. | Broken by the waiter (N-1 limit), asymmetric pickup, or resource hierarchy. |
The Dining Philosophers Problem teaches a core lesson: when multiple processes share resources, you need a clear strategy to avoid circular waits. Using semaphores along with a limit on how many processes can compete at once keeps things moving without deadlocks. It is a small, contained problem on the surface, but the ideas behind the solution show up constantly in real operating system design.