Herausforderungen und Fallstricke bei der Entwicklung für Multi-Core-Systeme

Vermeidung eines Data Race

Führen Entwickler das Programm wiederholt aus, treten gelegentlich Programmabbrüche auf. Auslöser ist ein sogenannter Data Race, das heißt eine Konstellation, bei der mehrere Threads auf dieselben Daten (in diesem Fall die Variable sum) zugreifen und versuchen, diese zu verändern. Die Variable sum ist als 64-Bit-Datentyp (double) implementiert.

Das Speichermodell von Java realisiert 64-Bit-Datentypen als nichtatomar, das heißt, nicht Thread-sicher, da eine Schreiboperation des Werts in zwei Schritten erfolgt, eine für jede 32-Bit-Hälfte. Hierdurch kann ein Zustand entstehen, bei dem ein Thread einen 64-Bit-Wert liest, bei dem die erste 32-Bit-Hälfte durch einen anderen Thread bereits verändert wurde, die zweite Hälfte jedoch noch nicht (siehe hierzu Java Language Specification).

Abhilfe kann hier unter anderem die Kennzeichnung der Variable als volatile schaffen. Für die mit volatile gekennzeichneten 64-Bit-Variablen (wie double und long) stellt die Java-Laufzeitumgebung sicher, dass Schreibvorgänge stets Thread-sicher sind und andere Threads immer nur vollständig (über beide 32-Bit-Hälften) geschriebene Werte sehen. Wird volatile bei folgendem Beispiel eingeführt, läuft die Anwendung stabil ohne Programmabbrüche durch, was jedoch mit einer deutlich längeren Laufzeit einhergeht.

class Data {
...
volatile double sum;
}

Die Ergebnisausgabe des Programms zeigt allerdings nach jeder Programmausführung unterschiedliche Ergebnisse an. Das korrekte Ergebnis von 100 Millionen fehlt. Grund ist die Berechnung der Summe: Dabei kommt es zu einer sogenannten Race Condition. Das heißt, das Ergebnis ist abhängig von der zeitlichen Reihenfolge, in der die Threads die Einzeloperationen ausführen.

Die Summenberechnung besteht aus drei Einzeloperationen: Einlesen der alten Summe, Addieren der Summe mit dem jeweiligen Wert aus dem Array und schließlich dem Speichern der neuen Summe. Die zeitliche Abfolge, um diese Operationen über mehrere Threads abzuarbeiten, ist zufällig und nicht deterministisch. Entsprechend kann es zu Fehlern bei der Berechnung kommen, wie Abbildung 5 zeigt.

Race Condition bei Summenberechnung (Abb. 5) (Bild: Volkswagen AG)

Synchronisation des kritischen Abschnitts

Um das Race-Condition-Problem bei der Summenberechnung zu lösen, gibt es in Java die Möglichkeit, Methoden als synchronized zu kennzeichnen. Dabei ist sichergestellt, dass sie immer nur ein Thread zur Zeit ausführt. Alle anderen Threads müssen warten, bis ein ausführender Thread die Methode wieder verlassen hat. Für die Umsetzung wird die Summenberechnung in die synchronisierte Methode increaseSum der Klasse Data verschoben (nächstes Codebeispiel). So lässt sich das Data-Race-Problem aus dem vorhergehenden Abschnitt gleich mit lösen. Auf das Schlüsselwort volatile kann in diesem Fall verzichtet werden.

class Data {
double[] array;
double sum;
Data(double[] array) { this.array = array; }
public synchronized void increaseSum(double i) {
sum += i;
}
}
class Summation extends Thread {
Data data;
int start, end;
Summation (Data data, int start, int end) {
this.data = data;
this.start = start;
this.end = end;
}
@Override
public void run() {
for (int i = start; i < end; i++) {
data.increaseSum(data.array[i]);
}
}
}

Bei erneutem Ausführen des Programms wird das korrekte Ergebnis reproduzierbar ausgegeben. Allerdings liegt die Laufzeit für zwei Threads bei circa 5000 Millisekunden und damit um mehr als eine Größenordnung höher als bei der nicht synchronisierten Variante im ersten Codebeispiel. Die letzte Codeversion verdeutlicht, dass die Synchronisation große Einbußen bei der Performance nach sich zieht, weil die benötigte Logik zur Summenberechnung um ein Vielfaches komplexer ist.

Beim Aufruf einer synchronisierten Methode wird eine Sperre auf dem Objekt gesetzt beziehungsweise beim Verlassen der Methode zurückgesetzt. Ist die Methode bereits gesperrt, wird der aufrufende Thread blockiert. Neben der eigentlichen Berechnung der Summe erfolgt im Beispiel somit auch der Aufruf dieses Synchronisationsmechanismus 100 Millionen Mal.

Zugriff auf gemeinsam genutzte Daten reduzieren

Der zweite Lösungsansatz vereint die Vorteile des ersten (hohe parallele Effizienz) und vierten Codebeispiels (Vermeidung von Race Conditions). Dazu ist der Zugriff auf gemeinsam durch beide Threads genutzte Daten deutlich zu reduzieren. Das folgende Listing führt innerhalb der Summenberechnung eine lokale Variable sum ein, die nur vom jeweiligen Thread verwendet wird. Das heißt, die Threads arbeiten zur Berechnung auf eigenen Daten und erst nach Abschluss der Iteration erfolgt die Addition der beiden Teilsummen. Nur dieser letzte Schritt erfordert eine Synchronisation. Bei einer erneuten Ausführung des Programmcodes für ein Array mit 100 Millionen Einträgen und zwei Threads, ist das korrekte Ergebnis reproduzierbar bei einer Laufzeit von circa 200 Millisekunden erreicht.

class Summation extends Thread {
Data data;
int start, end;
Summation (Data data, int start, int end) {
this.data = data;
this.start = start;
this.end = end;
}
@Override
public void run() {
double sum = 0.0;
for (int i = start; i < end; i++) {
sum += data.array[i];
}
data.increaseSum(sum);
}
}