ABA – A ist nicht gleich A

Inhaltsverzeichnis

Ein bekanntes Problem in nebenläufigen Programmen ist das so genannte ABA-Problem. Das bedeutet, dass ein Wert zweimal gelesen wird und jedes Mal den gleichen Wert A zurückgibt. Die Schlussfolgerung, dass sich der Wert nicht geändert hat, ist falsch. Es hat sich ein B dazwischen eingenistet.

Doch zuerst stelle ich das subtile Problem vor. Das Szenario ist ganz einfach. Ein Fahrer sitzt im Auto und wartet darauf, dass die Ampel grün wird. Grün steht in dem Fall für B und rot für A. Was passiert?

1. Der Fahrer schaut auf die Ampel, und diese ist rot (A).
2. Nun ist er gelangweilt und kontrolliert die Neuigkeiten auf seinem Smartphone. Dabei vergisst er die Zeit.
3. Er schaut nochmals auf die Ampel. Diese ist immer noch rot (A).

Klar, die Ampel ist zwischen den zwei Kontrollblicken grün (B) gewesen. Der Fahrer denkt aber, dass die zwei Rotphasen eine lange Rotphase sind.

Was bedeutet das für Threads oder auch Prozesse? Nun noch mal ein wenig formaler.

1. Thread 1 liest eine Variable var mit dem Wert A.
2. Thread 1 bekommt die CPU entzogen und Thead 2 läuft.
3. Thread 2 ändert den Wert der Variable var von A nach B nach A.
4. Thread 1 bekommt wieder die CPU und kontrolliert die Variable A. Da die Variable var denselben Wert besitzt, fährt Thread 1 mit seiner Arbeit fort.

Oft ist dies kein Problem. Es lässt sich einfach ignorieren.

Kein Problem

Betrachtet sei nun das folgende Beispiel. Die Funktion fetch_mult (1) multipliziert ein std::atomic<T>& shared mit mult.

// fetch_mult.cpp

#include <atomic>
#include <iostream>

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

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

Die zentrale Beobachtung ist es zu sehen, dass es ein kleines Zeitfenster zwischen dem Lesen des alten Wertes T oldValue = shared.load (2) und dem Vergleich mit dem neuen Wert (3) gibt. Daher kann ein anderer Thread zum Zuge kommen und den alten Wert von oldValue auf anotherValue wieder zurück auf oldValue setzen. Der anotherValue repräsentiert das B.

Oft macht es keinen Unterschied, ob der erste gelesene Wert in der zweiten Leseoperation der ursprüngliche Wert ist. Aber in lock-freien, nebenläufigen Datenstrukturen kann ABA schwerwiegende Folgen haben.

Eine lock-freie Datenstruktur

Ich werde in diesem Artikel keine lock-freie Datenstruktur im Detail vorstellen, dafür einen lock-freien Stack verwenden, der als einfach verkettete Liste implementiert ist. Der Stack unterstützt zwei Operationen.

1. "Pop" (auskellern) das erste Element und gibt einen Zeiger darauf zurück.
2. "Push" (einkellern) das spezifizierte Objekt auf den Stack.

Um das ABA-Problem zu identifizieren, möchte ich die "pop"-Operation beschreiben. Sie führt im Wesentlichen die folgenden Schritte in einer Schleife aus, bis die Operation erfolgreich war.

1. Referenziere den Kopfknoten: head
2. Referenziere den Nachfolger des Kopfknotens: headNext
3. Mache headNext zum neuen Kopfknoten, falls head noch der Kopfknoten ist.

Hier sind die ersten zwei Knoten des Stacks:

Stack: TOP -> head -> headNext -> ...

Nun konstruiere ich das ABA-Problem.

ABA in Aktion

Der Stack besitzt die folgende Struktur.

Stack: TOP -> A -> B -> C

Thread 1 ist aktiv und will den Kopf des Stack entfernen (pop).

• Thread 1 speichert
• head = A
• headNext = B

Bevor Thread 1 sein Entfernen des Kopfes vollenden konnte, kommt Thread 2 zum Zuge.

• Thread 2 entfernt A (pop).

    Stack: TOP -> B -> C

• Thread 2 entfernt B und löscht B (pop).
  

    Stack: TOP -> C

• Thread 2 fügt A wieder hinzu (push).

    Stack: TOP -> A -> C

Thread 1 bekommt wieder die CPU und kontrolliert, ob A == head gilt. Da A == head tatsächlich gilt, wird B zum neuen Kopf des Stacks. Aber B wurde bereits gelöscht. Daher besitzt das Programm undefiniertes Verhalten.

Es gibt ein paar Heilmittel gegen das ABA-Problem.

Heilmittel gegen ABA

Das konzeptionelle Problem für ABA ist recht offensichtlich. Ein Knoten B == headNext wurde gelöscht, obwohl ein anderer Knoten A == head noch diesen referenzierte. Die Lösung des Problems ist es, das vorzeitige Löschen des Knotens zu verhindern. Hier sind ein paar Heilmittel.

Tagged state reference

Eine einfach Lösung besteht darin, zu jedem Knoten hinzuzufügen, wie oft er erfolgreich modifizierte wurde. Das Ergebnis ist, das eine "compare and swap"-Operation eventuell fehlschlagen wird, obwohl der Test true ergab.

Die drei nächsten Techniken basieren auf der Idee der Deferred Reclamation (verzögerte Wiederverwertung).

Garbage Collection

Garbage Collection sichert zu, dass eine Variable erst gelöscht wird, wenn diese nicht mehr benötigt wird. Das hört sich vielversprechend an, hat aber einen großen Nachteil. Die meisten Garbage-Collectoren sind nicht lock-frei. Daher besitzt man eine lock-freie Datenstruktur, die in ein nicht lock-freies System eingebunden ist.

Hazard Pointers

Von Wikipedia: Hazard pointers:

In a hazard-pointer system, each thread keeps a list of hazard pointers indicating which nodes the thread is currently accessing. (In many systems this "list" may be provably limited to only one or two elements.) Nodes on the hazard pointer list must not be modified or deallocated by any other thread. ... When a thread wishes to remove a node, it places it on a list of nodes "to be freed later", but does not actually deallocate the node's memory until no other thread's hazard list contains the pointer. This manual garbage collection can be done by a dedicated garbage-collection thread (if the list "to be freed later" is shared by all the threads); alternatively, cleaning up the "to be freed" list can be done by each worker thread as part of an operation such as "pop".

Hier kommt das Zitat in einfachen Worten. Jeder Thread hält eine Liste von Hazard-Pointern, die er gerade verwendet. Die Elemente der Liste werden nicht sofort gelöscht, sondern erst auf Listen geschoben, die für das Löschen vorgesehen sind. Das Löschen findet manuell oder automatisch erst später statt.

RCU

RCU steht für Read Copy Update und ist eine Synchronisationstechnik, die für Datenstrukturen verwendet wird, die fast nur gelesen werden. RCU wurde von Paul McKenney entwickelt und wird im Linux-Kernel seit 2002 eingesetzt.

Die Idee ist relativ einfach und folgt dem Akronym. Um ein Datum zu ändern, muss eine Kopie davon erzeugt werden, auf der die Modifikation stattfindet. Im Gegensatz finden alle lesenden Operationen auf den ursprünglichen Daten statt. Falls kein lesender Zugriff mehr erfolgt, kann die Datenstruktur einfach mit seiner modifizierten Kopie ersetzt werden.

Mehr Details zu RCU gibt es im Artikel von Paul McKenney: "What is RCU, Fundamentally?" Als Teil des "concurrency toolkit" gibt es zwei Proposals für die nächsten C++-Standards. Der Proposal P0233r0 für Hazard Pointers und der Proposal P0461R0 für RCU.

Wie geht's weiter?

Ich bin mir noch nicht sicher. Ich überlege mir gerade das nächste große Thema, das Potenzial für mindestens 20 aufregenden Artikel besitzt. Lasse dich überraschen. ()