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

Toto téma používá problém s jídelnami filozofie ilustrovat, jak používat concurrency::join třídy k zabránění zablokování ve vaší aplikaci. V softwarové aplikaci dojde k vzájemnému zablokování, když dva nebo více procesů každý uchovává prostředek a vzájemně čeká na další proces uvolnění některého jiného prostředku.

Problém s jídelnami je konkrétním příkladem obecné sady problémů, ke kterým může dojít, když je sada prostředků sdílena mezi více souběžnými procesy.

Požadavky

Než začnete s tímto názorem, přečtěte si následující témata:

• Asynchronní agenti

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

• Asynchronní bloky zpráv

• Funkce pro předávání zpráv

• Synchronizační datové struktury

Oddíly

Tento názorný postup obsahuje následující části:

• The DiningOlogs problem

• Implementace naïvu

• Použití spojení k zabránění vzájemnému zablokování

The DiningOlogs problem

Problém s jídelnami ukazuje, jak se v aplikaci vyskytuje vzájemné zablokování. V tomto problému sedí pět filosofů u kulatého stolu. Každý filosof se střídá mezi myšlením a jídlem. Každý filosof musí sdílet hůlku se sousedem vlevo a další hůlku se sousedem vpravo. Toto rozložení je znázorněno na následujícím obrázku.

Chcete-li jíst, musí filozofie držet dvě hůlky. Pokud každý filosof drží jen jednu hůlku a čeká na další, pak žádný filozofie nemůže jíst a všechny hladovět.

[Nahoře]

Implementace naïvu

Následující příklad ukazuje naïve implementace problému jídelny filozofie. Třída philosopher , která je odvozena od souběžnosti::agent, umožňuje každému filozofie jednat nezávisle. V příkladu se používá sdílené pole souběžnosti::critical_section objekty, aby každý philosopher objekt získal výhradní přístup ke dvojici hůlek.

Chcete-li spojit implementaci s ilustrací, philosopher třída představuje jeden filozofie. Proměnná int představuje každou hůlku. Objekty critical_section slouží jako držáky, na kterých jsou chytáčky. Metoda run simuluje život filosofa. Metoda think simuluje akt myšlení a eat metoda simuluje akt stravování.

Objekt philosopher uzamkne oba critical_section objekty, aby simulovali odebrání hůlky z držáků předtím, než zavolá metodu eat . Po volání eatphilosopher objekt vrátí chopky držitelům nastavením critical_section objektů zpět do odemknutého stavu.

Tato pickup_chopsticks metoda znázorňuje, kde může dojít k vzájemnému zablokování. Pokud každý philosopher objekt získá přístup k jednomu z zámků, nemůže pokračovat žádný philosopher objekt, protože druhý zámek je řízen jiným philosopher objektem.

Příklad

// 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írujte ukázkový kód a vložte ho do projektu sady Visual Studio nebo ho vložte do pojmenovaného philosophers-deadlock.cpp souboru a potom v okně příkazového řádku sady Visual Studio spusťte následující příkaz.

cl.exe /EHsc philosophers-deadlock.cpp

[Nahoře]

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

V této části se dozvíte, jak pomocí vyrovnávacích pamětí zpráv a funkcí předávání zpráv eliminovat riziko zablokování.

Chcete-li tento příklad propojit s předchozím objektem, philosopher třída nahradí každý critical_section objekt pomocí concurrency::unbounded_buffer objektu a objektu join . Objekt join slouží jako arbiter, který poskytuje hůlky filozofie.

Tento příklad používá unbounded_buffer třídu, protože když cíl přijme zprávu z objektu unbounded_buffer , zpráva se odebere z fronty zpráv. To umožňuje unbounded_buffer objektu, který obsahuje zprávu, která označuje, že je k dispozici chopička. Objekt unbounded_buffer , který neobsahuje žádnou zprávu, značí, že se používá chopka.

Tento příklad používá objekt, který není greedy join , protože spojení bez greedy dává každému philosopher objektu přístup k oběma hůlky pouze v případě, že oba unbounded_buffer objekty obsahují zprávu. Greedy spojení by nezabránilo zablokování, protože greedy join přijímá zprávy, jakmile budou k dispozici. Zablokování může nastat, pokud všechny greedy join objekty obdrží jednu ze zpráv, ale čekat na to, až ostatní budou k dispozici.

Další informace o greedy a non-greedy spojení a rozdíly mezi různými typy vyrovnávací paměti zpráv naleznete v části Asynchronní bloky zpráv.

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

1. Odeberte z příkladu následující kód.

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

1. Změňte typ datových _left _right členů philosopher třídy na unbounded_buffer.

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

1. Upravte konstruktor tak philosopher , aby jako jeho parametry převzal unbounded_buffer objekty.

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. Upravte metodu pickup_chopsticks tak, aby k příjmu zpráv z vyrovnávací paměti pro obě hůlky používal objekt, který není greedy join .

// 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. Upravte metodu putdown_chopsticks uvolnění přístupu k hůlkám odesláním zprávy do vyrovnávací paměti zprávy pro obě hůlky.

// 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. Upravte metodu run tak, aby držela výsledky pickup_chopsticks metody a předala tyto výsledky metodě putdown_chopsticks .

// 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. Upravte deklaraci chopsticks proměnné ve wmain funkci tak, aby byla polem unbounded_buffer objektů, které obsahují každou 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);
});

Popis

Následující příklad ukazuje dokončený příklad, který používá objekty bez greedy join k odstranění rizika zablokování.

Příklad

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

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

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

Probíhá kompilace kódu

Zkopírujte ukázkový kód a vložte ho do projektu sady Visual Studio nebo ho vložte do pojmenovaného philosophers-join.cpp souboru a potom v okně příkazového řádku sady Visual Studio spusťte následující příkaz.

cl.exe /EHsc philosophers-join.cpp

[Nahoře]

Viz také

Návody pro Concurrency Runtime
Knihovna asynchronních agentů
Asynchronní agenti
Asynchronní bloky zpráv
Funkce pro předávání zpráv
Synchronizační datové struktury