Útmutató: Csatlakozás használata a holtpont megelőzéséhez

Ez a szakasz az étkező filozófusok problémáját használja arra, hogy bemutassa, hogyan lehet használni az egyidejűség::join osztályt a holtpont elkerülése érdekében az alkalmazásban. Egy szoftveralkalmazásban holtpont akkor fordul elő, ha két vagy több folyamat mindegyike egy erőforrást tárol, és kölcsönösen megvárja, amíg egy másik folyamat más erőforrást bocsát ki.

Az étkező filozófusok problémája egy konkrét példa az általános problémákra, amelyek akkor fordulhatnak elő, ha egy erőforráskészlet több egyidejű folyamat között van megosztva.

Előfeltételek

Mielőtt elkezdené ezt az útmutatót, olvassa el az alábbi témaköröket:

• Aszinkron ügynökök

• Útmutató: Agent-Based-alkalmazás létrehozása

• Aszinkron üzenetblokkok

• Üzenetátadási függvények

• Szinkronizálási adatstruktúrák

Szakaszok

Ez az útmutató a következő szakaszokat tartalmazza:

• Az étkező filozófusok problémája

• Naiv megvalósítás

• Csatlakozás használata a Holtpont megelőzéséhez

Az étkező filozófusok problémája

Az étkező filozófusok problémája bemutatja, hogyan történik holtpont egy alkalmazásban. Ebben a problémában öt filozófus ül egy kerek asztalnál. Minden filozófus váltogatja a gondolkodást és az evést. Minden filozófusnak meg kell osztania egy evőpálcikát a bal oldali szomszéddal, és egy másik evőpálcikát a jobb oldali szomszéddal. Az alábbi ábrán ez az elrendezés látható.

Egy filozófusnak két evőpálcikát kell tartania, hogy egyen. Ha minden filozófus csak egy evőpálcikát tart, és egy másikra vár, akkor egyetlen filozófus sem tud enni és éhezni.

[Felső]

Egyszerű, naiv megvalósítás

Az alábbi példa az étkezési filozófusok problémájának naiv megvalósítását mutatja be. Az philosopher osztály, amely a concurrency::agent tulajdonságokat örökli, lehetővé teszi, hogy minden filozófus függetlenül cselekedjen. A példa egy megosztott tömböt használ a concurrency::critical_section objektumokból, hogy minden philosopher objektum kizárólagos hozzáférést kapjon egy pár evőpálcikához.

A megvalósítás és az illusztráció összekapcsolásához az philosopher osztály egy filozófust jelöl. A int változók az egyes evőpálcikát jelölik. A critical_section tárgyak olyan tartókként szolgálnak, amelyeken a evőpálcikák pihennek. A run módszer a filozófus életét szimulálja. A think módszer a gondolkodást szimulálja, a eat módszer pedig az étkezést szimulálja.

Az philosopher objektum mindkét critical_section objektumot zárolja, hogy a szimuláció során eltávolítsa az evőpálcikákat a tartókból, mielőtt meghívja a eat metódust. A hívás eat után az philosopher objektum visszaadja az evőpálcikákat a tartókhoz az critical_section objektumok feloldott állapotba visszaállításával.

A pickup_chopsticks módszer bemutatja, holtpont fordulhat elő. Ha minden philosopher objektum hozzáfér az egyik zároláshoz, akkor egyetlen objektum sem philosopher folytathatja, mert a másik zárolást egy másik philosopher objektum vezérli.

példa

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

A kód összeállítása

Másolja ki a példakódot, és illessze be egy Visual Studio-projektbe, vagy illessze be egy elnevezett philosophers-deadlock.cpp fájlba, majd futtassa a következő parancsot egy Visual Studio parancssori ablakban.

cl.exe /EHsc philosophers-deadlock.cpp

[Felső]

Csatlakozás használata a Holtpont megelőzéséhez

Ez a szakasz bemutatja, hogyan használható üzenetpufferek és üzenetátadási függvények a holtpont esélyének kiküszöbölésére.

A példának a korábbihoz való kapcsolásához a philosopher osztály minden egyes critical_section objektumot lecserél, egy concurrency::unbounded_buffer objektum és egy join objektum használatával. Az join objektum egy arbiterként szolgál, amely a filozófusnak biztosítja a evőpálcikákat.

Ez a példa azért használja az unbounded_buffer osztályt, mert amikor egy cél üzenetet kap egy unbounded_buffer objektumtól, az üzenet el lesz távolítva az üzenetsorból. Ez lehetővé teszi, hogy egy unbounded_buffer üzenetet tartalmazó objektum jelezze, hogy az evőpálcika elérhető. Egy unbounded_buffer üzenet nélküli objektum azt jelzi, hogy a evőpálcika használatban van.

Ez a példa egy nem mohó join objektumot használ, mert egy nem mohó illesztés minden objektum számára csak akkor biztosít philosopher hozzáférést mindkét evőpálcához, ha mindkét unbounded_buffer objektum üzenetet tartalmaz. A kapzsi csatlakozás nem akadályozná meg a holtpontot, mert a mohó illesztés azonnal fogadja az üzeneteket, amint elérhetővé válnak. Holtpont akkor fordulhat elő, ha minden kapzsi join objektum megkapja az egyik üzenetet, de örökké várnak, amíg a másik elérhetővé válik.

A kapzsi és nem mohó illesztésekről, valamint a különböző üzenetpuffertípusok közötti különbségekről az Aszinkron üzenetblokkok című témakörben olvashat bővebben.

A holtpont megakadályozása ebben a példában

1. Távolítsa el a következő kódot a példából.

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

1. Módosítsa az _left és _right adattagok típusát a philosopher osztályban unbounded_buffer-ra.

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

1. Módosítsa a philosopher konstruktort úgy, hogy unbounded_buffer objektumokat vegyen fel paraméterként.

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. Módosítsa úgy a pickup_chopsticks metódust, hogy egy nem mohó join objektummal fogadjon üzeneteket mindkét evőpálcika üzenetpuffereiből.

// 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. Módosítsa úgy a putdown_chopsticks metódust, hogy felszabadítsa a evőpálcikákhoz való hozzáférést azáltal, hogy üzenetet küld a két evőpálcika üzenetpuffereinek.

// 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. Módosítsa a metódust run a metódus eredményeinek pickup_chopsticks tárolására és az eredményeknek a putdown_chopsticks metódusnak való átadására.

// 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. Módosítsa a chopsticks függvény változójának wmain deklarációját úgy, hogy az egy-egy üzenetet tartalmazó objektumtömb unbounded_buffer legyen.

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

Leírás

Az alábbiakban az a kész példa látható, amely nem mohó join objektumokat használ a holtpont kockázatának kiküszöbölésére.

példa

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

Ez a példa a következő kimenetet hozza létre.

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

A kód összeállítása

Másolja ki a példakódot, és illessze be egy Visual Studio-projektbe, vagy illessze be egy elnevezett philosophers-join.cpp fájlba, majd futtassa a következő parancsot egy Visual Studio parancssori ablakban.

cl.exe /EHsc philosophers-join.cpp

[Felső]

Lásd még

Egyidejűségi futtatókörnyezeti útmutatók
Aszinkron ügynökök könyvtára
Aszinkron ügynökök
Aszinkron üzenetblokkok
Üzenetátadási függvények
Szinkronizálási adatstruktúrák