Exemplarische Vorgehensweise: Verhindern von Deadlocks mit join

Artikel
08/10/2011

In diesem Thema wird anhand des Philosophenproblems illustriert, wie sich mit der Concurrency::join-Klasse Deadlocks in der Anwendung verhindern lassen. In einer Softwareanwendung tritt ein Deadlock auf, wenn mindestens zwei Prozesse jeweils über eine Ressource verfügen und warten, bis von einem anderen Prozess eine weitere Ressource freigegeben wird.

Das Philosophenproblem ist ein spezifisches Beispiel dafür, welche Probleme allgemein auftreten können, wenn ein Satz von Ressourcen von mehreren gleichzeitig ablaufenden Prozessen gemeinsam verwendet wird.

Vorbereitungsmaßnahmen

Lesen Sie sich folgende Themen durch, bevor Sie mit dieser exemplarischen Vorgehensweise beginnen:

Abschnitte

Diese exemplarische Vorgehensweise enthält folgende Abschnitte:

Das Philosophenproblem
Eine naive Implementierung
Verhindern von Deadlocks mit join

Das Philosophenproblem

Das Philosophenproblem veranschaulicht, wie Deadlocks in einer Anwendung auftreten. Bei diesem Problem sitzen fünf Philosophen an einem runden Tisch. Die einzelnen Philosophen haben Phasen, in denen sie denken, und Phasen, in denen sie essen. Jeder Philosoph muss ein Essstäbchen mit dem Tischnachbarn zu seiner Linken und ein anderes Essstäbchen mit dem Tischnachbarn zu seiner Rechten teilen. Die folgende Abbildung veranschaulicht diese Anordnung.

Das Philosophenproblem

Um essen zu können, benötigt ein Philosoph zwei Essstäbchen. Wenn jeder Philosoph nur ein Essstäbchen hat und auf das zweite wartet, kann kein Philosoph essen und alle bleiben hungrig.

[Nach oben]

Eine naive Implementierung

Im folgenden Beispiel wird eine naive Implementierung des Philosophenproblems veranschaulicht. Durch die philosopher-Klasse, die von Concurrency::agent abgeleitet wird, kann jeder Philosoph unabhängig handeln. Im Beispiel wird ein freigegebenes Array von philosopher-Objekten verwendet, damit jedes Concurrency::critical_section-Objekt exklusiven Zugriff auf ein Paar Essstäbchen hat.

Um die Implementierung mit der Abbildung in Verbindung zu bringen, stellt die philosopher-Klasse einen Philosophen dar. Jedes Essstäbchen wird durch eine int-Variable dargestellt. Die critical_section-Objekte dienen als Halter für die Essstäbchen. Die run-Methode simuliert das Leben des Philosophen. Die think-Methode simuliert das Denken und die eat-Methode das Essen.

Ein philosopher-Objekt sperrt beide critical_section-Objekte, um das Herausnehmen der Essstäbchen aus den Haltern zu simulieren, bevor die eat-Methode aufgerufen wird. Nach dem Aufruf von eat werden die Essstäbchen wieder vom philosopher-Objekt in die Halter zurückgelegt, und zwar durch Zurücksetzen der critical_section-Objekte in den entsperrten Zustand.

Die pickup_chopsticks-Methode veranschaulicht, wo ein Deadlock auftreten kann. Wenn jedes philosopher-Objekt Zugriff auf eine der Sperren erlangt, kann kein philosopher-Objekt fortfahren, weil die andere Sperre von einem anderen philosopher-Objekt gesteuert wird.

Beispiel

Code

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

Kompilieren des Codes

Kopieren Sie den Beispielcode, und fügen Sie ihn in ein Visual Studio-Projekt ein. Alternativ dazu können Sie ihn in eine Datei mit dem Namen philosophers-deadlock.cpp einfügen und dann folgenden Befehl in einem Visual Studio 2010-Eingabeaufforderungsfenster ausführen.

cl.exe /EHsc philosophers-deadlock.cpp

[Nach oben]

Verhindern von Deadlocks mit join

In diesem Abschnitt wird gezeigt, wie Meldungspuffer und Meldungsübergabefunktionen verwendet werden, um Deadlocks zu vermeiden.

Um dieses Beispiel mit dem früheren in Verbindung zu bringen, ersetzt die philosopher-Klasse alle critical_section-Objekte mit einem Concurrency::unbounded_buffer-Objekt und einem join-Objekt. Das join-Objekt dient als Vermittler, das dem Philosophen die Essstäbchen bereitstellt.

In diesem Beispiel wird die unbounded_buffer-Klasse verwendet, da die Meldung aus der Meldungswarteschlange entfernt wird, wenn ein Ziel eine Meldung von einem unbounded_buffer-Objekt empfängt. So kann ein unbounded_buffer-Objekt, das eine Meldung enthält, darauf hinweisen, dass das Essstäbchen zur Verfügung steht. Ein unbounded_buffer-Objekt, das keine Meldung enthält, weist darauf hin, dass das Essstäbchen verwendet wird.

In diesem Beispiel wird ein nicht gieriges join-Objekt verwendet, da ein nicht gieriger Join nur dann jedem philosopher-Objekt Zugriff auf beide Essstäbchen gewährt, wenn beide unbounded_buffer-Objekte eine Meldung enthalten. Ein gieriger Join würde Deadlocks nicht verhindern, da Meldungen von ihm akzeptiert werden, sobald sie verfügbar sind. Deadlocks können auftreten, wenn alle gierigen join-Objekte eine der Meldungen empfangen, aber ewig warten, bis die andere verfügbar wird.

Weitere Informationen zu gierigen und nicht gierigen Joins sowie zu den Unterschieden zwischen den verschiedenen Meldungspuffertypen finden Sie unter Asynchrone Nachrichtenblöcke.

So verhindern Sie Deadlocks in diesem Beispiel

Entfernen Sie folgenden Code aus dem Beispiel.

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

Ändern Sie den Typ der Datenmember _left und _right der philosopher-Klasse in unbounded_buffer.

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

Ändern Sie den philosopher-Konstruktor, damit unbounded_buffer-Objekte als Parameter verwendet werden.

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

Ändern Sie die pickup_chopsticks-Methode, um ein nicht gieriges join-Objekt zum Empfangen von Meldungen von den Meldungspuffern für beide Essstäbchen.

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

Ändern Sie die putdown_chopsticks-Methode, um den Zugriff auf die Essstäbchen freizugeben, indem eine Meldung an die Meldungspuffer für beide Essstäbchen gesendet wird.

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

Ändern Sie die run-Methode, um die Ergebnisse der pickup_chopsticks-Methode aufzunehmen und diese Ergebnisse an die putdown_chopsticks-Methode weiterzuleiten.

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

Ändern Sie die Deklaration der chopsticks-Variable in der wmain-Funktion, damit sie ein Array von unbounded_buffer-Objekten ist, die jeweils über eine Meldung verfügen.

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

Beispiel

Beschreibung

Nachfolgend sehen Sie das vollständige Beispiel, bei dem nicht gierige join-Objekte verwendet werden, um das Risiko von Deadlocks auszuschließen.

Code

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

Kommentare

Folgende Ergebnisse werden zurückgegeben:

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

Kompilieren des Codes

Kopieren Sie den Beispielcode, und fügen Sie ihn in ein Visual Studio-Projekt ein. Alternativ dazu können Sie ihn in eine Datei mit dem Namen philosophers-join.cpp einfügen und dann folgenden Befehl in einem Visual Studio 2010-Eingabeaufforderungsfenster ausführen.

cl.exe /EHsc philosophers-join.cpp

[Nach oben]