Dela via

Genomgång: Använda join för att förhindra blockering

Det här avsnittet använder problemet med ätande filosofer för att illustrera hur du använder concurrency::join-klassen för att förhindra en deadlock i din applikation. I ett program uppstår dödläge när två eller flera processer var och en innehåller en resurs och ömsesidigt väntar på att en annan process ska släppa någon annan resurs.

Problemet med matfilosofer är ett specifikt exempel på den allmänna uppsättning problem som kan uppstå när en uppsättning resurser delas mellan flera samtidiga processer.

Förutsättningar

Läs följande avsnitt innan du påbörjar den här genomgången:

Sektioner

Den här genomgången innehåller följande avsnitt:

Problemet med matfilosofer

Problemet med matfilosofer illustrerar hur ett dödläge uppstår i ett program. I det här problemet sitter fem filosofer vid ett runt bord. Varje filosof växlar mellan att tänka och äta. Varje filosof måste dela en ätpinnar med grannen till vänster och en annan ätpinnar med grannen till höger. Följande bild visar den här layouten.

Problemet med matfilosofer.

För att äta måste en filosof hålla två ätpinnar. Om varje filosof bara har en ätpinne och väntar på en annan, kan ingen filosof äta och alla kommer att svälta.

[Topp]

En naiv implementering

I följande exempel visas en naiv implementering av problemet med matfilosofer. Klassen philosopher , som härleds från samtidighet::agent, gör det möjligt för varje filosof att agera självständigt. I exemplet används en delad array av concurrency::critical_section-objekt för att ge varje philosopher-objekt exklusiv åtkomst till ett par ätpinnar.

För att relatera implementeringen till bilden philosopher representerar klassen en filosof. En int variabel representerar varje ätpinne. Föremålen critical_section fungerar som hållare som ätpinnarna vilar på. Metoden run simulerar filosofens liv. Metoden think simulerar tänkandet och metoden eat simulerar ätandet.

Ett philosopher objekt låser båda critical_section objekten för att simulera borttagningen av ätpinnarna från hållarna innan metoden anropas eat . Efter anropet till eat returnerar objektet philosopher ätpinnarna till hållarna genom att ställa in objekten critical_section tillbaka till det olåsta tillståndet.

Metoden pickup_chopsticks visar var dödläge kan uppstå. Om varje philosopher objekt får åtkomst till ett av låsen kan inget philosopher objekt fortsätta eftersom det andra låset styrs av ett annat philosopher objekt.

Exempel

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

Kompilera koden

Kopiera exempelkoden och klistra in den i ett Visual Studio-projekt, eller klistra in den i en fil med namnet philosophers-deadlock.cpp och kör sedan följande kommando i ett Visual Studio-kommandotolkfönster.

cl.exe /EHsc philosophers-deadlock.cpp

[Topp]

Använda "join" för att förhindra dödläge

Det här avsnittet visar hur du använder meddelandebuffertar och funktioner för meddelandeöverföring för att eliminera risken för dödläge.

För att koppla detta exempel till det tidigare exemplet, ersätter klassen philosopher varje critical_section-objekt genom att använda ett concurrency::unbounded_buffer objekt och ett -objekt. Objektet join fungerar som en skiljedomare som tillhandahåller ätpinnarna till filosofen.

I det här unbounded_buffer exemplet används klassen eftersom meddelandet tas bort från meddelandekön när ett mål tar emot ett meddelande från ett unbounded_buffer objekt. På så sätt kan ett unbounded_buffer objekt som innehåller ett meddelande indikera att ätpinnarna är tillgängliga. Ett unbounded_buffer objekt som inte innehåller något meddelande anger att ätpinnar används.

I det här exemplet används ett icke-girigt join objekt eftersom en icke-girig koppling ger varje philosopher objekt åtkomst till båda ätpinnarna endast när båda unbounded_buffer objekten innehåller ett meddelande. En girig anslutning skulle inte förhindra dödläge eftersom en girig anslutning accepterar meddelanden så snart de blir tillgängliga. Dödläge kan inträffa om alla giriga join objekt tar emot ett av meddelandena men väntar för evigt på att det andra ska bli tillgängligt.

Mer information om giriga och icke-giriga kopplingar och skillnaderna mellan de olika typerna av meddelandebuffertar finns i Asynkrona meddelandeblock.

Förhindra dödläge i det här exemplet

  1. Ta bort följande kod från exemplet.
// A shared array of critical sections. Each critical section 
// guards access to a single chopstick.
critical_section locks[philosopher_count];
  1. Ändra typen på datamedlemmarna _left och _right i philosopher-klassen till unbounded_buffer.
// Message buffer for the left chopstick.
unbounded_buffer<chopstick>& _left;
// Message buffer for the right chopstick.
unbounded_buffer<chopstick>& _right;
  1. Ändra philosopher konstruktorn så att den tar unbounded_buffer objekt som dess parametrar.
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. Ändra pickup_chopsticks-metoden så att den använder ett ej girigt join-objekt för att ta emot meddelanden från meddelandebuffertarna för båda ätpinnarna.
// 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. putdown_chopsticks Ändra metoden för att frigöra åtkomst till ätpinnarna genom att skicka ett meddelande till meddelandebuffertarna för båda ätpinnarna.
// 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. run Ändra metoden för att lagra resultatet av pickup_chopsticks metoden och skicka dessa resultat till putdown_chopsticks metoden.
// 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. Ändra deklarationen av variabeln chopsticks i funktionen så att den wmain är en matris med unbounded_buffer objekt som var och en innehåller ett meddelande.
// 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);
});

Beskrivning

Följande visar det slutförda exemplet som använder icke-giriga join objekt för att eliminera risken för dödläge.

Exempel

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

Det här exemplet genererar följande utdata.

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

Kompilera koden

Kopiera exempelkoden och klistra in den i ett Visual Studio-projekt, eller klistra in den i en fil med namnet philosophers-join.cpp och kör sedan följande kommando i ett Visual Studio-kommandotolkfönster.

cl.exe /EHsc philosophers-join.cpp

[Topp]

Se även

Genomgång av samtidighetskörning
Asynkront agentbibliotek
Asynkrona agenter
Asynkrona meddelandeblock
Funktioner för meddelandeöverföring
Datastrukturer för synkronisering