Instruções passo a passo: usando join para Evitar Deadlock

Este tópico usa o problema do jantar dos filósofos para ilustrar como usar a classe concurrency::join para evitar o deadlock em seu aplicativo. Em um aplicativo de software, o deadlock ocorre quando cada um dos dois ou mais processos mantiver um recurso e mutuamente aguardar até que outro processo libere algum outro recurso.

O problema do jantar dos filósofos é um exemplo específico do conjunto geral de problemas que podem ocorrer quando um conjunto de recursos é compartilhado entre vários processos simultâneos.

Pré-requisitos

Leia os seguintes tópicos antes de iniciar este passo a passo:

• Agentes assíncronos

• Instruções passo a passo: criando um aplicativo com base no agente

• Blocos de mensagens assíncronos

• Funções de transmissão de mensagem

• Estruturas de dados de sincronização

Seções

Este passo a passo contém as seguintes seções:

• O problema dos filósofos gastronômicos

• Uma implementação ingênua

• Usar join para evitar deadlock

O problema dos filósofos gastronômicos

O problema do jantar dos filósofos ilustra como o deadlock ocorre em um aplicativo. Neste problema, cinco filósofos sentam-se em uma mesa redonda. Todos os filósofos alternam entre pensar e comer. Todo filósofo deve compartilhar um palitinho com o vizinho à esquerda e outro palitinho com o vizinho à direita. A ilustração a seguir mostra esse layout.

Para comer, um filósofo deve segurar dois palitinhos. Se cada filósofo tiver apenas um palitinho e estiver esperando por outro, então nenhum filósofo poderá comer e todos ficarão com fome.

[Parte superior]

Uma implementação ingênua

O exemplo a seguir mostra uma implementação ingênua do problema do jantar dos filósofos. A classe philosopher, que deriva de concurrency::agent, permite que cada filósofo aja de modo independente. O exemplo usa uma matriz compartilhada de objetos concurrency::critical_section para dar a cada objeto philosopher acesso exclusivo a um par de palitinhos.

Para relacionar a implementação à ilustração, a classe philosopher representa um filósofo. Uma variável int representa cada palitinho. Os objetos critical_section servem como suportes nos quais os palitinhos ficam. O método run simula a vida do filósofo. O método think simula o ato de pensar e o método eat simula o ato de comer.

Um objeto philosopher bloqueia ambos os objetos critical_section para simular a remoção dos palitinhos dos filósofos antes de chamar o método eat. Após a chamada a eat, o objeto philosopher retorna os palitinhos para os filósofos definindo os objetos critical_section de volta para o estado desbloqueado.

O método pickup_chopsticks ilustra onde o deadlock pode ocorrer. Se cada objeto philosopher obtiver acesso a um dos bloqueios, nenhum objeto philosopher poderá continuar porque o outro bloqueio é controlado por outro objeto philosopher.

Exemplo

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

Compilando o código

Copie o código de exemplo e cole-o em um projeto do Visual Studio, ou cole-o em um arquivo chamado philosophers-deadlock.cpp e execute o comando a seguir em uma janela do Prompt de comando do Visual Studio.

cl.exe /EHsc philosophers-deadlock.cpp

[Parte superior]

Usar join para evitar deadlock

Esta seção mostra como usar buffers de mensagens e funções de passagem de mensagens para eliminar a chance de deadlock.

Para relacionar este exemplo ao anterior, a classe philosopher substitui cada objeto critical_section usando um objeto concurrency::unbounded_buffer e um objeto join. O objeto join serve como um árbitro que fornece os palitinhos para o filósofo.

Este exemplo usa a classe unbounded_buffer porque quando um destino recebe uma mensagem de um objeto unbounded_buffer, a mensagem é removida da fila de mensagens. Isso permite que um objeto unbounded_buffer que contém uma mensagem indique que o palitinho está disponível. Um objeto unbounded_buffer que não contém nenhuma mensagem indica que o palitinho está sendo usado.

Este exemplo usa um objeto join não greedy porque uma junção não greedy dá a cada objeto philosopher acesso a ambos os palitinhos somente quando ambos os objetos unbounded_buffer contêm uma mensagem. Uma junção greedy não evitaria o deadlock porque uma junção greedy aceita mensagens assim que elas se tornam disponíveis. O deadlock poderá ocorrer se todos os objetos join greedy receberem uma das mensagens, mas esperarem para sempre que o outro fique disponível.

Para obter mais informações sobre junções greedy e não greedy e as diferenças entre os vários tipos de buffer de mensagens, confira Blocos de mensagens assíncronos.

Para evitar deadlock neste exemplo

1. Remova o código a seguir do exemplo.

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

1. Altere o tipo e os membros de dados _left e _right da classe philosopher para unbounded_buffer.

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

1. Modifique o construtor philosopher para usar objetos unbounded_buffer como seus 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);
}

1. Modifique o método pickup_chopsticks para usar um objeto join não greedy para receber mensagens dos buffers de mensagem para ambos os palitinhos.

// 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. Modifique o método putdown_chopsticks para liberar o acesso aos palitinhos enviando uma mensagem para os buffers de mensagem para ambos os palitinhos.

// 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. Modifique o método run para manter os resultados do método pickup_chopsticks e passar esses resultados para o 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();
}

1. Modifique a declaração da variável chopsticks na função wmain para ser uma matriz de objetos unbounded_buffer em que cada um contém uma mensagem.

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

Descrição

Abaixo é possível ver o exemplo concluído que usa objetos join não greedy para eliminar o risco de deadlock.

Exemplo

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

Este exemplo gerencia a seguinte saída.

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

Compilando o código

Copie o código de exemplo e cole-o em um projeto do Visual Studio, ou cole-o em um arquivo chamado philosophers-join.cpp e execute o comando a seguir em uma janela do Prompt de comando do Visual Studio.

cl.exe /EHsc philosophers-join.cpp

[Parte superior]

Confira também

Instruções passo a passo do runtime de simultaneidade
Biblioteca de agentes assíncronos
Agentes assíncronos
Blocos de mensagens assíncronos
Funções de transmissão de mensagem
Estruturas de dados de sincronização