Dining philosophers in C++11: Chandy-Misra algorithm

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:

1. 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.
2. 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.
3. 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.
4. 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());

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 <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;
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()
{
}

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());

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();
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!```

3 Replies to “Dining philosophers in C++11: Chandy-Misra algorithm”

1. Bob says:

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

2. Dola says:

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?

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