===================
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:

---- CODE (type=cpp) ----------------------------------------------------------
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:

---- CODE (type=cpp) ----------------------------------------------------------
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:

---- CODE (type=cpp) ----------------------------------------------------------
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:

---- CODE (type=cpp) ----------------------------------------------------------
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:

---- CODE (type=cpp) ----------------------------------------------------------
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:

---- CODE (type=sh) -----------------------------------------------------------
submit hpc session15 session15.tar
-------------------------------------------------------------------------------

:navigate: up    -> doc:index
           back  -> doc:session15/page06
           next  -> doc:session15/page08