Home     Up     Next Browse Files

Konkurrierende Zugriffe auf eine Ressource

Bei unser bisherigen Parallelisierung nach dem Fork-And-Join-Pattern waren die einzelnen Threads vollkommen unabhängig voneinander. D.h. die einzelnen Threads haben weder direkt noch indirekt auf gemeinsame Datenstrukturen oder Ressourcen zugegriffen. Um diese Vorgehensweise konsequent durchzuziehen, haben wir insbesondere in jedem Thread einen neuen Pseudo-Zufallszahlen-Generator angelegt und mit Seed-Werten versorgt. Dies ist eine Operation, die nicht ganz billig ist. Während auf der Thales die Erzeugung einer pseudo-zufälligen, gleichverteilten Zahl unter Verwendung von std::mt19937 im Durchschnitt etwa 8,4 Nanosekunden benötigt, kostet das Einrichten mindestens 9 Mikrosekunden, wobei das noch deutlich mehr wird, wenn etwas mehr Entropie als nur eine 32-Bit-Zahl gewünscht wird.

Beispiele wie dieses führen zu der Frage, ob konkurrierende Zugriffe auf die gleiche Ressource wie beispielsweise einen Pseudo-Zufallszahlengenerator möglich sind. Die POSIX-Schnittstelle und auch die Thread-Schnittstelle von C++11 bieten für diesen Zweck sogenannte Mutex-Variablen (mutex steht für mutual exclusion), mit deren Hilfe sichergestellt werden kann, dass nicht mehrere Threads zum gleichen Zeitpunkt auf eine Ressource zugreifen. Stattdessen bekommt immer nur ein Thread temporär den Zugriff. Andere Threads, die gleichzeitig zugreifen möchten, müssen dann solange warten, bis der andere Zugriff beendet ist.

Die Verwendung einer Mutex-Variablen des Typs std::mutex aus <mutex> ist recht einfach:

Der Zugriff auf einen Pseudo-Zufallszahlengenerator ließe sich dann so verpacken:

struct MyRandomGenerator {
   MyRandomGenerator() : mt(std::random_device()()), uniform(-100, 100) {
   }
   double gen() {
      mutex.lock();
      double val = uniform(mt);
      mutex.unlock();
      return val;
   }
   std::mutex mutex;
   std::mt19937 mt;
   std::uniform_real_distribution<double> uniform;
};

Die Methode gen sichert sich hier zunächst mit mutex.lock() den exklusiven Zugriff, ruft dann einen Wert ab und gibt schließlich den exklusiven Zugriff wieder frei.

Die Variablen der MyRandomGenerator-Klasse sind aber öffentlich zugänglich, d.h. jeder kann auch ohne die Verwendung der Methode gen auf mt oder gar mutex zugreifen. Bei den bisherigen Klassen hat uns dies bislang weniger gestört, bei Klassen wie diesen erscheint es sinnvoll, eine versehentliche Nutzung zu unterbinden, die an der Methode gen vorbeigeht. In C++ ist dies möglich, indem ein Teil der Deklarationen einer Klasse mit private: für den Zugriff von außen gesperrt wird. Auf private Daten können dann nur noch die Methoden der Klasse zugreifen:

struct MyRandomGenerator {
      MyRandomGenerator() : mt(std::random_device()()), uniform(-100, 100) {
      }
      double gen() {
         mutex.lock();
         double val = uniform(mt);
         mutex.unlock();
         return val;
      }
   private:
      std::mutex mutex;
      std::mt19937 mt;
      std::uniform_real_distribution<double> uniform;
};

Die Korrektheit der Lösung hängt natürlich immer davon ab, dass das mutex.unlock() unter keinen Umständen versäumt wird, nachdem zuvor mutex.lock() aufgerufen wurde. Passiert dies doch, warten alle anderen Threads, die mit gen() einen Wert abholen wollen, endlos. Es kommt damit zu einem Endlos-Hänger, auch deadlock genannt. Kann dies hier passieren, nachdem der Zugriff von außen unterbunden ist und sich so übersichtlich mutex.lock() mit mutex.unlock() paart? Ja, es ist theoretisch möglich, wenn es bei dem Aufruf von uniform(mt) zu einer Ausnahmenbehandlung kommt (exception) und im Zuge davon auch der Aufruf von gen automatisch abgebaut wird, ohne dass mehr die Gelegenheit besteht, mutex.unlock() aufzurufen. Die obige Lösung ist somit nicht exception safe.

Es gibt in C++ nur einen Weg, so ein Problem zu lösen und der geht über Destruktoren. C++ garantiert, dass beim Abbau eines Blocks aufgrund einer Ausnahmenbehandlung die Destruktoren der dort deklarierten lokalen Variablen in jedem Fall aufgerufen werden. Entsprechend muss der Aufruf von mutex.unlock() einem Destruktor überlassen werden. Wir begegnen hier wieder dem RAII-Prinzip (resource acquisition is initialization), bei dem ein Objekt die Verantwortung für die Verwendung der Mutex-Variable übernimmt, die

Aufgabe

Schreiben Sie eine einfache RAII-Klasse wie beschrieben für Mutex-Variablen, bauen Sie diese in MyRandomGenerator ein und testen Sie dies, indem Sie die vor einer Woche entstandene Fassung von randominit9.cpp_ ausbauen.

Die Vorlesungsbibliothek steht auf unseren Rechnern unter /home/numerik/pub/hpc/session15 zur Verfügung. Die Header können entsprechend mit -I/home/numerik/pub/hpc/session15 eingebunden werden.

session13/random_init8.cpp 
#include <thread>
#include <random>
#include <vector>
#include <cstdlib>
#include <hpc/matvec/gematrix.h>
#include <hpc/matvec/apply.h>
#include <hpc/matvec/print.h>

template<typename T>
struct Slices {
   Slices(T nof_threads, T problem_size) :
         nof_threads((assert(nof_threads > 0), nof_threads)),
         problem_size(problem_size),
         remainder(problem_size % nof_threads),
         slice_size(problem_size / nof_threads) {
   }
   T offset(T index) {
      assert(index < nof_threads);
      if (index < remainder) {
         return index * (slice_size + 1);
      } else {
         return remainder * (slice_size + 1) +
                (index - remainder) * slice_size;
      }
   }
   T size(T index) {
      assert(index < nof_threads);
      if (index < remainder) {
         return slice_size + 1;
      } else {
         return slice_size;
      }
   }
   T nof_threads; T problem_size;
   T remainder; T slice_size;
};

template<typename MA>
typename std::enable_if<hpc::matvec::IsRealGeMatrix<MA>::value, void>::type
randomInit(MA& A) {
   using ElementType = typename MA::ElementType;
   using Index = typename MA::Index;

   std::random_device random;
   std::mt19937 mt(random());
   std::uniform_real_distribution<ElementType> uniform(-100,100);

   hpc::matvec::apply(A, [&](ElementType& val, Index i, Index j) -> void {
      val = uniform(mt);
   });
}

int main() {
   using namespace hpc::matvec;
   GeMatrix<double> A(51, 7);
   unsigned int nof_threads = std::thread::hardware_concurrency();

   std::vector<std::thread> threads(nof_threads);
   Slices<GeMatrix<double>::Index> slices(nof_threads, A.numRows);
   for (int index = 0; index < nof_threads; ++index) {
      auto firstRow = slices.offset(index);
      auto numRows = slices.size(index);
      auto A_ = A(firstRow, 0, numRows, A.numCols);
      threads[index] = std::thread([=]() mutable { randomInit(A_); });
   }
   for (int index = 0; index < nof_threads; ++index) {
      threads[index].join();
   }
   /* print a small block of each of the initialized matrices */
   print(A, "A");
}
Home     Up     Next