Walkthrough: Using join to Prevent Deadlock
This topic uses the dining philosophers problem to illustrate how to use the concurrency::join class to prevent deadlock in your application. In a software application, deadlock occurs when two or more processes each hold a resource and mutually wait for another process to release some other resource.
The dining philosophers problem is a specific example of the general set of problems that may occur when a set of resources is shared among multiple concurrent processes.
Prerequisites
Read the following topics before you start this walkthrough:
Sections
This walkthrough contains the following sections:
The Dining Philosophers Problem
A Naïve Implementation
Using join to Prevent Deadlock
The Dining Philosophers Problem
The dining philosophers problem illustrates how deadlock occurs in an application. In this problem, five philosophers sit at a round table. Every philosopher alternates between thinking and eating. Every philosopher must share a chopstick with the neighbor to the left and another chopstick with the neighbor to the right. The following illustration shows this layout.
.png "The Dining Philosophers Problem")
To eat, a philosopher must hold two chopsticks. If every philosopher holds just one chopstick and is waiting for another one, then no philosopher can eat and all starve.
[Top]
A Naïve Implementation
The following example shows a naïve implementation of the dining philosophers problem. The philosopher class, which derives from concurrency::agent, enables each philosopher to act independently. The example uses a shared array of concurrency::critical_section objects to give each philosopher object exclusive access to a pair of chopsticks.
To relate the implementation to the illustration, the philosopher class represents one philosopher. An int variable represents each chopstick. The critical_section objects serve as holders on which the chopsticks rest. The run method simulates the life of the philosopher. The think method simulates the act of thinking and the eat method simulates the act of eating.
A philosopher object locks both critical_section objects to simulate the removal of the chopsticks from the holders before it calls the eat method. After the call to eat, the philosopher object returns the chopsticks to the holders by setting the critical_section objects back to the unlocked state.
The pickup_chopsticks method illustrates where deadlock can occur. If every philosopher object gains access to one of the locks, then no philosopher object can continue because the other lock is controlled by another philosopher object.
Example
Code
// philosophers-deadlock.cpp
// compile with: /EHsc
#include <agents.h>
#include <string>
#include <array>
#include <iostream>
#include <algorithm>
#include <random>
using namespace concurrency;
using namespace std;
// Defines a single chopstick.
typedef int chopstick;
// The total number of philosophers.
const int philosopher_count = 5;
// The number of times each philosopher should eat.
const int eat_count = 50;
// A shared array of critical sections. Each critical section
// guards access to a single chopstick.
critical_section locks[philosopher_count];
// Implements the logic for a single dining philosopher.
class philosopher : public agent
{
public:
explicit philosopher(chopstick& left, chopstick& right, const wstring& name)
: _left(left)
, _right(right)
, _name(name)
, _random_generator(42)
{
send(_times_eaten, 0);
}
// Retrieves the number of times the philosopher has eaten.
int times_eaten()
{
return receive(_times_eaten);
}
// Retrieves the name of the philosopher.
wstring name() const
{
return _name;
}
protected:
// Performs the main logic of the dining philosopher algorithm.
void run()
{
// Repeat the thinks/eat cycle a set number of times.
for (int n = 0; n < eat_count; ++n)
{
think();
pickup_chopsticks();
eat();
send(_times_eaten, n+1);
putdown_chopsticks();
}
done();
}
// Gains access to the chopsticks.
void pickup_chopsticks()
{
// Deadlock occurs here if each philosopher gains access to one
// of the chopsticks and mutually waits for another to release
// the other chopstick.
locks[_left].lock();
locks[_right].lock();
}
// Releases the chopsticks for others.
void putdown_chopsticks()
{
locks[_right].unlock();
locks[_left].unlock();
}
// Simulates thinking for a brief period of time.
void think()
{
random_wait(100);
}
// Simulates eating for a brief period of time.
void eat()
{
random_wait(100);
}
private:
// Yields the current context for a random period of time.
void random_wait(unsigned int max)
{
concurrency::wait(_random_generator()%max);
}
private:
// Index of the left chopstick in the chopstick array.
chopstick& _left;
// Index of the right chopstick in the chopstick array.
chopstick& _right;
// The name of the philosopher.
wstring _name;
// Stores the number of times the philosopher has eaten.
overwrite_buffer<int> _times_eaten;
// A random number generator.
mt19937 _random_generator;
};
int wmain()
{
// Create an array of index values for the chopsticks.
array<chopstick, philosopher_count> chopsticks = {0, 1, 2, 3, 4};
// Create an array of philosophers. Each pair of neighboring
// philosophers shares one of the chopsticks.
array<philosopher, philosopher_count> philosophers = {
philosopher(chopsticks[0], chopsticks[1], L"aristotle"),
philosopher(chopsticks[1], chopsticks[2], L"descartes"),
philosopher(chopsticks[2], chopsticks[3], L"hobbes"),
philosopher(chopsticks[3], chopsticks[4], L"socrates"),
philosopher(chopsticks[4], chopsticks[0], L"plato"),
};
// Begin the simulation.
for_each (begin(philosophers), end(philosophers), [](philosopher& p) {
p.start();
});
// Wait for each philosopher to finish and print his name and the number
// of times he has eaten.
for_each (begin(philosophers), end(philosophers), [](philosopher& p) {
agent::wait(&p);
wcout << p.name() << L" ate " << p.times_eaten() << L" times." << endl;
});
}
Compiling the Code
Copy the example code and paste it in a Visual Studio project, or paste it in a file that is named philosophers-deadlock.cpp and then run the following command in a Visual Studio Command Prompt window.
cl.exe /EHsc philosophers-deadlock.cpp
[Top]
Using join to Prevent Deadlock
This section shows how to use message buffers and message-passing functions to eliminate the chance of deadlock.
To relate this example to the earlier one, the philosopher class replaces each critical_section object by using a concurrency::unbounded_buffer object and a join object. The join object serves as an arbiter that provides the chopsticks to the philosopher.
This example uses the unbounded_buffer class because when a target receives a message from an unbounded_buffer object, the message is removed from the message queue. This enables an unbounded_buffer object that holds a message to indicate that the chopstick is available. An unbounded_buffer object that holds no message indicates that the chopstick is being used.
This example uses a non-greedy join object because a non-greedy join gives each philosopher object access to both chopsticks only when both unbounded_buffer objects contain a message. A greedy join would not prevent deadlock because a greedy join accepts messages as soon as they become available. Deadlock can occur if all greedy join objects receive one of the messages but wait forever for the other to become available.
For more information about greedy and non-greedy joins, and the differences between the various message buffer types, see Asynchronous Message Blocks.
To prevent deadlock in this example
Remove the following code from the example.
// A shared array of critical sections. Each critical section // guards access to a single chopstick. critical_section locks[philosopher_count];Change the type of the _left and _right data members of the philosopher class to unbounded_buffer.
// Message buffer for the left chopstick. unbounded_buffer<chopstick>& _left; // Message buffer for the right chopstick. unbounded_buffer<chopstick>& _right;Modify the philosopher constructor to take unbounded_buffer objects as its parameters.
explicit philosopher(unbounded_buffer<chopstick>& left, unbounded_buffer<chopstick>& right, const wstring& name) : _left(left) , _right(right) , _name(name) , _random_generator(42) { send(_times_eaten, 0); }Modify the pickup_chopsticks method to use a non-greedy join object to receive messages from the message buffers for both chopsticks.
// Gains access to the chopsticks. vector<int> pickup_chopsticks() { // Create a non-greedy join object and link it to the left and right // chopstick. join<chopstick, non_greedy> j(2); _left.link_target(&j); _right.link_target(&j); // Receive from the join object. This resolves the deadlock situation // because a non-greedy join removes the messages only when a message // is available from each of its sources. return receive(&j); }Modify the putdown_chopsticks method to release access to the chopsticks by sending a message to the message buffers for both chopsticks.
// Releases the chopsticks for others. void putdown_chopsticks(int left, int right) { // Add the values of the messages back to the message queue. asend(&_left, left); asend(&_right, right); }Modify the run method to hold the results of the pickup_chopsticks method and to pass those results to the putdown_chopsticks method.
// Performs the main logic of the dining philosopher algorithm. void run() { // Repeat the thinks/eat cycle a set number of times. for (int n = 0; n < eat_count; ++n) { think(); vector<int> v = pickup_chopsticks(); eat(); send(_times_eaten, n+1); putdown_chopsticks(v[0], v[1]); } done(); }Modify the declaration of the chopsticks variable in the wmain function to be an array of unbounded_buffer objects that each hold one message.
// Create an array of message buffers to hold the chopsticks. array<unbounded_buffer<chopstick>, philosopher_count> chopsticks; // Send a value to each message buffer in the array. // The value of the message is not important. A buffer that contains // any message indicates that the chopstick is available. for_each (begin(chopsticks), end(chopsticks), [](unbounded_buffer<chopstick>& c) { send(c, 1); });
Example
Description
The following shows the completed example that uses non-greedy join objects to eliminate the risk of deadlock.
Code
// philosophers-join.cpp
// compile with: /EHsc
#include <agents.h>
#include <string>
#include <array>
#include <iostream>
#include <algorithm>
#include <random>
using namespace concurrency;
using namespace std;
// Defines a single chopstick.
typedef int chopstick;
// The total number of philosophers.
const int philosopher_count = 5;
// The number of times each philosopher should eat.
const int eat_count = 50;
// Implements the logic for a single dining philosopher.
class philosopher : public agent
{
public:
explicit philosopher(unbounded_buffer<chopstick>& left,
unbounded_buffer<chopstick>& right, const wstring& name)
: _left(left)
, _right(right)
, _name(name)
, _random_generator(42)
{
send(_times_eaten, 0);
}
// Retrieves the number of times the philosopher has eaten.
int times_eaten()
{
return receive(_times_eaten);
}
// Retrieves the name of the philosopher.
wstring name() const
{
return _name;
}
protected:
// Performs the main logic of the dining philosopher algorithm.
void run()
{
// Repeat the thinks/eat cycle a set number of times.
for (int n = 0; n < eat_count; ++n)
{
think();
vector<int> v = pickup_chopsticks();
eat();
send(_times_eaten, n+1);
putdown_chopsticks(v[0], v[1]);
}
done();
}
// Gains access to the chopsticks.
vector<int> pickup_chopsticks()
{
// Create a non-greedy join object and link it to the left and right
// chopstick.
join<chopstick, non_greedy> j(2);
_left.link_target(&j);
_right.link_target(&j);
// Receive from the join object. This resolves the deadlock situation
// because a non-greedy join removes the messages only when a message
// is available from each of its sources.
return receive(&j);
}
// Releases the chopsticks for others.
void putdown_chopsticks(int left, int right)
{
// Add the values of the messages back to the message queue.
asend(&_left, left);
asend(&_right, right);
}
// Simulates thinking for a brief period of time.
void think()
{
random_wait(100);
}
// Simulates eating for a brief period of time.
void eat()
{
random_wait(100);
}
private:
// Yields the current context for a random period of time.
void random_wait(unsigned int max)
{
concurrency::wait(_random_generator()%max);
}
private:
// Message buffer for the left chopstick.
unbounded_buffer<chopstick>& _left;
// Message buffer for the right chopstick.
unbounded_buffer<chopstick>& _right;
// The name of the philosopher.
wstring _name;
// Stores the number of times the philosopher has eaten.
overwrite_buffer<int> _times_eaten;
// A random number generator.
mt19937 _random_generator;
};
int wmain()
{
// Create an array of message buffers to hold the chopsticks.
array<unbounded_buffer<chopstick>, philosopher_count> chopsticks;
// Send a value to each message buffer in the array.
// The value of the message is not important. A buffer that contains
// any message indicates that the chopstick is available.
for_each (begin(chopsticks), end(chopsticks),
[](unbounded_buffer<chopstick>& c) {
send(c, 1);
});
// Create an array of philosophers. Each pair of neighboring
// philosophers shares one of the chopsticks.
array<philosopher, philosopher_count> philosophers = {
philosopher(chopsticks[0], chopsticks[1], L"aristotle"),
philosopher(chopsticks[1], chopsticks[2], L"descartes"),
philosopher(chopsticks[2], chopsticks[3], L"hobbes"),
philosopher(chopsticks[3], chopsticks[4], L"socrates"),
philosopher(chopsticks[4], chopsticks[0], L"plato"),
};
// Begin the simulation.
for_each (begin(philosophers), end(philosophers), [](philosopher& p) {
p.start();
});
// Wait for each philosopher to finish and print his name and the number
// of times he has eaten.
for_each (begin(philosophers), end(philosophers), [](philosopher& p) {
agent::wait(&p);
wcout << p.name() << L" ate " << p.times_eaten() << L" times." << endl;
});
}
Comments
This example produces the following output.
aristotle ate 50 times. descartes ate 50 times. hobbes ate 50 times. socrates ate 50 times. plato ate 50 times.
Compiling the Code
Copy the example code and paste it in a Visual Studio project, or paste it in a file that is named philosophers-join.cpp and then run the following command in a Visual Studio Command Prompt window.
cl.exe /EHsc philosophers-join.cpp
[Top]
See Also
Concepts
Synchronization Data Structures