C++: Race Conditions am laufenden Band
Mit dem Begriff Race Condition werden häufig Programmfehler assoziiert, die vom zeitlichen Verhalten abhängen, und aufgrund ihrer schlechten Reproduzierbarkeit nur schwer auffindbar sind. Doch was passiert, wenn man fortlaufend Race Conditions erzeugt? Diese Frage betrachte ich anhand eines einfachen Beispiels, das im folgenden Listing skizziert ist. Mehrere Threads inkrementieren ohne Synchronisation wiederholt eine globale Variable, und am Ende wird das Soll- und Ist-Ergebnis miteinander verglichen.
extern int global_counter;
// executed by several threads
for (int i = 0; i < N; ++i)
++global_counter;Implementierung
Die Implementierung des Beispiels ist ein wenig komplizierter als oben skizziert. Um den Eindruck nicht zu verzerren, sind in den folgenden Listings alle relevanten Teile dargestellt. Den Anfang macht die globale Zählvariable sowie die Deklaration der Funktion actual_inc, die für die Änderung verantwortlich ist, und in einer getrennten Übersetzungseinheit definiert wird, um Optimierungen des Compilers gezielt zu beschränken.
int actual = 0;
extern void actual_inc();Der eigentliche Test erfolgt durch die Funktion run. Die beiden Parameter bestimmen die Anzahl der Threads sowie die Anzahl der Schleifendurchläufe jedes Threads. Die Zählvariable wird vor dem Start der Threads noch auf 0 zurückgesetzt. Am Ende wird schließlich das Verhältnis zwischen dem tatsächlichen und dem erwarteten Ergebnis berechnet und in einem double zurückgegeben. Der Wert sagt also aus, welcher Anteil der erwarteten Updates tatsächlich sichtbar geworden ist.
double run(int concurrency, int iterations)
{
auto&& worker = [iterations] {
for (int i = 0; i < iterations; ++i)
actual_inc();
};
actual = 0;
std::vector<std::thread> threads;
for (int i = 0; i < concurrency; ++i)
threads.emplace_back(worker);
for (auto&& thread : threads)
thread.join();
int expected = concurrency * iterations;
return 1.0 * actual / expected;
}Schließlich finden sich in einer getrennten Übersetzungseinheit noch die beiden folgenden Definitionen. Die Trennung ist wichtig, denn ohne sie würde der Compiler obige Schleife fast vollständig durch eine einzelne Addition ersetzen. Dabei ist auch darauf zu achten, die sogenannten Link Time Optimizations (LTO) zu deaktivieren.
int actual = 0;
void actual_inc()
{
++actual;
}Der Test wird auf einer Intel Dual-Core CPU (Ive Bridge) ausgeführt. Entsprechend der Anzahl logischer Kerne werden vier parallele Threads verwendet (concurrency=4), und bei jeder Ausführung inkrementiert jeder Thread die Zählvariable 1 Million Mal (iterations=1'000'000). Um aussagekräftige Ergebnisse zu erzielen wird der Test 10 000 Mal wiederholt und verschiedene Quantile bestimmt.
Ergebnis
Die Implementierung enthält offensichtlich eine Data Race. Nach Sprachspezifikation ist das Ausführungsverhalten damit undefiniert und jedes Ergebnis möglich. Sieht man darüber hinweg, dann kann man sich die Frage stellen, wie stark das Ergebnis durch die fehlende Atomarität verzerrt wird.
Dass zumindest einige Inkrement-Operationen untergehen, sollte niemanden überraschen – die tatsächlich Anzahl dagegen schon: Bei vier Threads liegt der Fehler über 70% – und zwar nicht in Einzelfällen sondern bei mehr als 99% der Ausführungen.
Was kann man daraus nun lernen? Eine wichtige Regel ist, dass Data Races zu vermeiden sind. Diese Regel gilt selbst dann, wenn man Ungenauigkeiten in Kauf nehmen kann. Denn selbst in einfachsten Fällen ist der Fehler, der durch Data Races verursacht wird, untragbar groß.