Procedura dettagliata: utilizzo della classe join per impedire un deadlock

Articolo
08/11/2011

In questo argomento viene utilizzato il problema dei filosofi a cena per illustrare come utilizzare la classe Concurrency::join per impedire un deadlock nell'applicazione. In un'applicazione software il deadlock si verifica quando due o più processi contengono ognuno una risorsa e attendono reciprocamente che l'altro processo rilasci l'altra risorsa.

Il problema dei filosofi a cena è un esempio specifico del set generale di problemi che si possono verificare quando un set di risorse è condiviso tra più processi simultanei.

Prerequisiti

Prima di iniziare questa procedura dettagliata, leggere gli argomenti seguenti:

Sezioni

In questa procedura dettagliata sono contenute le sezioni seguenti:

Problema dei filosofi a cena
Implementazione naïve
Utilizzo della classe join per impedire un deadlock

Problema dei filosofi a cena

Il problema dei filosofi a cena illustra come si verifica un deadlock in un'applicazione. In questo problema, cinque filosofi siedono a una tavola rotonda. I filosofi alternano momenti durante i quali meditare e momenti durante i quali mangiare. Ogni filosofo deve condividere un bastoncino con il vicino a sinistra e un altro bastoncino con il vicino a destra. Nella figura seguente viene illustrato questo schema.

Problema dei filosofi a cena

Per mangiare un filosofo deve avere due bastoncini. Se ogni filosofo ha un solo bastoncino e deve aspettare l'altro bastoncino, nessun filosofo potrà mangiare e tutti morirebbero di fame.

[vai all'inizio]

Implementazione naïve

Nell'esempio seguente viene illustrata un'implementazione naïve del problema dei filosofi a cena. La classe philosopher che deriva da Concurrency::agent consente a ogni filosofo di agire indipendentemente. Nell'esempio viene utilizzata una matrice condivisa di oggetti Concurrency::critical_section per concedere a ogni oggetto philosopher l'accesso esclusivo a una coppia di bastoncini.

Per correlare l'implementazione all'illustrazione, la classe philosopher rappresenta un solo filosofo. La variabile int rappresenta ogni bastoncino. Gli oggetti critical_section fungono da contenitori per i bastoncini. Il metodo run simula la vita del filosofo. Il metodo think simula l'atto di pensare e il metodo eat simula l'atto di mangiare.

Un oggetto philosopher blocca entrambi gli oggetti critical_section per simulare la rimozione dei bastoncini dai contenitori prima di chiamare il metodo eat. Dopo la chiamata a eat, l'oggetto philosopher restituisce i bastoncini ai contenitori impostando di nuovo gli oggetti critical_section sullo stato sbloccato.

Il metodo pickup_chopsticks illustra dove si può verificare il deadlock. Se ogni oggetto philosopher può accedere a uno dei blocchi, nessun oggetto philosopher potrà continuare poiché l'altro blocco viene controllato da un altro oggetto philosopher.

Esempio

Codice

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

Compilazione del codice

Copiare il codice di esempio e incollarlo in un progetto di Visual Studio o incollarlo in un file denominato philosophers-deadlock.cpp, quindi eseguire il comando seguente in una finestra del prompt dei comandi di Visual Studio 2010.

cl.exe /EHsc philosophers-deadlock.cpp

[vai all'inizio]

Utilizzo della classe join per impedire un deadlock

In questa sezione viene illustrato come utilizzare i buffer dei messaggi e le funzioni di passaggio dei messaggi per eliminare la possibilità di deadlock.

Per correlare questo esempio al precedente, la classe philosopher sostituisce ogni oggetto critical_section utilizzando un oggetto Concurrency::unbounded_buffer e un oggetto join. L'oggetto join funge da arbitro che fornisce i bastoncini al filosofo.

In questo esempio viene utilizzata la classe unbounded_buffer poiché quando una destinazione riceve un messaggio da un oggetto unbounded_buffer, il messaggio viene rimosso dalla coda di messaggi. In questo modo un oggetto unbounded_buffer che contiene un messaggio può indicare che è disponibile il bastoncino. Un oggetto unbounded_buffer che non contiene messaggi indica che il bastoncino è in uso.

In questo esempio viene utilizzato un oggetto join non-greedy poiché un join non-greedy concede a ogni oggetto philosopher l'accesso a entrambi i bastoncini solo quando entrambi gli oggetti unbounded_buffer contengono un messaggio. Un join greedy non impedirebbe un deadlock poiché un join greedy accetta i messaggi non appena diventano disponibili. Un deadlock può verificarsi se tutti gli oggetti join greedy ricevono uno dei messaggi ma attendono all'infinito che l'altro messaggio diventi disponibile.

Per ulteriori informazioni sui join greedy e non-greedy e le differenze tra i vari tipi di buffer dei messaggi, vedere Blocchi dei messaggi asincroni.

Per impedire un deadlock in questo esempio

Rimuovere dall'esempio il codice seguente.

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

Modificare il tipo dei membri dati _left e _right della classe philosopher con unbounded_buffer.

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

Modificare il costruttore philosopher per accettare gli oggetti unbounded_buffer come parametri.

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

Modificare il metodo pickup_chopsticks in modo da utilizzare un oggetto join non-greedy per ricevere i messaggi dai buffer dei messaggi per entrambi i bastoncini.

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

Modificare il metodo putdown_chopsticks per rilasciare l'accesso ai bastoncino inviando un messaggio ai buffer dei messaggi per entrambi i bastoncini.

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

Modificare il metodo run per contenere i risultati del metodo pickup_chopsticks e passarli al metodo 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();
}

Modificare la dichiarazione della variabile chopsticks nella funzione wmain per essere una matrice di oggetti unbounded_buffer contenente ognuno un messaggio.

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

Esempio

Descrizione

Di seguito viene illustrato l'esempio completato che utilizza oggetti join non-greedy per eliminare il rischio di deadlock.

Codice

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

Commenti

Questo esempio produce l'output che segue.

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

Compilazione del codice

Copiare il codice di esempio e incollarlo in un progetto di Visual Studio o incollarlo in un file denominato philosophers-join.cpp, quindi eseguire il comando seguente in una finestra del prompt dei comandi di Visual Studio 2010.

cl.exe /EHsc philosophers-join.cpp

[vai all'inizio]