Dining Philosophers in C++11

UPDATE: for an implementation of the Chandy/Misra solution see Dining philosophers in C++11: Chandy-Misra algorithm

The problem of the dining philosophers, first proposed by Edsger Dijkstra and reformulated by Tony Hoare, is a famous problem for concurrent programming that illustrates problems with synchronizing access to data. The description of the problem, taken from Wikipedia, is the following:

Five silent philosophers sit at a round table with bowls of spaghetti. Forks are placed between each pair of adjacent philosophers.

Each philosopher must alternately think and eat. However, a philosopher can only eat spaghetti when they have both left and right forks. Each fork can be held by only one philosopher and so a philosopher can use the fork only if it is not being used by another philosopher. After an individual philosopher finishes eating, they need to put down both forks so that the forks become available to others. A philosopher can take the fork on their right or the one on their left as they become available, but cannot start eating before getting both forks.

Eating is not limited by the remaining amounts of spaghetti or stomach space; an infinite supply and an infinite demand are assumed.

The idea is to find a solution so that none of the philosophers would starve, i.e. never have the chance to acquire the forks necessary for him to eat.

Below I propose a simple implementation to this problem using C++11 language and library features. The following classes are defined:

  • fork represents a fork at the table; the only member of this structure is a std::mutex that will be locked when the philosopher picks up the fork and unlocked when he puts it down.

  • table represents the round table where the philosophers are dining. It has an array of forks, but also an atomic boolean that indicates that the table is ready for the philosophers to start thinking and eating.

  • philosopher represents a philosopher dining at the table. It has a name and a reference to the forks on his left and right.

Most of the implementation of the solution is part of the philosopher class. When an object of this class is instantiated, a thread is started. This thread is joined when the object is destroyed. The thread runs a loop of thinking and eating until the dinner is signaled to end by setting the ready member of the table to false. There are three main methods in the philosopher class:

  • dine() is the thread function; this is implemented as a simple loop of thinking and eating.

  • think() is the method that represents the thinking period. To model this the thread sleeps for a random period of time.

  • eat() is the method that models the eating. The left and right forks are acquired in a deadlock free manner using std::lock. After the forks, i.e. mutexes, are acquired, their ownership is transfered to a std::lock_guard object, so that the mutexes are correctly released when the function returns. Eating is simulated with a sleep.

To see how this works, we create a table object and an array of phylosophers. Upon creating the philosopher objects their own working thread is started, but nothing happens until the table is signaled as being ready. Philosophers then compete for the forks (i.e. mutexes), eat and think until the dinner is signaled as finished by setting the ready flag of the table object back to false.

The whole implementation is show below:

The output for this program (that varies with each execution) has the following form:

Though the problem is usually described in terms of five philosophers, any number of philoposhers can be present at the table (of course, at least two are necessary for the problem to make sense). Adding more philosophers does not require any changes in the implementation.

, , , , , , Hits for this post: 1914 .
Trackback

7 comments untill now

  1. Gravatar

    Closely related article which uses dining philosophers to explore the implementation of std::lock: http://howardhinnant.github.io/dining_philosophers.html

  2. Gravatar

    Minor nitpick: string_view was introduced in C++17

  3. Gravatar

    This problem is a classical demonstration of circular dependency and deadlock — your code does nothing to prevent that.
    Just remove the time delays, let it run longer and observe the program to lock up and the philosophers starve to death.
    There is also a busy loop in dining start up which should be solved with condition variables instead, which became an important part of C++ in 2011.
    The design is nice, but the implementation naive and incorrect, useful perhaps just to expose the potential problems.

    Also, last time I checked thread_local did not work with MSVC++.

  4. Gravatar

    Yes, you are correct, this implementation does not prevent starting. Therefore, I have written a new post, where I provide an implementation of the Chandy/Misra solution.

    http://mariusbancila.ro/blog/2017/01/20/dining-philosophers-in-c11-chandy-misra-algorithm/

    On the other hand, thread_local does work in Visual Studio 2015. I was actually using Visual Studio 2017, even though I did not mention it; that’s why I could use string_view. So in the new implementation, I dropped that to be C++11 compliant.

  5. Gravatar

    I’ve just gone over this code and tested it. I can find no deadlock. Starvation will be a function of the quality of implementation of std::lock. A well implemented std::lock will minimize starvation.

    I took out the print statements, thinking and waiting under eat, and installed a counter to see how many times each philosopher got to eat. Ran it for a minute and printed out the number of times each philosopher got to eat. No philosopher was starved. Each accessed with +/- 10% of the average. Testing was done with clang/libc++ on macOS. ymmv.

  6. Gravatar

    Is the call to the philosopher.dine() missing? I see main() calls dine() but how is the philosopher.dine() method called?

    Not sure if I am missing something.

  7. Gravatar

    You are missing something: the philosopher class has a thread, and the thread function is philosopher::dine. The thread object is instantiated in the constructor’s initialization list: lifethread(&philosopher::dine, this).

Add your comment now