2  Konkurrierender Zugriff

Grundlagen sind Kapitel 3 und 4 des Lehrbuchs (Hettel und Tran (2016))

2.1 Konkurrierender Zugriff auf Daten

Duch die parallele bzw. die überlappende Ausführung nebenläufiger Programmteile kann es zu inkonsistenten Datenzuständen kommen. Dies wird auch “data race” bzw. “race condition” genannt, da die einzelnen Programmteile wie in einem Rennen um den Zugriff auf Speicherstellen konkurrieren. In konventionellen Programmiersprachen, die mehr oder minder direkten Zugriff auf die Nebenläufigkeitskonstrukte der zugrundeliegenden Betriebssysteme liefern, ist das Erkennen und Vermeiden von “race conditions” nicht einfach und kann zu schwerwiegenden Laufzeitfehlern führen, die sich nur von Zeit zu Zeit manifestieren. Ein bekanntes Beispiel ist der medizinische Elektronenbeschleuniger Therac-25, der aufgrund eines fehlerhaften nebenläufigen Zugriffs auf eine Kontrollvariable bei sechs Patienten zwischen Juni 1985 und Januar 1987 massive teils tödliche Strahlungsüberdosierungen verursacht hat (Leveson und Turner (1993), Leveson (2017)).

Beim Design moderner und speziell auf Sicherheit ausgelegter Programmiersprachen wird diesem Aspekt besonderes Augenmerk gewidmet.

  • In Erlang ist Nebenläufigkeit völlig auf Message Passing ausgelegt. Es gibt daher keinen konkurrierenden Zugriff auf geteilte Variablen.
  • Bei Clojure gibt es aufgrund des funktionalen Designs wenig Erfordernis, geteilte Variablen zu nutzen. Falls man das doch möchte, wird man bei Atoms, Agents und Software Transactional Memory sehr gut unterstützt, Kollisionen zu behandeln.
  • Bei Rust ist es das erklärte Ziel Fehler beim konkurrierenden Zugriff bereits zur Compile-Zeit zu erkennen und damit zu verhindern. Dafür ist das Typ-System um Besitz- bzw. Verantwortungseigenschaften erweitert worden.
  • Die Programmiersprache Go hat mit den Kommunikationskanälen zwischen nebenläufigen Co-Routinen das “Communicating Sequential Processes”-Paradigma in den Fokus der Praxis zugrückgebracht. Auch wenn man in Go davon abweichen kann und direkt auf gemeinsame Variablen zugreifen kann, bieten Kanäle eine mächtige Abstraktion um “data races” zu vermeiden. Die neuere Programmiersprache Julia hat viel davon übernommen und bietet u.a. auch Kanäle an.

In Java kann man leider leicht Fehler machen und Programme entwickeln, die zu “race conditions” führen. Es gibt zwar auch “sichere” Frameworks für Java, die wir auch später im Semester behandeln werden, aber es ist unerlässlich, sich genau mit den Problemen des konkurrierenden Zugriffs (hier am Beispiel von Java) auseinanderzusetzen.

2.1.1 Java Speichermodell

  • Stack (pro Thread):
    • Parameter, die einer Methode übergeben werden
    • lokale Variablen
      • Referenzen auf Objekte (im Heap)
      • Werte von primitiven Typen
    • etwaiger Rückgabewert
  • Heap (global: für alle Threads):
    • Objekte
    • Instanzvariablen
    • Klassenvariablen (static)

Hettel und Tran (2016, 35)

Hettel und Tran (2016, 35)

Jeder Thread hat einen eigenen Stack-Speicher. Alles Threads teilen sich den Zugriff auf den Heap (Ausnahme threadlokal gespeicherte Objekte, s. Abschnitt “threadlokale Daten”).

Die folgenden “primitiven Typen” sind fest in Java eingebaut und werden anders behandelt als Objekte. Werte von lokalen Variablen dieser Typen werden direkt auf dem Stack gespeichert und nicht als Referenz auf Speicherstellen im Heap.

2.1.1.1 primitive Typen

2.1.1.1.1 boolean
  • genau zwei Ausprägungen
  • Größe im Speicher aber nicht präzise definiert
  • default-Wert: false
2.1.1.1.2 int
  • ganze Zahlen
  • 32-bit signed 2-Komplement Integer
  • Wertebereich: -231 bis +231-1
  • default-Wert: 0
  • ab Java 8: auch unsigned: 0 bis 232-1 (mit Integer.xxxUnsigned(…), vgl. z.B. Java-8 API von divideUnsigned in Integer1)
2.1.1.1.3 long
  • ganze Zahlen
  • 64-bit signed 2-Komplement Integer
  • Wertebereich: -263 bis +263-1
  • default-Wert: 0L
  • ab Java 8: auch unsigned: 0 bis 264-1 (mit Long.xxxUnsigned(…), vgl. z.B. Java-8 API-Dokumentation von divideUnsigned in Long2)
2.1.1.1.4 short
  • ganze Zahlen
  • 16-bit signed 2-Komplement Integer
  • Wertebereich: -215 bis +215-1
  • default-Wert: 0
2.1.1.1.5 byte
  • ganze Zahlen
  • 8-bit signed Integer
  • Wertebereich: -27 bis +27-1 (-128 bis 127)
  • default-Wert: 0
2.1.1.1.6 double
  • double-precision 64-bit IEEE 754 floating point
  • default-Wert: 0.0d
  • sobald mehrere Rechenschritte erfolgen nicht mehr genau \(\to\) niemals zwei double-Werte a und b direkt auf Gleichheit prüfen, sondern immer Math.abs(a-b)<0.00001 oder vergleichbar.
2.1.1.1.7 float
  • single-precision 32-bit IEEE 754 floating point
  • default-Wert: 0.0f
  • sobald mehrere Rechenschritte erfolgen nicht mehr genau \(\to\) niemals zwei float-Werte a und b direkt auf Gleichheit prüfen, sondern immer Math.abs(a-b)<0.00001 oder vergleichbar.
2.1.1.1.8 char
  • 16-bit Unicode
  • default-Wert: '\u0000'

2.1.2 Konkurrierender Zugriff

Hettel und Tran (2016, 37)

Hettel und Tran (2016, 37)

Es kann sein, dass lokale Variablen aus mehreren Threads auf dasselbe Objekt im Heap verweisen. Im Beispiel in der gezeigten Abbildung verweist jeweils die lokale Variable p in Thread 1 und Thread 2 auf dasselbe Objekt vom Typ Person mit der Instanzvariable id mit dem Wert 42 (ein Wert des primitiven Typs int), vname bzw. nname mit dem Wert Otto bzw. Meier (eigentlich eine Referenz auf ein String-Objekt, hier aber direkt als Wert (String-Literal) dargestellt).

Da beide Threads parallel arbeiten könnten, könnte es zu konkurrierenden Zugriffen auf das Person-Objekt kommen. Damit es dabei nicht zu inkonsistenten Zuständen kommt, muss der konkurrierende Zugriff auf geteilte Ressourcen (speziell Speicher bzw. Variablen) bei paralleler Programmierung speziell behandelt werden. Java bietet dazu eine Reihe von Mechanismen und eingebauten Besonderheiten des Speichermodells, die man kennen muss, um korrekt arbeitende nebenläufige Programme entwickeln zu können.

Das folgende Programm wird nun Schritt für Schritt simuliert. Dabei wird jeweils die Auswirkung auf den Speicher bildlich dargestellt.

2.1.3 Anwendung des Java Speichermodells

public class RamTest extends Thread {
    private final int i;

    public RamTest(int i) {
        this.i = i;
    }

    public void print(int i) {
        var a = i * i;
        var b = Integer.valueOf(a);
        System.out.println(b);
    }

    @Override
    public void run() {
        print(this.i);
    }

    public static void main(String... args) {
        new Thread(new RamTest(2)).start();
        new Thread(new RamTest(3)).start();
    }
}

Die Verwendung des Konstruktors von Integer (und den anderen Zahlen-Wrappern) ist deprecated. Stattdessen soll die Factory-Methode valueOf benutzt werden, um neue Instanzen zu erzeugen. Hintergrund ist, dass für denselben Zahlenwert nicht mehrere Zahlen-Objekte instanziiert werden sollen.

  • Hauptprogramm startet

Wenn das Programm startet, ist der Heap leer. Die main-Methode wird in einem eigenen Thread ausgeführt (“main Thread”). Da die Methode einen Parameter hat, wird der oben auf dem Stack des “main Thread” gespeichert. Eigentlich werden Arrays im Heap gespeichert, so dass der Wert, der auf dem Stack gespeichert wird, eine Referenz auf das Array im Heap ist. Im Beispiel werden jedoch keine Kommandozeilenparameter übergeben. Um das auszudrücken, ist das hier als Literal eines leeren Arrays dargestellt.

  • new RamTest(2) Aufruf

Der Konstruktor von RamTest wird mit dem Parameter i mit dem Wert 2 aufgerufen. Dieser Parameter wird mit seinem Wert wird oben auf dem Stack des “main Thread” abgelegt.

  • new RamTest(2) Objekterzeugung

Der Aufruf des Konstruktors erzeugt ein neues Objekt im Heap und setzt dessen Instanzvariable i auf den Wert des Konstruktor-Parameters i.

  • new RamTest(2) fertig

Der Konstruktor ist fertig und der Parameter i wird vom Stack des “main Thread” gelöscht.

  • new RamTest(2).start()

Am RamTest-Objekt wird im “main Thread” die start-Methode aufgerufen, so dass die Methode run des RamTest-Objekts beginnt, nebenläufig zu laufen. Deshalb wird ein neuer Stack für den neuen Thread erzeugt. Eine Referenz auf ` this, also dasRamTest-Objekt (erbt vonThread``), wird auf dem Stack gespeichert.

  • new RamTest(3)

Der zweite Konstruktor wird mit dem Parameter i = 3 aufgerufen, was auf dem Stack des “main Threads” abgelegt wird.

Das zweite Objekt wird erzeugt und dessen Instanzvariable auf den Wert des Konstruktor-Parameters i (auf dem Stack des “main Thread” gespeichert) gesetzt.

  • new RamTest(3).start()

Die start-Methode des neuen RamTest-Objekts wird aufgerufen, so dass ein zweiter Stack mit einer this-Referenz auf das neue Objekt erzeugt wird.

  • Hauptprogramm endet

Die main-Methode ist fertig abgearbeitet. Deshalb wird der “main Thread” beendet. Demzufolge wird der Stack dieses Threads gelöscht.

  • run() \(\to\) print(this.i)

Die run-Methoden beider Threads beginnen nun zu arbeiten. Es wird jeweils print aufgerufen. Der Parameter i dieser Methode wird auf dem jeweiligen Stack abgelegt und erhält den Wert der jeweiligen Instanzvariable des RamTest-Objekts.

  • var a = i * i (parallel)

Beide run-Methoden laufen und erzeugen eine lokale Variable namens a, die auf das Quadrat des Aufrufparameters i gesetzt wird. Die lokale Variable wird oben auf dem Stack des jeweiligen Threads gespeichert.

  • var b = Integer.valueOf(a) 2x

Beide run-Methoden erzeugen jeweils ein Integer-Objekt für die jewelige lokale Variable a und speichern eine Referenz auf das neue Integer-Objekt in der lokalen Variable b, die auf dem jeweiligen Stack gespeichert wird.

2.1.4 Zugriff auf Daten von Threads

class Counter {
3    int counter = 1;

    void set(int i) {
        this.counter = i;
    }
}

// ...

1var c = new Counter();
2var t1 = new Thread(() -> c.set(2));
var t2 = new Thread(() -> c.set(3));
t1.start();
t2.start();
t1.join();
t2.join();
4System.out.println(c.counter);
1
c ist ein Objekt im Heap.
2
Die beiden Threads t1 und t2 haben jeweils eine Referenz auf dieses Objekt im Heap (“Closure”).
3
Beide Threads greifen konkurrierend auf die Instanzvariable counter von c zu.
4
Die Ausgabe kann entweder 2 oder 3 sein. 
class Counter {
3    int counter = 1;

    void add(int i) {
        var temp = this.counter;
        temp = temp + i;
        this.counter = temp;
    }
}

// ...

1var c = new Counter();
2var t3 = new Thread(() -> c.add(3));
var t4 = new Thread(() -> c.add(4));
t3.start();
t4.start();
t3.join();
t4.join();
System.out.println(c.counter);
1
c ist ein Objekt im Heap.
2
Die beiden Threads t3 und t4 haben jeweils eine Referenz auf dieses Objekt im Heap (“Closure”).
3
Beide Threads greifen konkurrierend auf die Instanzvariable counter von c zu.
Nun ist es aber komplizierter: Die beiden Instruktionen counter = counter + 3 bzw. counter = counter + 4 bestehen tatsächlich aus mehreren Schritten, die in der Implementierung von add angedeutet ist:
  • Zuerst muss der aktuelle Wert der Instanzvariablen counter in eine (lokale) Puffervarible temp kopiert werden.
  • Dort wird die der Parameter i hinzuaddiert.
  • Das Ergebnis, das in temp gespeichert ist, wird zurück in die Instanzvariable gespeichert.

Wenn Sie nun einwenden, dass dies auch ohne den Umweg über die lokale Puffervariable temp realisiert werden kann (this.counter += i), haben Sie zwar Recht, aber man darf nicht davon ausgehen, dass diese Instruktion atomar wäre. Der Java-Compiler macht daraus im Java-Byte-Code im Class-File auch den Umweg über eine Puffervariable.

Es kann im gezeigten Beispiel u.a. zu folgenden Traces kommen, die vor allem zu einem unterschiedlichen Wert der Variablen c.counter führen:

Fall 1:

t3: temp = 1
t3: temp = 1+3
t3: c.counter = 4
t4: temp = 4
t4: temp = 4+4
t4: c.counter = 8

\(\to\) 8

Fall 2:

t3: temp = 1
t3: temp = 1+3
t4: temp = 1
t3: c.counter = 4
t4: temp = 1+4
t4: c.counter = 5

\(\to\) 5

Fall 3:

t3: temp = 1
t4: temp = 1
t3: temp = 1+3
t4: temp = 1+4
t4: c.counter = 5
t3: c.counter = 4

\(\to\) 4

2.1.4.1 Begriffe

  • Möglichkeit unterschiedlicher Traces: Race Condition (auch: Data Race)
  • kritische Abschnitte (engl. “critical regions”)

Wenn von zwei Threads aus auf denselben Speicher (hier die Instanzvariable counter) zugegriffen wird, kann es zu unterschiedlichen Zugriffssequenzen kommen. Der Ablauf ist nicht deterministisch. Es kann zu unterschiedlichen Ergebnissen kommen, je nachdem welche Ablaufsequenz passiert.

Programmabschnitte, die sich in der Abarbeitung nicht überlappen dürfen, heißen kritische Abschnitte (critical regions). Beginnt die Abarbeitung eines kritischen Abschnitts, sollte verhindert werden, dass andere kritische Abschnitte begonnen werden, die sich gegenseitig ausschließen.

  • Im vorigen Beispiel sind die Methoden set und add kritische Abschnitte.
  • Sie schließen sich gegenseitig und untereinander aus.

Je nach Anwendung kann es in Ordnung sein, dass Race Conditions existieren. Beim Beispiel mit set kann es beispielsweise nicht zu inkonsistenten Zuständen kommen.

Das Beispiel mit add zeigt aber, dass es bei Race Conditions sehr wohl zu Inkonsistenzen kommen kann. Das ist immer dann der Fall, wenn die kritische Region aus mehreren Schritten besteht. Man kann analog zu Datenbankanwendungen von einer Transaktion sprechen. Durch gegenseitigen Ausschluss muss sichergestellt werden, dass kritische Abschnitte, die Transaktionen darstellen, sich in der Ausführung nicht überlappen können.

  • gegenseitiger Ausschluss = “mutual exclusion”, verkürzt “mutex”

2.2 Memory Barriers

2.2.1 Hardware-Speichermodell und “sequentielle Konsistenz”

  • JVM arbeitet intern auf einem hardwarenäheren Speichermodell.
  • Zur Optimierung der Verschiebeoperationen von/nach Caches darf die Reihenfolge von Operationen geändert werden, wenn das keine inhaltliche Änderung bedeutet (außer eine Variable ist mit volatile gekennzeichnet).
  • Threads werden dabei aber nicht berücksichtigt.

Hettel und Tran (2016) (abgewandelt)

Hettel und Tran (2016) (abgewandelt)

2.2.2 Besonderheit des Java Speichermodells bei Nebenläufigkeit

Threads greifen immer auf eine lokale Kopie des Heaps zu!

  • enthält die transitive Hülle aller vom dem Stack referenzierten Objekte im Heap
  • lokale Heap-Kopien können untereinander abweichen
  • keine Kommunikation zwischen Threads über Variablen
  • Ausnahme volatile
    • solche Variablen verhalten sich so, als wären sie im “echten Heap” (und nicht in der gecachten Kopie)
  • Ausnahme synchronized
    • lokaler Cache wird aktualisiert:
    • “pull” beim Eintritt in synchronized-Block
    • “push” beim Ende eines synchronized-Blocks

Die Kennzeichnung einer Variable mit dem Schlüsselwort volatile und der Beginn bzw. das Ende von synchronized-Blöcken (bzw. Methoden) stellen Memory Barriers dar.

Hettel und Tran (2016, 35) (abgewandelt)

Hettel und Tran (2016, 35) (abgewandelt)

Im abgebildeten Beispiel enthält die lokal gecachte Kopie des Heaps von…

  • Thread 1: Obj1, Obj2 und Obj3
  • Thread 2: nichts
  • Thread 3: Obj2, Obj3 und Obj4
  • Thread 4: nichts

Ändert Thread 1 “seine” Version von Obj3, hat das keine Auswirkung auf Thread 3, falls synchronized oder volatile nicht benutzt werden.

Hätten sowohl Thread 1 als auch Thread 3 Referenzen auf Obj2, die beide mit volatile gekennzeichnet wären, würden sie Änderungen von Obj2 untereinander austauschen.

2.2.3 Sequentielle Konsistenz durch Memory Barrier

Folgende Fälle bilden Memory Barriers, an denen die Cache-lokalen Änderungen zwischen Threads ausgetauscht werden:

  • Zugriff auf volatile-Variablen
    Das Schreiben einer volatile-Variablen bewirkt die Synchronisierung mit allen Threads, die zu einem späteren Zeitpunkt die Variable lesen.
  • Lock-Objekte bzw. synchronized
    Eine Lock-Freigabe synchronisiert alle durchgeführten Änderungen mit allen Threads, die danach den Lock erwerben.
  • Starten eines Threads
    Alle Aktionen vor dem Starten finden vor der ersten Operation des neu gestarteten Threads statt.
  • Initialisierung
    mit Defaultwerten (0, false oder null) aller Variablen sorgt für die Synchronisierung mit dem ersten Zugriff.
  • Ende eines Threads
    bewirkt die Synchronisierung mit jeder Aktion eines auf dessen Ende wartenden Threads. Wenn z.B. ein join()-Aufruf zurückkehrt, sieht der Aufrufer alle von dem Thread gemachten Änderungen.
  • Unterbrechung
    Wenn Thread T1 Thread T2 unterbricht, wird garantiert, dass alle Threads die Unterbrechung sehen. Ein Aufruf von isInterrupted() liefert immer den aktuellen Unterbrechungsstatus.

2.2.3.1 Mehr zur Behandlung von volatile-Variablen

Der Zugriff auf volatile-Variablen hat die folgenden Eigenschaften:

  • Schreiben und Lesen von volatile-Variablen ist atomar (wird nicht durch andere Operationen anderer Threads unterbrochen.
  • Wenn Thread A eine volatile-Variable v modifiziert und Thread B sie danach liest, dann sind auch alle anderen von Thread A vor der Modifikation von vdurchgeführten Änderungen für B sichtbar (Store-Load-Barriere).
  • Zugriffe auf volatile-Variablen dürfen nicht umgeordnet werden.
  • Normale Anweisungen dürfen nicht mit Zugriffen auf volatile-Variablen vertauscht werden.

Es ist zu beachten, dass für volatile-Referenzvariablen Folgendes gilt:

  • Es wird garantiert, dass die Referenz immer aktuell und jede Änderung sichtbar ist.
  • Es wird nicht garantiert, dass der “Inhalt” des referenzierten Objekts aktuell ist.

2.3 Threadlokaler Objektspeicher

2.3.1 Threadlokale Daten

Besonderheit: threadlokaler Speicher (TLS)

  • TLS mit Heap für Objekte, die nur ein bestimmter Thread “sehen” kann.
  • nur für Objekte vom Typ T, wenn über ThreadLocal<T> erzeugt
    \(\to\) hier ist T Integer
  • sehr viel schneller als Heap, braucht nicht synchronisiert werden
public class ThreadLocalDemo {
    public static class Runner implements Runnable {
        public static ThreadLocal<Integer> mem =
            new ThreadLocal<>() {
                @Override
                protected Integer initialValue() {
                    return Integer.valueOf(1);
                }
            };
        @Override
        public void run() {
            while (true) {
                mem.set(mem.get() + 1);
            }
        }
    }
    public static void main(String... args) {
        var runnable = new Runner();
        new Thread(runnable, "Runner-1").start();
        new Thread(runnable, "Runner-2").start();
    }
}

Die Klasse ThreadLocal ist ein Wrapper, um TLS in Java bereitzustellen.

Im Beispiel wird ein Objekt einer anonymen Subklasse von ThreadLocal erzeugt, bei der die Methode initialValue überschrieben ist. Diese Methode wird am Anfang des Lebenszyklus’ von ThreadLocal-Objekten aufgerufen, um das threadlokal gespeicherte Objekt zu initialisieren.

Der Zugriff auf so gewrappte Objekte erfolgt über die Methoden get und set (s. Beispiel in run()-Methode).

2.3.2 Threadlokaler Zufallszahlengenerator

Man kann einen threadlokalen Zufallszahlengenerator abrufen. Dieser ist nicht threadsicher implementiert und damit effizienter als der “normale” Zufallszahlengenerator java.util.Random, der threadsicher implementiert ist. ThreadLocalRandom aus dem Package java.util.concurrent hat aber dieselbe Signatur wie Random:

import java.util.Random;
import java.util.concurrent.ThreadLocalRandom;

Random r = ThreadLocalRandom.current();

2.4 Gegenseitiger Ausschluss (“Mutex”)

Mutex = MUTual EXclusion (engl. für “gegenseitiger Ausschluss”)

2.4.1 synchronized-Schlüsselwort für Methoden

  • Schlüsselwort synchronized in Methoden-Signatur
public synchronized void doubler() {
    this.counter = this.counter * 2;
}
  • bewirkt gegenseitigen Ausschluss
    • nur maximal ein Thread
    • für alle synchronized-Methoden eines Objekts gemeinsam
  • keine Synchronisation von Methodenaufrufen an unterschiedlichen Objekten
  • Eintritt/Austritt in/aus synchronized-Block fungiert gleichzeitig als Memory Barrier (wichtig für Getter und Setter)

2.4.2 synchronized-Block

Intern wird zur Synchronisation der sog. Monitor-Mechanismus verwendet: In Java hat jedes Objekt einen Monitor. Der Monitor kann frei oder belegt sein.

Wird der gegenseitige Ausschluss mit synchronized verwendet und ein Thread versucht in einen so geschützten kritischen Abschnitt einzutreten, wird geprüft, ob der zugehörige Monitor frei ist.

Ist er frei, wird er durch diesen Thread belegt.

Ist er hingegen schon belegt, wird dieser Thread in den Zustand BLOCKED gebracht und in den Wartebereich des Monitors verschoben.

Verlässt der Thread, der gerade den Monitor belegt, den kritischen Abschnitt, wird der nächste Thread aus dem Wartebereich des Monitors ausgewählt, der als nächstes zurück in den Zustand RUNNING gebracht wird und in den kritischen Abschnitt eintreten darf.

Aus Efizienzgründen wird hierfür keine Warteschlange verwendet, die dafür sorgen würde, dass der am längsten wartende Thread als nächster in den kritischen Abschnitt eintreten darf. Stattdessen wird der Thread, der als nächster drankommt, zufällig ausgewählt.

  • Schlüsselwort für Methoden-Signatur ist nur “syntaktischer Zucker” für synchronized-Block
    • Monitor von this
    • über den ganzen Methodenrumpf
public void doubler() {
    // ...
    synchronized (this) {
        // ...
    }
    // ...
}
  • ermöglicht Unterscheidung
    • unterschiedliche Monitore
    • gegenseitiger Ausschluss nur für die wirklich kritischen Code-Teile und nicht den ganzen Methodenrumpf

Nur Objekte haben einen Monitor. Werte der primitiven (eingebauten) Typen können nicht als Monitor verwendet werden.

2.4.3 synchronized-Block mit anderem Objekt als Monitor

private final Object lock = new Object();

public void doubler() {
    synchronized (this.lock) {
        this.counter = this.counter * 2;
    }
}
  • Monitor (“Schlossvariable”) kann ein Objekt einer beliebigen Klasse sein, z.B. Object.
  • Muss von allen Threads “gesehen” werden können.

2.4.4 synchronized-Schlüsselwort für Klassenmethoden

  • falls die Methode static ist (Klassenmethode), wird die Klasse selber als Monitor verwendet
class C {
    static synchronized void m() {
        // work
    }
}

… ist identisch mit …

class C {
    static void m() {
        synchronized (C.class) {
            // work
        }
    }
}

2.4.5 Threadsicherheit von Vector und HashTable

  • StringBuffer, Vector und HashTable:
    • alle Methoden synchronized
  • StringBuilder, ArrayList, LinkedList, HashMap, IdentityHashMap, TreeMap
  • keine Methode synchronized
  • effizienter
  • Transaktionen (z.B. Iterieren)
    • in der Regel nicht threadsicher
private static Vector<Integer> vec = new Vector<>();
public static void main(String... args) throws InterruptedException {
    var remover = new Thread(() -> {
        for (var i = 0; i < vec.size(); i++) {
            if ((vec.get(i) % 2) == 1) {
                vec.remove(i);
            }
        }
    }, "Odd-Remover");
    var adder = new Thread(() -> {
        for (var i = 0; i < MAX; i++) {
            vec.add(i);
        }
    }, "Adder");
    remover.start();
    adder.start();
    remover.join();
    adder.join();
}

Auch wenn jeder einzelne Zugriff auf eine Methode von Vector threadsicher ist, stellen in diesem Beispiel die beiden for-Schleifen kritische Abschnitte dar, die sich gegenseitig ausschließen, da sie nebenläufig auf denselben Container zugreifen.

Um die Iterationen über die vec-Elemente threadsicher zu machen, kann das vec-Objekt als Monitor verwendet werden:

var remover = new Thread(() -> {
    synchronized (vec) {
        for (var i = 0; i < vec.size(); i++) {
            if ((vec.get(i) % 2) == 1) {
                vec.remove(i);
            }
        }
    }
}, "Odd-Remover");
var adder = new Thread(() -> {
    synchronized (vec) {
        for (var i = 0; i < MAX; i++) {
            vec.add(i);
        }
    }
}, "Adder");

2.4.6 synchronized im Sequenzdiagramm (Notation für diese LV)

public class Sync {
    private static Object l = new Object();

    public static void m1() {
        synchronized (l) {
            /* ... */
        }
    }

    public static void main(String... args) {
        var t1 = new Thread(Sync::m1); t1.start();
        var t2 = new Thread(Sync::m1); t2.start();
    }
}

Das, was hier gezeigt wird, ist eine “Privatnotation” nur für diese Lehrveranstaltung. Sie weicht auch vom Lehrbuch (Hettel und Tran (2016)) ab. Die Notation dort ist leider nicht sehr stringent.

Das folgende Sequenzdiagramm soll mit dem Quellcode oben harmonieren. Da das synchronized-Konstrukt in Sequenzdiagrammen nicht gut dargestellt werden kann, wird es hier folgendermaßen ausgedrückt:

  • Das Eintreten in einen synchronized-Block wird durch den Methodenaufruf lock() markiert.
  • Das Verlassen des synchronized-Blocks würde durch den Aufruf von unlock() gezeigt.
  • Wenn der Monitor des Lock-Objekts noch frei ist und der aufrufende Thread in den kritischen Abschnitt eintreten darf, wird das hier durch den gestrichelten return-Pfeil als Antwort auf den lock()-Aufruf angezeigt (wie beim jeweils lock()-Aufruf von t1 an l).
  • Die kurze blaue Lifeline zwischen dem lock()-Aufruf und dem return-Pfeil soll andeuten, dass der jeweilige aufrufende Thread solange blockiert ist.
  • Um anzuzeigen, dass der Monitor des Lock-Objekts zwischen dem lock()-Aufruf (konkret erst, nachdem dem Aufrufer geantwortet wurde - das ist der return-Pfeil) und dem unlock()-Aufruf belegt sind, hat er solange eine rote Lifeline.
  • lock()-Aufrufe, die auf eine rote Lifeline treffen (wie beim lock()-Aufruf von t2 an l), führen dazu, dass der Aufrufer blockiert wird, bis der return-Pfeil bei ihm ankommt.

2.4.7 Deadlock durch gegenseitiges Warten

Durch gegenseitiges Warten kann eine Verklemmung (engl. Deadlock) eintreten. Vier notwendige Kriterien müssen für eine Verklemmung zutreffen (Coffman, Elphick und Shoshani (1971)):

  1. gegenseitiger Ausschluss
  2. Belegungs- und Wartebedingung: Ein Thread, der bereits eine Sperre besitzt, darf eine weitere anfordern.
  3. Ununterbrechbarkeitsbedingung: Die von einem Thread belegte Sperre kann nur von ihm selbst wieder freigegeben werden.
    -> bis hier: Java synchronized
    ab hier: programmabhängig ->
  4. zyklische Wartebedingung: Es existiert eine zyklische Kette von zwei oder mehreren Threads, in der die Threads gegenseitig die Sperre eines anderen verlangen.

Hier folgt ein Beispielprogramm, das solch eine Deadlock-Situation durch verschachtelte synchronized-Blöcke provoziert.

public class Deadlock {
    private static Object l1 = new Object();
    private static Object l2 = new Object();
    public static void m1() {
        synchronized (l1) {
            synchronized (l2) {
                /* ... */
            }
        }
    }
    public static void m2() {
        synchronized (l2) {
            synchronized (l1) {
                /* ... */
            }
        }
    }
    public static void main(String... args) {
        var t1 = new Thread(Deadlock::m1); t1.start();
        var t2 = new Thread(Deadlock::m2); t2.start();
    }
}

Die Verklemmung des vorigen Programms kann mit den im vorigen Abschnitt eingeführten Mitteln zur Verwendung gegenseitigen Ausschlusses in UML-Sequenzdiagrammen folgendermaßen dargestellt werden: