Dining Philosophers in C++ 11

I have previously shown how to solve the problem using c#. I have to say that C++ 11 is officially awesome! Here’s my offering using that language.

There are numerous solutions to the dining philosophers problem on the internet and I will not be reciting the story. You can find it at one of the following two links:

A few notes. Each philosopher is marked with a circle and can pick a chopstick on the left and on the right before he can eat. So, if philosopher 1 picks chopstick #5, philosopher #5 must wait for philosopher 1 to finish eating before he can pick the chopstick.

Application of this pattern could be transferring of money from one account A to another account B. Similarity would be where you have to acquire locks on A and B before money could exchange hands. That is necessary to ensure that only one transaction could go through both accounts at the same time. Another example could be swapping of two objects in multithreaded environment where you have to use both instances of the objects to acquire locks.

In this project I am introducing quite a few concepts, so let us discuss them.

In this example we have each thread to lock a pair of mutexes to perform some operation. If thread 1 locked on mutex 1 and is waiting for mutex 2, while at the same time thread 2 locked on mutex 2 and is waiting on mutex 1, the result will be a deadlock and the program will hang.

The common advice for avoiding deadlock is to acquire two mutexes in the same order, and that is what I recommended in my C# example. Sometimes it is easy to enforce in code, but in the example of transferring funds between accounts A and B, if you do two transfers at the same time from A to B, and B to A, you may not be able to achieve the order. Besides, someone maintaining code could not realize that the call requires to pass mutexes in a certain order and make a mistake. Another example where order may be difficult to enforce is in swapping of two objects. If two threads try to exchange data between the same two instances with the parameters swapped, the program may deadlock.

C++ 11 has a solution to the deadlocks in the std::lock function which can lock two or more mutexes to aleviate risk of deadlocks.

First we must ensure that we are not locking twice on the same mutex, illegal operation which results in undefined behavior. std::recursive_lock allows multiple locking by the same thread.

Next call to std::lock locks two mutexes, and two std::lock_guard instances are constructed, one for each mutex. std::adopt_lock parameter indicates that the mutexes are already locked and they should adopt the ownership of the existing lock.

auto eat = [](Chopstick* leftChopstick, Chopstick* rightChopstick, int philosopherNumber) 
{ 
    if (leftChopstick == rightChopstick) 
        throw exception("Left and right chopsticks should not be the same!"); 

    lock(leftChopstick->m, rightChopstick->m);    // ensures there are no deadlocks 
    lock_guard<mutex> a(leftChopstick->m, adopt_lock); 
    lock_guard<mutex> b(rightChopstick->m, adopt_lock);                     

    string pe = "Philosopher " + to_string(philosopherNumber) + " eats.\n"; 
    cout << pe; 

    //std::chrono::milliseconds timeout(500); 
    //std::this_thread::sleep_for(timeout); 
};

here Chopstick is defined as following:

class Chopstick 
{ 
public: 
    Chopstick(){}; 
    mutex m; 
};

You will notice that auto eat is a name for an anonymous lambda which can be used multiple times in our code just like an ordinary function call. The actual type for eat is some implementation-dependent type selected by compiler to keep track of lambdas.

What’s left is to create objects that we will use for synchronization, these are the chopsticks:

static const int numPhilosophers = 5; 

// 5 utencils on the left and right of each philosopher. Use them to acquire locks. 
vector< unique_ptr<Chopstick> > chopsticks(numPhilosophers); 

for (int i = 0; i < numPhilosophers; ++i) 
{ 
    auto c1 = unique_ptr<Chopstick>(new Chopstick()); 
    chopsticks[i] = move(c1); 
}

Note the use of std::unique_ptr which will ensure that objects will be destroyed automatically as soon as they leave the scope and std::move function which will copy the pointer to c1 into the chopsticks vector and null c1 so that it could not be used later.

Next we are going to allocate threads, one for each philosopher:

// This is where we create philosophers, each of 5 tasks represents one philosopher. 
vector<thread> tasks(numPhilosophers); 

tasks[0] = thread(eat,  
        chopsticks[0].get(),                        // left chopstick:  #1 
        chopsticks[numPhilosophers - 1].get(),        // right chopstick: #5 
        0 + 1,                                        // philosopher number 
        1, 
        numPhilosophers 
    ); 

for (int i = 1; i < numPhilosophers; ++i) 
{ 
    tasks[i] = (thread(eat,  
            chopsticks[i - 1].get(),                // left chopstick 
            chopsticks[i].get(),                    // right chopstick 
            i + 1,                                    // philosopher number 
            i, 
            i + 1 
            ) 
        ); 
}

Finally we can execute all threads in a loop and wait for all of them to complete:

// May eat! 
for_each(tasks.begin(), tasks.end(), mem_fn(&thread::join));

std::mem_fn is a call wrapper.

And here is a possible output:

/* 
   Philosopher 1 picked 1 chopstick. 
   Philosopher 3 picked 2 chopstick. 
   Philosopher 1 picked 5 chopstick. 
   Philosopher 3 picked 3 chopstick. 
Philosopher 1 eats. 
Philosopher 3 eats. 
   Philosopher 5 picked 4 chopstick. 
   Philosopher 2 picked 1 chopstick. 
   Philosopher 2 picked 2 chopstick. 
   Philosopher 5 picked 5 chopstick. 
Philosopher 2 eats. 
Philosopher 5 eats. 
   Philosopher 4 picked 3 chopstick. 
   Philosopher 4 picked 4 chopstick. 
Philosopher 4 eats. 
*/

Summary

I hope the code will help some of you to learn concepts of thread synchronization and parallel programming using C++ 11.

Source Code Files

program.cpp – the only file in the project  
Code can be downloaded here.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: