The Dining Philosophers Problem (Or Your Introduction to Thinking in Computer Science)

Who's this article recommended for

Absolute rookies wondering what to expect from a study in computer science and how it can help elevate their general approach to coding.

Five Philosophers, Sitting in a Circle

Imagine that you're in charge of the eating arrangements of five sober philosophers sitting in a circle. On each side of them is a chopstick, which adds up to five chopsticks in total.

The philosophers, naturally, love to think. But they're also there to eat. The only way that they can eat is if they have two chopsticks.

How do you design a system (or algorithm, if you will) that ensures the philosophers can eat and think and eat and think and eat and think?

System constraints

There are three constraints to take into consideration here:
a. Food is infinite, ie a philosopher can eat for as long as they want, and
b. A philosopher can think for as long as they want.
c. A philosopher can only eat when they have two chopsticks

Thinking about the problem

A very useful framework for solving programming challenges like this one is Lambda School's acronym-based formula, called the UPER framework. It's straightforward and intuitive. It reads as follows:

• U for Understand
• P for Plan
• E for Execute
• R for Reflect (Loop!)

Understand

In trying to understand the problem, I made a drawing of the five philosophers and placed the chopsticks on each side of them, until I had the chopsticks distributed among them.

As soon as this was done, I spent some time thinking about the problem, which led me to realize that the chopsticks lend themselves to a concept known in computer science as semaphores. I'll supply a simple definition:

A semaphore is something used to keep track of a resource upon which a process (or series of processes) is dependent. In the case of the Dining Philosophers problem, we can think of the resource (chopsticks) in terms of a counting semaphore. A counting semaphore simply counts up (or down) on the availability of the resource (the chopstick).

Explained in a different way, if you wanted to use a bathroom in a building with only three bathrooms, you could meet the building manager who keeps an updated semaphore of how many bathrooms are occupied and how many are free. Armed with the semaphore, the building manager can then decide (using different techniques) who gets to use the rooms when they're free. After allocating a room, the building manager deducts one resource from the semaphore, and if a room becomes available again, he adds one more resource to the semaphore.

Long talk, but understanding the Dining Philosophers problem suggests that this is a resource allocation problem, so we need a counting semaphore to keep track of the chopsticks.

semaphore = 5

Plan

Now, we need to plan the best way to allocate the chopsticks so that each philosopher can eat and think without obstructing the activities of another one.

First, we can see that the philosophers have two states: eating and thinking.

philosopher.state[0] = {eating:true, thinking:false}

These states are mutually exclusive (a thinking philosopher is not eating, and an eating philosopher is not thinking).

We can go further in our assumptions that when one philosopher picks up a chopstick, it means they're ready to eat, and are simply waiting for the philosopher on either side of them to drop the chopstick they're holding.

In other words, there's a mid-state we have to account for. Let's call it ready_to_eat which we can observe by seeing a philosopher pick up one chopstick.

If we've planned properly, we should have a system that works like this:

philosopher[i] has 0 chopsticks
philosopher[i] is in thinking state
semaphores = 5
philosopher[i] picks up 1 chopstick
ready_to_eat = true
semaphores=4
philosopher[i] picks up second chopstick
semaphores=3
philosopher[i] is in eating state
philosopher[i] puts down chopsticks
semaphores=5
philosopher[i] is in thinking state`

We can then loop indefinitely with these states and conditions accounted for.

Execute

This is the bit where we then create the program and run it with five processes (philosophers) in place. This program is nearly perfect, but as soon as we execute, we'll experience something called a deadlock (when processes are jammed and unable to terminate/complete execution because resources are locked in place).

In other words, the semaphores go down to zero, but all philosophers are locked in a ready_to_eat limbo state forever.

What happened? All philosophers picked a chopstick each! They're not thinking or eating - but they're ready to eat but have no spare chopsticks!

Reflect

In the reflection phase, we sit in the dark and ponder on our code and figure out ways to fix execution problems. In this case, we're going to reflect on fixing the deadlock problem before returning to execution.

Here are a few ways to resolve the deadlock problem:

1. Have four, not five philosophers: If we have one chopstick more than philosophers at the table, it becomes possible for a philosopher to be eating while other philosophers are in a ready_to_eat state without a deadlock happening.

2. We can also artificially constrain the system using a FIFO system + a skip: we start philosopher 1 at at eating state, which also puts philosopher 3 at an eating state. This means only philosopher 4 can be in a ready_to_eat state. If philosopher 4 is truly ready to eat, they’ll pick the chopsticks after 3 is ready and done, otherwise the chopsticks will be free for use by 5 when 1 is done. Whenever the counting semaphore defaults to zero, restart the FIFO (First in, First Out) system + a skip.

3. Make it so a philosopher can only pick up a chopstick when both right and left chopsticks are free.

Closing notes

Can you think of additional ways to fix the deadlock of the philosophers? Share!