zurück zum Artikel

C++ Core Guidelines: Die Auflösung des Rätsels

Modernes C++

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.

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.

C++ Core Guidelines: Die Auflösung des Rätsels
Thread 1
C++ Core Guidelines: Die Auflösung des Rätsels
Thread 2
C++ Core Guidelines: Die Auflösung des Rätsels
C++ Core Guidelines: Die Auflösung des Rätsels
C++ Core Guidelines: Die Auflösung des Rätsels
Thread 1
C++ Core Guidelines: Die Auflösung des Rätsels

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.


URL dieses Artikels:
http://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