Návod: Použití metody join k zabránění vzájemnému zablokování

Toto téma používá problém obědvajících filosofů znázorňující způsob použití concurrency::join třídy, aby nedošlo k zablokování aplikace.V softwarové aplikaci zablokování dochází, když dva nebo více procesů každý obsahovat prostředek a vzájemně čekat jiný proces uvolnit některé jiné zdroje.

Problém obědvajících filosofů je konkrétní příklad sady obecné problémy, které mohou nastat při sadu prostředků je sdílena mezi více souběžných procesů.

Požadavky

Před zahájením tohoto návodu naleznete v následujících tématech:

• Asynchronní agenti

• Návod: Vytvoření aplikace založené na agentovi

• Asynchronní bloky zpráv

• Funkce usnadnění

• Synchronizační datové struktury

Oddíly

Tento návod obsahuje následující oddíly:

• Problém obědvajících filozofů

• Naivní implementace

• Předcházení zablokování pomocí spojení

Problém obědvajících filozofů

Problém obědvajících filosofů ukazuje, jak v aplikaci, dojde k zablokování.V tomto problému pěti filosofů sedět u kulatého stolu.Každý filosofovi střídavě myslím a pít.Každý filosofovi musí sdílet chopstick soused vlevo a jinou chopstick s souseda vpravo.Následující ilustrace znázorňuje toto rozložení.

K jídlu, filosofovi musí mít dva chopsticks.Pokud filosofovi, každý obsahuje právě jeden chopstick a čekání na jiný, pak můžete jíst žádné filosofovi a všechny starve.

[Nahoře]

Naivní implementace

Následující příklad ukazuje provádění problém obědvajících filosofů naïve.philosopher Třídy, která je odvozena z concurrency::agent, umožňuje každému filosofovi jednat nezávisle.V příkladu je sdílená pole concurrency::critical_section objekty, které chcete dát philosopher objekt na pár chopsticks výhradní přístup.

K provedení na obrázku, se vztahují philosopher třída představuje jeden filosofovi.int Proměnná představuje každý chopstick.critical_section Slouží jako držitelé, na které chopsticks umístěte objekty.run Metoda simuluje život filosofovi.think Metoda simuluje aktu myšlení a eat metoda simuluje aktu pít.

A philosopher objekt zamkne oba critical_section objekty pro simulaci odstranění chopsticks od držitelů před volá eat metody.Po volání eat, philosopher objekt vrátí chopsticks držitelům nastavením critical_section objekty zpět do stavu odemčení.

pickup_chopsticks Metoda ukazuje, kde může dojít k vzájemnému zablokování.Pokud každý philosopher objektu získává přístup k některé zámky pak č philosopher objekt můžete pokračovat, protože ostatní zámek je řízen jiným philosopher objektu.

Příklad

Kód

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

Probíhá kompilace kódu

Zkopírovat ukázkový kód a vložit jej do projektu sady Visual Studio nebo vložit do souboru s názvem filosofů deadlock.cpp a potom spusťte následující příkaz v okně Příkazový řádek Visual Studio.

cl.exe /EHsc philosophers-deadlock.cpp

[Nahoře]

Předcházení zablokování pomocí spojení

V této části ukazuje, jak eliminovat pravděpodobnost zablokování pomocí funkcí předávání zpráv a zpráva vyrovnávací paměti.

Platí tento příklad je starší philosopher třídy nahradí každou critical_section pomocí objektu concurrency::unbounded_buffer objekt a join objektu.join Objekt slouží jako arbiter, které poskytuje chopsticks filosofovi.

V tomto příkladu unbounded_buffer třídy protože kdy cíl obdrží zprávu z unbounded_buffer objekt, je zpráva odebrána z fronty zpráv.Díky tomu unbounded_buffer objekt, který obsahuje zprávu, která označuje, zda chopstick je k dispozici.unbounded_buffer Objekt, který obsahuje žádná zpráva označuje, že je používán chopstick.

V tomto příkladu non hladový join objektu, protože-hladový spojení poskytuje všechny philosopher přístup k oběma chopsticks objektu pouze tehdy, když obě unbounded_buffer objekty obsahují zprávy.Hladový spojení by nedošlo k zablokování, protože hladový spojení přijímá zprávy, jakmile budou k dispozici.Může dojít k vzájemnému zablokování, pokud všechny Hladové join objekty jedné zprávy přijímat, ale stále čekat další k dispozici.

Další informace o spojeních-hladový a hladový a rozdíly mezi různými druhy vyrovnávací paměti zprávy, viz Asynchronní bloky zpráv.

Jak v tomto příkladu zabránit zablokování

1. Následující kód odeberte z příkladu.

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

2. Změna typu _left a _right datové členy philosopher třídu unbounded_buffer.

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

3. Změnit philosopher konstruktor se unbounded_buffer objekty jako její 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);
   }
   

4. Změnit pickup_chopsticks metodu použít non hladový join objekt, který chcete přijímat zprávy z vyrovnávací paměti zprávy pro oba 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);
   }
   

5. Změnit putdown_chopsticks metoda k uvolnění přístupu k chopsticks odesláním zprávy do vyrovnávací paměti zprávy pro oba 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);
   }
   

6. Změnit run metoda pro uložení výsledků pickup_chopsticks metoda a předávat tyto výsledky 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();
   }
   

7. Změnit prohlášení o chopsticks v proměnné wmain funkci jako pole unbounded_buffer objekty, že každý obsahovat jednu zprávu.

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

Příklad

Description

Následující příklad zobrazuje vyplněný příklad, který používá non hladový join objekty, které chcete vyloučit riziko vzájemného zablokování.

Kód

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

Komentáře

Tento příklad vytvoří následující výstup.

Probíhá kompilace kódu

Zkopírovat ukázkový kód a vložit jej do projektu sady Visual Studio nebo vložit do souboru s názvem filosofů join.cpp a potom spusťte následující příkaz v okně Příkazový řádek Visual Studio.

cl.exe /EHsc philosophers-join.cpp

[Nahoře]

Viz také

Koncepty

Knihovna asynchronních agentů

Asynchronní agenti

Asynchronní bloky zpráv

Funkce usnadnění

Synchronizační datové struktury

Další zdroje

Návody k Concurrency Runtime