7 Threadsichere Container-Datenstrukturen

7.1 Container-Typen

7.1.1 Threadsicherheit von Containern

Vector, Stack, HashTable und Dictionary
- Alle öffentlichen Methoden sind synchronized.
- Locking unnötiger Overhead in Single-Threadumgebungen
- außerdem gibt es effizientere Methoden (vgl. z. B. ReadWriteLock)
java.util.Collection-Implementierungen
- sind deshalb nicht synchronisiert
- Stattdessen gibt es Wrapper-Klassen, die die nicht threadsicheren Collection-Implementierungen kapseln:

List<Person> listUnsafe = new ArrayList<>();
List<Person> listSafe = Collections.synchronizedList(listUnsafe);

Zugriffe auf die Instanz listSafe der Wrapper-Klasse werden in diesem Beispiel auf threadsichere Weise an die gewrappte Instanz der threadunsicheren Klasse ArrayList “durchgereicht”.

7.1.2 Collection Interfaces

7.1.3 Listenimplementierungen

bei ArrayList:

das am Ende Einfügen ist sehr unaufwändig (O(1)), außer wenn das Array bereits voll ist. Dann muss mehr Speicher alloziiert werdenund die Elemente umkopiert werden (O(N))
Einfügen in der Mitte \(\to\) alle folgenden müssen verschoben werden (O(N))

Hettel und Tran (2016, 126, linker Teil)

7.1.4 Listenimplementierungen

bei LinkedList:

das am Ende Einfügen erfordert Itereration über die ganze Liste (O(N))
Einfügen in der Mitte \(\to\) Iteration bis dorthin, dann einfügen (O(N))

Hettel und Tran (2016, 126, rechter Teil)

7.1.5 `java.util.Collections.synchronizedXXX`

Jeder Zugriff auf eine durch synchronizedXXX erzeugte Collection/Map wird durch synchronized(this) geschützt.

nicht sehr effizient
immer die ganze Collection (oft nicht nötig)
keine Unterscheidung zwischen Lesen und Ändern
nur einzelne Methode ist synchronized, Problem bei “Transaktion” (z.B. Iterieration über Collection)

Das Ergebnis von synchronizedXXX(c) ist immer mit dem Original c “verbunden”: Wird c “direkt” geändert, kann es zu Zugriffsverletzungen kommen. Deshalb besser keine Referenz auf die Original-Collection speichern.

7.2 Threadsichere Iteration

7.2.1 Problem beim Iterieren

7.2.1.1 Zugriff über Index (“for-Schleife”)

for (var i = 0; i < list.size(); i++) {/*...*/ list.get(i) /*...*/}

nebenläufig Element aus list entfernen
- \(\to\) IndexOutOfBoundsException (am Ende)
nebenläufig Element zu list hinzufügen
- \(\to\) keine Iteration über alle Elemente
nebenläufig Element aus list ändern
- \(\to\) funktioniert

7.2.1.2 Zugriff über Iterator (oder “for-each-Schleife”/“enhanced for loop”)

for (var p : list) {/*...*/}

… identisch mit…

var it = list.iterator();
while (it.hasNext()) {
    var p = it.next();
    // ...
}

nebenläufig Element aus list ändern/entfernen oder zu list hinzufügen
\(\to\) ConcurrentModificationException

Der Iterator prüft nämlich bei jedem Schritt, ob eine nebenläufige Veränderung von list stattgefunden hat. In dem Fall wird eine ConcurrentModificationException geworfen.

7.2.2 Lösung für Threadsicheres Iterieren

Durch synchronizedCollection ist nur jeder einzelne isolierte Zugriff geschützt.

Beim Iterieren muss daher in der Regel ein “äußerer Lock” benutzt werden:

var listUnsafe = new ArrayList<Type>();
var listSafe = Collections.synchronizedCollection(listUnsafe);

synchronized (listSafe) {
    for (var e : listSafe) {
        f(e);
    }
}

Enhanced for loops (“for-each-Schleifen”) sind nur “syntaktischer Zucker” für die Anwendung von Iteratoren. Aus dem obigen Quellcode erzeugt der Compiler zuerst das Folgende:

var listUnsafe = new ArrayList<Type>();
var listSafe = Collections.synchronizedCollection(listUnsafe);

synchronized (listSafe) {
    var it = listSafe.iterator();
    while (it.hasNext()) {
        var e = it.next();
        f(e);
    }
}

Um das Werfen einer ConcurrentModificationException wegen paralleler Änderung der Collection zu verhindern, müssen andere Threads davon abgehalten werden, sie nebenläufig zu modifizieren. Daher ist der synchronized-Block um die Schleife herum erforderlich. Er sorgt dafür, dass die Schleife im gegenseitigen Ausschluss in Hinblick auf die Nutzung der Collection traversiert wird:

Ein Aufruf von listSafe.add(x) nach dem Beginn der Schleife würde also blockiert, bis die Schleife fertig abgearbeitet ist. Erst danach würde das Element x hinzugefügt werden. Daher kommt es nicht zu einer ConcurrentModificationException (bei einem der Aufrufe von next() oder hasNext()).

Würde allerdings die Änderung der zugrundeliegenden Liste über listUnsafe.add(x) erfolgen, greift der gegenseitige Ausschluss nicht. Die Liste wird nebenläufig geändert und der auf die Änderung folgende Aufruf von next() oder hasNext() resultiert in einer ConcurrentModificationException.

Diese Prinzipien gelten ebenso für die anderen Wrapper (synchronizedList, synchronizedSet, synchronizedMap, synchronizedSortedMap, synchronizedSortedSet).

7.2.3 Threadsicher über `HashMap` iterieren

var mapUnsafe = new HashMap<KeyType, ValType>();
var mapSafe = Collections.synchronizedMap(mapUnsafe);
synchronized (mapSafe) {
    for (var k : mapSafe.keySet()) {
        f(mapSafe.get(k));
    }
}

Beim Iterieren über eine Map muss die gesamte Datenstruktur gesperrt werden, da sonst während des Iterierens eine ConcurrentModificationException geworfen werden kann, wenn aus einem anderen Thread heraus die Map z.B. mit put modifiziert wird. Ohne synchronized (mapSafe) wäre nur jeder einzelne Zugriff auf mapSafe threadsicher, nicht die Gesamttransaktion (Iterieration über alle Elemente).

7.3 Selektives Locking eines Containers

7.3.1 Optimierung des Locking einer verketteten Liste durch “Hand-over-Hand Locking”

Das Hand-over-Hand Locking-Verfahren ist ein Beispiel für eine weitere Optimierung: Hier werden nur ganz selektiv die wenigen Elemente des Containers gelockt, auf die gerade zugegriffen wird. Der ganze Rest bleibt für Zugriffe anderer Threads frei. Dadurch kann bei vielen Anwendungen einer höherer Grad an Parallelität erreicht werden.

Bei einer verketteten Liste muss man bei einigen Operationen durch die Liste iterieren. Dafür muss man auf die Elemente der Liste lesend zugreifen.

Es ist nicht erforderlich, dass die gesamt Liste dafür gelockt wird.

Hier wird immer nur das eine Element gelockt, das gerade untersucht wird (1).
Beim Schritt zum nächsten Element wird kurzfristig das nächste Element mitgelockt (1,2),
dann kann der vorige Lock gelöst werden (2),
Beim Schritt zum nächsten Element wird kurzfristig das nächste Element mitgelockt (2,3),
dann kann der vorige Lock gelöst werden (3),
Beim Schritt zum nächsten Element wird kurzfristig das nächste Element mitgelockt (3,4). Nun ist die richtige Position in der Liste erreicht und das neue Element kann zwischen (3,4) eingefügt werden.

7.4 Experimentaldesign

7.4.1 Planung von Experimenten

Am Anfang steht eine Hypothese über die Wirkzusammenhänge. Man postuliert also eine Abhängigkeit zwischen Elementen einer Situation.
Dann wird ein Plan erstellt, wie die Hypothese experimentell untersucht werden kann¹.
Aus den protokollierten Beobachtungen werden schließlich Rückschlüsse auf die zu prüfende Hypothese gezogen.

Hypothese über Wirkzusammenhänge (postulieren von Abhängigkeiten zwischen Elementen der Situation)
Planung, wie die Hypothese experimentell untersucht werden kann
aus protokollierten Beobachtungen Rückschlüsse auf Hypothese ziehen

7.4.1.1 unabhängige Variable (UV)

Einflussgröße der Situation, die mehrere Ausprägungen hat.

Die Dimension einer UV kann metrisch sein (Anzahl Elemente eines Containers) oder aus einzelnen Ausprägungen ohne Ordnung und Abstand voneinander bestehen (Art der Implementierung eines Interfaces).

7.4.1.2 abhängige Variable (AV)

Messgröße, die man beobachten kann und von der man Änderungen erwartet, wenn UV variiert werden

Meistens ist die Dimension einer AV metrisch (muss aber nicht sein). Beispiele sind Ausführungszeit, Leistungsaufnahme, Temperatur, …

7.4.1.3 Experiment

systematische Variation der UV bei gleichzeitiger Beobachtung der Auswirkung auf die AV