Procedura dettagliata: Uso della classe join per impedire un deadlock

Questo argomento usa il problema dei filosofi di pranzo per illustrare come usare la classe concurrency::join per evitare deadlock nell'applicazione. In un'applicazione software si verifica un deadlock quando due o più processi bloccano ognuno una risorsa e attendono entrambi che un altro processo rilasci altre risorse.

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

Prerequisiti

Leggere gli argomenti seguenti prima di iniziare questa procedura dettagliata:

• Agenti asincroni

• Procedura dettagliata: creazione di un'applicazione basata sugli agenti

• Blocchi dei messaggi asincroni

• Funzioni di passaggio dei messaggi

• Strutture di dati di sincronizzazione

Sezioni

Questa procedura dettagliata contiene le sezioni seguenti:

• Il problema dei filosofi da pranzo

• Implementazione ingenua

• Uso di join per impedire deadlock

Il problema dei filosofi da pranzo

Il problema dei filosofi del pranzo illustra come si verifica un deadlock in un'applicazione. In questo problema, cinque filosofi siedono a un tavolo rotondo. Ogni filosofo alterna il pensiero e il mangiare. Ogni filosofo deve condividere una bacchetta con il vicino a sinistra e un'altra bacchetta con il vicino a destra. La figura seguente mostra questo layout.

Per mangiare, un filosofo deve contenere due bacchette. Se ogni filosofo tiene solo una bacchetta e aspetta un'altra, allora nessun filosofo può mangiare e tutti affamati.

[Torna all'inizio]

Implementazione ingenua

L'esempio seguente mostra un'implementazione ingenua del problema dei filosofi della ristorazione. La philosopher classe, che deriva da concurrency::agent, consente a ogni filosofo di agire in modo indipendente. Nell'esempio viene usata una matrice condivisa di oggetti concurrency::critical_section per concedere a ogni philosopher oggetto l'accesso esclusivo a una coppia di bacchette.

Per correlare l'implementazione all'illustrazione, la philosopher classe rappresenta un filosofo. Una int variabile rappresenta ogni levetta. Gli critical_section oggetti fungono da segnaposto su cui riposa le bacchette. Il run metodo simula la vita del filosofo. Il think metodo simula l'atto di pensare e il eat metodo simula l'atto di mangiare.

Un philosopher oggetto blocca entrambi critical_section gli oggetti per simulare la rimozione delle bacchette dai titolari prima di chiamare il eat metodo . Dopo la chiamata a eat, l'oggetto philosopher restituisce le bacchette ai titolari impostando nuovamente gli critical_section oggetti sullo stato sbloccato.

Il pickup_chopsticks metodo illustra dove può verificarsi il deadlock. Se ogni philosopher oggetto ottiene l'accesso a uno dei blocchi, nessun philosopher oggetto può continuare perché l'altro blocco è controllato da un altro philosopher oggetto.

Esempio

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

Compilazione del codice

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

cl.exe /EHsc philosophers-deadlock.cpp

[Torna all'inizio]

Uso di join per evitare il deadlock

Questa sezione illustra come usare i buffer dei messaggi e le funzioni di passaggio dei messaggi per eliminare la probabilità di deadlock.

Per correlare questo esempio a quello precedente, la philosopher classe sostituisce ogni critical_section oggetto usando un oggetto concurrency::unbounded_buffer e un join oggetto . L'oggetto join funge da arbitro che fornisce le bacchette al filosofo.

In questo esempio viene utilizzata la unbounded_buffer classe perché quando una destinazione riceve un messaggio da un unbounded_buffer oggetto , il messaggio viene rimosso dalla coda di messaggi. Ciò consente a un unbounded_buffer oggetto che contiene un messaggio di indicare che la levetta è disponibile. Un unbounded_buffer oggetto che non contiene alcun messaggio indica che viene usata la levetta.

In questo esempio viene utilizzato un oggetto non greedy join perché un join non greedy consente a ogni philosopher oggetto di accedere a entrambe le bacchette solo quando entrambi unbounded_buffer gli oggetti contengono un messaggio. Un join greedy non impedisce il deadlock perché un join greedy accetta i messaggi non appena diventano disponibili. Il deadlock può verificarsi se tutti gli oggetti greedy join ricevono uno dei messaggi, ma attendere per sempre che l'altro diventi disponibile.

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

Per evitare deadlock in questo esempio

1. Rimuovere il codice seguente dall'esempio.

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

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

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

1. Modificare il philosopher costruttore per accettare unbounded_buffer gli oggetti 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);
}

1. Modificare il pickup_chopsticks metodo per usare un oggetto non greedy join per ricevere messaggi dai buffer dei messaggi per entrambe le bacchette.

// 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. Modificare il putdown_chopsticks metodo per rilasciare l'accesso alle bacchette inviando un messaggio ai buffer dei messaggi per entrambe le bacchette.

// 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. Modificare il run metodo per contenere i risultati del pickup_chopsticks metodo e passare tali risultati al putdown_chopsticks metodo .

// 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. Modificare la dichiarazione della chopsticks variabile nella wmain funzione in modo che sia una matrice di unbounded_buffer oggetti che contengono ogni 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 (begin(chopsticks), end(chopsticks), 
   [](unbounded_buffer<chopstick>& c) {
      send(c, 1);
});

Descrizione

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

Esempio

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

Questo esempio produce il seguente output:

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 oppure incollarlo in un file denominato philosophers-join.cpp e quindi eseguire il comando seguente in una finestra del prompt dei comandi di Visual Studio.

cl.exe /EHsc philosophers-join.cpp

[Torna all'inizio]

Vedi anche

Procedure dettagliate del runtime di concorrenza
Libreria di agenti asincroni
Agenti asincroni
Blocchi dei messaggi asincroni
Funzioni di passaggio dei messaggi
Strutture di dati di sincronizzazione