Was ist sperrungsfreie Multithread-Programmierung?

Ich habe Leute/Artikel/SO-Posts gesehen, die sagen, dass sie ihren eigenen “lock-free” Container für die Multithread-Nutzung entworfen haben. Angenommen, sie haben keinen leistungssteigernden Modulus-Trick angewendet (dh jeder Thread kann nur basierend auf einem bestimmten Modulo einfügen), wie können Datenstrukturen multithreaded, aber auch lock-frei sein???

Diese Frage richtet sich an C und C++.

Der Schlüssel zur Lock-freien Programmierung ist die Verwendung von Hardware-intrinsischen atomar Operationen.

Tatsächlich müssen sogar Sperren selbst diese atomaren Operationen verwenden!

Der Unterschied zwischen gesperrter und sperrfreier Programmierung besteht jedoch darin, dass ein sperrfreies Programm niemals von einem einzelnen Thread vollständig zum Stillstand gebracht werden kann. Wenn dagegen in einem Sperrprogramm ein Thread eine Sperre erwirbt und dann auf unbestimmte Zeit ausgesetzt wird, wird das gesamte Programm blockiert und kann nicht fortfahren. Im Gegensatz dazu kann ein Lock-freies Programm auch dann Fortschritte machen, wenn einzelne Threads auf unbestimmte Zeit ausgesetzt sind.

Hier ist ein einfaches Beispiel: Eine gleichzeitige Erhöhung des Zählers. Wir stellen zwei Versionen vor, die beide „thread-safe“, also mehrfach gleichzeitig aufrufbar sind. Zuerst die gesperrte Version:

int counter = 0;
std::mutex counter_mutex;

void increment_with_lock()
{
    std::lock_guard<std::mutex> _(counter_mutex);
    ++counter;
}

Jetzt die Lock-freie Version:

std::atomic<int> counter(0);

void increment_lockfree()
{
    ++counter;
}

Stellen Sie sich jetzt Hunderte von Threads vor, die alle anrufen increment_* gleichzeitig funktionieren. In der gesperrten Version kein Thread kann Fortschritte machen bis der Lock-Holding-Thread den Mutex entsperrt. In der Version ohne Schloss hingegen Alle Threads können Fortschritte machen. Wenn ein Thread aufgehalten wird, wird er einfach nicht seinen Teil der Arbeit leisten, aber alle anderen können mit ihrer Arbeit weitermachen.

Es ist erwähnenswert, dass im Allgemeinen die sperrungsfreie Programmierung den Durchsatz und den mittleren Latenzdurchsatz gegen eine vorhersagbare Latenz eintauscht. Das heißt, ein lock-freies Programm wird normalerweise weniger erledigt als ein entsprechendes lock-Programm, wenn es nicht zu viele Konflikte gibt (da atomare Operationen langsam sind und einen Großteil des restlichen Systems beeinflussen), aber es garantiert, niemals unvorhersehbar zu produzieren große Latenzen.

Bei Sperren besteht die Idee darin, dass Sie eine Sperre erwerben und dann Ihre Arbeit in dem Wissen erledigen, dass niemand sonst eingreifen kann, und dann die Sperre freigeben.

Für “lock-free” ist die Idee, dass Sie Ihre Arbeit woanders erledigen und dann versuchen, diese Arbeit atomar in den “sichtbaren Zustand” zu bringen und es erneut zu versuchen, wenn Sie fehlschlagen.

Die Probleme mit “lock-free” sind:

• Es ist schwierig, einen Lock-freien Algorithmus für etwas zu entwerfen, das nicht trivial ist. Dies liegt daran, dass es nur begrenzte Möglichkeiten gibt, den Teil des „atomaren Festschreibens“ auszuführen (oftmals basierend auf einem atomaren „Vergleichen und Tauschen“, das einen Zeiger durch einen anderen Zeiger ersetzt).
• Wenn es zu Konflikten kommt, ist die Leistung schlechter als bei Sperren, da Sie wiederholt Arbeiten ausführen, die verworfen/wiederholt werden
• Es ist praktisch unmöglich, einen Lock-freien Algorithmus zu entwerfen, der sowohl korrekt als auch “fair” ist. Dies bedeutet, dass (unter Konkurrenz) einige Aufgaben Glück haben können (und ihre Arbeit wiederholt übernehmen und Fortschritte machen) und andere sehr unglücklich sein können (und wiederholt fehlschlagen und es erneut versuchen).

Die Kombination dieser Dinge bedeutet, dass es nur für relativ einfache Dinge unter geringer Konkurrenz gut ist.

Forscher haben Dinge wie verkettete Listen ohne Sperren (und FIFO/FILO-Warteschlangen) und einige Bäume ohne Sperren entworfen. Ich glaube nicht, dass es etwas Komplexeres als diese gibt. Wie diese Dinge funktionieren, denn es ist schwer, es ist kompliziert. Der vernünftigste Ansatz wäre, festzustellen, an welcher Art von Datenstruktur Sie interessiert sind, und dann im Internet nach relevanten Forschungsergebnissen zu sperrenfreien Algorithmen für diese Datenstruktur zu suchen.

Beachten Sie auch, dass es etwas gibt, das “blockfrei” genannt wird, was wie sperrfrei ist, außer dass Sie wissen, dass Sie die Arbeit immer festschreiben können und es nie erneut versuchen müssen. Es ist noch schwieriger, einen blockfreien Algorithmus zu entwerfen, aber Konflikte spielen keine Rolle, sodass die anderen beiden Probleme mit lock-free verschwinden. Hinweis: Das Beispiel “gleichzeitiger Zähler” in der Antwort von Kerrek SB ist überhaupt nicht frei von Sperren, sondern tatsächlich blockfrei.

Die Idee von “lock free” ist nicht wirklich, keine Sperre zu haben, die Idee ist, die Anzahl der Sperren und/oder kritischen Abschnitte zu minimieren, indem einige Techniken verwendet werden, die es uns ermöglichen, für die meisten Operationen keine Sperren zu verwenden.

Es kann mit erreicht werden optimistische Gestaltung oder Transaktionsgedächtniswo Sie die Daten nicht für alle Vorgänge sperren, sondern nur an einigen bestimmten Punkten (wenn Sie die Transaktion im Transaktionsspeicher ausführen oder wenn Sie in einem optimistischen Design ein Rollback durchführen müssen).

Andere Alternativen basieren auf atomaren Implementierungen einiger Befehle, wie z CAS (Compare And Swap), das erlaubt uns sogar, das zu lösen Konsensproblem eine Implementierung davon gegeben. Indem Referenzen ausgetauscht werden (und kein Thread an den gemeinsamen Daten arbeitet), ermöglicht uns der CAS-Mechanismus die einfache Implementierung eines lock-freien optimistischen Designs (Austauschen zu den neuen Daten, wenn und nur wenn niemand sie bereits geändert hat, und dies erfolgt atomar).

Um jedoch den zugrunde liegenden Mechanismus für einen von diesen zu implementieren, werden einige Sperren ausgeführt höchstwahrscheinlich verwendet werden, aber der Zeitraum, in dem die Daten gesperrt werden, ist (angeblich) auf ein Minimum zu beschränken, wenn diese Techniken richtig angewendet werden.

Die neuen C- und C++-Standards (C11 und C++11) führten Threads und von Threads gemeinsam genutzte atomare Datentypen und Operationen ein. Eine atomare Operation gibt Garantien für Operationen, die in ein Rennen zwischen zwei Threads geraten. Sobald ein Thread von einer solchen Operation zurückkehrt, kann er sicher sein, dass die Operation vollständig durchlaufen wurde.

Eine typische Prozessorunterstützung für solche atomaren Operationen existiert auf modernen Prozessoren für Vergleichen und Tauschen (CAS) oder atomare Inkremente.

Zusätzlich dazu, dass er atomar ist, kann der Datentyp die Eigenschaft „lock-free“ haben. Dies hätte vielleicht “zustandslos” geprägt werden sollen, da diese Eigenschaft impliziert, dass eine Operation auf einem solchen Typ das Objekt niemals in einem Zwischenzustand belassen wird, selbst wenn es von einem Interrupt-Handler unterbrochen wird oder ein Lesevorgang eines anderen Threads dazwischen fällt eines Updates.

Mehrere atomare Typen können lock-frei sein (oder auch nicht), es gibt Makros, die auf diese Eigenschaft getestet werden können. Es gibt immer einen Typ, der garantiert sperrfrei ist, nämlich atomic_flag.