C++ Core Guidelines: Die Auflösung des Rätsels
Das Rätsel des letzten Artikels wird aufgelöst. Dank der Leser ist die Problemanalyse sehr genau.
Heute löse ich das Rätsel des letzten Artikels [1] auf. Dank meiner Leser ist die Problemanalyse sehr genau.
Zuerst möchte ich eine kleine Erinnerungshilfe geben. Das Rätsel beginnt mit der Regel CP.100 der C++ Core Guidelines.
CP.100: Don’t use lock-free programming unless you absolutely have to. [2]
Die Regel enthält die Herausforderung, dass der folgende Codeschnipsel einen Bug enthält, der auf das ABA-Problem zurückzuführen ist. Mein Artikel ABA – A ist nicht gleich A [3] gibt eine einfache Einführung in das ABA-Problem.
extern atomic<Link*> head; // the shared head of a linked list
Link* nh = new Link(data, nullptr); // make a link ready for insertion
Link* h = head.load(); // read the shared head of the list
do {
if (h->data <= data) break; // if so, insert elsewhere
nh->next = h; // next element is the previous head
} while (!head.compare_exchange_weak(h, nh)); // write nh to head or to h
Hier ist ein ausführbares Codefragement zu dem Codeschnipsel. Die tiefe Codeanalyse folgt unmittelbar.
#include <atomic>
class Link {
public:
Link(int d, Link* p) : data(d), next(p) {}
int data;
Link* next;
};
void foo (int data) {
extern std::atomic<Link*> head;
Link* nh = new Link(data, nullptr); // (1)
Link* h = head.load(); // (2)
do {
if (h->data <= data) break; // (3)
nh->next = h; // (4)
} while (!head.compare_exchange_weak(h, nh)); // (5)
}
Zuerst einmal: Was tut das Programm? Das Programm erzeugt eine einfach verkettete Liste von Knoten (Link). Jeder Knoten besitzt einen Zeiger und ein Datenfeld. Der Zeiger verweist auf den nächsten Knoten (node->next) und das Datenfeld speichert den Wert ab: node->data. Jeder neue Knoten wird so in die Liste eingefügt, dass data in aufsteigender Reihenfolge sortiert ist.
Um einen neuen Knoten an die richtige Stelle in die Liste einzuführen, sind die folgenden Schritte notwendig.
- Zeile 1: Ein neuer Knoten wird erzeugt. Das ist unproblematisch, weil in jedem Thread lokal neuer Speicher angefordert wird.
- Zeile 2: Der Zeiger auf head wird gelesen. Diese Operation ist atomar, daher ist die Operation in Isolation betrachtet unkritisch. Was bedeutet dies in Isolation betrachtet? Zeile 2 erzeugt mit Zeile 5 eine Art Transaktion. Zeile 2 speichert den initialen Zustand der Transaktion und Zeile 5 veröffentlicht die Transaktion, falls sich in der Zwischenzeit ihre Ausgangsbedingung nicht geändert hat. Lediglich der Wert von data wird geprüft. Dies kann zur Folge haben, dass die Funktion beendet wird, falls head bereits kleiner als das neue Datum ist.
- Zeile 3: Entsprechend der letzten Zeile, ist diese Zeile auch in Ordnung.
- Zeile 4: nh ist ein lokaler Knoten. Damit ist die Zuweisung nh->next unproblematisch. Es kann zwar passieren, dass der Kopf h in der Zwischenzeit verändert wurde und damit nh->next nicht auf den neuen head verweist. Dies wird aber gegebenenfalls erst dann ein Problem, wenn diese Veränderung in der folgenden Zeile 5 veröffentlicht wird.
- Zeile 5: Der Befehl head.compare_exchange_weak(h, nh) vergleicht den head mit dem gespeicherten Knoten h in der Zeile 2. Gegebenenfalls tauscht er beide in einer atomaren Operation aus, sobald beide gleich sind. Falls der head ungleich h ist, wird h auf head gesetzt. Zeile 5 stellt das Ende der atomaren Transaktion dar und veröffentlicht die veränderte, einfach verkettete Liste.
Welches Problem besitzen diese Codezeilen? Die ganze Transaktion basiert auf dem Zeigervergleich in Zeile 5. Falls sich der Zeigervergleich korrumpieren lässt, gilt dies auch für die einfach verkettete Liste.
Es gibt ein kleines Zeitfenster zwischen dem Laden von head (Zeile 2) und dem Test, ob der aktuelle head (Zeile 5) dem alten head in Zeile 2 noch entspricht. Das bedeutet, in diesem kleinen Zeitfenster kann ein anderer Thread ausgeführt werden und den head verändern, sodass es der ursprüngliche head nicht mitbekommt.
Jetzt stelle ich eine solche Sequenz von Events dar, die die einfache verkettete Liste korrumpiert.
Bruch der Invariante
Die Invariante der folgenden einfach verketteten Liste ist es, dass ihre Elemente aufsteigend sortiert sind. Der blaue Knoten steht für den Kopf der Liste. Dies ist Anfangszustand der Liste. Der Kopf besitzt die Adresse 0x0815.
Thread 1
- Will den neuen Knoten mit dem Wert 42 hinzufügen.
- 42 < 47, daher soll der neue Knoten zum neuen Kopf werden.
- Kurz bevor die Zeile 5 ausgeführt wird, kommt der Thread 2 zum Zuge.
Thread 2
- Entfernt den aktuellen Kopf mit dem Wert 47.
- Macht den Knoten mit dem Wert 60 zum neuen Kopf.
- Möchte den neuen Knoten mit dem Wert 30 zum neuen Kopf machen.
- Macht den Knoten mit dem Wert 30 zum neuen Kopf und verwendet für ihn die Adresse 0x0815. Dies war die Adresse des vorherigen Kopfes 47 und dies passiert gerne, da Speicher wiederverwendet wird.
Thread 1
- Machte den Knoten mit dem Wert 42 zum neuen Kopf. Dies ist möglich, da der Vergleich in Zeile 5 den alten mit dem neuen Kopf vergleicht und beide die gleiche Adresse besitzen: 0x0815.
Jetzt gilt die Invariante der einfach verketteten Liste nicht mehr, da die Werte der Knoten nicht mehr aufsteigend sortiert sind.
Wie geht's weiter?
Jetzt bin ich fast fertig mit den Regeln zur Concurrency und zum lock-freien Programmieren im Besonderen. Die verbleibenden Regeln gehen auf falsche Annahmen zu Hardware/Compiler-Kombinationen ein und widmen sich dem berühmt-berüchtigten Double-Checked Locking Pattern. ( [4])
URL dieses Artikels:
https://www.heise.de/-4095198
Links in diesem Artikel:
[1] https://heise.de/-4090498
[2] http://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines#Rconc-lockfree
[3] https://heise.de/-3740324
[4] mailto:rainer@grimm-jaud.de
Copyright © 2018 Heise Medien