Demonstra Passo a passo: Usando a associação para evitar o Deadlock

Este tópico usa o problema de filósofos jantar para ilustrar como usar o Concurrency::join classe para evitar o bloqueio em seu aplicativo. Em um aplicativo de software, deadlock ocorre quando dois ou mais processos que cada mantêm um recurso e mutuamente esperar por outro processo liberar algum outro recurso.

O problema de filósofos de jantar é 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 tópicos a seguir antes de começar este passo a passo:

• Agentes assíncronos

• Demonstra Passo a passo: Criando um aplicativo baseado em agente

• Blocos de mensagens assíncronas

• Funções de transmissão de mensagens

• Estruturas de dados de sincronização

Seções

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

• O problema do jantar dos filósofos

• Uma implementação simples

• Usando a associação para evitar o Deadlock

O problema do jantar dos filósofos

O problema de filósofos jantar ilustra como o deadlock ocorre em um aplicativo. Neste problema, cinco filósofos sentar-se de uma mesa redonda. Cada filósofo alterna entre alimentares e pensando. Cada filósofo deve compartilhar um chopstick com o vizinho para a esquerda e outra chopstick com o vizinho à direita. A ilustração a seguir mostra esse layout.

Para comer, um filósofo deverá manter dois Pauzinhos de japoneses. Se cada filósofo mantém apenas um chopstick e está aguardando a outra, em seguida, nenhum filósofo pode comer e enfraquecer por todos.

go to top

Uma implementação simples

O exemplo a seguir mostra uma implementação simples do problema filósofos jantar. O philosopher classe, que é derivada de Concurrency::agent, permite que cada filósofo atuar de forma independente. O exemplo usa um conjunto compartilhado de Concurrency::critical_section objetos para dar a cada philosopher acesso exclusivo do objeto a um par de Pauzinhos japoneses.

Para relacionar a implementação para ilustração, o philosopher classe representa um filósofo. Um int variável representa cada chopstick. O critical_section objetos servem como proprietários na qual o resto do Pauzinhos japoneses. O run método simula a vida útil do filósofo. O think método simula o ato de pensamento e o eat método simula o ato de comer.

A philosopher objeto bloqueia ambos critical_section objetos simular a remoção de Pauzinhos de japoneses, dos proprietários de antes que ele chama o eat método. Após a chamada para eat, o philosopher retorna os Pauzinhos japoneses para os proprietários, definindo a critical_section objetos de volta ao estado desbloqueado.

O pickup_chopsticks método ilustra onde o deadlock pode ocorrer. Se cada philosopher objeto obtém acesso a um dos bloqueios, e não philosopher objeto pode continuar porque o outro bloqueio é controlado por outra philosopher objeto.

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

Compilando o código

Copie o código de exemplo e colá-lo em um Visual Studio do projeto, ou colá-lo em um arquivo que é chamado filósofos deadlock.cpp e, em seguida, execute o seguinte comando um Visual Studio 2010 janela do Prompt de comando.

cl.exe /EHsc philosophers-deadlock.cpp

go to top

Usando a associação para evitar o Deadlock

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

Para relacionar Este exemplo para o anterior, o philosopher classe substitui cada critical_section o objeto usando um Concurrency::unbounded_buffer objeto e um join objeto. O join objeto serve como um arbitrador que fornece as Pauzinhos japoneses filósofo.

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

Este exemplo usa um não greedy join porque uma associação não greedy dá a cada philosopher acesso a ambos os Pauzinhos japoneses de objeto somente quando ambos unbounded_buffer objetos contêm uma mensagem. Uma associação greedy não impediria que o bloqueio porque uma associação greedy aceita mensagens assim que forem disponibilizados. Deadlock pode ocorrer se todas as greedy join objetos receber uma das mensagens, mas esperar para sempre para o outro se torne disponível.

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

Para evitar o bloqueio neste exemplo

1. Remova o seguinte código do exemplo.

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

2. Alterar o tipo da _left e _right membros de dados do philosopher classe unbounded_buffer.

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

3. Modificar o philosopher o construtor para tirar unbounded_buffer objetos 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);
   }
   

4. Modificar o pickup_chopsticks método para usar um não greedy join o objeto para receber mensagens dos buffers de mensagem para os dois Pauzinhos japoneses.

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

5. Modificar o putdown_chopsticks método para liberar o acesso aos Pauzinhos de japoneses, enviando uma mensagem para os buffers de mensagem para os dois Pauzinhos japoneses.

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

6. Modificar o run método para armazenar os resultados da pickup_chopsticks método e passar esses resultados para o putdown_chopsticks método.

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

7. Modificar a declaração da chopsticks variável na wmain a função de ser uma matriz de unbounded_buffer os objetos que cada mantenha 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 (chopsticks.begin(), chopsticks.end(), 
      [](unbounded_buffer<chopstick>& c) {
         send(c, 1);
   });
   

Exemplo

Descrição

Veja a seguir o exemplo completo que usa não greedy join objetos para eliminar o risco de deadlock.

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

Comentários

O exemplo produz 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 colá-lo em um Visual Studio do projeto, ou colá-lo em um arquivo que é chamado filósofos join.cpp e, em seguida, execute o seguinte comando um Visual Studio 2010 janela do Prompt de comando.

cl.exe /EHsc philosophers-join.cpp

go to top

Consulte também

Conceitos

Biblioteca de agentes assíncronos

Agentes assíncronos

Blocos de mensagens assíncronas

Funções de transmissão de mensagens

Estruturas de dados de sincronização

Outros recursos

Asynchronous Agents How-to and Walkthrough Topics