In my previous post, Dining Philosophers in C++11, I have provided an implementation for the dining philosophers problem using modern C++ features, such as threads and mutexes. However, it was noted in the comments that the implementation did not prevent the philosophers starving to death when you remove the waiting times.
An algorithm that prevents the philosophers from starving was proposed by Mani Chandy and J. Misra and is known as the Chandy/Misra solution. This is a bit different than the original problem because it requires the philosophers to communicate with each other. The algorithm, as described on Wikipedia, is the following:
- For every pair of philosophers contending for a resource, create a fork and give it to the philosopher with the lower ID (n for agent Pn). Each fork can either be dirty or clean. Initially, all forks are dirty.
- When a philosopher wants to use a set of resources (i.e. eat), said philosopher must obtain the forks from their contending neighbors. For all such forks the philosopher does not have, they send a request message.
- When a philosopher with a fork receives a request message, they keep the fork if it is clean, but give it up when it is dirty. If the philosopher sends the fork over, they clean the fork before doing so.
- After a philosopher is done eating, all their forks become dirty. If another philosopher had previously requested one of the forks, the philosopher that has just finished eating cleans the fork and sends it.
In order to implement this, we must make several changes to the solution proposed in the previous post:
- forks and philosophers must have identifiers
- there is an initial setup of both forks and philosophers
- use std::condition_variable to communicate between threads
- increase the number of philosophers
Because it has been also argued that string_view is only available in C++17 and this implementation is supposed to work in C++11, I have replaced that with std::string const&.
In this implementation, philosophers, i.e. threads, need to communicate with each other to request the forks, i.e. resources. For this, we will use a std::condition_variable, which is a synchronization primitive that enables the blocking of one or more threads until another thread notifies it. A std::condition_variable requires a std::mutex to protect access to a shared variable. The following class, sync_channel, contains both a condition variable and a mutex and provides two methods: one that waits on the condition variable, blocking the calling thread(s), and one that notifies the condition variable, unblocking all the threads that are waiting for a signal.
class sync_channel
{
std::mutex mutex;
std::condition_variable cv;
public:
void wait()
{
std::unique_lock<std::mutex> lock(mutex);
cv.wait(lock);
}
void notifyall()
{
std::unique_lock<std::mutex> lock(mutex);
cv.notify_all();
}
};
The table class from the previous implementation is modified: the forks are no longer defined here, but a sync_channel is used to prevent philosophers start dining until the table setup is completed. Its name has been changed to table_setup.
struct table_setup
{
std::atomic<bool> done{ false };
sync_channel channel;
};
The fork class is no longer a wrapper for a mutex. It has an identifier, an owner, a flag to indicate whether it is dirty or clean, a mutex, and a sync_channel that enables owners to request used forks. It has two methods:
- request() that enables a philosopher to request the fork. If the fork is dirty, it is set to clean, and the ownership is given to the philosopher that asked for it. If the fork is clean (i.e. the current owner is eating), than the philosopher that asked for it will block, waiting for it to become dirty (i.e. the current owner has finished eating).
void request(int const ownerId) { while (owner != ownerId) { if (dirty) { std::lock_guard<std::mutex> lock(mutex); dirty = false; owner = ownerId; } else { channel.wait(); } } } - done_using() a philosopher indicates that has finished eating and notifies other philosopher that is waiting for the fork that it can have it.
void done_using() { dirty = true; channel.notifyall(); }
There are less changes to the philosopher class: it has an identifier, and there are no more waiting times to simulate eating and thinking. There are some small changes to the following methods:
- dine(): each philosopher only starts eating after the entire table has been setup. A condition variable, from the table_setup object is used for this.
void dine() { setup.channel.wait(); do { think(); eat(); } while (!setup.done); } - eat(): each philosopher first requests the left and right fork. When they are available, they are locked using std::lock() to avoid possible deadlocks, and then their ownership is transfered to a std::lock_guard object, so they are properly released when done. After eating, the fork is set as dirty and other philosophers waiting for it are notified of this.
void eat() { left_fork.request(id); right_fork.request(id); std::lock(left_fork.getmutex(), right_fork.getmutex()); std::lock_guard<std::mutex> left_lock(left_fork.getmutex(), std::adopt_lock); std::lock_guard<std::mutex> right_lock(right_fork.getmutex(), std::adopt_lock); print(" started eating."); print(" finished eating."); left_fork.done_using(); right_fork.done_using(); }
According to the initial setup, each fork is given to the philosopher with the lower ID. That means fokm 1, placed between philosopher 1 and N, goes to philosopher 1. Fork 2, placed between philosophers 2 and 3 is given to philosopher 2. Eventually, fork N, placed between philosophers N and 1, is given to philosopher 1. Overall, this means all philosophers have initially 1 fork, except for the first one that has two, and the last philosopher, that has none.
Put all together, the code looks like this:
#include <array>
#include <mutex>
#include <thread>
#include <atomic>
#include <chrono>
#include <iostream>
#include <string>
#include <iomanip>
#include <condition_variable>
std::mutex g_lockprint;
constexpr int no_of_philosophers = 7;
class sync_channel
{
std::mutex mutex;
std::condition_variable cv;
public:
void wait()
{
std::unique_lock<std::mutex> lock(mutex);
cv.wait(lock);
}
void notifyall()
{
std::unique_lock<std::mutex> lock(mutex);
cv.notify_all();
}
};
struct table_setup
{
std::atomic<bool> done{ false };
sync_channel channel;
};
class fork
{
int id;
int owner;
bool dirty;
std::mutex mutex;
sync_channel channel;
public:
fork(int const forkId, int const ownerId):
id(forkId), owner(ownerId), dirty(true)
{}
void request(int const ownerId)
{
while (owner != ownerId)
{
if (dirty)
{
std::lock_guard<std::mutex> lock(mutex);
dirty = false;
owner = ownerId;
}
else
{
channel.wait();
}
}
}
void done_using()
{
dirty = true;
channel.notifyall();
}
std::mutex& getmutex() { return mutex; }
};
struct philosopher
{
private:
int id;
std::string const name;
table_setup& setup;
fork& left_fork;
fork& right_fork;
std::thread lifethread;
public:
philosopher(int const id, std::string const & n, table_setup & s, fork & l, fork & r) :
id(id), name(n), setup(s), left_fork(l), right_fork(r), lifethread(&philosopher::dine, this)
{
}
~philosopher()
{
lifethread.join();
}
void dine()
{
setup.channel.wait();
do
{
think();
eat();
} while (!setup.done);
}
void print(std::string const & 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()
{
left_fork.request(id);
right_fork.request(id);
std::lock(left_fork.getmutex(), right_fork.getmutex());
std::lock_guard<std::mutex> left_lock(left_fork.getmutex(), std::adopt_lock);
std::lock_guard<std::mutex> right_lock(right_fork.getmutex(), std::adopt_lock);
print(" started eating.");
print(" finished eating.");
left_fork.done_using();
right_fork.done_using();
}
void think()
{
print(" is thinking ");
}
};
class table
{
table_setup setup;
std::array<fork, no_of_philosophers> forks
{
{
{ 1, 1 },
{ 2, 2 },
{ 3, 3 },
{ 4, 4 },
{ 5, 5 },
{ 6, 6 },
{ 7, 1 },
}
};
std::array<philosopher, no_of_philosophers> philosophers
{
{
{ 1, "Aristotle", setup, forks[0], forks[1] },
{ 2, "Platon", setup, forks[1], forks[2] },
{ 3, "Descartes", setup, forks[2], forks[3] },
{ 4, "Kant", setup, forks[3], forks[4] },
{ 5, "Nietzsche", setup, forks[4], forks[5] },
{ 6, "Hume", setup, forks[5], forks[6] },
{ 7, "Russell", setup, forks[6], forks[0] },
}
};
public:
void start()
{
setup.channel.notifyall();
}
void stop()
{
setup.done = true;
}
};
void dine()
{
std::cout << "Dinner started!" << std::endl;
{
table table;
table.start();
std::this_thread::sleep_for(std::chrono::seconds(60));
table.stop();
}
std::cout << "Dinner done!" << std::endl;
}
int main()
{
dine();
return 0;
}
The output of the program looks like this:
Dinner started! Russell is thinking Hume is thinking Nietzsche is thinking Kant is thinking Platon is thinking Descartes is thinking Aristotle is thinking Russell started eating. Nietzsche started eating. Nietzsche finished eating. Russell finished eating. Platon started eating. Nietzsche is thinking Kant started eating. Hume started eating. Russell is thinking Platon finished eating. Kant finished eating. Hume finished eating. Platon is thinking ... Nietzsche started eating. Descartes finished eating. Russell started eating. Nietzsche finished eating. Platon started eating. Russell finished eating. Kant started eating. Platon finished eating. Hume started eating. Kant finished eating. Aristotle started eating. Hume finished eating. Aristotle finished eating. Dinner done!
The class sync_channel seems weird: what is the mutex protecting? For set up table you need a table.has_set_up variable to make sure spuriously waked philosopher don’t start eating. For fork ownership you need to protect fork.owner and fork.dirty or two philosophers can pass line 54-56 at the same time and both go through 57-62 (one after another) and return while the fork only belongs to one of them.
In any case, a cv mutex not protecting cv’s condition seems “spurious”.
When I tried to run this program its just stuck. Only the dinner started line is printed, then its not printing anything. Is there something I need to enter in command line interface?