Instruktaż: Za pomocą sprzężenia, aby zapobiec zakleszczenia

Artykuł
05/01/2013

W tym temacie używa ucztujących filozofów, aby zilustrować sposób użycia concurrency::join klasy w celu uniknięcia zakleszczenia w aplikacji.W aplikacji zakleszczenia występuje, gdy dwa lub więcej procesów każdego zasobu przytrzymaj i wzajemnie poczekaj, aż inny proces zwolnić niektórych innych zasobów.

Ucztujących filozofów jest przykładem szczególnych ogólny zestaw problemów, które mogą wystąpić podczas współużytkowany zestaw zasobów w wielu równoczesnych procesów.

Wymagania wstępne

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

Sekcje

Ten instruktaż zawiera następujące sekcje:

Ucztujących Filozofów
Wdrożenie Naïve
Za pomocą sprzężenia, aby zapobiec zakleszczenia

Ucztujących Filozofów

Ucztujących filozofów ilustruje, jak zakleszczenie występuje w aplikacji.W ten problem pięciu filozofów siedzieć przy okrągłego stołu.Każdy filozof na przemian myślenia i jedzenia.Każdy filozof musi udostępniać chopstick sąsiada do lewej, a drugi chopstick z sąsiada w prawo.Poniższa ilustracja pokazuje ten układ.

Problem Ucztujących Filozofów

Do eat, filozof musi posiadać dwie pałeczki.Jeśli każdy filozof posiada tylko jeden chopstick i oczekuje na inną, następnie eat może nie filozof i uniemożliwić wykonywanie wszystkich.

Top

Wdrożenie Naïve

Poniższy przykład pokazuje wykonania naïve ucztujących filozofów.philosopher Klasy, która wynika z concurrency::agent, umożliwia każdego filozof działać niezależnie.W przykładzie użyto udostępnionej macierzy concurrency::critical_section obiektów nadaje każdemu philosopher wyłącznego dostępu do pary pałeczki obiektu.

Dotyczą realizacji do ilustracji, philosopher klasy reprezentuje jeden filozof.int Zmienna reprezentuje każdego chopstick.critical_section Obiektów służą jako posiadaczy, na których pałeczki odpoczynku.run Metody symuluje życia filozof.think Metody symuluje aktu myślenia i eat metody symuluje aktu jedzenia.

A philosopher obiektu blokuje zarówno critical_section obiekty do symulowania usunięcie pałeczki od posiadaczy przed nim wywołuje eat metody.Po wywołaniu eat, philosopher obiektu zwraca pałeczki posiadaczom przez ustawienie critical_section obiektów z powrotem do Państwa odblokowany.

pickup_chopsticks Metoda ilustruje, w których może wystąpić zakleszczenie.Jeśli każdy philosopher obiekt uzyska dostęp do jednego z blokad, a następnie nr 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 uruchom następujące polecenie w oknie wiersza polecenia usługi programu Visual Studio.

cl.exe /EHsc philosophers-deadlock.cpp

Top

Za pomocą sprzężenia, aby zapobiec zakleszczenia

W tej sekcji przedstawiono sposób użycia buforów wiadomości i funkcje służące do przekazywania wiadomości, aby wyeliminować ryzyko zakleszczenia.

W tym przykładzie do poprzedniej, dotyczą philosopher klasy zastępuje wszystkie critical_section obiektu za pomocą concurrency::unbounded_buffer obiektu i join obiektu.join Obiektu służy jako arbiter, która zapewnia pałeczki do filozof.

W tym przykładzie unbounded_buffer klasy, ponieważ gdy cel otrzymuje wiadomość z unbounded_buffer obiekt, po usunięciu wiadomości z kolejki wiadomości.Umożliwia to unbounded_buffer obiekt, który przechowuje wiadomości, aby wskazać, że chopstick jest dostępny.unbounded_buffer Obiekt, który przechowuje się żaden komunikat wskazuje, że używany jest chopstick.

W tym przykładzie użyto non sowa join obiektu, ponieważ daje-sowa sprzężenia, każdy philosopher dostęp do obu pałeczki obiekt tylko wtedy, gdy oba unbounded_buffer obiekty zawierają wiadomości.Sowa sprzężenia nie uniemożliwi zakleszczenia, ponieważ sowa sprzężenia akceptuje wiadomości, jak tylko staną się dostępne.Zakleszczenie może wystąpić w przypadku wszystkich sowa join obiekty wyświetlany jeden z komunikatów, ale czekają na inne, stanie 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 Asynchroniczne blokuje wiadomości.

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];

Zmienianie typu _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 obiektów, jak 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 non sowa metodę join obiektu do odbierania wiadomości z buforów wiadomości 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 metoda zwolnić dostęp do pałeczki poprzez wysyłanie wiadomości do buforów wiadomości dla obu pałeczki.

// 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 metody 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 w zmiennej wmain funkcję być tablicą unbounded_buffer obiektów każdego przytrzymaj klawisz jednej wiadomości.

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

Następujące pokazuje przykład używający innych niż sowa 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.

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 wkleić go w pliku o nazwie filozofów join.cpp , a następnie uruchom następujące polecenie w oknie wiersza polecenia usługi programu Visual Studio.

cl.exe /EHsc philosophers-join.cpp

Top