Operating System - Dining Philosophers Problem
What is the Dining Philosophers Problem?
Imagine five philosophers sitting around a circular dining table. Each philosopher alternates between thinking and eating.
There is:
-
A bowl of spaghetti in front of each philosopher.
-
One fork between each pair of philosophers.
-
So, 5 philosophers but only 5 forks in total (one between each philosopher).
To eat, a philosopher needs both the left and the right fork.
The Problem
The challenge is to design a protocol (solution) where:
-
No two philosophers use the same fork at the same time (mutual exclusion).
-
Philosophers don’t starve (they eventually get to eat).
-
No deadlock happens (e.g., all philosophers pick up their left fork and wait forever for the right one).
Example Situation:
Let’s label the philosophers P1, P2, P3, P4, P5 and the forks F1 to F5 as follows:
-
P1 has F1 (left) and F2 (right)
-
P2 has F2 and F3
-
...
-
P5 has F5 and F1
Problem Scenario (Deadlock Example):
-
All philosophers pick up their left fork at the same time:
-
P1 picks F1
-
P2 picks F2
-
P3 picks F3
-
P4 picks F4
-
P5 picks F5
-
-
Now, each philosopher is waiting for the right fork, but that fork is already taken by their neighbor.
-
No one can eat. No one will put down a fork. This is deadlock.
Common Solutions
1. Allow Only Four Philosophers to Sit at the Table at Once
-
This avoids the circular wait condition that leads to deadlock.
2. Use a Semaphore or Mutex
-
A philosopher checks (locks) both forks before picking them up.
-
If both are not available, they release the one they have and try again later.
3. Numbered Forks – Pick in Order
-
A philosopher always picks up the lower-numbered fork first, then the higher.
-
For example, P5 will pick up F1 before F5.
-
This prevents circular wait.
4. Asymmetric Behavior
-
Odd-numbered philosophers pick up the left fork first.
-
Even-numbered philosophers pick up the right fork first.
What It Teaches
-
Deadlock: When every process is waiting for a resource held by another, and none can proceed.
-
Starvation: When a process waits indefinitely because others keep taking the resources.
-
Concurrency Control: How to manage access to shared resources.