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

Article
08/10/2011

Cette rubrique utilise le problème du dîner de philosophes pour illustrer comment utiliser la classe Concurrency::join pour empêcher tout interblocage dans votre application. Dans une application, l'interblocage se produit lorsque plusieurs processus détiennent chacun une ressource et attendent mutuellement qu'un autre processus libère une autre ressource.

Le problème du dîner de philosophes est un exemple spécifique de l'ensemble général de problèmes qui peuvent se produire lorsqu'un jeu de ressources est partagé par plusieurs processus simultanés.

Composants requis

Lisez les rubriques suivantes avant de démarrer cette procédure pas-à-pas :

Sections

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

Le problème du dîner de philosophes
Une implémentation naïve
Utilisation de la jointure pour empêcher l'interblocage

Le problème du dîner de philosophes

Le problème du dîner de philosophes illustre comment l'interblocage se produit dans une application. Dans ce problème, cinq philosophes sont assis à une table ronde. Chaque philosophe pense et mange de manière alternée. Chaque philosophe doit partager une baguette avec son voisin de gauche et une autre baguette avec son voisin de droite. Voici une illustration.

Problème Dîner des philosophes

Pour manger, un philosophe doit tenir deux baguettes. Si chaque philosophe tient une seule baguette et en attend une autre, aucun philosophe ne peut manger et tous meurent de faim.

[retour en haut]

Une implémentation naïve

L'exemple suivant illustre une implémentation naïve du problème du dîner de philosophes. La classe philosopher, 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 accorder à chaque objet philosopher un accès exclusif à une paire de baguettes.

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

Un objet philosopher verrouille les deux objets critical_section pour simuler la suppression des baguettes des supports avant d'appeler la méthode eat. Après l'appel à eat, l'objet philosopher repose les baguettes sur les supports en replaçant les objets critical_section à l'état déverrouillé.

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

Exemple

Code

// 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 (philosophers.begin(), philosophers.end(), [](philosopher& p) {
      p.start();
   });

   // Wait for each philosopher to finish and print his name and the number
   // of times he has eaten.
   for_each (philosophers.begin(), philosophers.end(), [](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 2010.

cl.exe /EHsc philosophers-deadlock.cpp

[retour en haut]

Utilisation de la jointure pour empêcher l'interblocage

Cette section indique comment utiliser des tampons de messages et des fonctions de passage de messages pour éliminer tout risque d'interblocage.

Pour comparer cet exemple au précédent, la classe philosopher remplace chaque objet critical_section à l'aide d'un objet Concurrency::unbounded_buffer et d'un objet join. L'objet join fait office d'arbitre qui fournit les baguettes au philosophe.

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

Cet exemple utilise un objet join non gourmand car une jointure non gourmande accorde à chaque objet philosopher un accès aux deux baguettes uniquement lorsque les deux objets unbounded_buffer contiennent un message. Une jointure gourmande n'empêcherait pas l'interblocage car elle accepte les messages dès qu'ils sont disponibles. L'interblocage peut se produire si tous les objets join gourmands reçoivent l'un des messages mais attendent indéfiniment que l'autre soit disponible.

Pour plus d'informations sur les jointures gourmandes et non gourmandes et sur les différences entre les différents types de tampons de messages, consultez Blocs de messages asynchrones.

Pour empêcher l'interblocage dans cet exemple

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

Modifiez le type des membres de données _right et _left de la classe philosopher en unbounded_buffer.

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

Modifiez le constructeur philosopher de façon à prendre des objets unbounded_buffer comme 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);
}

Modifiez la méthode pickup_chopsticks de façon à utiliser un objet join non gourmand pour recevoir des messages en provenance 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);
}

Modifiez la méthode putdown_chopsticks de façon à libérer l'accès aux baguettes en envoyant un message aux tampons de messages 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);
}

Modifiez la méthode run de façon à stocker les résultats de la méthode pickup_chopsticks et à passer ces résultats à la méthode 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();
}

Modifiez la déclaration de la variable chopsticks dans la fonction wmain de sorte qu'elle soit un tableau d'objets unbounded_buffer contenant 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 (chopsticks.begin(), chopsticks.end(), 
   [](unbounded_buffer<chopstick>& c) {
      send(c, 1);
});

Exemple

Description

Voici l'exemple complet qui utilise des objets join non gourmands pour éliminer le risque d'interblocage.

Code

// 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 (chopsticks.begin(), chopsticks.end(), 
      [](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 (philosophers.begin(), philosophers.end(), [](philosopher& p) {
      p.start();
   });

   // Wait for each philosopher to finish and print his name and the number
   // of times he has eaten.
   for_each (philosophers.begin(), philosophers.end(), [](philosopher& p) {
      agent::wait(&p);
      wcout << p.name() << L" ate " << p.times_eaten() << L" times." << endl;
   });
}

Commentaires

Cet exemple génère 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 2010.

cl.exe /EHsc philosophers-join.cpp

[retour en haut]