Dining philosophers problem in C++11

Question

Is this implementation correct? Do you find any threading problem? Also, what parts of the code can be changed to be more C++11-ish?

#include <iostream>
#include <vector>
#include <thread>
#include <random>
#include <condition_variable>


namespace {
    int sleep_for_random_time() {
        std::random_device rd;
        std::mt19937 mt(rd());
        std::uniform_real_distribution<double> dist(1000, 4000);

        return dist(mt);
    }
}

class DiningPhilosopher {
public:
    DiningPhilosopher(int numOfPhilosophers_ = 5, int numOfForks_ = 5, int numOfEating_ = 3) : numOfPhilosophers(numOfPhilosophers_), numOfForks(numOfForks_), numOfEating(numOfEating_) {
        forks.push_back(new Fork);
        forks.push_back(new Fork);
        forks.push_back(new Fork);
        forks.push_back(new Fork);
        forks.push_back(new Fork);

        numAllowed = numOfForks - 1;
    }

    ~DiningPhilosopher() {
        for(const auto& fork : forks) {
            delete fork;
        }
    }

    DiningPhilosopher(const DiningPhilosopher&) = delete;
    DiningPhilosopher& operator = (const DiningPhilosopher&) = delete;

    void StartDining() {
        for(int i = 0; i < numOfPhilosophers; ++i) {
            threads.push_back(std::thread(&DiningPhilosopher::Philosopher, this, i));
        }

        std::for_each(threads.begin(),threads.end(), std::mem_fn(&std::thread::join));
    }
private:
    void WaitForPermission() {
        std::lock_guard<std::mutex> lock(permission);
        cv.wait(permission, [this] { return numAllowed > 0; });
        --numAllowed;
    }

    void GrantPermission() {
        std::lock_guard<std::mutex> lock(permission);
        ++numAllowed;

        if(numAllowed == 1) {
            cv.notify_all();
        }
    }

    void Think(int id) {
        std::chrono::milliseconds duration(sleep_for_random_time());
        std::this_thread::sleep_for(duration);
    }

    void Eat(int id) {
        this->WaitForPermission();
        forks[id]->mux.lock();
        forks[(id + 1) % numOfForks]->mux.lock();

        std::cout << "Philosopher "<< id << " is eating" << std::endl;
        this->Think(id);
        std::cout << "Philosopher "<< id << " has finished eating" << std::endl;

        forks[id]->mux.unlock();
        forks[(id + 1) % numOfForks]->mux.unlock();

        this->GrantPermission();
    }

    void Philosopher(int id) {
        for(int i = 0; i < numOfEating; ++i) {
            this->Think(id);
            this->Eat(id);
        }

        std::cout << "Philosopher " << id << " DONE" << std::endl;
    }

    struct Fork {
        std::mutex mux;
    };

    int numOfEating;
    int numOfPhilosophers;
    int numAllowed;
    int numOfForks;
    std::vector<std::thread> threads;
    std::vector<Fork*> forks;
    std::mutex permission;
    std::condition_variable_any cv;
};


int main()
{
    DiningPhilosopher dp;
    dp.StartDining();

    return 0;
}

Answer 1

struct Fork {
    std::mutex mux;
};
std::vector<Fork*> forks;

I think the problem you want to solve by using pointers here is that a std::mutex is not copyable nor movable. By using raw owning pointers, you'll get a bunch of unpleasant properties. For example, you have to implement a destructor, and might have to worry about exception safety.

Typically, using smart pointers instead of raw owning pointers is a better idea, since it avoids many of those unpleasant side-effects. But the original problem can be solved differently:

std::vector<std::mutex> forks; // data member
DiningPhilosopher(..) // constructor
  : // ...
  , forks(5)
{}

This uses a vector constructor that constructs 5 std::mutex in-place. It therefore does not require that the value type is movable. You cannot resize such a vector, though, nor can you add new entries via push_back etc, even if there's space left (capacity > size). If you have a fixed number of forks, you could use a std::array as well.

If you need to add more forks later, or need to resize:

std::vector<std::unique_ptr<std::mutex>> forks;
DiningPhilosopher(..) // constructor
  : // ...
  , forks(5)
{
    for(auto& fork : forks) fork = std::make_unique<std::mutex>();
}

make_unique is C++14, but can be easily implemented in C++11 as well. It is also possible to use std::generate_n:

DiningPhilosopher(..) // constructor
  : // ...
{
    std::generate_n(std::back_inserter(forks), 5
                    []{ return std::make_unique<std::mutex>(); });
}

---

threads.push_back(std::thread(&DiningPhilosopher::Philosopher, this, i));

This can be replaced by the slightly simpler:

threads.emplace_back(&DiningPhilosopher::Philosopher, this, i);

Or even:

threads.push_back([this, i]{ Philosopher(i); });

---

std::for_each(threads.begin(),threads.end(), std::mem_fn(&std::thread::join));

alternative:

for(auto& t : threads) t.join();

One might argue about the use of "raw loops", but you don't need the position of each thread (the iterator) here. Therefore, I'd say that a for-each loop is fine as well; and it's shorter.

---

void Philosopher(int id)

The name of this function surprised me when I encountered &DiningPhilosopher::Philosopher earlier. It almost looked like a data member, since it's not formulated as a verb. From a code organization perspective, I think it should be earlier in the code, before the functions it calls. This allows a top-down reading from the higher to lower level functions.

---

 std::cout << "Philosopher "<< id << " is eating" << std::endl;
 this->Think(id);
 std::cout << "Philosopher "<< id << " has finished eating" << std::endl;

The philosopher thinks while they're eating? Ok, I think it is code reuse, but the name confused me. Why not introduce an intermediary function wait_for_random_time that is used to implement both thinking and (the actual) eating? Similarly, the function Eat doesn't just let a philosopher eat. It does more (waiting to eat etc.)

---

int sleep_for_random_time() {
    std::random_device rd;
    std::mt19937 mt(rd());
    std::uniform_real_distribution<double> dist(1000, 4000);

    return dist(mt);
}

glampert has already criticised the name of this function in his answer, the fact that it repeatedly creates a random_device as well as a mt19937, and the usage of double.

I'd also like to point out that creating both generators seems strange to me: First you get a (potentially pseudo-)random number from one random number generator (the random_device). Then, you use it to seed another random number generator, to create a pseudo-random number. The second step is unnecessary, if you trust the quality of your random_device implementation enough: It either produces true random numbers, or - and that's the Quality Of Implementation aspect - evenly distributed pseudo-random numbers. The following should be sufficient:

int sleep_for_random_time() {
    std::random_device rd;
    std::uniform_int_distribution<int> dist(1000, 4000);
    return dist(rd);
}

The original code followed a common pattern of creating pseudo-random numbers. Typically, one does not use the random device to create all random numbers because it is slow (it might run out of entropy, too, depending on the implementation). You'd therefore use it only once to initialize a single mersenne twister. Successive requests for pseudo-random numbers would use this single mersenne twister to produce pseudo-random numbers. For example:

 int sleep_for_random_time() {
     static std::mt19937 mt{ std::random_device{}() };
     std::uniform_int_distribution<int> dist(1000, 4000);
     return dist(mt);
 }

Arguably, even the distribution should be static, to allow recycling unused bits of the output of the generator. As Deduplicator points out, there could/should be one generator per thread. The above code uses one shared generator, which is not thread-safe, since dist(mt) modifies the state of the (now shared) generator. There are several ways to make this thread-safe, one of them is:

 int sleep_for_random_time() {
     thread_local std::mt19937 mt{ std::random_device{}() };
     std::uniform_int_distribution<int> dist(1000, 4000);
     return dist(mt);
 }

This associates an individual mersenne twister for each thread. Each of them is created once, for the lifetime of the thread.

---

this->Think(id);

Again this line, but this time in isolation. First, why is there a this? It seems to be used whenever you call a member function. Why?

Additionally, the id is currently unnecessary. If it was not, there should be a way IMHO to make sure that each philosopher thinks for themselves. Something like

Think();

should be sufficient; however it requires an object to represent each philosopher. Since you already have a thread object for each philosopher, that seems possible and simple to realize. These objects could also get (read-only!) access to the options such as numOfEating.

Answer 2

I have only a few comments:

• The name you gave to sleep_for_random_time() is ambiguous. Some might interpret that the function sleeps for a random amount of time, while some might interpret that it returns a random value for a call to sleep_for(). The latter is true. Either change the name or change the functionality. Since it is a local function, then perhaps make this function perform the sleep call directly, instead of generating a random number that is used outside only once.

• This is probably not very important in your case, but creating a random_device and an mt19937 for every call of a function can be expensive. Ideally, in a more performance focused scenario, you would create them once and reuse several times.

• What's the point of creating a uniform_real_distribution<double> if the return type of the function coerces the value to int?

• Manually locking/unlocking a mutex is not a good idea. An exception or misplaced return might result in a deadlock. std::lock_guard exists so that you don't have to do that.

• Finally, you are using C++11, so don't handle those Fork pointers manually, use unique_ptr.

Answer 3

Does it work.

Short answer: No
Long answer:

You have avoided deadlock by limiting the number of people allowed to eat. But when the philosophers are not eating they are supposed to be thinking (here they are stuck not thinking a condition variable waiting for a signal).

Also your technique basically causes serial access to the table.

Say you have 4 philosophers. By your rules only three are allowed to eat. So 1/2/3 make it passed the WaitForPermission() stage and grab there left fork. But only 3 can now grab the right fork (the other two are sitting holding forks but not eating and not thinking).

So you have effectively serialized access to a parallel device (thus fail).

Remember the dinning philosopher problem is a metaphor for access to real world devices. If you are not using the device you should be doing real work not wasting the CPU doing nothing (ie you should be thinking).

Code Review

Line way to long:

DiningPhilosopher(int numOfPhilosophers_ = 5, int numOfForks_ = 5, int numOfEating_ = 3) : numOfPhilosophers(numOfPhilosophers_), numOfForks(numOfForks_), numOfEating(numOfEating_) {

Put the initializer list one element per line:

DiningPhilosopher(int numOfPhilosophers_ = 5, int numOfForks_ = 5, int numOfEating_ = 3)
    : numOfPhilosophers(numOfPhilosophers_)
    , numOfForks(numOfForks_)
    , numOfEating(numOfEating_)
{

You may also notice that your compiler generates warnings about that. The variables are initialized in the same order as they are declared see below (not the order in the initializer list).

int numOfEating; *
int numOfPhilosophers; *
int numAllowed;
int numOfForks; *
std::vector<std::thread> threads;
std::vector<Fork*> forks;
std::mutex permission;
std::condition_variable_any cv;

If you follow this rule (and re-order your declarations). Then you can safely move the initalization of numAllowed into the initializer list.