Attempt at solution for Dining Philosopher algorithm

Question

I know there are a lot of different solutions to solve the "Dining Philosophers" problem, but I wanted to get some feedback on a solution that I have so far.

My motivation for working on this is to prepare for future job interviews and to get more familiar with threads and C++.

#define P 5
#include <iostream>
#include <mutex>
#include <thread>
#include <Windows.h>
std::thread *threads[P]; //my philosophers
std::mutex mtx[P]; //forks
std::mutex cout;
bool pickUp(int left, int right) {
 if (mtx[left].try_lock()) {
 if (mtx[right].try_lock()) {
 return true;
 }
 else {
 mtx[left].unlock();
 }
 }
 return false;
}
void putDown(int left, int right) {
 mtx[left].unlock();
 mtx[right].unlock();
}
void run(int philID) {
 int leftIndex = philID-1;
 int rightIndex = (philID) % (P-1);
 while (1) {
 if (pickUp(leftIndex, rightIndex)) {
 cout.lock();
 std::cout << "Philosopher " << philID << " eats.\n";
 cout.unlock();
 putDown(leftIndex, rightIndex);
 Sleep(50); //cannot acquire again right away
 }
 else {
 cout.lock();
 std::cout << "Philosopher " << philID << " thinks.\n";
 cout.unlock();
 }
 }
}
int main() {
 for (int i = 1; i <= P; i++) {
 threads[i-1] = new std::thread(run, i);
 }
 for (int i = 1; i <= P; i++) {
 if (threads[i - 1]->joinable())
 threads[i - 1]->join();
 }
 return 0;
}

My pickUp() function takes the indices of the philosophers "fork" in the array of mutexes and tries to get first the left and then the right fork. If it cannot get the right immediately, it simply puts the left fork down and returns false. If this happens then the philosopher "thinks" before trying to pickup his forks again.

If both forks are able to be picked up, then he eats and then puts down both his forks. This alone was enough to avoid deadlock, but there was the problem of starvation for other philosophers. To solve this, I added a Sleep() call of 50 milliseconds so that a philosopher cannot instantly grab his forks again.

Is this enough to be considered an adequate answer to this problem? It works fine, but is there a "better" solution that I am missing?

• Emily L.: Please add a description of the Dining philosophers problem to your question. This will make it more likely that people who are not intimately familiar with the problem will spend the time on your question.

Answer 1

Overall

Wow. Correct implementation.
Your the first person to post what I would call a proper implementation.

Good Job.

Code Review

Prefer NOT to use #define

#define P 5

Nearly every use of #define has a better alternative in C++ (unless you are really abstracting OS specific details).

In this case case you are defining a constant integer. There is an explicit version of that for C++.

constexpr int globalConstantP = 5; // More than 1 letter

While we are on P. A variable of length 1 is not very meaningful. Your code should be self documenting. This really means your variable names should be meaningful.

Avoid Platform specific includes.

#include <Windows.h>

This is the one place where #define comes in useful. Abstracting platfrom specific details. The Windows and Unix versions of sleep are different.

#if defiend(WIN32)
#include <Windows.h>
#define doSleep(X) Sleep(X)
#elif defined(__linux__)
#include <unistd.h>
#define doSleep(X) sleep(X * 1000)
#elif defined (__APPLE__) && defined (__MACH__)
#include <unistd.h>
#define doSleep(X) sleep(X * 1000)
#else
#error "Unsupported Platform"
#endif

Avoid using pointers

std::thread *threads[P];

In modern C++ you should never (or practically never) be calling new and delete. You should use automatic variables for all situations so that you can make sure the constructor/destructor and thus RAII kicks in to do the resource management. When you do need dynamically allocated objects they should be wrapped in smart pointers so that they can not leak.

Here you don't need pointers at all. Just use std::thread.

Avoid global variables

std::thread *threads[P];
std::mutex mtx[P]; //forks

Global mutable state is the bane of many problems in program. But especially testing. It is best to pass objects to functions (by reference) and manipulate them or even better to just manipulate the object by calling the member functions.

I would have created a class called Table that had the array of std::thread and std::mutex objects. Then your functions below become methods than manipulate the object.

cout!!!

std::mutex cout;

That is too easy to be confused with std::cout. Please put it in a namespace and the very least. I would actually create your own stream class (one that can be locked) and pass that as the output object to the constructor of your Table class.

Thinking should sleep

It take times to think.
It should also take time to think.

 if (pickUp(leftIndex, rightIndex)) {
 std::cout << "Philosopher " << philID << " eats.\n";
 doSleep(rand() % 20);
 // Don't put Down the forks until you have had time
 // time to do some eating. Remeber you are simulating work
 // after having obtained the resources. The work should
 // take none zero time.
 putDown(leftIndex, rightIndex);
 else {
 std::cout << "Philosopher " << philID << " thinks.\n";
 // When the philosopher is thinking the time should
 // also be none zero as you are simulating doing work
 // that is not related to the resource.
 doSleep(rand() % 20);
 }

Joinable

 if (threads[i - 1]->joinable())
 threads[i - 1]->join();

No need to test for joinable if you have never called detach on your thread.

Return 0

 return 0;

No need to return 0 at the end of main(). It does that automatically.

Normally you use return 0 to indicate there was a success BUT also to indicate that it could fail and there is another way to exit that could return a non zero value. When I see a return 0 I immediately start looking for alternative returns paths to see under what conditions the application will fail.

So if your application can not fail don't return anything (this is an indication that it can't fail). The compiler will add the return 0 if one was not provided.

• Jerry Coffin: ...but rather than writing your own doSleep, better to just use this_thread::sleep_for(period);
• Loki Astari: Yes don't actually use doSleep().