Passo a passo: Usando o método join para evitar o deadlock

Este tópico usa o problema dos filósofos de jantar para ilustrar como usar a classe concurrency::join para evitar o bloqueio no seu aplicativo. Em um aplicativo de software, o impasse ocorre quando dois ou mais processos cada um detém um recurso e aguardam mutuamente que outro processo libere algum outro recurso.

O problema dos filósofos à mesa é um exemplo específico do conjunto amplo de problemas que podem ocorrer quando um conjunto de recursos é compartilhado entre múltiplos processos simultâneos.

Pré-requisitos

Leia os seguintes tópicos antes de começar este passo a passo:

Secções

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

O Problema dos Filósofos Gastronómicos
Uma aplicação ingénua
Usando a junção para evitar o impasse

O Problema dos Filósofos Gastronómicos

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

O Problema dos Filósofos Gastronómicos.

Para comer, um filósofo deve segurar dois pauzinhos. Se cada filósofo segura apenas um pauzinho e está esperando por outro, então nenhum filósofo pode comer e todos morrer de fome.

[Topo]

Uma aplicação ingénua

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

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

Um objeto philosopher bloqueia ambos os objetos critical_section para simular a remoção dos pauzinhos dos suportes antes de chamar o método eat. Após a chamada para eat, o objeto philosopher devolve os pauzinhos aos suportes, definindo os objetos critical_section ao estado desbloqueado.

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

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, em seguida, execute o seguinte comando em uma janela do prompt de comando do Visual Studio.

cl.exe /EHsc philosophers-deadlock.cpp

[Topo]

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 com o anterior, a philosopher classe substitui cada critical_section objeto usando um objeto concurrency::unbounded_buffer e um join objeto. O join objeto serve como árbitro que fornece os pauzinhos ao filósofo.

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

Este exemplo usa um objeto não ganancioso join porque uma junção não gananciosa dá a cada philosopher objeto acesso a ambos os pauzinhos somente quando ambos os unbounded_buffer objetos contêm uma mensagem. Uma adesão gananciosa não evitaria o impasse porque uma adesão gananciosa aceita mensagens assim que elas ficam disponíveis. O impasse pode ocorrer se todos os objetos gananciosos join receberem uma das mensagens, mas esperarem para sempre que a outra fique disponível.

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

Para evitar impasse neste exemplo

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];

Altere o tipo dos 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;

Modifique o philosopher construtor para tomar unbounded_buffer objetos 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);
}

Modifique o pickup_chopsticks método para usar um objeto não ganancioso join para receber mensagens dos buffers de mensagens para ambos os pauzinhos.

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

Modifique o método putdown_chopsticks para liberar o acesso aos pauzinhos enviando uma mensagem para os buffers de mensagem de ambos os pauzinhos.

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

Modifique o run método para manter os resultados do 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();
}

Modifique a declaração da variável chopsticks na função wmain como um array de objetos unbounded_buffer que cada um contenha 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

A seguir mostra o exemplo concluído que usa objetos não gananciosos join para eliminar o risco de impasse.

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 produz o seguinte resultado.

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, em seguida, execute o seguinte comando em uma janela do prompt de comando do Visual Studio.

cl.exe /EHsc philosophers-join.cpp

[Topo]

Ver também

Passo a passo do Concurrency Runtime
Biblioteca de agentes assíncronos
Agentes assíncronos
Blocos de mensagens assíncronas
Funções de passagem de mensagens
Estruturas de dados de sincronização

Feedback

Esta página foi útil?

Last updated on 2025-11-07

Partilhar via

Passo a passo: Usando o método join para evitar o deadlock

Pré-requisitos

Secções

O Problema dos Filósofos Gastronómicos

Uma aplicação ingénua

Exemplo

Compilando o código

Usar join para evitar deadlock

Para evitar impasse neste exemplo

Descrição

Exemplo

Compilando o código

Ver também

Feedback

Recursos adicionais