Пошаговое руководство. Использование класса join для предотвращения взаимоблокировки

Мақала
10/12/2023

В этом разделе показано, как использовать класс параллелизма::join , чтобы предотвратить взаимоблокировку в приложении. В приложении программного обеспечения взаимоблокировка возникает, когда два или несколько процессов используют ресурс и одновременно ожидают, пока другой процесс не освободит какой-либо из ресурсов.

Проблема столовой философов является конкретным примером общего набора проблем, которые могут возникнуть, когда набор ресурсов делится между несколькими параллельными процессами.

Необходимые компоненты

Ознакомьтесь со следующими разделами перед началом работы с этим пошаговом руководстве.

Разделы

Это пошаговое руководство содержит следующие разделы:

Проблема столовой философов
Наивная реализация
Использование соединения для предотвращения взаимоблокировки

Проблема столовой философов

Проблема столовой философов иллюстрирует, как взаимоблокировка возникает в приложении. В этой проблеме пять философов сидят на круглом столе. Каждый философ чередуется между мышлением и едой. Каждый философ должен поделиться палкой с соседом слева и другим хубом с соседом справа. На следующем рисунке показан этот макет.

Проблема столовой философов.

Чтобы съесть, философ должен держать два колеи. Если каждый философ держит только один палочкой и ждет другого, то ни один философ не может есть и все голодать.

[В начало]

Наивная реализация

В следующем примере показана наивная реализация проблемы столовой философов. Класс philosopher , производный от параллелизма::agent, позволяет каждому философу действовать независимо. В этом примере используется общий массив объектов параллелизма::critical_section для предоставления каждому philosopher объекту монопольного доступа к паре срезов.

Чтобы связать реализацию с иллюстрацией, philosopher класс представляет одного философа. Переменная представляет каждую int мерку. Объекты critical_section служат держателями, на которых покоится колб. Метод run имитирует жизнь философа. Метод think имитирует акт мышления и eat метод имитирует действие еды.

Объект philosopher блокирует оба critical_section объекта, чтобы имитировать удаление прирезных точек от держателей перед вызовом eat метода. После вызова eatобъекта возвращаются поступки держателям, philosopher задав critical_section объекты обратно в разблокированное состояние.

Метод pickup_chopsticks иллюстрирует, где может произойти взаимоблокировка. Если каждый philosopher объект получает доступ к одной из блокировок, объект не philosopher может продолжаться, так как другая блокировка управляется другим philosopher объектом.

Пример

C++

// 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;
   });
}

Компиляция кода

Скопируйте пример кода и вставьте его в проект Visual Studio или вставьте его в файл с именем philosophers-deadlock.cpp , а затем выполните следующую команду в окне командной строки Visual Studio.

cl.exe /EHsc philosophers-deadlock.cpp

[В начало]

Использование класса join для предотвращения взаимных блокировок

В этом разделе показано, как использовать буферы сообщений и функции передачи сообщений, чтобы устранить вероятность взаимоблокировки.

Чтобы связать этот пример с предыдущим philosopher , класс заменяет каждый critical_section объект с помощью параллелизма::unbounded_buffer объекта и join объекта. Объект join служит арбитером, который предоставляет палки философу.

В этом примере используется unbounded_buffer класс, так как когда целевой объект получает сообщение от unbounded_buffer объекта, сообщение удаляется из очереди сообщений. Это позволяет объекту unbounded_buffer , в котором содержится сообщение, указывающее, что палка доступна. Объект unbounded_buffer , который не содержит сообщения, указывает на то, что используется прирезная палочка.

В этом примере используется не жадный объект, так как не жадное join соединение дает каждому philosopher объекту доступ к обоим прирезкам только в том случае, если оба unbounded_buffer объекта содержат сообщение. Жадное присоединение не предотвратит взаимоблокировку, так как жадное соединение принимает сообщения, как только они становятся доступными. Взаимоблокировка может произойти, если все жадные join объекты получают одно из сообщений, но подождите, пока другой станет доступным.

Дополнительные сведения о жадных и не жадных соединениях и различиях между различными типами буферов сообщений см. в разделе "Асинхронные блоки сообщений".

Предотвращение взаимоблокировки в этом примере

Удалите следующий код из примера.

C++

// 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на .

C++

// Message buffer for the left chopstick.
unbounded_buffer<chopstick>& _left;
// Message buffer for the right chopstick.
unbounded_buffer<chopstick>& _right;

Измените конструктор, philosopher чтобы принимать unbounded_buffer объекты в качестве параметров.

C++

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 объект для получения сообщений из буферов сообщений для обоих колбочек.

C++

// 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 метод, чтобы освободить доступ к палкам, отправив сообщение в буферы сообщений для обоих колбочек.

C++

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

C++

// 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 объектов, которые хранят одно сообщение.

C++

// 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);
});

Description

Ниже показан полный пример, использующий не жадные объекты для устранения риска взаимоблокировки join .

Пример

C++

// 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;
   });
}

В этом примере формируются следующие данные:

Output

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.

cl.exe /EHsc philosophers-join.cpp

[В начало]

См. также

Пошаговые руководства по среде выполнения с параллелизмом
Библиотека асинхронных агентов
Асинхронные агенты
Асинхронные блоки сообщений
Функции передачи сообщений
Структуры данных синхронизации

Бөлісу құралы:

Пошаговое руководство. Использование класса join для предотвращения взаимоблокировки

Необходимые компоненты

Разделы

Проблема столовой философов

Наивная реализация

Пример

Компиляция кода

Использование класса join для предотвращения взаимных блокировок

Предотвращение взаимоблокировки в этом примере

Description

Пример

Компиляция кода

См. также

Кері байланыс

Қосымша ресурстар