Blockierende und nichtblockierende Algorithmen

Inhaltsverzeichnis

Blockierend, nichtblockierend, "lock-free" und "wait-free". Jeder dieser Begriffe beschreibt eine Charakteristik eines Algorithmus, wenn er in einer nebenläufigen Umgebung ausgeführt wird. Macht man sich daher Gedanken zum Laufzeitverhalten eines Programms, bedeutet es oft, ihn ins richtige Körbchen zu legen. Daher geht es heute um das Einsortieren.

Ein Algorithmus fällt in eine von zwei Kategorien: blockierend oder nicht-.

Los geht es mit den blockierenden Algorithmen.

Blockierend

Intuitiv wissen wir natürlich, was blockierend für einen Algorithmus bedeutet. Aber bei Gleichzeitigkeit geht es nicht um Intuition, hier geht es um präzise Begriffe. Der einfachste Weg, "blockierend" für einen Algorithmus zu definieren, ist es, sich auf nichtblockierend zurückzuziehen. Der Begriff wird sehr schön in dem Buch "Java Concurreny in Practice" definiert.

• "Non-blocking: An algorithm is called non-blocking if failure or suspension of any thread cannot cause failure or suspension of another thread." (Ein Algorithmus heißt nichtblockierend, wenn ein Fehler oder die Sperre eines Threads nicht zu einem Fehler oder der Sperre eines anderen Threads führt.)

Die Definition enthält nicht den Ausdruck "Lock". Das ist richtig, denn nichtblockierend ist ein allgemeinerer Ansatz.

Ein Programm zu "blockierend" ist ziemlich einfach. Das typische Kochrezept besteht darin, mehr als einen Mutex zu verwenden und sie in verschiedene Reihenfolgen zu locken. Glückliches Timing, und schon gibt es ein Deadlock. Aber es gibt viel mehr Rezepte, um einen blockierenden Algorithmus zu erzeugen. Jedes Mal, wenn man auf eine Ressource warten musst, lauert eine Blockade.

Hier sind ein paar Beispiele für synchronisierte Zugriffe auf eine Ressource:

• eine Bedingungsvariable mit wait.
• ein Future mit get oder wait.
  

Selbst der join-Aufruf auf einem Thread kann mit ein wenig Innovation dazu verwendet werden, einen Thread für immer zu blockieren.

// deadlockWait.cpp

#include <iostream>
#include <mutex>
#include <string>
#include <thread>

std::mutex coutMutex;

int main(){

  std::thread t([]{
    std::cout << "Still waiting ..." << std::endl;            // 2
    std::lock_guard<std::mutex> lockGuard(coutMutex);         // 3
    std::cout << "child: " << std::this_thread::get_id() << std::endl;}
  );

  {

    std::lock_guard<std::mutex> lockGuard(coutMutex);          // 1
    std::cout << "creator: " << std::this_thread::get_id() << std::endl;

    t.join();                                                  // 5

  }                                                            // 4

}

Die Programmausführung bleibt sofort stehen.

Was passiert hier? Der Erzeuger-Thread lockt (1) den Mutex. Nun führt das Kind (2) aus. Damit das Kind den Mutex (3) erhält, muss der Erzeuger-Thread diesen erst wieder freigeben. Aber der Erzeuger-Thread gibt den Mutex erst dann wieder frei, wenn der lockGuard (1) seinen Gültigkeitsbereich (4) verlässt. Das passiert aber nie, denn der Kinder-Thread muss dazu erst den Mutex coutMutex locken.

Auf die blockierenden folgen nun die nichtblockierenden Algorithmen.

Nichtblockierend

Die Hauptkategorien für nichtblockierende Algorithmen sind "lock-free" und "wait-free". Jeder Wait-free-Algorithmus ist "lock-free", und jeder Lock-free-Algorithmus ist nichtblockierend. Nichtblockierend und "lock-free" sind aber verschiedene Konzepte. Es gibt eine zusätzliche Zusicherung, die "obstruction-free" genannt wird. Diese werde ich aber in diesem Artikel ignorieren, da sie nicht besonders relevant ist. Nichtblockierende Algorithmen werde typischerweise mit CAS-Anweisungen umgesetzt.

CAS steht für "compare and swap". CAS heißt in C++ compare_exchange_strong oder compare_exchange_weak. Ich werde in diesem Artikel die Strong-Version verwenden. Falls mehr Information benötigt werden, finden sie sich in meinen Artikel "Der atomare Wahrheitswert". Die zentrale Idee beider Algorithmen ist es, dass der Aufruf atomicValue.compare_exchange_strong(expected, desired) die folgende Strategie in atomare Weise umsetzt.

• Falls der Vergleich von atomicValue mit expected true ergibt, wird in derselben atomaren Operation atomicValue auf desired gesetzt.
• Falls der Vergleich false zurückgibt, wird expected auf atomicValue gesetzt.

Jetzt möchte ich einen genaueren Blick auf "lock-free" und "wait-free" werfen. Beginnen werde ich mit den Definitionen von "lock-free" und "wait-free". Beide Definitionen sind sehr ähnlich. Daher ergibt es Sinn, diese gegenüberzustellen.

• Lock-free: Ein nichtblockierender Algorithmus ist "lock-free", falls ein systemweiter Fortschritt zugesichert ist.

• Wait-free: Ein nichtblockierender Algorithmus ist "wait-free", falls ein Fortschritt für jeden Thread zugesichert ist.

Lock-free

// fetch_mult.cpp

#include <atomic>
#include <iostream>

template <typename T>
T fetch_mult(std::atomic<T>& shared, T mult){                          // 1
  T oldValue = shared.load();                                          // 2
  while (!shared.compare_exchange_strong(oldValue, oldValue * mult));  // 3
  return oldValue;
}

int main(){
  std::atomic<int> myInt{5};
  std::cout << myInt << std::endl;          
  fetch_mult(myInt,5);
  std::cout << myInt << std::endl;         
}

Der Algorithmus fetch_mult (1) multipliziert eine std::atomic shared mit mult. Die entscheidende Beobachtung ist es, dass es ein kleines Zeitfenster zwischen dem Lesen des alten Werts oldValue = shared Load (2) und dem Vergleich mit dem neuen Wert (3) gibt. Daher kann immer ein anderer Thread zu genau diesem Zeitpunkt den alten Wert ändern. Wer sich diese verschränkte Ausführung von Threads vergegenwärtigt, dem ist unmittelbar klar, dass der Algorithmus keinen Fortschritt für jeden Thread garantieren kann. Daher ist der Algorithmus "lock-free", aber nicht "wait-free".

Hier ist die Ausgabe des Programms.

Während ein Lock-free-Algorithmus systemweiten Fortschritt garantiert, garantiert ein Wait-free-Algorithmus Fortschritt für jeden Thread.

Wait-free

Wenn man sich den Lock-free-Algorithmus im letzten Beispiel genauer anschaut, wird auffallen, dass ein compare_exchange_strong-Aufruf Synchronisation anwendet. Zuerst wird der alte Wert ausgelesen und dann wird der neue Wert gesetzt, falls die Anfangsbedingung noch zutrifft. Falls das gilt, wird der neue Wert veröffentlicht. Wenn nicht, werden die Schritte wiederholt, falls man ihn in einer while-Schleife verwendet. Daher verhält sich compare_exchange_strong wie eine atomare Transaktion.

Die entscheidenden Zeilen des nächsten Programms kommen ganz ohne Synchronisation aus.

// relaxed.cpp

#include <vector>
#include <iostream>
#include <thread>
#include <atomic>
 
std::atomic<int> cnt = {0};
 
void add(){                                           // 1
    for (int n = 0; n < 1000; ++n) {
        cnt.fetch_add(1, std::memory_order_relaxed);  // 2
    }
}
 
int main(){
    std::vector<std::thread> v;
    for (int n = 0; n < 10; ++n) {
        v.emplace_back(add);
    }
    for (auto& t : v) {
        t.join();
    }
    std::cout << "Final counter value is " << cnt << '\n';
}

Die Funktion add (1) ist einen scharfen Blick wert. Der Ausdruck (2) kommt ohne Synchronisation aus. Der atomare Wert cnt wird lediglich um 1 inkrementiert. Und hier kommt die Ausgabe des Programms. Das Ergebnis ist immer 1000, da 10 Threads 1000 Mal 1 hinzuaddieren.

Der Einfachheit halber, habe ich ein paar weitere Zusicherungen wie "starvation-free" als Untermenge von blockierenden Algorithmen oder "wait-free bounded" als Untermenge von Wait-free-Algorithmen in diesem Artikel ignoriert. Die Details dazu lassen sich schön auf dem Blog "Concurreny Freaks" nachlesen.

Wie geht's weiter?

Im nächsten Artikel schreibe ich über eine Kuriosität. Sie heißt ABA und stellt eine Art "false positive" für CAS-Anweisungen dar. Das bedeutet, obwohl es scheint, dass der alte Wert eines CAS-Befehls sich nicht geändert hat, ist er in der Zwischenzeit doch verändert worden. ()