Procédure pas à pas : utilisation de la classe join pour empêcher l’interblocage

Cette rubrique utilise le problème des philosophes à manger pour illustrer comment utiliser la classe concurrency ::join pour empêcher l’interblocage dans votre application. Dans une application logicielle, un blocage se produit lorsque au moins deux processus comportent chacun une ressource et attendent mutuellement qu’un autre processus en libère une autre.

Le problème des philosophes à manger est un exemple spécifique de l’ensemble général de problèmes qui peuvent se produire lorsqu’un ensemble de ressources est partagé entre plusieurs processus simultanés.

Prérequis

Lisez les rubriques suivantes avant de commencer cette procédure pas à pas :

• Agents asynchrones

• Procédure pas à pas : création d’une application basée sur un agent

• Blocs de messages asynchrones

• Fonctions de passage de messages

• Structures de données de synchronisation

Sections

Cette procédure pas à pas contient les sections suivantes :

• Le problème des philosophes à manger

• Une implémentation naïve

• Utilisation de la jointure pour empêcher l’interblocage

Le problème des philosophes à manger

Le problème des philosophes à manger illustre la façon dont le blocage se produit dans une application. Dans ce problème, cinq philosophes siègent à une table ronde. Chaque philosophe alterne entre penser et manger. Chaque philosophe doit partager une baguette avec le voisin à gauche et une autre baguette avec le voisin à droite. L’illustration suivante montre cette disposition.

Pour manger, un philosophe doit tenir deux baguettes. Si chaque philosophe ne contient qu’une seule baguette et attend un autre, alors aucun philosophe ne peut manger et toutes les faims.

[Haut]

Une implémentation naïve

L’exemple suivant montre une implémentation naïve du problème des philosophes à manger. La philosopher classe, qui dérive de concurrency ::agent, permet à chaque philosophe d’agir indépendamment. L’exemple utilise un tableau partagé d’objets concurrency ::critical_section pour donner à chaque philosopher objet un accès exclusif à une paire de baguettes.

Pour lier l’implémentation à l’illustration, la philosopher classe représente un philosophe. Une int variable représente chaque baguette. Les critical_section objets servent de supports sur lesquels reposent les baguettes. La run méthode simule la vie du philosophe. La think méthode simule l’acte de pensée et la eat méthode simule l’acte de manger.

Un philosopher objet verrouille les deux critical_section objets pour simuler la suppression des baguettes des porteurs avant d’appeler la eat méthode. Après l’appel, eatl’objet philosopher renvoie les baguettes aux porteurs en définissant les critical_section objets sur l’état déverrouillé.

La pickup_chopsticks méthode illustre l’endroit où un blocage peut se produire. Si chaque philosopher objet accède à l’un des verrous, aucun objet ne philosopher peut continuer, car l’autre verrou est contrôlé par un autre philosopher objet.

Exemple

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

Compilation du code

Copiez l’exemple de code et collez-le dans un projet Visual Studio, ou collez-le dans un fichier nommé philosophers-deadlock.cpp , puis exécutez la commande suivante dans une fenêtre d’invite de commandes Visual Studio.

cl.exe /EHsc philosophers-deadlock.cpp

[Haut]

Utilisation de jointures pour prévenir les interblocages

Cette section montre comment utiliser des mémoires tampons de message et des fonctions de passage de messages pour éliminer le risque d’interblocage.

Pour lier cet exemple à celui précédent, la philosopher classe remplace chaque critical_section objet à l’aide d’un objet concurrency ::unbounded_buffer et d’un join objet. L’objet join sert d’arbitre qui fournit les baguettes au philosophe.

Cet exemple utilise la unbounded_buffer classe, car lorsqu’une cible reçoit un message d’un unbounded_buffer objet, le message est supprimé de la file d’attente de messages. Cela permet à un unbounded_buffer objet qui contient un message d’indiquer que la baguette est disponible. Un unbounded_buffer objet qui ne contient aucun message indique que la baguette est utilisée.

Cet exemple utilise un objet non gourmand, car une jointure non gourmande join donne à chaque philosopher objet l’accès aux deux baguettes uniquement lorsque les deux unbounded_buffer objets contiennent un message. Une jointure gourmande n’empêcherait pas l’interblocage, car une jointure gourmande accepte les messages dès qu’elles deviennent disponibles. L’interblocage peut se produire si tous les objets gourmands join reçoivent l’un des messages, mais attendent pour toujours que l’autre devienne disponible.

Pour plus d’informations sur les jointures gourmandes et non gourmandes et les différences entre les différents types de mémoire tampon de message, consultez Blocs de messages asynchrones.

Pour empêcher l’interblocage dans cet exemple

1. Supprimez le code suivant de l’exemple.

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

1. Remplacez le type des membres de données de _left_right la philosopher classe unbounded_bufferpar .

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

1. Modifiez le philosopher constructeur pour prendre unbounded_buffer des objets en tant que paramètres.

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. Modifiez la pickup_chopsticks méthode pour utiliser un objet non gourmand join pour recevoir des messages des tampons de messages pour les deux baguettes.

// 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. Modifiez la méthode pour libérer l’accès putdown_chopsticks aux baguettes en envoyant un message aux tampons de message pour les deux baguettes.

// 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. Modifiez la run méthode pour contenir les résultats de la pickup_chopsticks méthode et transmettre ces résultats à la putdown_chopsticks méthode.

// 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. Modifiez la déclaration de la chopsticks variable dans la wmain fonction pour qu’elle soit un tableau d’objets unbounded_buffer qui contiennent chacun un message.

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

Description

L’exemple suivant montre l’exemple terminé qui utilise des objets non gourmands join pour éliminer le risque d’interblocage.

Exemple

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

Cet exemple produit la sortie suivante.

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

Compilation du code

Copiez l’exemple de code et collez-le dans un projet Visual Studio, ou collez-le dans un fichier nommé philosophers-join.cpp , puis exécutez la commande suivante dans une fenêtre d’invite de commandes Visual Studio.

cl.exe /EHsc philosophes-join.cpp

[Haut]

Voir aussi

Procédures pas à pas relatives au runtime d’accès concurrentiel
Bibliothèque d’agents asynchrones
Agents asynchrones
Blocs de messages asynchrones
Fonctions de passage de messages
Structures de données de synchronisation