Simulating Dining Philosophers with SimPy

Explore race conditions, deadlock, and shared resources in Python

Photo by Marisa Harris on Unsplash

The dining philosophers problem is a problem in computer science, and specifically in concurrent systems. Originally invented by Edsger Dijkstra as an exam question, it soon assumed the current form and became a classic. It can be regarded as a toy problem, but it effectively showcases the fundamental conundrum of resource contention. Today we will use it as a perfect excuse for a tutorial on Simpy, a discrete event simulation package for Python, that lends itself very well to modelling the problem. The setup description goes as follows:

There are K philosophers sitting at a round table. Each of them has a bowl of rice in front of them, and there is one chopstick — one only! — between each adjacent pair of bowls. Each philosopher thinks for an indeterminate amount of time, then becomes hungry and has to eat. To eat, he/she must get both the left and right chopsticks. Notice that neighboring philosophers, as a consequence, must alternately use the chopstick that sits between them. When done eating the philosopher puts the chopsticks down and begins a new thinking session.

Quite unrealistically, the philosophers don’t spontaneously communicate and aren’t worried about sharing chopsticks without washing them between uses, but this is just a model! We can begin writing a Python function using Simpy to simulate the K dining philosophers, and introduce the main concepts in the meantime.

In Simpy, all the simulated stuff lives in an instance of Environment , in our case table , declared at line 4. Environments become interesting when there are resources over which someone will compete: in our case, the chopsticks , which are a list of K instances of the Resource class. A Resouce must be referred to an environment, which in our case is (unsurprisingly) table , and has a capacity , meaning how many usage requests can be satisfied by the resource at the same time. The capacity of a chopstick is 1, as it can be used only by a single philosopher at a time (an example of a resource with capacity>1 would be, for example, a bathroom with more than one stall).
At lines 10–11, we use the process method of table to add K processes to the environment, one process for each philosopher. Processes are event generators; in our case, they will issue events such as grabbing a chopstick (as soon as it becomes available) and releasing it. This will probably be a bit clearer in a moment, when we look at the next piece of code. I personally find that Environments and Resources don’t make complete sense without processes… and vice versa: you’ll need to consider both to have the complete picture. According to what we wrote, the processes are calls tophilosopher_process , which in turn is an argument of our function. We will have to pass something that can be called with the right signature.

Now that we got the environment out of the way, we can study the philosophers. Ultimately, the problem is interesting because, if left to their own devices, the philosophers might come up with some behavior that brings them to a state of deadlock, in which no progress is possible and they will starve. For example, let’s say that they use this procedure:

while True:
    # 1-think for a random amount of time
    # 2-grab left chopstick
    # 3-grab right chopstick
    # 4-eat
    # 5-release left chopstick
    # 6-release right chopstick

As we saw in the previous section, the philosopher is represented by a process, and in fact we can see from the above pseudocode that it will issue the usage request for the chopsticks. Therefore, we are going to write a function — in particular, in Python lingo, a generator. Let’s code it up in and go through it.

There sure are quite a few yield statements in there. A process in Simpy can spew out as many events as necessary through yield , and under the hood the Simpy engine will iterate through the events generated by all the declared processes and make them happen in the correct order. In the philosophers’ case, we allow (and would like) it to go on forever, but it is not necessary: a process can also terminate explicitly after having yielded a finite amount of events, if such is the nature of the modeled object.
There are three types of events we are issuing here:

• Resource.request() issues the request of usage of a resource. The execution of the issuing process will not proceed until this request is fulfilled by the engine. If the resource is unavailable (in other words, at full capacity due to previous requests), the simulation will go on until it becomes available (if ever!) before assigning the resource to the process and resuming its execution.
• Resource.release(request) returns 1 unit of capacity to a previously requested resource. It needs a previously fulfilled request as an argument.
• Environment.timeout(duration) instructs the Simpy engine to continue the simulation for a time of duration before coming back and resuming the execution. During this time, naturally, other processes may issue their own events. Timeouts are the only way in which time passes in Simpy simulations! Without timeouts in between them, all other events would be generated at time 0.

Notice that grabbing or putting down a chopstick is not an atomic operation, but it has a duration, handling_time. The rest of the code should be pretty straightforward. We set up a small logging system that appends records to a list, that will allow us to see more clearly what happens in the end. Also, the signature of philosopher contains some extra configuration parameters that we will have to fix (for example by using partial) before passing it to our run_dining_philosophers function. Let’s tie all together in a main script and try it out:

First of all, this code terminates even if the processes have an infinite loop inside them. How so? They somehow stop generating events, and Simpy recognizes this and stops the simulation. Let’s see the printed log:

<T=210131.76>  Phil_#0 is hungry!
<T=210133.76>  Phil_#0 has taken L chopstick (#0)
<T=210140.80>  Phil_#1 is done, releases chopsticks #1/#2
<T=210144.80>  Phil_#0 has taken R chopstick (#1) and can eat
<T=210145.72>  Phil_#3 is done, releases chopsticks #3/#4
<T=210164.80>  Phil_#0 is done, releases chopsticks #0/#1
<T=210179.26>  Phil_#4 is hungry!
<T=210181.26>  Phil_#4 has taken L chopstick (#4)
<T=210183.26>  Phil_#4 has taken R chopstick (#0) and can eat
<T=210203.26>  Phil_#4 is done, releases chopsticks #4/#0
<T=210214.71>  Phil_#3 is hungry!
<T=210215.58>  Phil_#2 is hungry!
<T=210215.80>  Phil_#4 is hungry!
<T=210216.71>  Phil_#3 has taken L chopstick (#3)
<T=210217.14>  Phil_#0 is hungry!
<T=210217.58>  Phil_#2 has taken L chopstick (#2)
<T=210217.80>  Phil_#4 has taken L chopstick (#4)
<T=210217.82>  Phil_#1 is hungry!
<T=210219.14>  Phil_#0 has taken L chopstick (#0)
<T=210219.82>  Phil_#1 has taken L chopstick (#1)

At a certain point, all the thinking philosophers become hungry about at the same time and in the brief handling_time needed to actually grab their respective left chopstick¹, they all find that their neighbor has grabbed the one at their right. They cannot proceed according to the current algorithm. They are in deadlock.

Let’s see a possible solution to our problem: odd philosophers start with the left chopstick , and even philosophers start with the right one.

If you use this version of the philosopher process instead of the previous one, the deadlock disappears and the program won’t stop. I like this solution because it is somewhat elegant, does not require extra synchronization primitives and requires just a small modification to completely avoid deadlock, but it has a major problem in practice: if K is odd, the last philosopher has an advantage over the others and will have to wait less on average for the chopsticks. In fact, the pair of philosophers 0–1, 2–3…will want the chopstick between them as their first one, but the last philosopher does not have such a competitor for his/her first chopstick and this is an advantage.
There are other solutions to the problem (and other variations of the problem itself) taking into account fairness requirements, asymmetry and other subtle interaction phenomena, and you should look at them if you are interested in shared resources and synchronization. Nevertheless, with this relatively simple setup I hope to have given the gist of it and showcased the fundamentals of Simpy!

Meme by author

[1] If the handling was indeed atomic the problem would exist anyways but essentially never occur in practice, as shown e.g. in Solution#2 here involving a mutex for each chopstick…and Simpy resources are indeed mutexes. In fact, if you set handling_timeto 0, the probability of deadlock is astronomical.