Wskazówki: korzystanie ze złączy w celu zapobiegania zakleszczeniom

Artykuł
06/09/2015

W tym temacie używa do zilustrowania sposobu korzystania problem ucztujących filozofów concurrency::join klasy w celu uniknięcia zakleszczenia w aplikacji.W aplikacji zakleszczenie występuje, gdy dwie lub więcej procesów każdego przytrzymaj zasobu i wzajemnie czekać na inny proces do uwolnienia niektórych innych zasobów.

Problem ucztujących filozofów jest konkretnym przykładzie ogólny zestaw problemów, które mogą wystąpić podczas zestaw zasobów jest współużytkowane przez wiele procesów równoczesnych.

Wymagania wstępne

Przed rozpoczęciem tego instruktażu, przeczytaj następujące tematy:

Sekcje

Ten instruktaż zawiera następujące sekcje:

Problem ucztujących filozofów
Prosta implementacja
Korzystając ze złączy, aby zapobiec zakleszczeniu

Problem ucztujących filozofów

Problem ucztujących filozofów ilustruje, jak zakleszczenie występuje w aplikacji.W tym problem pięciu filozofów siedzieć przy okrągłym stole.Każdy filozof przemian myślenia i jedzenia.Każdy filozof musi dzielić chopstick z sąsiada do lewej, a drugi chopstick z sąsiadem w prawo.Na poniższej ilustracji przedstawiono ten układ.

Problem ucztujących filozofów

Jeść, filozof musi posiadać dwie pałeczki.Jeśli każdy filozof posiada tylko jeden chopstick i czeka na inny, następnie jeść nie filozof i wszystkie głodować.

[U góry]

Prosta implementacja

W poniższym przykładzie prostego stosowania problem ucztujących filozofów.philosopher Klasa, która wywodzi się z concurrency::agent, umożliwia każdej filozof do działania niezależnie od siebie.W przykładzie użyto udostępnionej macierzy concurrency::critical_section obiektów, aby dać każdej philosopher obiekt wyłączny dostęp do pary pałeczki.

Odnosić się wykonania ilustracji, philosopher klasy reprezentuje jeden filozof.int Zmienna reprezentuje każdego chopstick.critical_section Obiektów służą jako posiadaczy, na których PAŁECZKAMI odpoczynku.run Metoda symuluje życia filozofa.think Metoda symuluje aktu myślenia i eat metoda symuluje z jedzenia.

A philosopher obiektu blokuje zarówno critical_section obiektów, aby symulować usunięcie pałeczki od posiadaczy przed nim wywołania eat metody.Po wywołaniu eat, philosopher obiekt zwraca PAŁECZKAMI posiadaczom przez ustawienie critical_section obiektów z powrotem do stanu odblokowany.

pickup_chopsticks Metoda ilustruje, gdzie może wystąpić zakleszczenia.Jeśli każde philosopher obiekt uzyska dostęp do jednego z blokad, a następnie nie philosopher obiektu można kontynuować, ponieważ inne blokady jest kontrolowana przez innego philosopher obiektu.

Przykład

Kod

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

Kompilowanie kodu

Skopiuj przykładowy kod i wklej go w projekcie programu Visual Studio lub wkleić go w pliku o nazwie filozofów deadlock.cpp , a następnie uruchomić następujące polecenie w oknie wiersza polecenia programu Visual Studio.

cl.exe /EHsc philosophers-deadlock.cpp

[U góry]

Korzystając ze złączy, aby zapobiec zakleszczeniu

W tej sekcji przedstawiono sposób użycia funkcje przekazywania wiadomości i wiadomości buforów wyeliminować ryzyko zakleszczenia.

Powiązać ten przykład to poprzednie philosopher klasa zastępuje wszystkie critical_section obiektu za pomocą concurrency::unbounded_buffer obiektu i join obiektu.join Obiektu służy jako arbitra, który zapewnia PAŁECZKAMI do filozofa.

W poniższym przykładzie użyto unbounded_buffer klasy, ponieważ kiedy tarczę otrzyma wiadomość od unbounded_buffer obiektu, wiadomość jest usuwana z kolejki wiadomości.Dzięki temu unbounded_buffer obiekt, który przechowuje wiadomości, aby wskazać, że chopstick jest dostępny.unbounded_buffer Obiekt, który przechowuje żaden komunikat wskazuje, że używany jest chopstick.

W tym przykładzie użyto non chciwy join obiektu, ponieważ-sowa sprzężenia nadaje każdemu philosopher obiektu dostęp do obu pałeczki tylko wtedy, gdy oba unbounded_buffer obiekty zawierają wiadomości.Intensywnie sprzężenia nie stanowi to przeszkody zakleszczenie ponieważ sowa sprzężenia akceptuje wiadomości, tak szybko, jak tylko staną się dostępne.Zakleszczenie może wystąpić, jeśli wszystkie sowa join obiekty wyświetlany jest jeden z komunikatów, ale czekają na inne stają się dostępne.

Aby uzyskać więcej informacji na temat sprzężeń sowa i sowa i różnice między różnymi rodzajami bufor wiadomości, zobacz Bloki komunikatów asynchronicznych.

W celu uniknięcia zakleszczenia w tym przykładzie

Usuń następujący kod z przykładu.

// A shared array of critical sections. Each critical section  
// guards access to a single chopstick.
critical_section locks[philosopher_count];

Zmień typ _left i _right danych członków philosopher klasy do unbounded_buffer.

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

Modyfikowanie philosopher Konstruktor do podjęcia unbounded_buffer obiekty jako jego parametry.

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

Modyfikowanie pickup_chopsticks metodę non chciwy join obiektu do odbierania wiadomości z buforów wiadomość dla obu pałeczki.

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

Modyfikowanie putdown_chopsticks metodę, aby zwolnić, wysyłając wiadomość do buforów wiadomość dla obu pałeczki dostęp do PAŁECZKAMI.

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

Modyfikowanie run metoda do przechowywania wyników z pickup_chopsticks metody i do przekazywania tych wyników do putdown_chopsticks metody.

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

Modyfikowanie deklaracji chopsticks zmiennej w wmain funkcji jako tablicę z unbounded_buffer obiektów, aby pełnić jedną wiadomość.

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

Przykład

Opis

Poniżej pokazano przykład korzystającej z nie chciwy join obiektów, aby wyeliminować ryzyko zakleszczenia.

Kod

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

Komentarze

Ten przykład generuje następujące wyniki.

Kompilowanie kodu

Skopiuj przykładowy kod i wklej go w projekcie programu Visual Studio lub wkleić go w pliku o nazwie filozofów join.cpp , a następnie uruchomić następujące polecenie w oknie wiersza polecenia programu Visual Studio.

cl.exe /EHsc philosophers-join.cpp

[U góry]