Now that we understand the Dining Philosophers Problem, we need to figure out a solution.
Our optimal solution will ensure that each philosopher has an equal time to eat and think.
Ideally, we would also want to maximize the amount of time each philosopher can spend on both tasks.
We also want to make sure no philosophers starve or wait too long to eat.
Please click on either button to learn more about the common solutions to the Dining Philosophers Problem.
The Dining Philosophers Problem has two common solutions:
The resource hierarchy solution establishes an ordering to the chopsticks. Each chopstick is numbered (order does not matter). The philosophers will pick up the lower numbered chopstick adjacent to them then pick up the one numbered higher. Regardless of how you number the chopsticks, you are guaranteed to have at least two philosphers who will reach for the same chopstick. Thus, only one of those two philosophers will be able to get that chopstick and proceed to grab the second. For example, if we number the chopsticks in counter-clockwise order with five philosophers around the table, the fifth philosopher will find that the lower numbered chopstick is to their right while every other philosopher's lower numbered chopstick is to their left. When reaching for the chopsticks, in this case, two of the philosophers will reach for the same one. Obviously, only one philosopher can hold a chopstick at any given time.
Let us assume, keeping our example from before, that the philosopher 1 beats the philosopher 5 to their shared chopstick. This keeps philosopher 5 waiting until philosopher 1 is done eating. However, philosopher 1 must wait for philosopher 2 to finish eating because they have philosopher 1's higher numbered chopstick. The same is true with philosopher 2 waiting on philosopher 3 and philosopher 3 waiting on philosopher 4. Philosopher 4, however, is good to go. Since philosopher 5 is waiting on philosopher 1, they have not picked up their higher numbered chopstick which is shared with philosopher 4. Philosopher 4 claims this chopstick and is able to eat. Once they are finished, they will set down their chopsticks which allows philosopher 3 to eat and so on. The resource hierarchy method guarantees at least one philosopher is able to eat at any given time while the others wait.
If we wanted to make sure all philosophers have a fair shot at eating (maybe one is very hungry and will not stop eating for a few hours), we can place a time limit on each philosopher when they begin eating. This prevents the philosophers from encountering resource starvation.
The arbitrator solution adds a new construct to the problem: a waiter. Instead of having a strict ordering to the chopsticks, we place a waiter in charge of ensuring only one philosopher has permission to eat at any given time. Our waiter will process each request to eat on a first-come-first-served basis. The waiter construct can be implemented as something called a mutex, meaning mutual exclusion. We ensure that only one philosopher can eat at a time by making the permission to eat a mutually exclusive resource. This by definition means that only one member of a group can access that resource at any given time. We might implement this as a lock meaning the first philosopher who asks for permission to eat is granted their request and claims the resource (permission to eat). Nobody else can obtain permission to eat until the currently eating philosopher finishes and gives it up. The waiter then gives permission to the next philosopher who requested permission to eat.
We can implement a timer scheme to ensure some degree of fair play. The waiter will give each philospher requesting permission a certain amount of time to eat before they must relinquish their permission and it is passed on to the next request. Essentially, the mutex lock they have on the permission to eat will time out and they must give up their lock. This constraint prevents the philosophers from encountering resource starvation.