Wofür sind Speichermodelle in Programmiersprachen gut?

von Hubert Schmid vom 2013-01-06

Früher waren Speichermodelle in Programmiersprachen kein großes Thema. Die erste Sprache mit signifikanter Verbreitung und definiertem Speichermodell war Java. Der erste Wurf von 1995 enthielt allerdings zahlreiche Fehler, und erst seit 2004 gibt es für Java eine weithin akzeptierte Spezifikation.

Mittlerweile sieht die Welt ein wenig anders aus: Fast alle bedeutenden Programmiersprachen mit Unterstützung für parallele Ausführung auf Basis gemeinsam genutzter Speicherbereiche spezifizieren jeweils für sich ein Speichermodell. Dazu gehören neben Java insbesondere C, C++ und C#, wobei die Spezifikationen ähnlich und gerade bei C und C++ sehr eng aufeinander abgestimmt sind.

Es ist nicht direkt ersichtlich, warum Parallelisierung eine komplexe Spezifikation für Speicheroperationen erfordert. Doch häufig wird übersehen, dass die Komplexität bereits durch das Ausführungsverhalten ohne Parallelisierung entsteht. Die Klasse Sum aus folgendem Listing dient dafür als Beispiel.

class Sum {
    int value;
    Sum(int count) {
        value = 0;
        for (int i = 1; i <= count; ++i) {
            value += i;
        }
    }
}

Der Code ist sehr einfach. Im Wesentlichen werden im Konstruktor die Zahlen von 1 bis count in der Member-Variable value addiert. Der Aufruf new Sum(5).value liefert beispielsweise den Wert 15. Irgendwie ist auch klar, wie der Ablauf des Programms aussieht. Im Zweifelsfall hilft ein Blick auf den erzeugten Bytecode:

0:  aload_0
1:  invokespecial #1   // Method java/lang/Object."<init>":()V
4:  aload_0
5:  iconst_0
6:  putfield      #2   // Field value:I
9:  iconst_1
10: istore_2
11: iload_2
12: iload_1
13: if_icmpgt     32
16: aload_0
17: dup
18: getfield      #2   // Field value:I
21: iload_2
22: iadd
23: putfield      #2   // Field value:I
26: iinc          2, 1
29: goto          11
32: return

Doch das ist alles nur Illusion. Der tatsächliche Ablauf sieht anders aus, und es gibt dafür ein offensichtliches Beispiel: Im obigen Code wird die Member-Variable value beim Aufruf new Sum(5) sechsmal geschrieben und fünfmal gelesen. Es ist jedoch anzunehmen, dass der JIT für die Berechnung ein Register verwendet und nur einmal in die Speicherstelle value schreibt.

Solche Transformationen sind wichtig, da sie die Performance des Programms signifikant verbessern. Dabei ist der Compiler nicht der einzige, der Optimierungen durchführt. Auch der Prozessor und die Speicherverwaltung ändern Reihenfolgen, führen Anweisungen spekulativ aus und verzögern Schreiboperationen.

Aus Sicht des Entwicklers ist wichtig: Abgesehen von der Ausführungsgeschwindigkeit sind diese Transformationen nicht beobachtbar – das heißt die Ausführung verhält sich so, als ob tatsächlich die Anweisungen in der angegebenen Reihenfolge ausgeführt würden.

Allerdings funktioniert dieses Vorgehen nicht mehr, sobald mehrere Threads mit gemeinsam genutztem Speicher im Spiel sind. Denn ein Thread könnte beispielsweise die Speicherstellen eines anderen Threads beobachten, um damit erkennen, dass die tatsächliche Ausführung nicht mit der Reihenfolge übereinstimmt, in der die Anweisungen im Quelltext stehen.

An dieser Stelle helfen Speichermodelle: Sie geben einerseits dem Entwickler eine hinreichend deterministische Semantik an die Hand und lassen andererseits dem Compiler und Prozessor die Freiheiten für notwendige Optimierungen. Die Grundaussage ist dabei fast immer die Gleiche: Wenn das Programm keine Data-Races enthält, so gilt Sequential-Consistency – das heißt zu jeder Ausführung gibt es eine sequentielle Reihenfolge aller Speicheroperationen, die sich mit der Reihenfolge der Anweisungen jedes Threads verträgt. Eine Data-Race existiert dabei, wenn zwei Threads auf die gleiche Speicherstelle zugreifen, mindestens eine der beiden Operationen eine Schreiboperation ist, und die beiden Operationen nicht korrekt synchronisiert sind.

Ein sehr bekanntes Beispiel mit Data-Races ist das sogenannte Double-checked-Locking-Anti-Pattern, das im folgenden Listing zu sehen ist. In diesem Code existiert offensichtlich eine Data-Race, denn die Variable instance kann gleichzeitig von einem Thread gelesen und von einem anderen Thread geschrieben werden. Damit sind Aussagen über die Ausführungsreihenfolge sehr schwierig, und tatsächlich funktioniert dieser Code in vielen Fällen nicht.

class Instance { /* ... */ }

class GlobalInstance {
    private static Instance instance = null;
    public static Instance getInstance() {
        if (instance == null) { // ERROR: data race
            synchronized (GlobalInstance.class) {
                if (instance == null) {
                    instance = new Instance(); // ERROR: data race
                }
            }
        }
        return instance;
    }
}

Data-Races entstehen also durch fehlende oder falsche Synchronisation. Korrekte Synchronisation von Speicherzugriffen bedeutet vereinfacht, dass die Speicherzugriffe nicht gleichzeitig stattfinden können. Die formale Spezifikation ist komplizierter, doch praktisch sind die Unterschiede vernachlässigbar – zumindest solange man die Synchronisationsprimitve nicht missbraucht. Das folgende Listing habe ich aus einer Präsentation von Hans Boehm, und es zeigt, wie man es nicht machen sollte:

// Thread 1
x = 42;
mutex.lock();

// Thread 2
while (mutex.try_lock())
    mutex.unlock();
int y = x;

Der zweite Thread kann die Variable x erst lesen, nachdem der erste Thread mutex.lock() aufgerufen hat. Trotzdem existiert eine Data-Race, die auf die etwas ungewöhnliche und vollkommen falsche Verwendung der Synchronisationsprimitive zurückzuführen ist. Normalerweise wird ein mutex verwendet, um einen kritischen Abschnitt abzusichern. In diesem Fall wird er hingegen verwendet, um den zweiten Thread zu steuern. Das Problem daran: Die Mutex-Operationen stellen sicher, dass keine Operationen den kritischen Abschnitt verlassen. Umgekehrt können aber jederzeit Operationen außerhalb des kritischen Abschnitts in den kritischen Abschnitt verschoben werden. In diesem Fall bedeutet das konkret, dass die Variable x erst nach dem Aufruf von mutex.lock() geschrieben wird, wodurch es offensichtlich eine Data-Race gibt.

Es gibt also eine ganz einfache Richtlinie für die parallele Programmierung: Alle Operationen auf gemeinsam benutztem Speicher müssen korrekt synchronisiert werden. Dann gilt die Sequential-Consistency und die beobachtbare Ausführung des Programms verträgt sich mit der Reihenfolge der Anweisungen aller Threads.