Der Zugriff auf gemeinsame Ressourcen, z.B. auf Objekte in Java, aus mehreren nebenläufigen Threads heraus, kann ohne Synchronisation zu inkonsistenten, ungewollten Zuständen führen. Dies tritt insbesondere dann auf, wenn mehrere Anweisungen im Kontrollfluss als eine atomare Aktion ausgeführt werden sollen, deren Effekt unbeeinflusst von Anweisungen sein muss, die in nebenläufigen Threads ausgeführt werden. Ähnliche Probleme treten im Umfeld von Datenbanken auf, wenn Transaktionen nicht ausreichend isoliert voneinander sind (s. ACID-Prinzip).

Race Conditions

Ein typisches Beispiel für ein Nebenläufigkeitsproblem sind sogenannte Race Conditions. Diese beschreiben in der Programmierung eine Konstellation, in der der abschließend erreichte Zustand mehrerer nebenläufig ausgeführter Anweisungen von der zeitlichen Verschränkung (engl. Interleaving) der Threads durch den Scheduler ist. Race Conditions, die während der Entwicklungszeit nicht erkannt worden sind, können später Fehler verursachen, die im Betrieb nur sehr selten auftreten und deren Ursache im Nachhinein schwer zu lokalisieren ist. Derartige Fehler scheinen nicht reproduzierbar zu sein, da sie nur bei ungünstiger Verschränkung der nebenläufigen Threads auftreten. Das Debugging von Race Conditions ist demzufolge äußerst aufwändig.

Das folgende Beispiel stellt 2 nebenläufige Threads dar, die dieselben einfachen Anweisungen ausführen. Es wird zunächst die serielle Ausführung der Threads nacheinander und anschließend eine verschränkte Ausführung abgebildet. Die am Ende erreichten Zustände unterscheiden sich, da eine potentielle Race Condition vorliegt. Im Fall der verschränkten Ausführung ist eine der beiden Zustandsänderungen an der gemeinsamen Ressource verloren gegangen. Wir sprechen von einem Lost Update.

Thread 1Thread 2Zustand der gemeinsamen Ressource
Lesen des Zustands (0)0
Verändern des Zustands (+1)0
Schreiben des Zustands (1)1
Lesen des Zustands (1)1
Verändern des Zustands (+1)1
Schreiben des Zustands (2)2
Thread 1Thread 2Zustand der gemeinsamen Ressource
Lesen des Zustands (0)0
Lesen des Zustands (0)0
Verändern des Zustands (+1)0
Verändern des Zustands (+1)0
Schreiben des Zustands (1)1
Schreiben des Zustands (1)1

Im folgenden Code-Beispiel werden 100 Threads gestartet (Zeilen 29-31), von denen jeder auf eine gemeinsame Ressource vom Typ int zugreift (Zeile 5) und diese 100x inkrementiert (Zeilen 22-24). Da die Ressource mit 0 initialisiert ist, sollte in der letzten Zeile demzufolge ein abschließend erreichter Zustand der Ressource von 100 x 100 = 10.000 ausgegeben werden. Da in dieser Implementierung aber eine Race Condition vorliegt, wird dieser Zustand praktisch i.d.R. nicht erreicht. Einige Updates der Ressource gehen verloren.

import java.util.concurrent.CountDownLatch;

class LostUpdate {

    int resource = 0; // shared resource

    // this method is the critical section
    void incrementResourceValue() {
        int t = resource;             // read resource value
        t++;                          // increment resource value
        resource = t;                 // write resource value
    }

    public static void main(String[] args) throws InterruptedException {
        new LostUpdate().runThreads(100);
    }

    void runThreads(int n) throws InterruptedException {
        CountDownLatch doneSignal = new CountDownLatch(n);

        Runnable runnable = () -> {
            for (int i = 0; i < 100; i++) { // each thread increments the resource value 100 times
                incrementResourceValue();
            }
            doneSignal.countDown(); // send a signal that this thread is completed
        };

        // start all threads
        for (int i = 0; i < n; i++) {
            new Thread(runnable).start();
        }

        // wait for all threads to complete
        doneSignal.await();

        System.out.println("Resource value = " + resource);
    }
}

Es existiert ein sogenannter kritischer Abschnitt (engl. Critical Section), indem sich nur ein Thread zurzeit befinden darf, damit keine Lost Updates auftreten. In dem obigen Code-Beispiel ist die Methode incrementResourceValue der kritische Abschnitt (Zeilen 8-12). Das Lesen, Inkrementieren und Schreiben des Zustands der Ressource muss als eine atomare Aktion ausgeführt werden und darf nicht durch eine Verschränkung der Threads unterbrochen werden. Eine naheliegende Idee ist es, den kritischen Abschnitt auf eine einzelne Anweisung zu reduzieren, z.B. indem die Methode incrementResourceValue wie folgt umgestaltet wird:

void incrementResourceValue() {
	resource++;   // read, increment, and write resource value
}

Aber auch diese äußerst einfache Anweisung ist nicht thread-safe, d.h. sie ist keine unteilbare Aktion, da sie im kompilierten Bytecode in mehrere Instruktionen zerlegt wird, die wiederum durch eine unglückliche Verschränkung nebenläufiger Threads nicht direkt nacheinander ausgeführt werden könnten. Der Bytecode der obigen Methode ist folgend dargestellt, wobei die Instruktionen der Anweisung resource++; sich von getfield bis putfield erstrecken. Der Bytecode einer kompilierten Java-Klasse, z.B. MyClass.class, lässt sich mittels javap -c MyClass.class anzeigen.

void incrementResourceValue();
    Code:
       0: aload_0
       1: dup
       2: getfield      #2                  // Field resource:I
       5: iconst_1
       6: iadd
       7: putfield      #2                  // Field resource:I
      10: return

Wechselseitiger Ausschluss für kritische Abschnitte

Das Blockieren von Threads am Anfang von kritischen Abschnitten bezeichnen wir allgemein als wechselseitigen Ausschluss (engl. Mutual Exclusion, kurz Mutex). Das Verfahren des wechselseitigen Ausschlusses lässt sich in folgende drei Phasen unterteilen:
  1. Ein Thread erlangt eine Sperre (engl. Lock) für einen kritischen Abschnitt, in dem der Zustand einer gemeinsamen Ressource verändert wird.
  2. Ein Thread durchläuft den kritischen Abschnitt und blockiert währenddessen andere Threads, die den kritischen Abschnitt in dieser Zeit ebenfalls betreten möchten.
  3. Ein Thread gibt die erlangte Sperre wieder frei und informiert die blockierten Threads darüber.

In Java muss das Schlüsselwort synchronized verwendet werden, um eine Methode oder einen beliebigen Anweisungsblock als kritischen Abschnitt zu kennzeichnen. Es gewährleistet, dass nur ein Thread gleichzeitig den kritischen Abschnitt betreten und durchlaufen darf. Erst durch die Verwendung des Schlüsselworts synchronized ist die folgende Methode tatsächlich thread-safe

.
synchronized void incrementResourceValue() {
	resource++;
}

Während sich ein Thread im kritischen Abschnitt befindet, sichert die JVM durch eine Sperre zu, dass weitere Threads am Anfang des kritischen Abschnitts blockiert werden. Dadurch wechseln die Threads ggf. aus dem Zustand Runnable in den Zustand Blocked. Eine Sperre wird in Java je Objekt gesetzt, d.h. mehrere synchronized-Methoden und -Blöcke, die sich auf dasselbe Objekt beziehen, sind nicht unabhängig voneinander, sondern teilen sich eine gemeinsame Sperre. Das folgende Code-Beispiel zeigt beispielhaft eine Klasse mit zwei synchronized-Methoden und einem synchronized-Block. Wenn ein Objekt X dieser Klasse instantiiert wird und ein Thread auf diesem Objekt X die Methode a aufruft, so kann kein anderer Thread die Methoden a, b und den synchronized-Block in Methode c betreten. Auf einem weiteren Objekt Y dieser Klasse hingegen wären dadurch keine Sperren gesetzt und die synchronized-Methoden und -Blöcke könnten weiterhin aufgerufen werden, ohne zu blockieren.

class SharedResource {

    // synchronized method
    synchronized void a() {
        // ...
    }

    // another synchronized method
    synchronized void b() {
        // ...
    }

    // method containing a synchronized block
    void c() {
        // ...
        synchronized (this) {
            // ...
        }
        // ...
    }
}

Thread-Zustände in der JVM

Das folgende UML-Zustandsdiagramm visualisiert die möglichen Zustände eines Threads innerhalb der JVM sowie die möglichen Transitionen zwischen diesen Zuständen. Sperren mittels synchronized gewährleisten den wechselseitigen Ausschluss für kritische Abschnitte und können damit Race Conditions verhindern. Die JVM versetzt die Threads ggf. automatisch in den Zustand Blocked, falls auf eine Sperre, bedingt durch synchronized, zu warten ist: "Thread is blocked for synchronization".

Java Thread States and Life Cycle

Mittels synchronized können aber keine anwendungsspezifischen Bedingungen formuliert werden. Häufig ergibt sich in der Praxis die Situation, dass ein Thread auf ein bestimmtes Ereignis warten muss, bevor er sinnvoll weiterarbeiten kann. Er soll von einem anderen Thread benachrichtigt werden können, wenn dieser das Ereignis herbeigeführt hat, das aus dem Wartezustand befreit. Der grundlegende Mechanismus für das Warten auf Benachrichtigungen von anderen Threads kann in Java über die Methoden wait und notify abgebildet werden, die in der allgemeinen Oberklasse java.lang.Object implementiert sind und damit jedem Objekt zur Verfügung stehen. Wenn ein Thread die Methode wait auf einem Objekt aufruft, wird er in den Zustand Waiting versetzt: "Thread is waiting for notification". Erst wenn ein anderer Thread die Methode notify oder die Methode notifyAll auf demselben Objekt aufruft, wird der wartende Thread wieder aus dem Wartezustand befreit und in den Zustand Runnable versetzt. Die Methode wait kann auch mit einem Timeout-Argument versehen werden. In diesem Fall wird der Thread, wie bei einem Aufruf der Methode Thread.sleep, in den Zustand Timed Waiting versetzt. Über java.lang.management.ThreadInfo kann grundsätzlich ausgewertet werden, wie viel Zeit ein Thread in welchem der Zustände verbracht hat.

Der Zustand Runnable ist in die Zustände Ready und Running untergliedert. Wenn es mehr nebenläufige Threads als Prozessoren gibt, steuert der Scheduler den Wechsel der Threads zwischen diesen Zuständen. Im Zustand Running ist einem Thread tatsächlich ein Prozessor zugewiesen, so dass der Kontrollfluss des Threads abgearbeitet werden kann. Ein Thread im Zustand Ready wartet darauf, dass der Scheduler ihm im Zuge des Interleaving einen Prozessor zuweist.

Erzeuger-Verbraucher-Problem

Die Verwendung der Methoden wait und notify lässt sich über das sogenannte Erzeuger-Verbraucher-Problem motivieren. Wir stellen uns dazu folgendes Szenario vor:

Es folgt eine beispielhafte Implementierung des Erzeuger-Verbraucher-Problems. Der Speicher ist in der Klasse BoundedBufferSync implementiert und hat hier eine Kapazität von lediglich 3 Nachrichten. Es werden in der Klasse ProducerConsumerStarter jeweils 2 Erzeuger- und Verbraucher-Threads gestartet.

class Producer extends Thread {

    BoundedBuffer buffer;

    Producer(int id, BoundedBuffer buffer) {
        super("Producer " + id);
        this.buffer = buffer;
    }

    @Override
    public void run() {
        while (true) {
            try {
                sleep(ThreadLocalRandom.current().nextInt(0, 100)); // sleep
                buffer.put(UUID.randomUUID().toString()); // put a message to the buffer
            } catch (InterruptedException e) { }
        }
    }
}
class Consumer extends Thread {

    BoundedBuffer buffer;

    Consumer(int id, BoundedBuffer buffer) {
        super("Consumer " + id);
        this.buffer = buffer;
    }

    @Override
    public void run() {
        while (true) {
            try {
                sleep(ThreadLocalRandom.current().nextInt(0, 100)); // sleep
                buffer.take(); // take a message from the buffer
            } catch (InterruptedException e) { }
        }
    }
}
interface BoundedBuffer {

    // put a new message to the buffer, waiting if necessary for space to become available
    void put(String message) throws InterruptedException;

    // retrieve and remove a message from the buffer, waiting if necessary until a new message becomes available
    String take() throws InterruptedException;
}
import java.util.Queue;
import java.util.LinkedList;	

class BoundedBufferSync implements BoundedBuffer {

    int capacity;
    Queue<String> queue = new LinkedList<>();

    BoundedBufferSync(int capacity) {
        this.capacity = capacity;
    }

    public synchronized void put(String message) throws InterruptedException {
        while (queue.size() == capacity) {
            wait();
        }
        queue.add(message);
        System.out.printf("%s: %s\t [%d messages in buffer]\n", Thread.currentThread().getName(), message, queue.size());
        notify();
    }

    public synchronized String take() throws InterruptedException {
        while (queue.isEmpty()) {
            wait();
        }
        String message = queue.poll(); // retrieves and removes head of queue
        System.out.printf("%s: %s\t [%d messages in buffer]\n", Thread.currentThread().getName(), message, queue.size());
        notify();
        return message;
    }
}
class ProducerConsumerStarter {

    public static void main(String[] args) {

        BoundedBuffer buffer = new BoundedBufferSync(3); // select bounded buffer implementation here

        for (int i = 1; i <= 2; i++) {
            new Producer(i, buffer).start();
            new Consumer(i, buffer).start();
        }
    }
}
Es ist anzumerken, dass die Methode notify nur einen zufälligen Thread aus der Menge, der aktuell auf die betroffene Sperre wartenden Threads, aus dem Wartezustand befreit. Dadurch ist keine Fairness unter den wartenden Erzeugern und Verbrauchern gewährleistet. Das folgende Beispiel widmet sich der Herausforderung faires Warten, gemäß des Prinzips einer FIFO-Warteschlange, zu realisieren. Wir stellen uns dazu eine Parkgarage mit einer beschränkten Kapazität an Stellplätzen vor. In diese Parkgarage fahren Autos ein und aus. Wenn alle Stellplätze belegt sind, müssen neu ankommende Autos an einer Schranke vor der Parkgarage in einer FIFO-Warteschlange warten. Die Parkgarage ist die gemeinsam genutzte Ressource für mehrere nebenläufige Threads. Die Autos werden als Threads implementiert, die in einer Endlosschleife folgende Aktivitäten ausführen (Zeilen 22-27 in Klasse Car):
class Car extends Thread {

    ParkingGarage garage; // shared resource

    public static void main(String[] args) {
        int places = 3;  // number of slots in parking garage
        int cars = 7;    // number of cars

        ParkingGarage garage = new UnfairParkingGarageImpl(places); // select implementation of parking garage here
        for (int i = 1; i <= cars; i++) {
            new Car("Car " + i, garage).start();
        }
    }

    public Car(String name, ParkingGarage garage) {
        super(name);
        this.garage = garage;
    }

    @Override
    public void run() {
        while (true) {
            cruise();
            garage.enter(this);
            park();
            garage.leave(this);
        }
    }

    void cruise() { idle(30); } // cruise 0 to 30 ms

    void park() { idle(100); } // cruise 0 to 100 ms

    void idle(int maxSleepTime) {
        try {
            TimeUnit.MILLISECONDS.sleep(ThreadLocalRandom.current().nextInt(0, maxSleepTime));
        }
        catch (InterruptedException e) { }
    }
}
interface ParkingGarage {

    // car which enters the parking garage
    void enter(Car car);

    // car which leaves the parking garage
    void leave(Car car);
}

Der wechselseitige Ausschluss der Threads beim Einfahren und Ausfahren der Parkgarage ist sicherzustellen, d.h. die Methoden enter und leave der gemeinsamen Ressource ParkingGarage müssen in der jeweiligen Implementierung des Interface mittels synchronized als kritische Abschnitte gekennzeichnet werden (siehe unten Zeilen 11+25 in der Klasse UnfairParkingGarage). Im folgenden Code-Beispiel werden 2 alternative Implementierungen des Interface ParkingGarage dargestellt. In der Implementierung UnfairParkingGarage benachrichtigt ein Auto, das die Parkgarage verlässt, zufällig eines der wartenden Autos vor der Schranke und ermöglicht ihm das Einfahren in die Parkgarage. Dies geschieht durch den Aufruf der Methode notify in Zeile 28. Wenn die nummerierte Ankunft an der Schranke vor der Parkgarage nicht der ebenfalls nummerierten Einfahrt in die Parkgarage entspricht – also das FIFO-Prinzip verletzt ist, wird dies durch eine Ausgabe über System.err in Zeile 20 kenntlich gemacht. Dieser Fall wird bei der Ausführung des Programms relativ selten auftreten, kann aber beobachtet werden.

Die Implementierung FairParkingGarage unterscheidet sich leicht, um die Fairness beim Warten abzubilden – insbesondere in den Zeilen 16 und 32.
class UnfairParkingGarageImpl implements ParkingGarage {
    int places;
    int arrivalCount = 0;
    int entranceCount = 0;

    UnfairParkingGarageImpl(int places) {
        this.places = places;
    }

    @Override
    public synchronized void enter(Car car) {
        int arrival = ++arrivalCount;
        while (places == 0) {
            log(car.getName() + " stops at barrier [waiting cars = " + (arrivalCount - entranceCount) + "].");
            try {
                wait();
            } catch (InterruptedException e) { }
        }
        int entrance = ++entranceCount;
        log(car.getName() + " enters parking garage [arrival = " + arrival + ", entrance = " + entrance + "].", 
            arrival == entrance ? System.out : System.err);
        places--;
    }

    @Override
    public synchronized void leave(Car car) {
        log(car.getName() + " leaves parking garage.");
        places++;
        notify();
    }

    void log(String msg, PrintStream printStream) { printStream.println(msg); }

    void log(String msg) { log(msg, System.out); }
}
class FairParkingGarageImpl implements ParkingGarage {
    int places;
    int arrivalCount = 0;
    int entranceCount = 0;

    FairParkingGarageImpl(int places) {
        this.places = places;
    }

    @Override
    public synchronized void enter(Car car) {
        int arrival = ++arrivalCount;
        if (places == 0) {
            log(car.getName() + " stops at barrier [waiting cars = " + (arrivalCount - entranceCount) + "].");
        }
        while (arrival - 1 != entranceCount || places == 0) {
            try {
                wait();
            } catch (InterruptedException e) { }
        }
        int entrance = ++entranceCount;
        log(car.getName() + " enters parking garage [arrival = " + arrival + ", entrance = " + entrance + "].", 
            arrival == entrance ? System.out : System.err);
        places--;
        notifyAll();
    }

    @Override
    public synchronized void leave(Car car) {
        log(car.getName() + " leaves parking garage.");
        places++;
        notifyAll();
    }

    void log(String msg, PrintStream printStream) { printStream.println(msg); }

    void log(String msg) { log(msg, System.out); }
}

Es stellt sich beim genauen Hinsehen die Frage, warum auch am Ende der Methode enter die Methode notifyAll aufgerufen wird (Zeile 25). Dazu müssen wir uns vorstellen, dass die Parkgarage voll belegt ist, während mehrere Autos vor der Schranke warten. Nun verlassen direkt hintereinander mehrere Autos die Parkgarage, sodass wieder einige Stellplätze frei werden. Der gemeinsame kritische Abschnitt der Methoden enter und leave sichert zu, dass während des Ausfahrens eines Autos nicht gleichzeitig ein anderes Auto einfahren kann. Anschließend gelingt es dem vordersten Auto in der Warteschlange in die Parkgarage einzufahren. Nach dem Einfahren muss es die anderen wartenden Autos mittels notifyAll benachrichtigen (Zeile 25), da noch weitere Plätze frei sind und ansonsten nicht wieder belegt werden würden.

Im Package java.util.concurrent finden wir heute lange etablierte Interfaces und Klassen, die eine entwicklerfreundlichere API für die grundlegenden Muster zur Synchronisation von Threads bieten. Dazu zählen z.B. die Interfaces Lock als Alternative zu synchronized und Condition als Alternative zu den Methoden wait, notify und notifyAll. Blockierende FIFO-Warteschlangen bieten sämtliche Implementierungen des Interface BlockingQueue. Das folgende Code-Beispiel demonstriert wie der oben dargestellte, begrenzte und blockierende Speicher in der Klasse BoundedBufferSync alternativ über Lock- und Condition-Objekte (siehe BoundedBufferLock) bzw. über eine ArrayBlockingQueue (siehe BoundedBufferBlockingQueue) realisiert werden kann.

import java.util.Queue;
import java.util.LinkedList;	

class BoundedBufferSync implements BoundedBuffer {

    int capacity;
    Queue<String> queue = new LinkedList<>();

    BoundedBufferSync(int capacity) {
        this.capacity = capacity;
    }

    public synchronized void put(String message) throws InterruptedException {
        while (queue.size() == capacity) {
            wait();
        }
        queue.add(message);
        System.out.printf("%s: %s\t [%d messages in buffer]\n", Thread.currentThread().getName(), message, queue.size());
        notify();
    }

    public synchronized String take() throws InterruptedException {
        while (queue.isEmpty()) {
            wait();
        }
        String message = queue.poll(); // retrieves and removes head of queue
        System.out.printf("%s: %s\t [%d messages in buffer]\n", Thread.currentThread().getName(), message, queue.size());
        notify();
        return message;
    }
}
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
import java.util.concurrent.locks.Condition;
// ...

class BoundedBufferLock implements BoundedBuffer {

    int capacity;
    Queue<String> queue = new LinkedList<>();

    Lock lock = new ReentrantLock();
    Condition notFull = lock.newCondition();
    Condition notEmpty = lock.newCondition();

    BoundedBufferLock(int capacity) {
        this.capacity = capacity;
    }

    public void put(String message) throws InterruptedException {
        lock.lock(); // enter critical section
        try {
            while (queue.size() == capacity) {
                notFull.await();
            }
            queue.add(message);
            System.out.printf("%s: %s\t [%d messages in buffer]\n", Thread.currentThread().getName(), message, queue.size());
            notEmpty.signal();
        } finally {
            lock.unlock();  // leave critical section
        }
    }

    public String take() throws InterruptedException {
        lock.lock(); // enter critical section
        try {
            while (queue.isEmpty()) {
                notEmpty.await();
            }
            String message = queue.poll(); // retrieves and removes head of queue
            System.out.printf("%s: %s\t [%d messages in buffer]\n", Thread.currentThread().getName(), message, queue.size());
            notFull.signal();
            return message;
        } finally {
            lock.unlock();  // leave critical section
        }
    }
}
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.ArrayBlockingQueue;

class BoundedBufferBlockingQueue implements BoundedBuffer {

    int capacity;
    BlockingQueue<String> queue;

    public BoundedBufferBlockingQueue(int capacity) {
        queue = new ArrayBlockingQueue<>(capacity);
    }

    @Override
    public void put(String message) throws InterruptedException {
        queue.put(message);
        System.out.printf("%s: %s\t [%d messages in buffer]\n", Thread.currentThread().getName(), message, queue.size());
    }

    @Override
    public String take() throws InterruptedException {
        String message = queue.take();
        System.out.printf("%s: %s\t [%d messages in buffer]\n", Thread.currentThread().getName(), message, queue.size());
        return message;
    }
}

Die gezeigten Code-Beispiele zur Synchronisation von Threads in Java finden sich im Verzeichnis /concurrency des Modul-Repository.

Deadlock und Starvation

Wenn ein Thread nicht nur eine, sondern mehrere Sperren auf exklusiv nutzbare Ressourcen anfordert, kann es zu einer Verklemmung (engl. Deadlock) zwischen den nebenläufigen Threads kommen, die um den Zugriff auf die Ressourcen konkurrieren. Ein Deadlock bezeichnet den Zustand, bei dem eine zyklische Wartekette zwischen mehreren Threads eingetreten ist, wobei jeder beteiligte Thread auf die Freigabe von Sperren auf Ressourcen wartet, die ein anderer beteiligter Thread bereits exklusiv erlangt hat. Im einfachsten Fall sind, wie in der folgenden Abbildung visualisiert, nur 2 Threads und 2 Ressourcen beteiligt.

Für einen Deadlock müssen folgende Bedingungen erfüllt sein. Wenn nur eine Bedingung aufgehoben werden kann, wird auch der Deadlock aufgelöst.
  1. Ressourcen sind nur exklusiv unter wechselseitigem Ausschluss nutzbar.
  2. Belegte Ressourcen können einem Thread nicht entzogen werden.
  3. Threads, die bereits eine Ressource belegt haben, fordern weitere an.
  4. Es entsteht eine zyklische Wartekette zwischen den Threads. Jeder Thread belegt eine Ressource, die ein anderer Thread in der Wartekette anfordert.

Zur Vermeidung von Deadlocks kann ein optimistischer oder ein pessimistischer Ansatz des Sperrens von Ressourcen verfolgt werden. Beim Optimistic Locking ist die grundlegende Annahme, dass Deadlocks aufgrund geringer Konkurrenz beim exklusiven Zugriff auf Ressourcen selten auftreten. Es wird periodisch geprüft, ob ein Deadlock eingetreten ist. Falls ein Deadlock, also eine zyklische Wartekette, erkannt wird, wird einem der beteiligten Threads eine Sperre und damit der Zugriff auf eine Ressource entzogen. Damit wird die zweite der obigen Bedingungen gelöst. Die Transaktion, die aktuell im betroffenen Thread ausgeführt wird, muss zurückgerollt und neugestartet werden (= Rollback einer Transaktion).

Beim Pessimistic Locking hingegen sollen Deadlocks grundsätzlich vermieden werden. Dazu muss ein Thread alle benötigten Sperren auf exklusiv nutzbare Ressourcen gleich zu Beginn der auszuführenden Transaktion anfordern. Entweder wird das Anfordern aller Sperren als atomare Aktion in einem kritischen Abschnitt zusammengefasst, wodurch die dritte der obigen Bedingungen hinfällig wird – oder die einzeln angeforderten Sperren werden in einer definierten Reihenfolge erlangt, wodurch keine Zyklen mehr entstehen können und die vierte der obigen Bedingungen gelöst wird.

Wer in Lehrbüchern oder im Internet zum Thema Deadlock recherchiert, wird relativ schnell auf das berühmte Beispielproblem der Dining Philosophers stoßen. Die Problemstellung wurde bereits 1965 von Edsger Dijkstra für seine Studierenden formuliert und ist bis heute in der Informatik-Lehre etabliert. Wir stellen uns folgende Situation vor, die in der Abbildung unten veranschaulicht ist: 5 Philosophen sitzen an einem Tisch und denken. Vor jedem Philosophen liegt ein Teller, um gelegentlich davon zu essen. Zum Essen benötigt ein Philosoph zwei Gabeln, die links und rechts des Tellers liegen. Zu einem zufälligen Zeitpunkt nimmt jeder Philosoph zwei Gabeln und isst zufällig lange, bis er sich wieder dem Denken zuwendet. Es stehen auf dem Tisch aber insgesamt nur 5 Gabeln zur Verfügung, und jeder Philosoph benötigt die beiden Gabeln links und rechts seines Tellers zum Essen.

Die Philosophen sind in diesem Beispiel die Threads, die um den exklusiven Zugriff auf die Gabeln als Ressourcen konkurrieren. Wenn alle Philosophen zeitgleich zuerst die rechte und dann die linke Gabel nehmen, entsteht ein Deadlock, bei dem jeder Philosoph auf seinen linken Nachbarn warten muss, bis dieser die benötigte Gabel wieder freigibt. In diesem Zustand würden alle Philosophen verhungern. Ein Deadlock kann vermieden werden, wenn das Erlangen beider Gabeln als atomare Aktion in einem kritischen Abschnitt realisiert wird.

Ein Blick auf die obige Abbildung zeigt, dass immer 2 Philosophen parallel essen können, z.B. Philosoph 1 und Philosoph 3 und anschließend Philosoph 2 und Philosoph 4. Wenn diese 4 Philosophen sich jeweils paarweise abwechseln, wird der fünfte Philosoph verhungern. Dieses Verhungern (engl. Starvation) eines Threads auf Kosten der anderen, weil es keine faire Warteschlange gibt, ist ebenfalls zu vermeiden. Für das Philosophen-Problem gibt es unterschiedliche Ansätze um Starvation zu vermeiden:

Es wird an dieser Stelle kein Java-Code als Lösung für das Philosophen-Problem dargestellt. Stattdessen soll die Lösung mit Hilfe der folgenden Klassen eigenständig entwickelt werden!

class Philosopher extends Thread  {
    int number;

    @Override
    public void run() {
        while (true) {
            // TODO: think, takeFork, eat, putFork
        }
    }
}
class Table {
    boolean[] forkUsed;

    synchronized void takeFork(int number) {
        // TODO ...
    }

    synchronized void putFork(int number) {
        // TODO ...
    }
}

Java Concurrency API

Die Java Concurrency API im Package java.util.concurrent stellt seit Java 5 diverse Interfaces und Klassen bereit, um nebenläufige Threads zu steuern und zu koordinieren. Dazu zählen: