Tutorial: Usar la clase join para evitar un interbloqueo

Artículo
08/10/2011

En este tema se usa el problema de la cena de los filósofos para ilustrar cómo se usa la clase Concurrency::join para evitar el interbloqueo en la aplicación. En una aplicación de software, el interbloqueo se produce cuando dos o más procesos mantienen un recurso y esperan mutuamente a que el otro proceso libere algún otro recurso.

El problema de la cena de los filósofos es un ejemplo concreto del conjunto general de problemas que se pueden producir cuando se comparte un conjunto de recursos entre varios procesos simultáneos.

Requisitos previos

Lea los siguientes temas antes de iniciar este tutorial:

Secciones

Este tutorial contiene las siguientes secciones:

El problema de la cena de los filósofos
Una implementación sencilla
Usar una combinación para evitar el interbloqueo

El problema de la cena de los filósofos

El problema de la cena de los filósofos ilustra cómo se produce el interbloqueo en una aplicación. En este problema, cinco filósofos están sentados a una mesa redonda. Cada filósofo alterna entre pensar y comer. Cada filósofo debe compartir un palillo con el vecino sentado a la izquierda y otro palillo con el vecino sentado a la derecha. En la siguiente ilustración se muestra este diseño.

El problema de la cena de los filósofos

Para comer, un filósofo debe tener en la mano dos palillos. Si cada filósofo tiene un solo palillo y está esperando a que le den otro, ninguno puede comer y todos se quedan sin comer.

[Ir al principio]

Una implementación sencilla

En el siguiente ejemplo se muestra una implementación sencilla del problema de la cena de los filósofos. La clase philosopher, que se deriva de Concurrency::agent, permite que cada filósofo actúe de forma independiente. En el ejemplo se usa una matriz compartida de objetos Concurrency::critical_section para dar acceso exclusivo a cada objeto philosopher a un par de palillos.

Para relacionar la implementación con la ilustración, la clase philosopher representa a un filósofo. Una variable int representa cada palillo. Los objetos critical_section sirven como contenedores en los que se encuentran los palillos. El método run simula la vida del filósofo. El método think simula el acto de pensar y el método eat simula el acto de comer.

Un objeto philosopher bloquea ambos objetos critical_section para simular la retirada de los palillos de los contenedores antes de llamar al método eat. Después de la llamada a eat, el objeto philosopher devuelve los palillos a los contenedores, y los objetos critical_section vuelven a establecerse en el estado desbloqueado.

El método pickup_chopsticks ilustra dónde se puede producir el interbloqueo. Si cada objeto philosopher obtiene acceso a uno de los bloqueos, ningún objeto philosopher puede continuar porque otro objeto philosopher controla el otro bloqueo.

Ejemplo

Código

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

Compilar el código

Copie el código de ejemplo y péguelo en un proyecto de Visual Studio o péguelo en un archivo denominado philosophers-deadlock.cpp y, a continuación, ejecute el siguiente comando en una ventana de símbolo del sistema de Visual Studio 2010.

cl.exe /EHsc philosophers-deadlock.cpp

[Ir al principio]

Usar una combinación para evitar el interbloqueo

En esta sección se muestra cómo usar los búferes de mensajes y las funciones de paso de mensajes para eliminar la oportunidad de que se produzcan interbloqueos.

Para relacionar este ejemplo con el anterior, la clase philosopher reemplaza cada objeto critical_section con un objeto Concurrency::unbounded_buffer y un objeto join. El objeto join sirve como un árbitro que proporciona los palillos al filósofo.

En este ejemplo se usa la clase unbounded_buffer porque cuando un destino recibe un mensaje de un objeto unbounded_buffer, el mensaje se quita de la cola de mensajes. Esto permite que un objeto unbounded_buffer contenga un mensaje para indicar que el palillo está disponible. Un objeto unbounded_buffer que no contiene ningún mensaje indica que el palillo se está usando.

Este ejemplo usa un objeto join no expansivo porque una combinación no expansiva solo da cada acceso a ambos palillos al objeto philosopher cuando ambos objetos unbounded_buffer contienen un mensaje. Una combinación expansiva no evitaría el interbloqueo porque aceptaría los mensajes en cuanto estuvieran disponibles. Se puede producir el interbloqueo si todos los objetos join expansivos reciben uno de los mensajes pero esperan para siempre a que el otro esté disponible.

Para obtener más información sobre las combinaciones expansivas y no expansivas, y las diferencias entre los diversos tipos de búfer de mensajes, vea Bloques de mensajes asincrónicos.

Para evitar el interbloqueo en este ejemplo

Quite el siguiente código del ejemplo.

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

Cambie el tipo de los miembros de datos _right y _left de la clase philosopher a unbounded_buffer.

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

Modifique el constructor philosopher de forma que tome los objetos unbounded_buffer como parámetros.

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

Modifique el método pickup_chopsticks para usar un objeto join no expansivo para recibir los mensajes de los búferes de mensajes para ambos palillos.

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

Modifique el método putdown_chopsticks para liberar el acceso a los palillos enviando un mensaje a los búferes de mensajes para ambos palillos.

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

Modifique el método run de forma que retenga los resultados del método pickup_chopsticks y pase esos resultados al método 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();
}

Modifique la declaración de la variable chopsticks en la función wmain para que sea una matriz de objetos unbounded_buffer, cada uno de los cuales contiene un mensaje.

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

Ejemplo

Descripción

A continuación se muestra el ejemplo completo que usa los objetos join no expansivos para eliminar el riesgo de interbloqueo.

Código

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

Comentarios

Este ejemplo produce el siguiente resultado.

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

Compilar el código

Copie el código de ejemplo y péguelo en un proyecto de Visual Studio o péguelo en un archivo denominado philosophers-join.cpp y, a continuación, ejecute el siguiente comando en una ventana de símbolo del sistema de Visual Studio 2010.

cl.exe /EHsc philosophers-join.cpp

[Ir al principio]