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

W tym temacie użyto problemu filozofów jadalni, aby zilustrować sposób używania klasy concurrency::join , aby zapobiec zakleszczeniom w aplikacji. W aplikacji programowej zakleszczenie występuje, gdy co najmniej dwa procesy przechowują zasób i wzajemnie oczekują na wydanie innego zasobu.

Problem filozofów z jadalnią jest konkretnym przykładem ogólnego zestawu problemów, które mogą wystąpić, gdy zestaw zasobów jest współużytkowany przez wiele współbieżnych procesów.

Wymagania wstępne

Przed rozpoczęciem tego przewodnika zapoznaj się z następującymi tematami:

• Agenci asynchroniczni

• Przewodnik: tworzenie aplikacji opartej o agentów

• Bloki komunikatów asynchronicznych

• Funkcje przekazywania komunikatów

• Struktury danych synchronizacji

Sekcje

Ten przewodnik zawiera następujące sekcje:

• Problem filozofów jadalni

• Naiwna implementacja

• Używanie sprzężenia w celu zapobiegania zakleszczeniom

Problem filozofów jadalni

Problem filozofów jadalni ilustruje, jak impas występuje w aplikacji. W tym problemie pięciu filozofów siedzi przy okrągłym stole. Każdy filozof alternatywne między myśleniem a jedzeniem. Każdy filozof musi podzielić się chopstick z sąsiadem po lewej stronie i inny chopstick z sąsiadem po prawej stronie. Na poniższej ilustracji przedstawiono ten układ.

Aby jeść, filozof musi trzymać dwa chopsticks. Jeśli każdy filozof posiada tylko jedną chopstick i czeka na inną, to żaden filozof nie może jeść i wszystkie głodować.

[Top]

Naiwna implementacja

W poniższym przykładzie przedstawiono naiwne wdrożenie problemu filozofów gastronomicznych. Klasa philosopher , która pochodzi z współbieżności::agent, umożliwia każdemu filozofowi niezależne działanie. W przykładzie użyto udostępnionej tablicy obiektów współbieżności::critical_section , aby dać każdemu philosopher obiektowi wyłączny dostęp do pary chopsticks.

Aby powiązać implementację z ilustracją, klasa reprezentuje jednego filozofa philosopher . Zmienna int reprezentuje każdy chopstick. Obiekty critical_section służą jako posiadacze, na których spoczywają chopsticky. Metoda run symuluje życie filozofa. Metoda think symuluje działanie myślenia, a eat metoda symuluje akt jedzenia.

Obiekt philosopher blokuje oba critical_section obiekty w celu symulowania usunięcia chopsticks z posiadaczy przed wywołaniem eat metody . Po wywołaniu metody eatphilosopher obiekt zwraca chopsticks do posiadaczy, ustawiając critical_section obiekty z powrotem na odblokowany stan.

Metoda pickup_chopsticks ilustruje, gdzie może wystąpić zakleszczenie. Jeśli każdy philosopher obiekt uzyska dostęp do jednej z blokad, żaden obiekt nie philosopher może kontynuować, ponieważ druga blokada jest kontrolowana przez inny philosopher obiekt.

Przykład

// 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 wklej go w pliku o nazwie philosophers-deadlock.cpp , a następnie uruchom następujące polecenie w oknie wiersza polecenia programu Visual Studio.

cl.exe /EHsc filozofów-impas.cpp

[Top]

korzystanie ze złączy w celu zapobiegania zakleszczeniom

W tej sekcji pokazano, jak używać buforów komunikatów i funkcji przekazywania komunikatów w celu wyeliminowania prawdopodobieństwa zakleszczenia.

Aby powiązać ten przykład z wcześniejszym, philosopher klasa zastępuje każdy critical_section obiekt przy użyciu obiektu concurrency::unbounded_buffer i join obiektu. Obiekt join służy jako arbiter, który zapewnia chopsticks filozofowi.

W tym przykładzie użyto unbounded_buffer klasy , ponieważ gdy obiekt docelowy odbiera komunikat z unbounded_buffer obiektu, komunikat zostanie usunięty z kolejki komunikatów. unbounded_buffer Dzięki temu obiekt, który zawiera komunikat, wskazuje, że chopstick jest dostępny. unbounded_buffer Obiekt, który nie zawiera komunikatu, wskazuje, że jest używana chopstick.

W tym przykładzie użyto niechłannego obiektu, ponieważ niechłanne join sprzężenie daje każdemu philosopher obiektowi dostęp do obu chopsticks tylko wtedy, gdy oba unbounded_buffer obiekty zawierają komunikat. Chciwy sprzężenie nie zapobiegnie impasowi, ponieważ chciwy sprzężenie akceptuje wiadomości, gdy tylko staną się dostępne. Zakleszczenie może wystąpić, jeśli wszystkie chciwe join obiekty otrzymają jeden z komunikatów, ale poczekaj na zawsze, aż inne staną się dostępne.

Aby uzyskać więcej informacji na temat chciwych i niechłannych sprzężeń oraz różnic między różnymi typami buforów komunikatów, zobacz Asynchroniczne bloki komunikatów.

W celu uniknięcia zakleszczenia w tym przykładzie

1. Usuń poniższy kod z przykładu.

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

1. Zmień typ składowych _left i _right danych philosopher klasy na unbounded_buffer.

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

1. Zmodyfikuj konstruktor, philosopher aby pobierał 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);
}

1. Zmodyfikuj metodę pickup_chopsticks tak, aby używała niechłannego join obiektu do odbierania komunikatów z buforów komunikatów dla obu 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);
}

1. Zmodyfikuj metodę putdown_chopsticks , aby zwolnić dostęp do chopsticks, wysyłając komunikat do buforów komunikatów dla obu 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);
}

1. Zmodyfikuj metodę run , aby przechowywać wyniki pickup_chopsticks metody i przekazać te wyniki 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();
}

1. Zmodyfikuj deklarację zmiennej chopsticks w wmain funkcji, aby być tablicą unbounded_buffer obiektów, które przechowują jeden komunikat.

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

opis

Poniżej przedstawiono ukończony przykład, który używa niechłannych join obiektów w celu wyeliminowania ryzyka zakleszczenia.

Przykład

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

W tym przykładzie są generowane następujące dane wyjściowe.

aristotle ate 50 times.
descartes ate 50 times.
hobbes ate 50 times.
socrates ate 50 times.
plato ate 50 times.

Kompilowanie kodu

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

cl.exe /EHsc filozofów-join.cpp

[Top]

Zobacz też

Środowisko uruchomieniowe współbieżności — wskazówki
Biblioteki agentów asynchronicznych
Agenci asynchroniczni
Bloki komunikatów asynchronicznych
Funkcje przekazywania komunikatów
Struktury danych synchronizacji