Passo a passo: Usar join para evitar a deadlock

Artigo
02/25/2013

Este tópico usa o problema de jantar de filósofos para ilustrar como usar a classe de concurrency::join para evitar bloqueio a completa em seu aplicativo.Em um aplicativo de software, a deadlock ocorrer quando dois ou mais processos cada propriedade mutuamente um recurso e espera para que outro processo libere qualquer outro recurso.

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

Pré-requisitos

Ler os seguintes tópicos antes de iniciar esta explicação passo a passo:

Seções

Essa explicação passo a passo contém as seções a seguir:

O problema de jantar de filósofos
Uma implementação de Naïve
Usar join para evitar a deadlock

O problema de jantar de filósofos

O problema de jantar de filósofos ilustra como deadlock ocorre em um aplicativo.Nesse problema, cinco filósofos sentam-se em uma tabela redonda.Cada filósofo alterna entre o pensamento e comer.Cada filósofo deve compartilhar um hashi com o vizinho à esquerda e outro hashi com o vizinho à direita.A ilustração a seguir mostra esse layout.

O problema de filósofos jantar

Para comer, um filósofo deve conter dois hashis.Se cada filósofo contém apenas um hashi e está aguardando outro, então nenhum filósofo pode comer e todos morrem de fome.

Superior[]

Uma implementação de Naïve

O exemplo a seguir mostra uma implementação de naïve do problema de jantar de filósofos.A classe de philosopher , que deriva de concurrency::agent, permite que cada filósofo para atuar independente.O exemplo usa uma matriz de objetos compartilhado de concurrency::critical_section para dar a cada objeto de philosopher acesso exclusivo a um par de hashis.

Para relacionar a implementação para a ilustração, a classe de philosopher representa um filósofo.Uma variável de int representa cada hashi.Os objetos de critical_section servem como suporta em que os hashis descansam.O método de run simula a vida de filósofo.O método de think simula o ato de pensamento e o método de eat simula o ato de comer.

Um objeto de philosopher bloqueia os dois objetos de critical_section para simular a remoção de hashis de suporte antes que chama o método de eat .Após a chamada a eat, o objeto de philosopher retorna os hashis para suportar definindo os objetos de critical_section de volta para o estado desbloqueado.

O método de pickup_chopsticks ilustra onde a deadlock pode ocorrer.Se cada objeto de philosopher acessa a um dos bloqueios, então nenhum objeto de philosopher pode continuar porque o outro bloqueio é controlada por outro objeto de philosopher .

Exemplo

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 (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 em um arquivo denominado philosophers-deadlock.cpp e execute o seguinte comando em uma janela de prompt de comando do Visual Studio.

cl.exe /EHsc philosophers-deadlock.cpp

Superior[]

Usar join para evitar a deadlock

Esta seção mostra como usar buffers de mensagem e funções mensagem- passar para eliminar a possibilidade de bloqueio completa.

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

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

Este exemplo usa um objeto não ávido de join como um não ávido se associa cada fornece acesso ao objeto de philosopher a ambos os hashis somente quando os dois objetos de unbounded_buffer contém uma mensagem.Um ávido join não evitaria a deadlock como um ávido joins aceita mensagens para que se torna disponíveis.A deadlock pode ocorrer se todos os objetos ávidos de join recebem uma das mensagens mas de espera para sempre que o outro para se tornar disponíveis.

Para obter mais informações sobre ávido e não ávido de adição, e as diferenças entre vários tipos de buffer de mensagem, consulte Blocos assíncronas de mensagem.

Para evitar bloqueio a completa nesse exemplo

Remova o código de exemplo a seguir.

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

Altere o tipo dos membros de dados de _left e de _right da classe de 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 o construtor de philosopher para receber objetos de 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);
}

Modificar o método de pickup_chopsticks para usar um objeto não ávido de join para receber mensagens de buffers de mensagem para ambos os hashis.

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

Modificar o método de putdown_chopsticks para liberar o acesso a hashis enviando uma mensagem aos buffers de mensagem para ambos os hashis.

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

Modificar o método de run para armazenar os resultados do método de pickup_chopsticks e passar os resultados para o método de 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();
}

Altere a declaração de variável de chopsticks na função de wmain como uma matriz de objetos que unbounded_buffer cada mensagem de uma propriedade.

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

Exemplo

Descrição

O seguinte mostra o exemplo completo que usa join não ávido objetos para eliminar o risco de bloqueio completa.

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

Comentários

O exemplo produz a seguinte saída.

Compilando o código

Copie o código de exemplo e cole-o em um projeto do Visual Studio, ou cole em um arquivo denominado philosophers-join.cpp e execute o seguinte comando em uma janela de prompt de comando do Visual Studio.

cl.exe /EHsc philosophers-join.cpp

Superior[]