How would one solve the dining philosophers problem at the end of 2018? It’s been 53 years since Dijkstra originally formulated the problem. Are we still using locks to solve it? Do we properly avoid deadlocks and starvation?
The vast majority of implementations I found doing an Internet search revealed to me that we are using mutexes or semaphores for it. But we mentioned previously that this is a bad approach; we should use tasks instead.
In this blog post, we give several solutions to the dining philosophers problem, each with some pros and cons. But, more importantly, we walk the reader through the most important aspects of using tasks to solve concurrency problems.
Instead of reaching for our higher-level frameworks, we opted to keep the level of abstractions as close as possible to raw tasks. This way, we hope to guide the reader to understand more about the essence of task-based programming. Our aim is to make the reader comprehend the machinery of composing tasks; those skills should be highly valuable.
The problem to be solved
We have N philosophers dining at a round table (the original problem stated 5 philosophers, but let’s generalize). Each philosopher has a bowl of spaghetti in front of him. A fork is placed between each pair of adjacent philosophers. As a consequence, each philosopher has a fork on his left and on his right side.
Each philosopher will alternatively eat and think. Eating requires a philosopher to pick up both forks (from his left and right side). One fork cannot be used simultaneously by two philosophers; this means that when a philosopher eats, the adjacent philosophers must think. After eating, each philosopher must put the forks down, so that they can be available to other philosophers (including self). If a philosopher tries to eat and has the fork taken, it must go back to thinking.
The problem is to design a concurrent algorithm that will make the philosophers alternate eating and thinking, following the above constraints, without deadlocking, and without starving.
There are two main pitfalls to be avoided when designing a solution to this problem: deadlock and starvation.
A deadlock can occur, for example, if each philosopher will pick up the left fork, and cannot pick the right fork (as the philosopher on his right already picked it), and the algorithm requires a philosopher to wait indefinitely until the fork can be picked up.
Starvation can occur, for example, if a philosopher finds at least one fork busy each time he wants to eat.
The problem is often invoked as an example of mutual exclusion: we have a set of resources that need to be shared between multiple actors. The typical approach to this is to add mutexes or semaphores for solving the problem.
For our study, we particularize the problem in the following ways:
- after eating K times, the philosophers will leave the table – we want to ensure that our program terminates
- a philosopher always starts thinking when joining the dinner
- for reporting purposes, we distinguish between thinking after successful eating and thinking after a failure to eat
None of this will essentially change the core of the problem; just makes it easier for us to describe what we are doing.
Let’s first approach the problem by thinking in terms of tasks. At the first approximation, for each philosopher, we can have 3 types of tasks—eat, think and leave—, and we have constraints between the eat tasks.
For 3 philosophers, the chain of tasks would look something like:
The think tasks don’t need any special synchronization; they can run in parallel with any other tasks. Same for the leave tasks. The eat tasks, however, have synchronization conditions, based on the forks near each philosopher. We illustrated this fact in our diagram by writing what forks each eat task needs (between forks f0, f1 and f2).
This diagram provides a good approximation of the problem, but it leaves one important detail out: what happens if a philosopher cannot pick up the forks to start eating? It needs to fall back to thinking some more. And we didn’t properly account for that in our diagram.
Let us be more precise, and this time create a pseudo state diagram with tasks that a philosopher is having, encoding the possible transitions.
After thinking and before eating the philosopher needs to acquire the forks. There needs to be some logic corresponding to this activity, and we’ve depicted it in our diagram with a rounded yellow square. If the forks were successfully acquired, we can enqueue the eating task. Otherwise, we need to remain in the thinking state. For demonstration purposes, we make a distinction here between a regular thinking task and a hungry thinking task; we might as well have encoded them with a single task.
After eating, we need to release the forks; again a rounded yellow box. If the philosopher has been eating the required number of times, we enqueue the leaving task, and the philosopher leaves the party.
As one may expect, the important part of solving this problem corresponds to the two rounded yellow boxes. These are the only nodes that may have different outcomes and may require more logic.
But, before showing how we might solve the problem, we make a short digression and introduce all our tasking constructs.
Always start a concurrency problem by trying to draw (at least at a higher level) the tasks involved.
The tasks framework
In a problem concerning philosophers, it makes sense for us to aim at understanding the essence of things. Instead of using a higher level framework for solving the problems (futures, continuations, task flows, etc.), we aim to use low-level tasks as much as possible. We use this approach, as we are aiming at two things:
- instructs the reader how to think in terms of tasks
- show that tasks are a good concurrency primitive, that can be used to solve a large variety of problems
Here are the only declarations that we are using for solving the problems with tasks:
And here is the implementation of these classes:
This is it. That’s the only framework implementation needed to start solving complex concurrency problems using tasks (well, dining philosophers is not exactly a complex problem, but still…).
We chose to use Intel’s Threading Building Blocks library because it makes it easier for us to deal with tasks. But we might as well implement our abstractions on top of pure C++11 std::async feature (I wouldn’t necessarily recommend that, but let’s leave that discussion to another post).
Looking at the implementation, things are relatively straightforward:
- in its simplest form, a task is a function with no parameters that doesn’t return anything
- the GlobalTaskExecutor will just enqueue a task to be executed in the global task execution system
- one can enqueue multiple tasks in parallel, and most likely, these tasks will be executed in parallel
- the GlobalTaskExecutor::enqueue does not block waiting for the task to be executed
- the task serializer ensures that only one task passed to it will be executed at a given time
- to achieve this it maintains a queue of tasks
- new tasks go to the back of the queue
- while the queue is not empty, extract one task from the queue and enqueue it in the underlying task executor
- after each task execution is complete, we call
onTaskDoneto continue the execution
- if there are still tasks in the queue, start the first one from the queue
- note the use of a lambda expression when enqueueing task in the serializer
- it is very useful for binding parameters to a function call
- also very useful to add a continuation to an existing task
- in our case, we want to call
onTaskDoneto enqueue the next task, as soon as the current task finishes executing
One can use lambda expressions to bind parameters to functions and transform them into zero-parameter functions that can be used as tasks.
Let’s approach now the dining philosophers problem by starting to look at the
Philosopher abstraction. We modeled the essential parts of the philosopher behavior but did not directly embed the dining protocol inside it. Instead, we keep the
Philosopher class open to change and use a
PhilosopherProtocol class to implement the details of the protocol (open-closed principle).
Let’s analyze this abstraction, piece by piece.
First, let’s look at the data for a philosopher. We have a name (currently not used), we keep track of how many meals the philosopher still needs to have before leaving the table, we have a flag telling us that the philosopher is done dining, and then we have a
PhilosopherProtocol object that the philosopher should follow, and finally an event log that we use for keeping track of the actions that the philosopher is doing.
doneDining_ flag is an atomic flag as it is accessed from multiple threads: it’s set by the thread that executes the leave task, and it’s also read from the main thread that checks if all the philosophers left the table.
start method is called whenever a philosopher joins the dining table. It will pass a protocol to the philosopher. This protocol is used to actually implement the concurrency part of the problem. The philosopher just registers himself to the protocol, describing the behavior for the following actions: eating, thinking while after failing to eat, regular thinking and leaving. Again, to be noted how we use a lambda expression to bind the
this parameter and form tasks that take no parameters.
The main thread will constantly call the
isDone method to check when all philosophers left. The
eventLog method is called after the philosopher left the table, to get the log of events associated with the philosopher, and do a pretty-print of the philosopher’s activities. Because this will only be called when all the tasks are done, there is no need to ensure thread-safety of this method.
Finally, we have
doLeave as private methods. These implement the behavior corresponding to each philosopher. In our implementation, these actions will just log the start of the activity, wait for a while, then log the end of the activity. After each of the action, we call the protocol to continue the philosopher’s dinner protocol.
As one can see, this form of design separates that dining policy out of the
Philosopher class. It allows us to implement multiple policies without changing this class. The
PhilosopherProtocol interface looks like this:
This should be self-explanatory.
If we create a number of different philosophers, with some dining protocol, we can obtain an output similar to this:
In this output, we mark with
E an eating task, with
t a pure thinking task, with
. a thinking task resulting after failing to eat and with
L the leaving task.
Now, let’s implement the protocol.
Take 1: an incorrect version
To warm ourselves up, let’s implement a version of the protocol that does not consider any constraints related to fork availability:
This is a very simple implementation of the protocol that will just chain tasks, and nothing else. There are however a few key takeaways from this simple protocol implementation.
Key observation 1. We can easily chain tasks together by hand; the trick is to add an
enqueue at the end of each task. In this case, the following flow happens;
startDining()enqueues the first thinking task
- at the end of the thinking task,
onThinkingDoneis called; this enqueues the eating task
- at the end of the eating task,
onEatingDone(false)is called; this enqueues the thinking task
- after 3 eating tasks, interleaved with thinking,
onEatingDone(true)is called; this enqueues the leaving task
This is actually a simple implementation of the tasks described in Figure 2, ignoring any constraints imposed by the availability of forks.
Key observation 2. We’ve actually implemented a
TaskSerializer by hand. Although we didn’t use a
TaskSerializer object, by how we do the enqueueing of tasks at the end of other tasks we essentially obtain serialization of tasks. This will guarantee that there will not be two tasks corresponding to a single philosopher executed in parallel.
One can create chains of tasks by hand by adding logic to enqueue the next task at the end of each task. This pattern can be used to implement by hand any task graph (i.e., model any concurrency problem).
Using a waiter
Ok, now it’s time to look into solving the problem with forks contention. Forks are a resource that requires exclusive access: two philosophers cannot use the same fork at the same time. We need to serialize the access to the forks while preventing the philosophers to enter a deadlock state.
One simple way of solving this problem is to add a waiter: this is one actor that is responsible for distributing the forks among the philosophers (see arbitrator solution). Instead of philosophers picking up the forks by themselves, they request the forks to the waiter; if the forks are available, they will be handed to the philosopher. Similarly, when a philosopher finishes eating, it will pass the forks to the waiter (hopefully to clean them before making them available to the next philosopher).
The implementation of such a protocol looks the following way:
The protocol implementation is still simple, as most of the work is done by the waiter. When thinking is done, it will request the waiter for the forks. Unlike the previous version, this operation can result in failure; therefore we have two possible continuations: the philosopher starts eating or the philosopher falls back to thinking as a result of an eating failure. The protocol just calls
requestForks passing the two tasks to be executed as a continuation; the waiter is guaranteed to enqueue one of these tasks.
When the philosopher is done eating, the forks are returned to the waiter by calling the
returnForks method. After that, the philosopher can enqueue the next task to be done: either thinking or leaving.
With this implementation, please note that the philosopher may start to think while the forks are being returned to the waiter. This reduces the latency for the philosopher, but adds another potential case to our problem; see below.
For this solution to work, there needs to be only one waiter that is shared amongst all protocol objects.
Now, let’s turn our attention to the
Waiter class. It keeps track of all the forks in use inside an
std::vector<bool> object. As philosophers may want to call the waiter from different threads, the waiter serializes the access to this data member by using a
TaskSerializer. Imagine how this would work in real life: the waiter can be called in parallel by multiple persons, but it cannot interact with multiple people at once. Therefore he keeps track of who called him, and as soon as he is done with one person, it moves to accommodate the request of the next one. In order words, the actions of the waiter are serialized.
TaskSerializer here would be somehow equivalent to using a mutex to protect the inner data of the waiter, with the main advantage that it will not block the callers.
Once this problem is solved, the actual logic inside the
Waiter class is simple: whenever it is asked for forks, checks for availability and responds correspondingly (success or failure); whenever the forks are returned, it will mark the forks as not being used anymore.
Encapsulation of threading concerns
Probably the biggest advantage of using tasks inside the
Waiter class is the encapsulation of inner threading logic. The fact that we are using a task serializer is not exposed to the outside world. We could have just as well used mutexes on inner tasks (abomination!).
If we would have just used mutexes without any tasks, the caller could observe the fact that the calls made to
Waiter would block. It could change its implementation, and moreover, in certain circumstances, it might also lead to deadlocks.
What we gained by doing this is composability. I’m not sure how to properly emphasize the importance of composability. Composability is fundamental in software engineering. That is because the main approach of solving problems in computer science is decomposition, which needs composition to aggregate the smaller wins.
We can say that this simple class implements the active object pattern: the method execution is decoupled from the method invocation. In some sense, this is also similar to the actor model.
One can hide the threading constraints from the outside world, by using an internal task serializer, and enqueueing all work to it. This proves really useful at decoupling concerns.
An interesting case
The way we constructed our waiter protocol, we can have a very interested: one philosopher is waiting on himself to release the forks.
We said that we wanted the philosopher to start thinking immediately after finishing to eat, in parallel with handling the forks to the waiter. That is good for latency (i.e., help the philosopher get to the thinking state faster). But, what happens if the waiter is busy for a long time?
The philosopher can finish up thinking, try to acquire the forks from the waiter, even before the waiter took the forks from him.
In our case, nothing bad happens. The philosopher will be just denied to eat and it will be back in the thinking state.
I wanted to briefly touch this case as we often encounter similar cases in practice. Each time we are doing things in parallel, we need to create a small indeterminism, which may lead to strange cases. We need to be fully prepared for such cases.
This implementation lacks fairness. For example, it may lead to this case:
Here, Socrates is denied to eat until both Plato and Aristotle leave the table. Poor Socrates, left starving…
Aristotle finished up the first thinking part and requests the forks. When Plato and Socrates first finish thinking they could not acquire the required forks from the waiter. Each time Socrates is done thinking and attempt to get the forks, the waiter will deny the request, and Socrates needs to think some more.
This may be attributed to Socrates’ luck, but the waiter is clearly unfair. If Socrates was requesting the forks earlier, why does the waiter give the forks to Plato and Aristotle? Probably because the waiter doesn’t have any memory of who requested the forks.
To add fairness to the implementation and avoid starving, we will add memory to the waiter.
Essentially, the algorithm is the same, but we add the
waitingQueue_ to maintain fairness. If a philosopher requests the forks, but a neighbor requested the forks before this one, the request will be denied. This way, the neighbor that requested the forks first will have priority.
The output of running the program would look like the following:
One can see with the naked eye that the philosophers have some kind of a round-robin turn for eating.
On the other hand, what’s also visible from this output is that there are times in which the forks are not used by any of the philosophers. That is because once a philosopher announces its intention to eat, it will prevent the neighbor philosophers from eating again, while the philosopher is thinking.
Be careful when adding fairness to concurrent processes; it often leads to worse throughput performance.
Synchronization at the fork level
The solutions presented so far solve the problem decently, but they do not scale properly. The waiter is a bottleneck. There is a common resource that needs to be exclusively taken in order to properly implement the dining protocol.
Another approach for this problem is to treat the forks as the resources that need to be taken. Instead of adding a contention in a central place, we distribute the contention to the forks. There is no need to make all the philosophers wait when a fork is needed when only one neighbor philosopher is affected.
Here is the implementation:
This is slightly more code, but not complicated at all. Nevertheless, we will explain it.
The first thing to notice is the implementation of the
Fork class. It uses the same active object pattern for keeping the threading implementation hidden from the caller. We could have implemented the whole thing with an atomic, but it wouldn’t be that much fun .
Whenever a fork is in use, we also keep track of what philosopher is using it. If another philosopher requests the fork we deny it, but we accept if the same philosopher requests the fork. This prevents some edge cases as discussed above with the waiter solution.
The protocol now becomes slightly more evolved. Whenever a philosopher wants to eat, we request the corresponding forks. The response from both forks, whether is a success or a failure, would be sent through a task notification to the
onForkStatus function. This will ensure that we have a response from both forks before start eating or thinking. If we have a reject from one fork, we must release the other fork. We do nothing more than just follow the possible scenarios; nothing fancy.
The part that is worth noting is the
serializer_ object attached to the protocol. Since we are getting notifications in terms for tasks from both fork objects, we need to ensure that they do not run in parallel. That’s why we instruct the
Fork objects to use a serializer when sending the notifications back. If we wouldn’t have the serializer, two notifications could be processed in parallel, and we would have a race condition inside the body of
A pattern for notifications
Please look more closely to the way the
ForkLevelPhilosopherProtocol objects know about the status of the two forks. They receive notifications from the two
But we don’t have any explicit abstractions for notifications. That is because we don’t need it. One can take the pair between a
TaskExecutor and a
Task to serve as a notification object. In our example, whenever the
Fork object needs to send a notification to the protocol object, it will enqueue the given task on the appropriate executor. That’s it. Simple as daylight.
One can use a pair between a `TaskExecutor` and a `Task` as a channel of sending notifications.
The astute reader might have noticed that this implementation does not have fairness. Indeed, with the way we have set up our fork synchronization, we don’t have a memory of who requested the forks first. We can have the same case in which Socrates is denied to eat until both Plato and Aristotle finish dining.
But, beware, in this case, adding fairness is not that easy. If we would simply want to keep track of who requested the forks, we would simply reach a live-lock situation. Imagine that each philosopher requests the left fork first, then the right fork. No one will be able to acquire the right fork, as it was already promised to the philosopher on the right. From that point on, it is guaranteed that the forks will not be acquired by any of the philosophers; they would always go back to thinking, wake up to have their requests denied.
On correctness of the current solution
But wait, doesn’t the solution presented here suffer from a similar problem? Let’s imagine the following scenario:
- all philosophers stop thinking at the same time
- they all start by acquiring the left fork; they will all send a notification to the forks on their left to acquire them
- then, they all send a notification to acquire the right forks
- the forks will process the messages in order; all the “take left” requests will be fulfilled before the “take right” ones
- this will essentially deny all the philosophers the possibility of eating
- they all go back to thinking, they all wake up at the same time, and the cycle continues
This is true, but this is mostly a theoretical problem. In practice, because enqueueing and executing tasks have some timing randomness, the possibility of this happening once is extremely small; and it exponentially decreases as the time goes by. It’s enough to have one small randomness to change the order of the tasks to be executed for the whole live-lock chain to be broken.
If we want to fix this problem, we could easily swap the fork requesting for one single philosopher (i.e., the first philosopher requests the right fork first, then the left one). We leave this as an exercise to the reader.
Conclusions and a few other notes
In this blog post, we walked the reader through building several solutions for the dining philosophers problem. The intent was not to build up the best possible solution (fastest, easiest, etc.) but rather to explore the various aspects of working with tasks. We intentionally tried to keep the number of concurrency abstractions to the minimum and guide the reader through the essentials of using tasks.
We’ve shown how to build a simple task system, and how to use it to solve various problems. Along the way, we encountered several patterns that can appear while building concurrent applications (with tasks):
- how one can use lambda expressions to transform regular function calls into task objects
- how one can enqueue tasks by hand to create arbitrarily complex chains or graphs of tasks.
- an active object pattern in which we keep the concurrency concerns of a class isolated from the calling code; this pattern also helps in achieving composability with actors that are doing work in a multi-threaded environment
- a pattern for notifications between various actors using tasks
Hope that after this (relatively longer) post the reader has a better grip on using tasks to build solutions for concurrency problems.
The dining philosophers problem was just a pretext for our journey.
All the code can be found on Github: at https://github.com/lucteo/tasks_concurrency/tree/dining_philosophers
Keep truthing! Until the next