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.
    struct fork
    {
       std::mutex mutex;
    };
  • 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.
    struct table
    {
       std::atomic<bool>                    ready{ false };
       std::array<fork, no_of_philosophers> forks;
    };
    
  • philosopher represents a philosopher dining at the table. It has a name and a reference to the forks on his left and right.
    struct philosopher
    {
    private:
       std::string const name;
       table const &     dinnertable;
       fork&             left_fork;
       fork&             right_fork;
       std::thread       lifethread;
       std::mt19937      rng{ std::random_device{}() };
    };

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.
       void dine()
       {
          while (!dinnertable.ready);
    
          do
          {
             think();
             eat();
          } while (dinnertable.ready);
       }
  • think() is the method that represents the thinking period. To model this the thread sleeps for a random period of time.
       void think()
       {
          static thread_local std::uniform_int_distribution<> wait(1, 6);
          std::this_thread::sleep_for(std::chrono::milliseconds(wait(rng) * 150));
    
          print(" is thinking ");
       }
  • 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.
       void eat()
       {
          std::lock(left_fork.mutex, right_fork.mutex);
    
          std::lock_guard<std::mutex> left_lock(left_fork.mutex,   std::adopt_lock);
          std::lock_guard<std::mutex> right_lock(right_fork.mutex, std::adopt_lock);
    
          print(" started eating.");
    
          static thread_local std::uniform_int_distribution<> dist(1, 6);
          std::this_thread::sleep_for(std::chrono::milliseconds(dist(rng) * 50));
    
          print(" finished eating.");
       }

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:

#include <array>
#include <mutex>
#include <thread>
#include <atomic>
#include <chrono>
#include <iostream>
#include <string>
#include <random>
#include <iomanip>
#include <string_view>

std::mutex g_lockprint;
constexpr  int no_of_philosophers = 5;

struct fork
{
   std::mutex mutex;
};

struct table
{
   std::atomic<bool>                    ready{ false };
   std::array<fork, no_of_philosophers> forks;
};

struct philosopher
{
private:
   std::string const name;
   table const &     dinnertable;
   fork&             left_fork;
   fork&             right_fork;
   std::thread       lifethread;
   std::mt19937      rng{ std::random_device{}() };
public:
   philosopher(std::string_view n, table const & t, fork & l, fork & r) :
      name(n), dinnertable(t), left_fork(l), right_fork(r), lifethread(&philosopher::dine, this)
   {
   }

   ~philosopher()
   {
      lifethread.join();
   }

   void dine()
   {
      while (!dinnertable.ready);

      do
      {
         think();
         eat();
      } while (dinnertable.ready);
   }

   void print(std::string_view text)
   {
      std::lock_guard<std::mutex> cout_lock(g_lockprint);
      std::cout
         << std::left << std::setw(10) << std::setfill(' ')
         << name << text << std::endl;
   }

   void eat()
   {
      std::lock(left_fork.mutex, right_fork.mutex);

      std::lock_guard<std::mutex> left_lock(left_fork.mutex,   std::adopt_lock);
      std::lock_guard<std::mutex> right_lock(right_fork.mutex, std::adopt_lock);

      print(" started eating.");

      static thread_local std::uniform_int_distribution<> dist(1, 6);
      std::this_thread::sleep_for(std::chrono::milliseconds(dist(rng) * 50));

      print(" finished eating.");
   }

   void think()
   {
      static thread_local std::uniform_int_distribution<> wait(1, 6);
      std::this_thread::sleep_for(std::chrono::milliseconds(wait(rng) * 150));

      print(" is thinking ");
   }
};

void dine()
{
   std::this_thread::sleep_for(std::chrono::seconds(1));
   std::cout << "Dinner started!" << std::endl;

   {
      table table;
      std::array<philosopher, no_of_philosophers> philosophers
      {
         {
            { "Aristotle", table, table.forks[0], table.forks[1] },
            { "Platon",    table, table.forks[1], table.forks[2] },
            { "Descartes", table, table.forks[2], table.forks[3] },
            { "Kant",      table, table.forks[3], table.forks[4] },
            { "Nietzsche", table, table.forks[4], table.forks[0] },
         }
      };

      table.ready = true;
      std::this_thread::sleep_for(std::chrono::seconds(5));
      table.ready = false;
   }

   std::cout << "Dinner done!" << std::endl;
}

int main()
{   
   dine();

   return 0;
}

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

Dinner started!
Descartes  is thinking
Descartes  started eating.
Descartes  finished eating.
Platon     is thinking
Platon     started eating.
Aristotle  is thinking
Platon     finished eating.
Aristotle  started eating.
Descartes  is thinking
Descartes  started eating.
Aristotle  finished eating.
Descartes  finished eating.
Nietzsche  is thinking
Nietzsche  started eating.
Kant       is thinking
Nietzsche  finished eating.
Kant       started eating.
Aristotle  is thinking
Aristotle  started eating.
Aristotle  finished eating.
Platon     is thinking
Platon     started eating.
...
Kant       is thinking
Kant       started eating.
Kant       finished eating.
Dinner done!

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.

9 Replies to “Dining Philosophers in C++11”

  1. 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++.

  2. 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.

    https://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.

  3. 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.

  4. 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).

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.