Bedingungsvariablen

Kehren wir kurz zu dem Pool-Pattern zurück. Den gab es in zwei Varianten, darunter eine, die mit einer festen Zahl an Objekten arbeitet. Es lohnt sich zu überlegen, wie dies realisiert werden kann.

Wenn wir mit einer festen Zahl arbeiten, dann liegt es nahe, einen std::vector dafür zu nehmen:

std::vector<T> engines;

Dieser kann dann im Konstruktor passend dimensioniert werden. Wenn wir so vorgehen, “behalten” wir alle Objekte des Pools im Pool selbst, wir geben nur Referenzen auf einzelne Objekte leihweise heraus, d.h. die Methode get liefert T& zurück und nicht T wie zuvor. Und bei free benötigen wir keine rvalue reference mehr, die normale Referenz genügt. Dafür haben wir das Problem, den Index des verliehenen Objekts zu finden. Wir implementieren das mit Hilfe einer trivialen linearen Suche, die mit Adressvergleichen arbeitet. So könnte das aussehen:

template<typename T>
struct RandomEnginePool {
      using EngineType = T;
      RandomEnginePool(std::size_t size) :
            size(size), inuse(size), engines(size) {
         std::random_device r;
         for (std::size_t i = 0; i < size; ++i) {
            engines[i].seed(r()); inuse[i] = false;
         }
      }
      T& get() {
         std::lock_guard<std::mutex> lock(mutex);
         for (std::size_t i = 0; i < size; ++i) {
            if (!inuse[i]) {
               inuse[i] = true; --nof_free_engines;
               return engines[i];
            }
         }
         /* problem: no free engine found */
      }
      void free(T& engine) {
         std::lock_guard<std::mutex> lock(mutex);
         bool found = false;
         for (std::size_t i = 0; i < size; ++i) {
            if (&engine == &engines[i]) {
               inuse[i] = false; ++nof_free_engines;
               found = true; break;
            }
         }
         assert(found);
      }
   private:
      std::mutex mutex;
      std::size_t size;
      std::vector<bool> inuse;
      std::vector<T> engines;
};

Das funktioniert soweit ganz gut -- es bleibt nur das nicht unerhebliche Problem, was zu tun ist, wenn get keinen frei verfügbaren Generator findet. In diesem Moment würden wir gerne den Aufrufer blockieren, bis ein Generator wieder zurückgegeben wird.

Für diese Art der Synchronisierung gibt es Bedingungsvariablen (condition variables). Eine Bedingungsvariable offeriert die Methode wait, mit der auf das Eintreten eines Ereignisses gewartet werden kann. Das Eintreten des Ereignisses kann mit den Methoden notify_one oder notify_all signalisiert werden.

Wichtig ist folgender Punkt bei Bedingungsvariablen: Ein Aufruf von notify_one oder notify_all verpufft wirkungslos, wenn kein Thread mit wait auf das Eintreten des Ereignisses wartet. Aufgeweckt werden mit notify_one und notify_all somit nur mit wait wartende Threads; auf spätere Aufrufe von wait wirkt sich das nicht aus. Bei notify_one wird genau einer der wartenden Threads geweckt, bei notify_all alle.

Vom Prinzip könnte eine möglicherweise wartende Methode so aussehen:

std::lock_guard<std::mutex> lock(mutex);
if (/* need to wait */) {
   lock.unlock();
   cv.wait(); /* cv is a condition variable */
   lock.lock();
}
/* we do not need to wait (any longer) */

Wichtig ist hier die temporäre Freigabe der Mutex-Variablen. Wenn wir diese nicht freigeben würden, könnte keine der Methoden auf die Datenstrukturen zugreifen und entsprechend würde es nie dazu kommen, dass das Eintreffen des Ereignisses signalisiert wird.

So könnte eine Methode aussehen, die ein Ereignis signalisiert:

std::lock_guard<std::mutex> lock(mutex);
/* ... */
if (/* someone waits */) {
   cv.notify_one();
}

Die Konstruktion hat ein Problem: Wenn sich zwischen lock.unlock() und cv.wait() in der oberen Methode ein cv.notify_one() in der unteren Methode einschiebt, verpufft das cv.notify_one() wirkungslos und der erstere Thread wartet vergeblich auf die Signalisierung des Ereignisses. Deswegen muss die Freigabe der Mutex-Variablen und der Aufruf von cv.wait atomar sein. Damit dies sichergestellt wird, muss lock an cv.wait übergeben werden. Ein weiterer kleiner Punkt ist der, dass std::lock_guard die temporäre Freigabe nicht unterstützt. Stattdessen ist ersatzweise std::unique_lock zu verwenden:

template<typename T>
struct RandomEnginePool {
      using EngineType = T;
      RandomEnginePool(std::size_t size) :
            size(size), nof_free_engines(size),
            inuse(size), engines(size) {
         std::random_device r;
         for (std::size_t i = 0; i < size; ++i) {
            engines[i].seed(r()); inuse[i] = false;
         }
      }
      T& get() {
         std::unique_lock<std::mutex> lock(mutex);
         if (nof_free_engines == 0) {
            cv.wait(lock);
         }
         for (std::size_t i = 0; i < size; ++i) {
            if (!inuse[i]) {
               inuse[i] = true; --nof_free_engines;
               return engines[i];
            }
         }
         assert(false);
      }
      void free(T& engine) {
         {
            std::unique_lock<std::mutex> lock(mutex);
            bool found = false;
            for (std::size_t i = 0; i < size; ++i) {
               if (&engine == &engines[i]) {
                  inuse[i] = false; ++nof_free_engines;
                  found = true; break;
               }
            }
            assert(found);
         }
         cv.notify_one();
      }
   private:
      std::mutex mutex;
      std::condition_variable cv;
      std::size_t size;
      std::size_t nof_free_engines;
      std::vector<bool> inuse;
      std::vector<T> engines;
};

Aufgabe

Passen Sie den RandomEngineGuard an den neuen Pool an und testen Sie dies.

Sie können wieder all Ihre Lösungen mit tar zu session15.tar zusammenpacken und auf der Thales einreichen:

submit hpc session15 session15.tar