Latches in C++20

25.01.2021 07:51 Uhr Rainer Grimm

Latches und Barriers sind Koordinationsdatentypen, die es Threads erlauben zu warten, bis ein Zähler den Wert Null besitzt. Ein std::latch lässt sich nur einmal, ein std::barrier hingegen mehrmals verwenden. Heute schaue ich mir Latches genauer an.

Latches und Barriers sind Koordinationsdatentypen, die es Threads erlauben zu warten, bis ein Zähler den Wert Null besitzt. Ein std::latch lässt sich nur einmal, ein std::barrier hingegen mehrmals verwenden. Heute schaue ich mir Latches genauer an.

Das gleichzeitige Aufrufen der Methoden eines std::latch oder einer std::barrier stellt kein Data Race dar. Ein Date Race ist ein solch elementarer Begriff in der Concurrency, dass ich ihn genauer vorstellen will.

Data Race

Ein Data Race ist eine Situation, in der zumindest zwei Threads gleichzeitig auf eine Variable zugreifen und zumindest einer der zwei Threads versucht, diese zu verändern. Wenn ein Programm in ein Data Race läuft, besitzt es undefiniertes Verhalten. Das heißt, dass keine verbindlichen Aussagen über das Programm mehr möglich sind. Das folgende Programm ist ein Beispiel hierfür:

// addMoney.cpp

#include <functional>
#include <iostream>
#include <thread>
#include <vector>

struct Account{
  int balance{100};                                         // (3)               
};

void addMoney(Account& to, int amount){                     // (2) 
  to.balance += amount;                                     // (1)       
}

int main(){
  
  std::cout << '\n';

  Account account;
  
  std::vector<std::thread> vecThreads(100);
                                           
  for (auto& thr: vecThreads) thr = std::thread(addMoney, std::ref(account), 50);  
  
  for (auto& thr: vecThreads) thr.join();
                                                 
  std::cout << "account.balance: " << account.balance << '\n';  // (4)
  
  std::cout << '\n';

}

Im Programm addieren 100 Threads 50 Euro mithilfe der Funktion addMoney (2) auf dasselbe Konto (1). Der ursprüngliche Wert ist 100 (3). Die entscheidende Beobachtung ist es, dass die Modifikation des Kontos ohne Synchronisation stattfindet. Damit ist dies ein Data Race und das Programm besitzt undefiniertes Verhalten. Führe ich das Programm mehrfach aus, beträgt der Kontostand am Ende des Programms zwischen 5000 und 5100 Euro (4).

Wie kann das passieren? Warum gehen ein paar 50 Euro Überweisungen verloren? Der Update-Prozess to.balance += amount; in Zeile (1) ist eine sogenannte Read-Modify-Write-Operation. Als solche wird zuerst der alte Wert von to.balance gelesen, dann aktualisiert und letztlich geschrieben. Nun ist die folgende Ausführung von Operationen möglich. Ich verwende der Anschaulichkeit halber in meiner Beschreibung konkrete Zahlen.

Thread A liest lediglich den Wert 500 Euro und dann kommt Thread B zum Zuge.
Thread B liest auch den Wert 500 Euro, fügt 50 Euro hinzu und aktualisiert den Kontostand auf 550 Euro.
Nun vollendet Thread A seinen Job, in dem er auch 50 Euro zum Kontostand hinzufügt. Damit schreibt Thread A ebenfalls den Wert 550 Euro.
Letztlich wird der Wert 550 zweimal geschrieben und damit können wir anstelle zweier Überweisungen von 50 Euro nur eine wahrnehmen.
Das heißt, dass eine Überweisung verloren geht und wir einen zu niedrigen Kontostand erhalten.

Zuerst möchte ich zwei Fragen beantworten, bevor ich std::latch und std::barrier im Detail vorstelle.

Zwei Fragen

Worin unterscheiden sich die beiden Mechanismen zur Koordination von Threads? Ein std::latch lässt sich nur einmal verwenden, ein std::barrier hingegen mehrmals. Ein std::latch wird gerne eingesetzt, um eine Aufgabe durch mehrere Threads ausführen zu lassen. Im Gegensatz dazu kommt ein std::barrier typischerweise zum Einsatz, wenn es darum geht, dass eine sich wiederholende Aufgabe durch mehrere Threads ausgeführt werden soll.
Welche neuen Anwendungsfälle lassen sich mit einem Latch und einer Barrier umsetzen, die sich in C++11 nicht schon mit Futures, Threads oder Bedingungsvariablen in Kombination mit einem Lock implementieren lassen? Latches und Barrier bieten keine neuen Anwendungsfälle an. Sie sind aber deutlich einfacher zu verwenden. Darüber hinaus sind sie oft deutlich performanter, da bei ihnen typischerweise lock-freie [1] Mechanismen zum Einsatz kommen.

Mit dem einfachen Datentyp std::latch möchte ich meinen Artikel fortführen.

std::latch

Zuerst werfe ich einen genaueren Blick auf das Interface eines std::latch.

Der Default-Wert für upd ist 1. Falls upd größer als der Zähler oder negativ ist, stellt das undefiniertes Verhalten dar. Der Aufruf lat.try_wait() wartet nicht, wie es sein Name vermuten lässt.

Das folgende Programm bossWorkers.cpp verwendet zwei Latches, um einen Boss-Worker-Ablauf umzusetzen. Ich synchronisiere das Schreiben auf std::cout mithilfe der Funktion synchronizedOut (1). Dadurch ist es einfacher, dem Ablauf zu folgen:

// bossWorkers.cpp

#include <iostream>
#include <mutex>
#include <latch>
#include <thread>

std::latch workDone(6);
std::latch goHome(1);                                       // (4)

std::mutex coutMutex;

void synchronizedOut(const std::string s) {                // (1)
    std::lock_guard<std::mutex> lo(coutMutex);
    std::cout << s;
}

class Worker {
 public:
     Worker(std::string n): name(n) { };
  
      void operator() (){
          // notify the boss when work is done
          synchronizedOut(name + ": " + "Work done!\n");
          workDone.count_down();                          // (2)

          // waiting before going home
          goHome.wait();                                  // (5)
          synchronizedOut(name + ": " + "Good bye!\n");
      }
 private:
    std::string name;
};

int main() {

    std::cout << '\n';

    std::cout << "BOSS: START WORKING! " << '\n';
  
    Worker herb("  Herb");
    std::thread herbWork(herb);
  
    Worker scott("    Scott");
    std::thread scottWork(scott);
  
    Worker bjarne("      Bjarne");
    std::thread bjarneWork(bjarne);
  
    Worker andrei("        Andrei");
    std::thread andreiWork(andrei);
  
    Worker andrew("          Andrew");
    std::thread andrewWork(andrew);
  
    Worker david("            David");
    std::thread davidWork(david);
    
    workDone.wait();                                       // (3)

    std::cout << '\n';

    goHome.count_down();

    std::cout << "BOSS: GO HOME!" << '\n';

    herbWork.join();
    scottWork.join();
    bjarneWork.join();
    andreiWork.join();
    andrewWork.join();
    davidWork.join();
  
}

Das Programm setzt einen einfachen Ablauf um. Die sechs Arbeiter herb, scott, bjarne, andrei, andrew und david müssen ihre Arbeit erledigen. Wenn sie mit ihr fertig sind, dekrementiert sie den Latch: workDone (2). Der Boss (main-Thread) ist so lange in Zeile (3) blockiert, bis der Zähler den Wert 0 hat. Wenn der Zähler den Wert 0 hat, verwendet der Boss den zweiten std::latch goHome, um den Arbeitern zu signalisieren, dass sie nach Hause gehen dürfen. In diesem Fall ist der initiale Zähler 1 (4). Der Aufruf goHome.wait (5) blockiert, bis der Zähler den Wert 0 besitzt.

Es fällt vermutlich auf, dass sich der Ablauf auch ohne Boss umsetzen lässt. Hier ist die moderne Variante:

// workers.cpp

#include <iostream>
#include <latch>
#include <mutex>
#include <thread>

std::latch workDone(6);
std::mutex coutMutex;

void synchronizedOut(const std::string& s) {
    std::lock_guard<std::mutex> lo(coutMutex);
    std::cout << s;
}

class Worker {
 public:
    Worker(std::string n): name(n) { };
  
    void operator() () {
        synchronizedOut(name + ": " + "Work done!\n");
        workDone.arrive_and_wait();  // wait until all work is done  (1)
        synchronizedOut(name + ": " + "See you tomorrow!\n");
    }
 private:
    std::string name;
};

int main() {

    std::cout << '\n';

    Worker herb("  Herb");
    std::thread herbWork(herb);
  
    Worker scott("    Scott");
    std::thread scottWork(scott);
  
    Worker bjarne("      Bjarne");
    std::thread bjarneWork(bjarne);
  
    Worker andrei("        Andrei");
    std::thread andreiWork(andrei);
  
    Worker andrew("          Andrew");
    std::thread andrewWork(andrew);
  
    Worker david("            David");
    std::thread davidWork(david);

    herbWork.join();
    scottWork.join();
    bjarneWork.join();
    andreiWork.join();
    andrewWork.join();
    davidWork.join();
  
}

Es gibt für mich nicht viel zu dem vereinfachten Ablauf hinzufügen. Der Aufruf workDone.arrive_and_wait(1) (1) ist äquivalent zu den Aufrufen count_down(upd); wait();. Das heißt, dass die Arbeiter sich selbst koordinieren können und der Boss im Gegensatz zum vorherigen Programm bossWorkers.cpp überflüssig ist.

Wie geht's weiter?

Eine std::barrier ist einer std::latch ähnlich. Ihre Stärke besteht aber darin, einen Job mehrmals auszuführen. Die std::barrier werde ich mir in meinem nächsten Artikel genauer anschauen. ( [2])

URL dieses Artikels:
https://www.heise.de/-5033716

Links in diesem Artikel:
[1] https://en.wikipedia.org/wiki/Non-blocking_algorithm
[2] mailto:rainer@grimm-jaud.de