Schrecken der Nebenläufigkeit

Das Therac-25 Disaster

Falsche Threadprogrammierung

Bilanz: drei Patienten getötet, mindestens drei schwer verletzt

Therac-25 war ein Linearbeschleuniger zur Anwendung in der Strahlentherapie. Er wurde von 1982 bis 1985 in elf Exemplaren von der kanadischen Regierungsfirma Atomic Energy of Canada Limited (AECL) gebaut und in Kliniken in den USA und in Kanada installiert. Durch Softwarefehler und mangelnde Qualitätssicherung war ein schwerer Funktionsfehler möglich, der von Juni 1985 bis 1987 drei Patienten das Leben kostete und drei weitere schwer verletzte, bevor geeignete Gegenmaßnahmen ergriffen wurden.

Dies ist einer der folgenschwersten Fehler in der Geschichte der Softwareentwicklung und ein oft studiertes Lehrbeispiel für Anforderungen an Software in sicherheitsrelevanten Bereichen.

Therac-25 war ein Elektronen-Linearbeschleuniger. Als therapeutische Strahlung, vor allem für die Krebstherapie, konnte entweder der Elektronenstrahl direkt oder die durch ein zwischengeschaltetes Target aus Wolfram erzeugte Röntgenstrahlung der Energie 25 MeV verwendet werden. Im direkten Modus wurde eine wesentliche geringere Brillanz (Stärke des Elektronenstrahls) eingestellt als im Röntgenmodus.

Die Vorgänger, Therac-6 und Therac-20, mit 6 bzw. 20 MeV Photonenenergie, waren nicht computerisierte Konstruktionen, bei denen die Sicherheitsmaßnahmen durch mechanische Verriegelung und die Überwachung der Systemfunktion durch analoge Messgeräte realisiert waren. Ein Computer des Typs PDP-11 und ein VT-100 Terminal wurden später allein zur Erleichterung der Bedienung hinzugefügt.

Die Neukonstruktion Therac-25 ersetzte diese durch Sensoren, deren Messwerte vom Computer ausgewertet wurden, und Aktoren, die unter Softwarekontrolle die verschiedenen Einstellungen ausführten. Ein Prototyp, noch ohne die Computersteuerung, wurde 1976 fertiggestellt, die erste Serienmaschine 1982. 1983 wurde eine Sicherheitsanalyse des Geräts durchgeführt, die das Vertrauen in die Überlegenheit der Softwarelösung ausdrückte, da Software keinem Verschleiß unterworfen sei.

Alle Vorfälle beruhten darauf, dass der Linearbeschleuniger mit der hohen Brillanz für den Röntgenmodus arbeitete, aber das Wolfram-Target nicht im Strahlengang war. Dies ist der gefährlichste mögliche Betriebszustand, der bei den Vorgängermodellen durch eine mechanische Verriegelung ausgeschlossen war. Die Strahlenbelastung in den sechs Fällen wurde nachträglich zu 40 bis 200 Gray abgeschätzt, eine normale Behandlung entspricht einer Dosis unter 2 Gray. Eine Strahlenbelastung des gesamten Körpers mit 10 Gray gilt als sicher tödlich, für lokalisierte Strahlenbelastungen liegen wenig Erfahrungswerte vor.

Der Computer des Therac-25 war zugleich für die Messwerterfassung und Steuerung des Geräts, als auch für die Benutzerinteraktion zuständig, durch Multitasking wurden beide Aufgaben quasi-gleichzeitig erledigt. Das Kernproblem dabei war die korrekte Synchronisation der beiden Prozesse. Unter gewissen Umständen konnte es passieren, dass nach einer Korrektur der Eingabedaten durch den Bediener vom Computer bei der Ansteuerung des Gerätes nur bei einem Teil der Daten die korrigierten Daten, bei dem anderen aber die alten Daten vor der Korrektur verwendet wurden.

Quelle: Wikipedia

Probleme der Thread-Programmierung

• Threads arbeiten im selben Adressraum, daher müssen Zugriffe auf Speicher koordiniert und geordnet erfolgen
• Thread kommunizieren über den gemeinsam genutzten Speicher, hier ist Koordination entscheidend
• Probleme im Bereich der Threads sind nur sehr schwer zu reproduzieren und treten häufig erst im Produktivsystem auf
• Parallelität und gemeinsame Speicher erfordern bestimme Sprachkonstrukte, die selbst zu neuen Problemen führen
• Menschen können nur schlecht in parallelen Abläufen denken

Threads lösen viele Probleme. Insbesondere erlauben sie, Programme deutlich schneller auszuführen. Mit Threads entstehen aber viele neue Probleme, da plötzlich parallele Aktionen auf den Speicher zugreifen. Ergreift man keine entsprechenden Maßnahmen kommt es zu Situationen, in denen nicht mehr vorhersehbar ist, was genau passiert und welchen Wert eine bestimmte Speicherstelle hat. Aus diesem Grund fließt ein großer Teil der Energie beim Programmieren mit Threads in die Schutzmaßnahmen.

Prozessor

Moderne Prozessoren bestehen aus vier Grundeinheiten:

• Die Control Unit speichert Zustände des Prozessors und ist für das Laden und Abarbeiten der Befehle zuständig.
• Die Input Output Unit verbindet den Prozessor mit dem Speicher und weiteren Peripheriegeräten.
• Die Arithmetisch-logische Einheit (ALU) führt Rechenoperationen durch.
• Die Register bieten schnellen Speicher, auf dem die ALU arbeiten kann.

An dieser Stelle sind vor allem die Register für uns wichtig, da sie mit Daten aus dem Hauptspeicher befüllt werden, um dann Berechnungen anzustellen. Dies bedeutet insbesondere, dass der Hauptspeicher nicht immer eine aktuelle Sicht auf die Daten haben kann, da sich diese in den Register geändert haben können, aber noch nicht in den Hauptspeicher geschrieben wurden.

Multicore und Caches

Die allermeisten der heute verfügbaren Prozessoren haben mehr als einen Kern und unterschiedliche Caches auf verschiedenen Ebenen. Somit ist die Frage „wo liegen die Daten?“ nicht mehr einfach zu beantworten, da Daten aus dem Hauptspeicher an unterschiedlichen Stellen abgelegt sein können:

• im Hauptspeicher selbst,
• in den Caches oder
• in den Registern des Prozessors.

An jeder dieser Stellen können die Daten in unterschiedlichen Versionen vorliegen.

NUMA - Architekturen

NUMA steht für Non Uniform Memory Access

AMD Opteron benutzt schon seit längerem eine NUMA-Architektur mit Hyper Transport als Protokoll zwischen den Prozessoren. Intel folgt aber inzwischen ebenfalls diesem Paradigma und integriert bei den aktuellen und zukünftigen Prozessoren ebenfalls den Speichercontroller in den Prozessor.

Problemklassen

• Safety Hazards – Probleme bei denen sich das Programm in Anwesenheit mehrerer Threads nicht mehr korrekt verhält
• race condition
• Liveness Hazards – Probleme bei denen ein Programm bei mehreren Threads in einen Zustand gerät, bei dem es keine Fortschritte mehr machen kann
• deadlock
• starvation
• livelock
• Performance Hazards – Probleme bei denen ein Programm zwar korrekt funktioniert, die Performance, trotz mehrerer Threads, jedoch schlecht ist

Die möglichen Probleme und Fehler, die mit Threads auftreten, kann man in drei Klassen einteilen. Während bei den Safety Hazards das Programm falsch arbeitet, bleibt es bei den Liveness Hazards einfach stehen. Nicht ganz so dramatisch sind die Performance Hazards, bei denen das Programm noch korrekt funktioniert aber nicht die gewünschte Performance zeigt.

Man unterscheidet innerhalb der einzelnen Fehlerklassen noch:

• race condition: Tritt auf, wenn sich zwei (oder mehrere) Threads ein Wettrennen liefern, z. B. beide versuchen gleichzeitig auf eine Variable zuzugreifen.
• deadlock: Threads blockieren sich gegenseitig, keiner kann mehr weiterarbeiten, weil sie wechselseitig auf Ressourcen warten, die der jeweils andere belegt hat.
• starvation: Thread verhungert, weil er nicht mehr zu Zuge kommt, z. B. weil ein anderer Thread eine Ressource belegt und nicht mehr freigibt, die der Thread benötigt.
• livelock: Thread läuft in einer Schleife, deren Abbruchbedingung nie erfüllt wird.

Beispiel: Safety Hazard (race condition)

public class SerialNumberGenerator {

    private int serienNummer = 0;

    public int naechsteNummer() {
        serienNummer++;
        return serienNummer;
    }
}

public class SerialNumberGenerator {

    private int serienNummer = 0;

    public int naechsteNummer() {

        int tmp = serienNummer;

        tmp = tmp + 1; // Thread 2

        serienNummer = tmp; // Thread 1

        return serienNummer;
    }
}

Das vorliegende Beispiel zeigt einen klassischen Safety Hazards. Die Operation serienNummer++ sieht zwar aus, wie eine einzige Aktion, besteht aber in Wirklichkeit aus drei Schritten:

1. Der Wert der Variable muss aus dem Hauptspeicher in den Operanden-Stack der VM gelesen werden (hier symbolisiert durch die Variable tmp). Denn der Prozessor kann nicht direkt auf Hauptspeicher rechnen; die Daten müssen in ein Register geladen werden, damit die ALU damit umgehen kann.
2. Der Prozessor inkrementiert den Wert auf dem Operanden-Stack (im Register) mithilfe der ALU.
3. Der Wert der Variable wird zurück in den Hauptspeicher geschrieben.

Betrachtet man die drei Schritte, wird sofort klar, dass eine race condition vorliegt. Es kann sein, dass beide Threads, die gleichzeitig Variable aus dem Hauptspeicher auf den Stack kopieren und damit denselben Wert erhalten. Somit wird eine Seriennummer doppelt vergeben.

Beispiel: Safety Hazard (check-then-act)

public class Singleton {

    private static Singleton instance;

    public static Singleton getInstance() {

        if (instance == null) { // Thread 2

            instance = new Singleton();  // Thread 1

        }

        return instance;
    }

}

Eine andere Art race condition liegt bei check-then-act vor. Hier wird eine Bedingung geprüft (check) und danach die Variable in der Bedingung verändert (act). Die Veränderung führt dann dazu, dass die Bedingung nicht mehr zutrifft.

Diese Konstruktion ist besonders anfällig für race conditions, weil die Prüfung und die Veränderung zwei getrennte Operationen sind, die nacheinander erfolgen. Somit kann es passieren, dass zwei (oder mehrere) Threads die Bedingung prüfen bevor einer von ihnen die Bedingung ändern kann. Somit treten mehrere Threads in den Rumpf der Bedingung ein, obwohl die Aktion eigentlich nur einmal ausgeführt werden sollte.

Hierdurch werden im vorliegenden Beispiel mehr als ein Objekt vom Typ Singleton erzeugt.

Beispiel: Liveness Hazard (Livelock)

class Looper implements Runnable {
    static boolean cont = true;

    public void run() {
        while (cont) {
            // mach was
        }
    }
}
public class Livelock {
    public static void main(String[] args) throws InterruptedException {
        Thread t = new Thread(new Looper());
        t.start();

        Thread.sleep(1000);
        Looper.cont = false;
    }
}

Das vorliegende Beispiel zeigt ein Livelock. Die Variable cont dient dazu, dem Thread, der Looper ausführt, zu signalisieren, dass er sich beenden soll. Die Veränderung erfolgt aus einem anderen Thread, dem Main-Thread.

Da die Variable nicht besonders gekennzeichnet ist (wir werden später noch volatile kennenlernen), wird es sehr häufig passieren, dass sie in einem Register oder einem Cache abgelegt wird. Da aber die Register pro Thread existieren können, wird die Änderung der Variable cont für den laufenden Thread gar nicht sichtbar, da der Main-Thread nur seine lokale Kopie der Variable verändert. Als Konsequenz läuft dann der Thread Looper ewig – es liegt ein Livelock vor.

Threadsafety

• Eine Klasse ist threadsicher (threadsafe), wenn sie bei der Verwendung mehrerer Threads keine der genannten Probleme zeigt
• Viele Klassen der Klassenbibliothek sind nicht threadsafe (z. B. SimpleDateFormat) und müssen explizit geschützt werden
• Unveränderliche (immutable) Objekte sind immer threadsafe
• Die meisten Collections sind nicht threadsafe, können aber mit Collections.synchronizedCollection() entsprechend verpackt werden
• Von einigen Klassen gibt es zwei Varianten (StringBuffer, StringBuilder), die eine threadsafe, die andere nicht

Wichtige Fragen bei Threads

• Atomizität (atomicity) – Welche Operationen eines Threads können von einem anderen unterbrochen werden, welche nicht?
• Reihenfolge (ordering) – In welcher Reihenfolge werden Operationen eines Threads ausgeführt?
• Sichtbarkeit (visibilitiy) – Wann werden Änderungen, die ein Thread macht, für andere Threads sichtbar?

Wenn man sich darüber Gedanken macht, ob eine Klasse threadsicher ist oder nicht, muss man sich über drei Eigenschaften von Operationen Gedanken machen:

• Atomizität: Welche Operationen sind überhaupt anfällig für Race Conditions? Hier ist wichtig, ob die Operation atomar (atomic) ist oder nicht: Ist sie atomar, wird sie entweder vollständig oder gar nicht ausgeführt. Eine Race Condition kann nicht auftreten. Ist die Operation nicht atomar, könne zwei Threads in Konflikt geraten.
• Reihenfolge: In welcher Reihenfolge werden Operationen ausgeführt? Die Reihenfolge im Quelltext entspricht auf modernen Computern nicht immer der Reihenfolge der Ausführung, daher braucht man eine Festlegung unter welchen Bedingungen die Reihenfolge beachtet wird.
• Sichtbarkeit: Wann sieht ein Thread Änderungen im Speicher? Durch Caches und Register gibt es mehrere Kopien der Daten im Speicher. Deswegen ist es wichtig zu definieren, wann eine Änderung in einer lokalen Kopie des Speichers durch einen Thread an andere Threads weitergegeben wird.

Atomare Operationen

• Eine atomare Operation kann nicht von einem anderen Thread gestört werden. Sie findet immer ganz oder gar nicht statt
• Ohne explizite Synchronisation sind nur folgende Operationen in Java atomar
• Lesen eines volatilen 32bit Feldes (byte, short, int, float, char, boolean)
• Schreiben eines volatilen 32bit Felds (byte, short, int, float, char, boolean)
• Nicht atomar sind
• Lesen oder Schreiben eines 64bit Feldes (long, double)
• Inkrementieren oder Dekrementieren eines 32bit Feldes
  int i = 0; i++;
• Es gibt spezielle Klassen, um komplexere atomare Operationen zu programmieren (java.util.concurrent.atomic.*)

Es gibt zwar einige Operationen in Java, die garantiert atomar sind, diese sind aber sehr begrenzt. So kann man zwar 32-Bit-Variablen atomar verändern aber diese Garantie reicht nicht aus, um damit threadsichere Programme zu schreiben. Bereits das Hochzählen der Variable ist nicht mehr atomar.

Ordering in Java

• Java fordert „within-thread as-if-serial“: Die Programmausführung und der Speicher müssen sich (in einem Threads) so verhalten, als ob die Instruktionen sequentiell ausgeführt würden
• Die VM darf beliebige Optimierungen machen, solange diese Bedingung erhalten bleibt

int i, k, m;                        int i, k, m;
i = 15;                             k = 18;
i++;                                i = 15;
k = 18;                             k++;
k++;                                i++;
m = i + k;                          m = i + k;

Die Java-VM darf die Reihenfolge, in der Instruktionen ausgeführt werden, beliebig ändern, solange für einen einzelnen Thread, der diese Instruktionen ausführt, keine Änderung sichtbar ist. D. h. für einen Thread fühlt es sich so an, als ob die Instruktionen seriell in der Reihenfolge des Programm-Sourcecodes ausgeführt würden (within-thread as-if-serial). Änderungen, die der Thread nicht bemerken kann, darf die VM aber beliebig ausführen.

Im vorliegenden Beispiel ist die Umsortierung für den ausführenden Thread nicht feststellbar, da auf die Variablen k und i erst bei der Zuweisung an m (m = i + k) wieder zugegriffen wird. Insofern darf die VM die Initialisierung und das Inkrementieren der Variablen in eine andere Reihenfolge bringen. Für den ausführenden Thread hat das keine Auswirkungen.

Greift aber ein anderer Thread parallel auf die Variablen zu, dann kann es passieren, dass die Umsortierung für diesen sichtbar wird, da die Garantie within-thread as-if-serial nur innerhalb eines Threads, nicht aber über Thread-Grenzen hinweg gilt. Ein Thread, der z. B. die Variablen k und i ausliest wird möglicherweise merken, dass k vor i erhöht wurde.

Was kommt hier raus?

public class PossibleReordering {

    static int x = 0, y = 0, a = 0, b = 0;

    public static void main(String[] args) throws Exception {

        Thread one = new Thread(() -> { a = 1; x = b; });
        Thread two = new Thread(() -> { b = 1; y = a; });

        one.start(); two.start();
        one.join();  two.join();

        System.out.printf("x=%d, y=%d", x, y);
    }
}

Es kann alles rauskommen

x=0, y=0
x=1, y=0
x=0, y=1
x=1, y=1

Dieses Beispiel zeigt sehr gut die Effekte, die durch das Umsortieren der Instruktionen und das Scheduling auftreten können.

Dadurch, dass nicht festgelegt ist, welcher Thread wann gescheduled wird, kann sowohl Thread 1 (one) als auch Thread 2 (two) zuerst starten. Abhängig davon, welcher Thread zuerst zum Zuge kommt, wird das die Ausgabe x=0, y=1 (Thread 1 kam zuerst dran) oder x=1, y=0 (Thread 2 kam zuerst zum Zuge) sein.

Durch das Umsortieren der Instruktionen innerhalb der Java-VM können aber noch andere Ergebnisse entstehen, nämlich x=0, y=0 und x=1, y=1. Da die Zuweisungen in den Threads (a=1, x=b) bzw. (b=1, y=a) jeweils unabhängig voneinander sind, kann die VM sie neu arrangieren zu (x=b, a=1) bzw. (y=a, b=1). Wenn jetzt ein Scheduling zwischen den Threads zwischen den Instruktionen erfolgt, können x=0, y=0 und x=1, y=1 als Ergebnis entstehen.

Das Java Memory Modell

Das Java Memory Model definiert, wie sich die Java VM bezüglich des Speichers verhalten muss

• Plattformunabhängigkeit der Sprache
• Unterschiedliches Verhalten der Plattformen (z. B. IBM vs. Intel)

Als plattformunabhängige Sprache muss Java genau spezifizieren, wie sich der Speicher bei mehreren Threads verhalten soll. Diese Spezifikation wird als Memory Model bezeichnet. Da die Spezifikation sehr komplex und nicht eingängig ist, wollen wir im Folgenden mit einem vereinfachten mentalen Modell arbeiten. Das Modell entspricht zwar nicht zu 100% der Realität, ist aber geeignet alle Effekte und Regeln zu erklären.

Prinzipiell kann man sich vorstellen, dass jeder Thread einen eigenen Speicher hat, auf dem er ausschließlich arbeitet (den Cache). Er greift also nie direkt auf den Hauptspeicher zu, sondern benutzt nur seine lokale Kopie der Daten. Wenn jetzt zwei Threads gleichzeitig auf demselben Speicher arbeiten, stellt sich die Frage zu welchem Zeitpunkt Änderungen sichtbar werden. Um dies zu spezifizieren, definieren wir zwei Operationen:

• Refresh: Der Thread lädt den Inhalt seines Caches neu aus dem Hauptspeicher, d. h. die Daten im Cache werden durch die Daten aus dem Hauptspeicher ersetzt.
• Flush: Der Thread schreibt den Inhalt seines Caches zurück in den Hauptspeicher. Danach entspricht der Hauptspeicherinhalt dem Inhalt des Caches.

Es ist offensichtlich, dass zwei Threads nur dann Daten miteinander austauschen können, wenn der eine Thread einen Flush macht und der andere danach einen Refresh. Aus diesem Grund ist es wichtig, zu definieren, wann diese Operationen erfolgen.

Garantien des Memory-Modells

• Thread-Start / Thread-Ende
• Start eines Threads → Refresh
• Ende eines Threads → Flush
• Zugriff auf volatile Variablen
• Lesen der Variable → Refresh
• Schreiben der Variable → Flush
• Synchronisation auf einem Lock
• Erhalt des Locks → Refresh
• Freigeben des Locks → Flush

Das Java-Memory-Modell definiert, wann ein Flush und wann ein Refresh erfolgen muss. Offensichtlich ist, dass beim Start eines Threads ein Refersh und bei der Beendigung ein Flush erfolgt.

Die anderen Regeln werden wir im Folgenden noch erläutern. An dieser Stelle sei noch der Zugriff auf final Instanz-Variablen erläutert.

• Ende des Konstruktors → Partieller Flush
• Erstmaliges Lesen der Variable → Partieller Refresh

Bei dem partiellen Flush einer finalen Variablen wird das Objekt auf das die Variable verweist zuzüglich aller abhängigen Objekten (Objekten die von diesem aus erreichbar sind) in den Hauptspeicher geflusht.

Bei einem partiellen Refresh einer finalen Variablen wird das Objekt auf das die Variable verweist zuzüglich aller abhängigen Objekten (Objekten die von diesem aus erreichbar sind) aus dem Hauptspeicher aufgefrischt.

Das Schlüsselwort volatile

• Die Garantien des Java Memory Models gelten nur für einen Thread, nicht aber über Threads hinweg
• volatile erweitert die Garantien für eine Variable bei mehreren Threads, die auf diese Variable zugreifen
• Ein Thread, der von einer volatile Variablen liest, sieht immer den letzten und aktuellen Wert, den ein anderer Thread hineingeschrieben hat
• Für die Java VM bedeutet das
• volatile Variablen dürfen nicht in Registern abgelegt werden
• volatile Variablen dürfen nicht anderweitig gecached werden
• volatile Variablen erzwingen eine Memory Barrier

Die Semantik von volatile erfordert sogar, dass alle anderen Variablen, die vor dem Schreiben der volatile Variablen geschrieben wurden ebenfalls für andere Threads sichtbar gemacht werden, sobald diese die volatile Variable gelesen haben, daher die Notwendigkeit einer Memory Barrier.

Man sollte trotzdem nicht zu viel auf volatile und dessen Semantik setzen, sondern eher andere Konstrukte, wie synchronized verwenden, da diese deutlich robuster sind.

Die Memory-Barrier hat dann zur Folge, dass beim Lesen der volatile-Variable ein Refresh und beim Schreiben ein Flush erfolgt.

Beispiel: volatile

class Looper implements Runnable {
    static volatile boolean cont = true;
    public void run() {
        while (cont) {
            // mach was
        }
    }
}

public class LivelockFixed {

    public static void main(String[] args) throws InterruptedException {
        Thread t = new Thread(new Looper());
        t.start();
        Thread.sleep(1000);
        Looper.cont = false;
    }
}

Durch das Hinzufügen von volatile zu boolean cont = true; verschwindet das Livelock aus dem vorhergehenden Beispiel. Jetzt sieht der Thread Looper die Änderung an der Variable durch den Main-Thread sofort.

Das Schlüsselwort synchronized

• Wie sorge ich dafür, dass ein bestimmtes Code-Segment nur von einem einzigen Thread gleichzeitig durchlaufen werden kann?
• Benötigt wird ein Mechanismus, um Bereiche sperren (to lock) zu können, sobald ein Thread eingetreten ist und andere Threads damit auszusperren (mutual exclusion, Mutex)
• Das Schlüsselwort synchronized stellt diesen zur Verfügung
• synchronized Methoden
• synchronized Blöcke
• Jedes Java-Objekt kann für die Sperre (lock) zusammen mit synchronized verwendet werden

Die Java-Spezifikation spricht davon, dass es sich bei dem Java-Mechanismus für Sperren um so genannte Monitore (monitors) handelt: „a monitor is a concurrency construct that encapsulates data and functionality for allocating and releasing shared resources (such as network connections, memory buffers, printers, and so on).“ Insofern kommt gelegentlich das Wort Monitor in der Literatur vor.

Es ist an dieser Stelle wichtig zu unterscheiden zwischen:

• Dem kritischen Abschnitt also dem Bereich des Programms, der nur von einem Thread betreten werden soll und
• der Sperre, dem Objekt, das signalisiert, ob der Abschnitt belegt ist oder nicht.

Man kann sich die Beziehung zwischen kritischem Abschnitt und Sperre wie bei einer Straßenkreuzung vorstellen: Die Kreuzung ist der Kritische Abschnitt, zu keinem Zeitpunkt sollten Fahrzeuge aus zwei unterschiedlichen Richtungen in die Kreuzung einfahren. Das Lock ist aber nicht die Kreuzung selbst, sondern die Ampel, die signalisiert, ob die Kreuzung befahren werden darf oder nicht.

In Java ist jedes Java-Objekt in der Lage als Lock zu dienen. Hierzu hat es ein spezielles, aus Java nicht lesbares, „Attribut“, das anzeigt, ob der kritische Abschnitt frei ist oder nicht.

Beispiel: Ungeschützte Klasse

public class SimpleStack {

    private Object[] stack;
    private int pos;

    public SimpleStack(int size) {
        stack = new Object[size];
        pos = 0;
    }

    public void push(Object o) {
        stack[pos++] = o;
    }

    public Object pop() {
       return stack[--pos];
    }
}

Die vorliegende Klasse ist nicht threadsicher, da sowohl die Operation stack[pos++] = o als auch stack[--pos] nicht atomar ist. Somit kann es passieren, dass Objekte auf dem Stack verloren gehen.

Beispiel: Synchronized bei Methoden

public class SimpleStack {
    private Object[] stack;
    private int pos;

    public SimpleStack(int size) {
        stack = new Object[size];
        pos = 0;
    }

    public synchronized void push(Object o) {
        stack[pos++] = o;
    }

    public synchronized Object pop() {
       return stack[--pos];
    }
}

Durch die Markierung der Methoden mit synchronized werden diese als kritische Abschnitte definiert (synchronized Methoden). Die Folge ist, dass innerhalb der Methode immer nur ein Thread sein kann. Wichtig ist an dieser Stelle zu verstehen, dass es zwei kritische Abschnitte gibt (push und pop), beide aber über ein gemeinsames Lock geschützt werden (Details folgen). Dieses Lock ist this. Deswegen kann zu einem Zeitpunkt nur ein Thread in push oder pop sein. Dies ist an dieser Stelle richtig, da es andernfalls wieder zur parallelen Veränderung des Zählers pos kommen könnte.

public class SimpleStack {
    private Object[] stack;
    private int pos;

    public SimpleStack(int size) {
        stack = new Object[size];
        pos = 0;
    }
    public void push(Object o) {
        synchronized (this) {
            stack[pos++] = o;
        }
    }
    public Object pop() {
        synchronized (this) {
            return stack[--pos];
        }
    }
}

Anstatt die Methoden mit synchronized zu markieren, kann man synchronized Blöcke verwenden. Hier gibt man das Objekt, das als Lock dienen soll, explizit an. In diesem Fall wird this verwendet. Damit ist diese Klasse äquivalent zu der vorhergehenden, denn in Java ist

synchronized void methode() {
    // Kritischer Abschnitt
}

gleichbedeutend mit

void methode() {
    synchronized (this) {
        // Kritischer Abschnitt
    }
}

Beispiel: Synchronized Blöcke

public class SimpleStack {
    private Object[] stack;  private int pos;
    private final Object lock = new Object();
    public SimpleStack(int size) {
        stack = new Object[size];
        pos = 0;
    }
    public void push(Object o) {
        synchronized (lock) {
            stack[pos++] = o;
        }
    }
    public Object pop() {
       synchronized (lock) {
           return stack[--pos];
       }
    }
}

Man kann anstatt des eigenen Objektes jedes andere Objekt in einem synchronized-Block verwenden. Hierdurch hat man die Möglichkeit, innerhalb einer Klasse verschiedene kritische Abschnitte mit unterschiedlichen Sperren zu schützen. Dies erlaubt dann, dass Threads gleichzeitig in verschiedenen kritischen Abschnitten sind, solange diese unterschiedliche Locks verwenden.

Wie funktioniert synchronized?

Grob kann man sich synchronized wie folgt vorstellen

• Jedes Objekt in Java hat ein und nur ein spezielles Token
• Ein Thread, der in den synchronized Block (oder die Methode) eintreten will, braucht das Token vom Objekt
• Das Objekt „übergibt“ dem Thread das Token
• Ein Thread, der einen synchronized-Block (oder die Methode) verlässt gibt das Token zurück an das Objekt

Es handelt sich hierbei nur um eine Verdeutlichung, wie synchronized prinzipiell funktioniert. In der konkreten VM ist die Implementierung anders als hier dargestellt.

Wie funktionieren synchronized genau?

Siehe externe Folien…

Synchronized im Zustandsdiagramm

Die Verwendung von synchronized und kritischen Abschnitten führt zu einem weiteren Zustand im Thread-Zustandsdiagramm: blockiert im Lock-Pool. Wenn ein Thread in einen kritischen Abschnitt eintreten möchte, das Lock aber nicht bekommen kann, da der Abschnitt bereits belegt ist, wird der Thread in einen speziellen Pool gelegt, den Lock-Pool. Diesen Pool gibt es für jedes Lock, sodass beim Freiwerden des Locks einfach zufällig ein Thread aus dem Pool ausgewählt werden kann und das Lock bekommt und damit in den kritischen Abschnitt eintreten kann. Auch nach Erhalt des Locks muss der Thread aber noch warten, bis der Scheduler ihn laufen lässt – insofern geht er vom Lock-Pool in den Zustand lauffähig über.

Java Locks sind reentrant

Der synchronized-Mechanismus ist reentrant

• Hat ein Thread bereits das Token eines bestimmten Objektes, kann er in alle anderen synchronized-Blöcke eintreten, die von dem Objekt geschützt werden
• Ansonsten gäbe es permanent Verklemmungen (deadlocks)

public synchronized void push(Object o) {
    stack[pos++] = o;
}

public synchronized Object pop() {
   return stack[--pos];
}

public synchronized void swap() {
    Object o1 = pop();
    Object o2 = pop();
    push(o1);
    push(o2);
}

Synchronized und das Memory Model

• synchronized impliziert eine Memory Barrier
• Alle Variablen, die ein Thread geschrieben hat, bevor er den synchronized-Block eines Monitors M verlassen hat sind für alle anderen Threads sichtbar, die einen synchronized-Block für eben diesen Monitor betreten

Die Abbildung stammt aus der Java-Spezifikation und verwendet daher den Begriff Monitor.

Das Betreten eines synchronized-Blocks führt zu einem Refresh, das Verlassen zu einem Flush. Wenn also zwei Threads einen kritischen Abschnitt benutzten, der auf demselben Lock-Objekt synchronisiert ist (nicht zwingend denselben kritischen Abschnitt), sorgt diese Regel dafür, dass der zweite Thread den Speicherzustand sieht, den der erste Thread hinterlassen hat. Alle Änderungen des ersten Threads werden also für den zweiten sichtbar.

Wie man in der Grafik sieht, geht die Garantie sogar noch weiter: Variablen, die der erste Thread verändert hat bevor er den kritischen Abschnitt betreten hat, werden für den zweiten Thread sichtbar nachdem er einen kritischen Abschnitt mit demselben Lock betreten hat.

Synchronized und Leseoperationen

Wegen der Auswirkungen auf die Sichtbarkeit von Variablen über Thread-Grenzen hinweg muss man synchronized nicht nur bei Schreib-, sondern auch bei Leseoperationen einsetzen

public synchronized void push(Object o) {
    stack[pos++] = o;
}

public synchronized Object pop() {
   return stack[--pos];
}

public Object peek() {
    return stack[pos - 1]; // FEHLER!!
}

synchronized hat also zwei Bedeutungen:

1. Es schützt kritische Abschnitte vor der parallelen Benutzung durch mehrere Threads.
2. Es sorgt über einen Flush-Refresh für die Sichtbarkeit von Änderungen im Speicher über Threadgrenzen hinweg.

Während die erste Regel eigentlich nur bei schreibenden Operationen relevant ist, führt die zweite dazu, dass man lesende Operationen mit synchronized schützen muss. Zwar benötigen diese gar nicht den Schutz von 1. würden dann aber wegen 2. auf möglicherweise veraltetem Speicher arbeiten. Denn die Garantie für die Sichtbarkeit von Speicheränderungen bezieht sich nur auf Threads die einen kritischen Abschnitt betreten, der durch dasselbe Lock geschützt ist. Gibt es keinen kritischen Abschnitt, gibt es keine Refresh und damit keine aktuellen Daten.

Aus diesem Grund ist das Beispiel falsch. Die lesende Methode peek muss ebenfalls durch ein synchronized geschützt werden, andernfalls sieht sie nicht den korrekten Zustand der Daten.

Lifelock und Synchonized

class Looper implements Runnable {
    private boolean cont = true;
    public void requestStop() { cont = false; }
    public void run() {
        while (cont) { // FEHLER!!
            // mach was
        }
    }
}
public class Livelock {
    public static void main(String[] args) throws InterruptedException {
        Looper looper = new Looper();
        Thread t = new Thread(looper);
        t.start();
        Thread.sleep(1000);
        looper.requestStop();
    }
}

class Looper implements Runnable {
    private boolean cont = true;
    public synchronized void requestStop() { cont = false;  }
    public void run() {
        while (cont) { // FEHLER!!
            // mach was
        }
    }
}
public class Livelock {
    public static void main(String[] args) throws InterruptedException {
        Looper looper = new Looper();
        Thread t = new Thread(looper);
        t.start();
        Thread.sleep(1000);
        looper.requestStop();
    }
}

class Looper implements Runnable {
    private boolean cont = true;
    public synchronized void requestStop() { cont = false; }
    private synchronized boolean cont() { return cont; }
    public void run() {
        while (cont()) {
            // mach was
        }
    }
}
public class FixedLiveLock {
    public static void main(String[] args) throws InterruptedException {
        Looper looper = new Looper();
        Thread t = new Thread(looper);
        t.start(); Thread.sleep(1000);
        looper.requestStop();
    }
}

Deadlocks

• Was passiert, wenn zwei Threads gegenseitig auf die Freigabe eines Locks durch den jeweils anderen Thread warten?
• Es kommt zur Verklemmung (deadlock) (Liveness Hazard)
• Die Threads können nicht weiterlaufen, sie blockieren sich gegenseitig
• Die VM wird die Verklemmung nicht automatisch auflösen
• Manchmal kann man einen blockierten Thread durch interrupt() wecken
• Gegenmaßnahmen
• Locks immer in derselben Reihenfolge nutzen

Der Zustand eines Deadlocks kann folgendermaßen definiert werden: Eine Menge von Threads befindet sich in einem Deadlock, wenn jeder dieser Threads auf ein Ereignis wartet, das nur ein anderer Threads aus dieser Menge verursachen kann.

Beispiel: Deadlock

class T1 implements Runnable {
    public void run() {
        synchronized (Deadlock.lock1) {
            Thread.yield();
            synchronized (Deadlock.lock2) {
            }
        }
    }
}
class T2 implements Runnable {
    public void run() {
        synchronized (Deadlock.lock2) {
            Thread.yield();
            synchronized (Deadlock.lock1) {
            }
        }
    }
}

class ClassForLock1 { /* empty */ }
class ClassForLock2 { /* empty */ }

public class Deadlock {

    public static Object lock1 = new ClassForLock1();
    public static Object lock2 = new ClassForLock2();

    public static void main(String[] args) {
        Thread t1 = new Thread(new T1());
        Thread t2 = new Thread(new T2());

        t1.start();
        t2.start();
    }
}

Tipp: Dedizierte Lock-Klassen

• Wenn ein Deadlock auftritt ist es wichtig zu wissen, welcher Thread auf welches Lock wartet
• Verwendet man Object als Klasse für die Lock-Objekte bekommt man nur dürftige Informationen
• Durch dedizierte Klassen für die Locks kann man die Fehlersuche deutlich verbessern

Die Java-VM ist in der Lage bei einem Deadlock anzuzeigen, welcher Thread auf welches Lock wartet. Hierzu dient das Werkzeug jconsole oder der Debugger von Eclipse. Hierbei ist es nützlich, wenn man den Locks sinnvolle Namen gibt, da man andernfalls nur Ausgaben der Form Object@138423 bekommt. Zu diesem Zweck benutzt man einfach statische innere Klassen, deren Namen einen Hinweis auf den Zweck des Locks gibt.

Thread Local Storage

• Der Heap wird von allen Threads gemeinsam genutzt
• Der Stack ist getrennt für die Threads
• Wie kann man Heap-Speicher für einen einzelnen Thread reservieren?
• Thread Local Storage erlaubt es, Speicher pro Thread auf dem Heap zu halten. Hierzu dient die Klasse ThreadLocal
• public Object get() – Liest die Variable aus
• public void set(Object value) – Setzt die Variable
• public void remove() – Entfernt die Daten aus dem ThreadLocal

Tatsächlich ist ThreadLocal inzwischen ein generischer Typ, sodass man nicht mehr mit Object und Casts hantieren muss. Korrekt lautet sie inzwischen:

• public T get()
• public void set(T value)
• public void remove()

Beispiel: ThreadLocal

public class Daten {
    public static final ThreadLocal<Integer> tl = new ThreadLocal<Integer>();
}

public class ThreadLocalDemo implements Runnable {

    public void run() {
        Daten.tl.set(0);

        while (true) {
            int wert = Daten.tl.get();
            Daten.tl.set(++wert);
            System.out.printf("Thread %s: Wert=%d%n",
                    Thread.currentThread().getName(), wert);
            Thread.yield();
        }
    }
}

Runnable runnable = new ThreadLocalDemo();
new Thread(runnable, "1").start();
new Thread(runnable, "2").start();

...
Thread 1: Wert=10280
Thread 2: Wert=9876
Thread 1: Wert=10281
Thread 2: Wert=9877
Thread 1: Wert=10282
Thread 2: Wert=9878
Thread 1: Wert=10283
Thread 2: Wert=9879
...

Amdahl’s Law

Der maximale Geschwindigkeitsgewinn (Speedup) durch Parallelprogrammierung wird durch Amdahl's Law nach oben begrenzt

• r_s – Nicht parallelisierbarer Anteil des Programms (sequentiell)
• r_p – Parallelisierbarer Anteil des Programms (parallel)
• n – Anzahl der Prozessoren

\[ \begin{align*} Speedup = \frac{1}{(r_s + \frac{r_p}{n})}, r_s + r_p = 1 \end{align*} \]

Quelle: Gene M. Amdahl, Validity of the single processor approach to achieve large scale computing capabilities, AFPIS spring joint computer conference, 1967

http://www-inst.eecs.berkeley.edu/~n252/paper/Amdahl.pdf