3  Steuerung von Threads

Grundlage sind Kapitel 5 und Abschnitt 8.1.3 des Lehrbuchs (Hettel und Tran (2016))

3.1 Einführung in Steuerungsprobleme

3.1.1 Verklemmungen und andere Zustände

3.1.1.1 Definition Verklemmung (engl. “Deadlock”)

“Eine Menge von Prozessen befindet sich in einem Deadlock-Zustand, wenn jeder Prozess aus der Menge auf ein Ereignis wartet, das nur ein anderer Prozess aus der Menge auslösen kann.”1

3.1.1.2 Verhungern (engl. “Starvation”)

Ein Prozess “verhungert”, wenn er nie Zugriff auf eine Ressource erhält, die von mehreren Prozessen beansprucht wird.

3.1.1.3 Livelock (Spezialfall von Verhungern)

Eine Menge Prozessen befindet sich in einem Livelock-Zustand, wenn mindestens ein Prozess verhungert, weil die Kontrolle zwischen anderen Prozessen hin und her geht, ohne dass verhungernde Prozesse die Kontrolle jemals mehr erlangen können. (Kein Deadlock!)

3.1.2 Prioritätsinversion (Umkehr der Priorität)

Problemsituation

  • Prozess mit niedriger Priorität hat Betriebsmittel akquiriert.
  • Prozess mit hoher Priorität möchte dasselbe Betriebsmittel und wird daher blockiert.
  • Ein lange laufender Prozess mit mittlerer Priorität kannibalisiert Rechenzeit, so dass der niederpriorisierte Prozess nicht mehr drankommt.
  • Der hochpriorisierte Thread verhungert.

Lösung (eine von mehreren möglichen): Prioritätsvererbung

Die Lösung Prioritätsvererbung betrifft eine Änderung des Schedulers.

Dabei wird die Priorität des Prozesses mit ursprünglich niedriger Priorität genau dann auf die Priorität des Prozesses mit der hohen Priorität angehoben (sie wird von ihm “geerbt”), wenn der Prozess mit hoher Priorität auf das vom ursprünglich niedrig priorisierten Prozess blockierte Betriebsmittel zugreifen will.

Der mittel priorisierte Prozess kann dadurch jetzt nicht mehr zum Zug kommen. Nachdem die Konrolle an den ursprünglich hoch priorisierten Prozess abgegeben wurde, muss der ursprünglich niedrig priosierte Prozess, der die Priorität geeerbt hatte, in der Priorisierung wieder auf das ursprüngliche niedrige Niveau zurückgestuft werden.

Beispiel: Pathfinder (NASA Mars-Fahrzeug, 1996)2

  • gemeinsame Ressource: Middleware zur Datenspeicherung
  • Prozess niederer Priorität: Geo/Met Datensammlung
  • Prozess hoher Priorität: Überwachung der Middleware (Watchdog)

Bei Pathfinder wurde Prioritätsvererbung angewendet, um das aufgetretene Prioritätsinversionsproblem zu lösen.

Die Bedeutung im Java-Umfeld ist gering oder zumindest unklar, da kein spezifisches Scheduling Verfahren für JVM vorgegeben ist.

3.2 Steuerung von Threads mit synchronized

3.2.1 Steuerung durch gegenseitigen Ausschluss (synchronized)

  • gegenseitige Beeinflussung durch synchronized
  • kann auch verschachtelt sein
    • Gefahr von Verklemmung
    • kann verborgen sein (synchronized in privater Implementierung einer Methode in externer Klasse - z.B. Library)

3.2.2 Deadlock durch gegenseitiges Warten

Eine Verklemmung kann durch gegenseitiges Warten 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.

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

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

3.2.3 Vermeidung des Verklemmungsproblems

Wenn alle Threads auf die Locks in derselben numerischen Reihenfolge zugreifen (in den synchronized-Block eintreten), dann kommt es nicht zu einem Deadlock (“global ordering rule”).

synchronized (left) {
    synchronized (right) {
        //…
    }
}

Die meisten Philosophen folgen diesem Schema: left und right sind Chopstick-Objekte. Philosoph \(i\) und Philosoph \(i+1\) teilen ein Chopstick-Objekt. Für Philosoph \(i\) ist das das rechte, auf das als Zweites zugegriffen wird, für Philosoph \(i+1\) ist das das linke, auf das als Erstes zugegriffen wird.

Nur im Fall des letzten bzw. 0. Philosophs wird diese Reihenfolge umgekehrt, daher kann es zum Deadlock kommen.

3.2.4 Praxiserfahrung

“To my mind, what makes multithreaded programming difficult is not that writing it is hard, but that testing it is hard. It’s not the pitfalls that you can fall into; it’s the fact that you don’t necessarily know whether you’ve fallen into one of them.”3

3.3 Steuerung von Threads mit synchronized und einem Warteraum

3.3.1 Steuerung über Monitor (wait + notify/notifyAll)

Manchmal ist es erforderlich Threads über Ereignisse zu steuern.

Dazu dient ein der Monitor eines “Vermittlerobjekts”. Es muss lediglich von Object erben. Die beteiligten Threads kommunizieren über den Monitor dieses Vermittlers miteinander.

Ein Thread muss im Besitz des Monitors des Vermittlers sein, um die Methoden wait(), notify() und notifyAll() aufrufen zu dürfen, sonst wird eine IllegalMonitorStateException geworfen.

Diese Methoden können somit nur innerhalb von synchronized-Blöcken bzw. -Methoden verwendet werden.

Alle wartenden Threads sind in der condition queue des Locks, auch condition variable oder Warteraum genannt.

3.3.2 Monitor: Auf Bedingung warten

3.3.2.1 obj.wait()

  • Der aufrufende Thread t1 prüft das Vorhandensein einer Wartebedingung (ist in der Regel kritischer Abschnitt, daher in synchronized-Block).
  • Der aufrufende Thread t1 muss spätestens jetzt den Monitor (“Schloss”) des vermittelnden Lock-Objekts obj belegt haben.
synchronized(obj){
    ... obj.wait(); ...
}
  • Ist die Wartebedingung erfüllt, trägt sich der aufrufende Thread t1 in die Warteliste des vermittelnden Lock-Objekts obj ein.
  • Der aufrufende Thread t1 gibt den Monitor von obj wieder frei.
  • t1 wechselt in den WAITING-Zustand und bleibt so lange darin, bis ihn ein anderer Thread (im Folgenden t2) durch obj.notify() oder obj.notifyAll() weckt oder er ein t1.interrupt() erhält.

3.3.3 Monitor: Signal zum Aufwachen

3.3.3.1 obj.notifyAll()

  • Der Signal sendende Thread t2 muss den Monitor des vermittelnden Lock-Objekts obj belegt haben.
synchronized(obj){
    ... obj.notifyAll(); ...
}
  • Der Scheduler weckt alle Threads auf, die im Warteraum von obj warten (neuer Zustand RUNNABLE).
  • Ein wieder aktivierter Thread schließt zunächst das Schloss obj wieder, bevor er mit den Anweisungen nach wait() fortfährt. Daher kann nur einer der wartenden Threads fortfahren, obwohl alle aufgeweckt wurden.

3.3.3.2 obj.notify()

  • Der Signal sendende Thread t2 muss den Monitor des vermittelnden Lock-Objekts obj belegt haben.
synchronized(obj){
    ... obj.notify(); ...
}
  • Der Scheduler wählt einen Thread aus, der im Warteraum von obj wartet, und weckt ihn auf (neuer Zustand RUNNABLE).
  • Dieser aktivierter Thread schließt zunächst das Schloss obj wieder, bevor er mit den Anweisungen nach wait() fortfährt.

3.3.4 Benutzungsmuster (idiomatischer Gebrauch von wait + notify/notifyAll)

synchronized(obj) {
    while (/* «Wartebedingung» */) {
        obj.wait();
    }
    /* «Benutzung geteilter Ressourcen» */
    obj.notifyAll();
}
  • while: Falls in der Zwischenzeit die Bedingung wieder eingetreten ist oder der Thread “fehlerhaft” geweckt wurde; if statt while wäre hier ein Fehler!
  • notifyAll: Falls mehrere Threads auf unterschiedliche Bedingungen an obj warten, muss zum Signalisieren immer notifyAll() benutzt werden!

Andernfalls kann es bei einem Interrupt dazu kommen, dass die Wirkung von notify() verlorengeht (falls ein Thread geweckt wird, der gerade auf eine noch nicht realisierte Bedingung wartet). Ein Deadlock wäre dadurch möglich.

3.3.4.1 Gegenseitiger Ausschluss mit synchronized und Interrupts

Wird ein Thread, der aufgrund eines sleep-, join- oder wait-Aufruf blockiert wurde, durch interrupt geweckt, wird eine InterruptedException geworfen und das Interrupt-Flag wird gelöscht. Dagegen gibt es keine Ausnahme, wenn der Thread bei synchronized auf die Freigabe der Sperre wartet. Zu beachten ist, dass der Thread ggf. die Sperre erlangen muss, bevor der catch-Block ausgeführt wird.

synchronized(this) {
    while (/* «Wartebedingung» */) {
        try {
            wait();
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
    }
}

/* «Behandlung des Interrupts» */ wird also nicht ausgeführt, solange andere Threads den Monitor von this besitzen.

3.4 Steuerung von Threads mit mehreren Bedingungsvariablen

3.4.1 Bedingungsvariablen

  • Eine Bedingungsvariable ist immer implizit bei synchronized vorhanden, auf der wait()/notify() bzw. notifyAll() ausgeführt werden kann.
  • Es gibt aber Anwendungen mit mehreren voneinander getrennten Bedingungen (z.B. “leer” und “voll” bei der Ringspeicher-Beispielaufgabe). Wenn immer alle Threads mit notifyAll() aufgeweckt werden, kann es sein, dass Verarbeitungskapazizät vergeudet wird. Mit Condition können mehrere getrennte “Warteräume” etabliert werden.
  • Deshalb ist es seit dem JDK 1.5 möglich, mehrere Bedingungsvariablen (Interface Condition aus dem Package java.util.concurrent.locks) in einem “Monitor” zu verwenden.
  • Statt synchronized muss dann aber das Interface Lock aus dem Package java.util.concurrent.locks benutzt werden, um den Monitor zu begrenzen.

3.4.2 Benutzungsmuster (idiomatischer Gebrauch von Lock)

Der Abschnitt zwischen lock.lock() und lock.unlock() ist ein im gegenseitigen Ausschluss über den Monitor lock geschützter kritischer Abschnitt. Das Paar lock.lock() und lock.unlock() wirkt also wie ein wie synchronized(lock)-Block. Nur der Thread, der den Lock veranlasst, kann ihn wieder lösen.

import java.util.concurrent.locks.ReentrantLock;

ReentrantLock lock = new ReentrantLock();
lock.lock();
try {
    /* «Benutzung geteilter Ressourcen» */
} finally {
    lock.unlock();
}

Der finally-Block am Ende wird verwendet, damit sichergestellt ist, dass der Lock auch im Fehlerfall wieder freigegeben wird.

3.4.3 Benutzungsmuster (idiomatischer Gebrauch von Condition)

Im Gegensatz zu synchronized sind lock() und unlock() keine Schlüsselwörter der Programmiersprache Java, sondern es handelt sich um Methoden, die im Lock-Interface spezifiziert sind. Dieses Interface und seine Implementierung ReentrantLock werden im Kapitel 8 ausführlich vorgestellt. Hier interessiert uns nur dir Fähigkeit von Lock mit Bedingungsvariablen vom Typ Condition umzugehen.

import java.util.concurrent.locks.ReentrantLock;
import java.util.concurrent.locks.Condition;

ReentrantLock lock = new ReentrantLock();
Condition condition = lock.newCondition();
lock.lock();
try {
    while (/* «Wartebedingung» */) {
        condition.await();
    }
    /* «Benutzung geteilter Ressourcen» */
} finally {
    lock.unlock();
}

Beim Prüfen der Wartebedingung muss eine Schleife verwendet werden (und keine einmalige Fallunterscheidung mit if), falls in der Zwischenzeit die Bedingung wieder eingetreten ist oder der Thread “fehlerhaft” geweckt wurde; hier würde if in eine Fehlersituation führen.

Man könnte fälscherlicherweise annehmen, dass es eine Ausnahme darstellen würde, wenn die Bedingungen komplett getrennt sind (“mutually exclusive”): Alle Threads, die in einem Warteraum warten, wären in der Lage ihre Arbeit wieder aufzunehmen, wenn deren jeweilige Bedingung eingetroffen ist. Es wäre jedoch falsch, if statt while beim Prüfen der Bedingung zu verwenden, denn es gibt den Fall, dass der Scheduler Threads von sich aus (ohne signal/signalAll bzw. notify/notifyAll) aus dem WAITING-Zustand aufweckt (“Spurious Wakeup”). In diesem Fall würde die Bedingung, auf deren Eintreten gewartet wird, zum Zeitpunkt des Erwachens nicht vorliegen.

Im Beispiel mit dem Ringpuffer würde if daher nicht ausreichen: Alle Threads, die aufgrund von put warten, könnten zwar weiterarbeiten, wenn ein Element aus dem Puffer entnommen wird, und auch alle Threads, die wegen take an der anderen Bedingungsvariable warten, könnten weiterarbeiten, wenn wieder mindestens ein Element in den Puffer gelegt wurde. Diese beiden Bedingungen können also nie gleichzeitig eintreten – sie sind gegenseitig exklusiv (“mutually exclusive”). Damit if ausreichend wäre, müsste man sich jedoch darauf verlassen können, dass im Moment des Aufwachens die Bedingung, auf die gewartet wurde (Ringpuffer nicht mehr voll bzw. nicht mehr leer) vorliegt. Wegen “Spurious Wakeups” ist das aber nicht gegeben.

Wenn die wartenden Threads nun “bedingungsgenau” in getrennten Warteräumen (für mehrere Bedingungsvariablen) verweilen, kann signal() statt signalAll() zum Aufwecken benutzt werden, da sichergestellt ist, dass ein zufällig ausgewählter aufgeweckter Thread eine Situation vorfindet, in der die Bedingung, auf die gewartet wurde, erfüllt ist.

Würden mehrere Threads auf unterschiedliche inhaltliche Bedingungen in demselben Warteraum warten, könnte es sein, dass ein Thread geweckt wird, der auf eine Bedingung wartet, die noch nicht eingetreten ist – er ruft daher await() für sich auf. Damit wären alle Threads dann im Zustand WAITING und es gäbe keine Möglichkeit, dass einer andere wecken könnte.

3.4.4 Das Interface java.util.concurrent.locks.Condition

import java.util.Date;
import java.util.concurrent.TimeUnit;

public interface Condition {
    public void await()  throws InterruptedException; // analog wait()
    public void awaitUninterruptibly();
    public long awaitNanos(long nanos) throws InterruptedException;
    public boolean await(long time, TimeUnit unit) throws InterruptedException;
    public boolean awaitUntil(Date deadline) throws InterruptedException;

    public void signal();      // analog notify()
    public void signalAll();   // analog notifyAll()
}
  • Condition gehört immer zu einem Lock-Objekt.
  • Das Lock-Objekt muss “geschlossen” sein, damit ein Condition-Objekt daraus erzeugt werden kann.
  • await():
    Der aufrufende Thread wird in den Zustand WAITING versetzt. Das Lock-Objekt wird wieder freigegeben. Thread wird geweckt, wenn…
    • Anderer Thread ruft signal() an der Condition-Instanz auf und der Thread wird vom Scheduler als nächster ausgewählt.
    • Anderer Thread ruft signalAll() der Bedingungsvariablen auf.
    • interrupt() in dem wartenden Thread.
    • Der Thread wird fälschlicherweise geweckt (“spurious wakeup”) - u.a. deshalb muss der Zustand der Bedingungsvariable mit while() getestet werden.