Nebenlaeufigkeit: wenn zwei Threads Daten teilen

Im ersten Grad war ein Thread eine Einheit, die der Scheduler starten kann, und ein Prozess die Kiste, der der Adressraum gehoert. Jetzt wird diese Unterscheidung zum Problem. Zwei Threads in einem Prozess teilen dieselben Daten: denselben Heap, dieselben globalen Variablen, denselben Zaehler. Nichts in der Hardware hindert sie daran, ihn im selben Augenblick anzufassen, und sobald sie es tun, ist die Arithmetik, die du geschrieben hast, nicht mehr die Arithmetik, die die Maschine ausfuehrt.

Fang mit dem kleinsten moeglichen Beispiel an. Zwei Threads, jeder erhoeht einen gemeinsamen Zaehler eine Million Mal. Jeder Programmierer sagt dir, die Antwort ist 2000000. Starte das Programm und lies die Zahl.

/* counter.c */
#include <pthread.h>
#include <stdio.h>

static long counter = 0;

static void *worker(void *arg) {
  (void)arg;
  for (long i = 0; i < 1000000; i++) {
    counter = counter + 1;
  }
  return NULL;
}

int main(void) {
  pthread_t a, b;
  pthread_create(&a, NULL, worker, NULL);
  pthread_create(&b, NULL, worker, NULL);
  pthread_join(a, NULL);
  pthread_join(b, NULL);
  printf("%ld\n", counter);
  return 0;
}

/* $ gcc -O2 -pthread counter.c -o counter && ./counter
 * 2000000   <- never guaranteed
 * 1431927   <- typical instead
 */Zwei Threads, ein gemeinsamer Zaehler, keine Sperre. Uebersetzt mit gcc -O2 -pthread. Der ausgegebene Wert aendert sich von Lauf zu Lauf.

Der Schleifenkoerper sieht wie eine Aktion aus, ist aber drei: den Zaehler in ein Register lesen, eins addieren, zurueckschreiben. Ein Takt des Schedulers kann zwischen zwei beliebige davon fallen, und auf zwei Kernen wechseln sich die Threads nicht einmal ab. Hier ist die kuerzeste Reihenfolge, in der eine Erhoehung verloren geht.

counter = 0

T1  r1 <- counter     r1 = 3417
T2  r2 <- counter     r2 = 3417
T1  r1 <- r1 + 1      r1 = 3418
T2  r2 <- r2 + 1      r2 = 3418
T1  counter <- r1     counter = 3418
T2  counter <- r2     counter = 3418

T1 done.  T2 done.  counter = 3418

Beide Threads lesen 3417, beide addieren eins, beide schreiben 3418. Es gab zwei Erhoehungen, und der Zaehler hat sich um eins bewegt. Das ist eine Wettlaufsituation: das Ergebnis haengt von der Reihenfolge ab, die der Scheduler zufaellig gewaehlt hat, nicht vom Programm. Bei einem echten Lauf des Programms oben kommen etwa 1,4 Millionen statt 2 Millionen heraus, und jedes Mal eine andere Zahl. Der Fehler ist nicht selten und kein zufaelliges Rauschen. Er ist eine zwingende Folge einer Verschraenkung, die du nicht kontrolliert hast.

Derselbe Verlust passiert ueberall, wo das Muster lesen - aendern - schreiben auftritt: ein Kontostand, ein Referenzzaehler, ein an eine Liste angefuegtes Element, ein Zaehler offener Verbindungen. Wichtig ist nicht der Operator. Wichtig ist, ob der Wert in zwei getrennten Schritten gelesen und zurueckgeschrieben wird, zwischen die ein anderer Thread rutschen kann.

Fuer einen einzelnen Zaehler gibt es eine leichtere Antwort. Prozessoren haben atomare Befehle zum Lesen-Aendern-Schreiben (lock xadd auf x86, ldrex und strex auf ARM), und der Compiler legt sie als atomare Operationen offen. Kein Sperrobjekt, kein wartender Thread, kein separater kritischer Abschnitt.

atomic_long counter = 0;

void *worker(void *arg) {
  (void)arg;
  for (long i = 0; i < 1000000; i++) {
    atomic_fetch_add_explicit(&counter, 1, memory_order_relaxed);
  }
  return NULL;
}

/* lock xadd   -> uncontended, a few nanoseconds
 * contended   -> the cache line is ping-ponged between cores
 */

Was eine Sperre kostet, haengt vollstaendig vom Andrang ab. Ohne Andrang ist eine atomare Addition ein paar Nanosekunden und ein Erwerb und eine Freigabe eines Mutex ein paar zig Nanosekunden: ein Befehl und zwei Barrieren. Der Aerger beginnt, wenn ein zweiter Thread dieselbe Sperre will. Dann muss das Betriebssystem diesen Thread parken, und das bedeutet einen Weg in den Kernel, einen Kontextwechsel und spaeter ein Aufwecken. Das sind Mikrosekunden, nicht Nanosekunden - zwei bis drei Groessenordnungen mehr als die geschuetzte Arbeit. Ist der kritische Abschnitt zehn Befehle lang und streiten vier Threads um die Sperre, verbringt die Sperre fast die ganze Zeit damit, Threads zwischen Kernen zu schieben, und das Programm wird langsamer, wenn du Kerne hinzufuegst. Deshalb ist ein wachsender Zaehler die klassische Scheinoptimierung: die atomare Fassung skaliert, bis die Cache-Zeile zwischen den Kernen hin und her springt, und dann hoert sie damit auf.

Jetzt der unangenehme Teil: warum hat das Zaehlerprogramm deinen Test bestanden? Ein Rennen braucht eine bestimmte Verschraenkung, und Verschraenkungen sind nicht gleich wahrscheinlich. Auf einem freien Kern laufen beide Threads lange Strecken am Stueck, und das schlechte Fenster wird vielleicht einmal auf eine Million Schleifendurchlaeufe getroffen. Auf einer ausgelasteten Maschine, mit angehaengtem Debugger oder im Betrieb unter Last wird dieses Fenster staendig getroffen. Also besteht der Test auf dem Laptop und der Vorfall passiert auf einem Server mit 32 Kernen. Fehler der Nebenlaeufigkeit haengen vom Zeitverlauf ab, deshalb ist das Ausbleiben eines Fehlers kein Beweis fuer Korrektheit. Schlimmer noch: eine zur Untersuchung eingefuegte Ausgabe kann den Zeitverlauf so weit aendern, dass der Fehler ganz verschwindet.

Die ehrliche Zusammenfassung: Menschen sind darin schlecht, und der Grund ist konkret. Ueber ein sequenzielles Programm nachzudenken heisst, einem Pfad zu folgen. Ueber zwei Threads nachzudenken heisst, ueber die Menge aller Verschraenkungen nachzudenken, und ihre Anzahl waechst kombinatorisch mit der Laenge des Codes. Niemand hat diese Menge im Kopf. Deshalb ist die praktische Antwort nicht, vorsichtig zu sein, sondern die Flaeche zu verkleinern: halte gemeinsam veraenderlichen Zustand so klein wie moeglich, bevorzuge unveraenderliche Daten zwischen Threads, ersetze gemeinsamen Speicher wo moeglich durch eine Nachrichtenwarteschlange und nimm eine Sperre nur um die wenigen Befehle, die sie wirklich brauchen. Wo die Invariante nicht offensichtlich zu machen ist, muss sie aufgeschrieben und mit dafuer gebauten Werkzeugen geprueft werden - Sanitizer, Modellpruefer und Stresstests, die den Zeitverlauf bewusst variieren -, nicht mit gewoehnlichen Unit-Tests.