Dining philosophers problem
Classic concurrency problem illustrating deadlock and synchronization.
The dining philosophers problem is a classic example in computer science, used to demonstrate synchronization challenges and solutions in concurrent algorithm design. Edsger Dijkstra originally posed it in 1965 as a student exam exercise, framing it as computers competing for tape drive access. Tony Hoare later adapted it into its current form.
In the problem, five philosophers sit at a round table, each with a plate. A single fork lies between each pair of adjacent plates. The meal is spaghetti, requiring two forks to eat. Each philosopher alternates between thinking and eating, but can only eat when holding both the left and right fork. This means a philosopher can eat only when both neighbors are thinking, not eating. After finishing, the philosopher puts down both forks. The challenge is to design a concurrent algorithm ensuring no philosopher starves—each can forever cycle between thinking and eating—despite having no knowledge of when others will eat or think.
The problem highlights difficulties in avoiding deadlock, where no progress is possible. A naive approach instructs each philosopher to: think until the left fork is available, pick it up; think until the right fork is available, pick it up; eat for a fixed time; put down the left fork; then the right fork; and repeat. This can lead to deadlock if every philosopher picks up their left fork simultaneously, leaving each waiting forever for the right fork. Other issues include resource starvation, mutual exclusion, and livelock.
Four conditions are necessary for deadlock: mutual exclusion (no fork used by multiple philosophers at once), resource holding (holding a fork while waiting for another), non-preemption (no philosopher can take a fork from another), and circular wait (each philosopher may wait on the neighbor to the left). A solution must break at least one condition. While negating mutual exclusion or non-preemption can work, most theoretical approaches treat those as fixed, instead addressing resource holding or circular wait.
Dijkstra’s solution negates resource holding by having philosophers atomically pick up both forks or wait, never holding just one fork outside a critical section. It uses one mutex, one semaphore per philosopher, and one state variable per philosopher. This is more complex than the resource hierarchy solution.
The resource hierarchy solution negates circular wai
- field
- Computer science
- known_for
- Illustrating synchronization issues and deadlock in concurrent algorithms
- originator
- Edsger Dijkstra (1965)
- reformulator
- Tony Hoare
- problem_type
- Concurrent algorithm design example
Lore & Background
The problem involves five philosophers dining together at a table, each with their own plate and a fork between each pair of adjacent plates. The dish is spaghetti that must be eaten with two forks. Each philosopher alternately thinks and eats, but can only eat when holding both left and right forks. Two forks are available only when both nearest neighbors are thinking. After eating, a philosopher puts down both forks. The challenge is to design a concurrent algorithm so that no philosopher starves, given incomplete information about others' intentions.
The problem was designed to illustrate challenges of avoiding deadlock, a state where no progress is possible. A naive solution—where each philosopher picks up the left fork, then the right fork, eats, and puts down both—can lead to deadlock if all five pick up their left forks simultaneously. Other issues include resource starvation, mutual exclusion, and livelock.
Several solutions exist. Dijkstra's solution negates resource holding by having philosophers atomically pick up both forks or wait, using a mutex, semaphores, and state variables. The resource hierarchy solution negates circular wait by numbering forks and requiring philosophers to pick up the lower-numbered fork first, but it is not always practical or fair. Other approaches include an arbitrator solution, limiting the number of diners, and the Chandy/Misra solution, which uses clean/dirty fork states and request messages.
Reader's Guide
The dining philosophers problem remains a foundational teaching tool in concurrent algorithm design, demonstrating core synchronization issues such as deadlock, starvation, and mutual exclusion. Its formulation by Dijkstra and subsequent refinement by Hoare established a canonical example that has been used for decades in computer science education. The problem's solutions—including Dijkstra's semaphore-based approach, the resource hierarchy method, and the Chandy/Misra distributed solution—illustrate different strategies for avoiding deadlock by negating one of its four necessary conditions: mutual exclusion, resource holding, non-preemption, or circular wait. While the problem is abstract, its principles apply directly to real-world systems involving shared resources, such as database access, operating system resource allocation, and network protocols. The resource hierarchy solution, though deadlock-free, highlights practical limitations when resource requirements are not known in advance or when fairness is needed. The Chandy/Misra solution extends the problem to arbitrary numbers of agents and resources, offering a fully distributed approach. Overall, the dining philosophers problem continues to serve as a benchmark for evaluating concurrency control mechanisms and as a gateway for students to understand the complexities of parallel computing.
Did You Know?
- The problem was originally formulated in 1965 by Edsger Dijkstra as a student exam exercise about computers competing for tape drive peripherals.
- Tony Hoare gave the problem its present form involving five philosophers and forks.
- A naive solution where each philosopher picks up the left fork first can lead to deadlock if all five do so simultaneously.
- The Chandy/Misra solution violates the requirement that philosophers do not speak to each other due to request messages.
More in Dutch inventions 1-24
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record