Пошаговое руководство. Использование класса join для предотвращения взаимоблокировки
В этом разделе на примере проблемы обедающих философов показано использование класса Concurrency::join для исключения взаимоблокировок в приложении. В программном приложении взаимоблокировка возникает, если каждый из двух или более процессов удерживает ресурс и ожидает освобождения какого-либо другого ресурса другим процессом.
Проблема обедающих философов является конкретным примером общего ряда проблем, когда несколько параллельных процессов совместно используют один набор ресурсов.
Обязательные компоненты
Прежде чем начать выполнение этого пошагового руководства, необходимо ознакомиться со следующими разделами.
Подразделы
Это пошаговое руководство содержит следующие подразделы.
Проблема обедающих философов
Упрощенная реализация
Использование join для предотвращения взаимоблокировок
Проблема обедающих философов
Проблема обедающих философов позволяет проиллюстрировать создание взаимоблокировки в приложении. Пять философов сидят за круглым столом. В определенный момент времени каждый из них может либо размышлять, либо есть. Каждый философ вынужден делиться лежащими перед ним китайскими палочками для еды: одной палочкой с соседом слева, а другой — с соседом справа. Расположение палочек на столе показано на следующем рисунке.
.png "Проблема обедающих философов")
Для еды каждому философу нужно две палочки. Если каждый философ держит в руках одну палочку и ждет, пока ему передадут другую, ни один из них не сможет поесть, и все умрут от голода.
[в начало]
Упрощенная реализация
В следующем примере показана упрощенная реализация проблемы обедающих философов. Класс philosopher, наследуемый от Concurrency::agent, позволяет каждому философу действовать независимо. В этом примере общий массив объектов Concurrency::critical_section используется для предоставления каждому объекту philosopher монопольного доступа к паре китайских палочек.
Для связи реализации с иллюстрацией класс philosopher представляет одного философа. Переменная int представляет одну палочку. Объекты critical_section используются в качестве держателей для китайских палочек. Метод run моделирует жизнь философа. Метод think моделирует процесс мышления, а метод eat — процесс еды.
Объект philosopher блокирует оба объекта critical_section, чтобы смоделировать удаление палочек из держателей до вызова метода eat. После вызова метода eat объект philosopher возвращает палочки держателям, возвращая объекты critical_section в незаблокированное состояние.
Метод pickup_chopsticks показывает, где возможны взаимоблокировки. Если каждый объект philosopher получит доступ к одной из блокировок, ни один из объектов philosopher не сможет продолжить работу, так как другая блокировка управляется другим объектом philosopher.
Пример
Код
// 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 (philosophers.begin(), philosophers.end(), [](philosopher& p) {
p.start();
});
// Wait for each philosopher to finish and print his name and the number
// of times he has eaten.
for_each (philosophers.begin(), philosophers.end(), [](philosopher& p) {
agent::wait(&p);
wcout << p.name() << L" ate " << p.times_eaten() << L" times." << endl;
});
}
Компиляция кода
Скопируйте код примера и вставьте его в проект Visual Studio или в файл с именем philosophers-deadlock.cpp, затем выполните в окне командной строки Visual Studio 2010 следующую команду.
cl.exe /EHsc philosophers-deadlock.cpp
[в начало]
Использование join для предотвращения взаимоблокировок
В этом разделе показано, как использовать буферы сообщений и функции передачи сообщений для снижения вероятности взаимоблокировки.
Чтобы связать этот пример с предыдущим, класс philosopher заменяет каждый объект critical_section объектами Concurrency::unbounded_buffer и join. Объект join выполняет функции арбитра, предоставляющего палочки философу.
В этом примере используется класс unbounded_buffer, поскольку когда целевой объект получает сообщение от объекта unbounded_buffer, это сообщение удаляется из очереди сообщений. Благодаря этому объект unbounded_buffer, хранящий сообщение, может показать, что палочка доступна. Объект unbounded_buffer, не содержащий сообщение, указывает, что палочка используется.
В этом примере используется нежадный объект join, поскольку нежадное соединение предоставляет каждому объекту philosopher доступ к двум палочкам только в том случае, если оба объекта unbounded_buffer содержат сообщение. Жадное соединение не позволяет предотвратить взаимоблокировку, так как жадное соединение принимает сообщения, как только они становятся доступными. Если все жадные объекты join получают одно из сообщений, но бесконечно ожидают, пока станут доступными другие, создаются взаимоблокировки.
Дополнительные сведения о жадных и нежадных соединениях и различиях между разными типами буферов сообщений см. в разделе Асинхронные блоки сообщений.
Как избежать взаимоблокировки в этом примере
Удалите из примера следующий код.
// A shared array of critical sections. Each critical section // guards access to a single chopstick. critical_section locks[philosopher_count];Измените тип членов данных _left и _right класса philosopher на unbounded_buffer.
// Message buffer for the left chopstick. unbounded_buffer<chopstick>& _left; // Message buffer for the right chopstick. unbounded_buffer<chopstick>& _right;Измените конструктор philosopher для принятия объектов unbounded_buffer в качестве параметров.
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); }Измените метод pickup_chopsticks, чтобы использовать нежадный объект join для получения сообщений из буферов сообщений для обеих палочек.
// 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); }Измените метод putdown_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); }Измените метод run, чтобы он хранил результаты метода pickup_chopsticks и передавал эти результаты методу putdown_chopsticks.
// 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(); }Измените объявление переменной chopsticks в функции wmain на массив объектов unbounded_buffer, каждый из которых содержит одно сообщение.
// 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 (chopsticks.begin(), chopsticks.end(), [](unbounded_buffer<chopstick>& c) { send(c, 1); });
Пример
Описание
Далее представлен полный пример, в котором для снижения вероятности взаимоблокировки используются нежадные объекты join.
Код
// 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 (chopsticks.begin(), chopsticks.end(),
[](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 (philosophers.begin(), philosophers.end(), [](philosopher& p) {
p.start();
});
// Wait for each philosopher to finish and print his name and the number
// of times he has eaten.
for_each (philosophers.begin(), philosophers.end(), [](philosopher& p) {
agent::wait(&p);
wcout << p.name() << L" ate " << p.times_eaten() << L" times." << endl;
});
}
Комментарии
После выполнения примера получается следующий результат.
aristotle ate 50 times.
descartes ate 50 times.
hobbes ate 50 times.
socrates ate 50 times.
plato ate 50 times.
Компиляция кода
Скопируйте код примера и вставьте его в проект Visual Studio или в файл с именем philosophers-join.cpp, затем выполните в окне командной строки Visual Studio 2010 следующую команду.
cl.exe /EHsc philosophers-join.cpp
[в начало]
См. также
Основные понятия
Библиотека асинхронных агентов
Структуры данных синхронизации
Другие ресурсы
Практические и пошаговые руководства, посвященные асинхронным агентам