6  Lock-Objekte und Semaphore

6.1 Nachteile von “synchronized”

• Durch synchronized blockierter Thread kann nicht mit interrupt() unterbrochen werden. interrupt() wirkt sich erst nach der Blockierung aus.
• kein Timeout
• keine Regel für Reihenfolge der Zuteilung an mehrere wartende Tasks
• nur Blockstruktur (Eintritt und Austritt in unterschiedlichen Methoden nicht möglich)

6.2 ReentrantLock

6.2.1 Lock-Implementierungen und ihre Beziehungen

6.2.2 Lock-Interface

public interface Lock {
    public void lock();
    public void lockInterruptibly() 
        throws InterruptedException;

    public boolean tryLock();
    public boolean tryLock(long time, TimeUnit unit) 
        throws InterruptedException;

    public void unlock();
    public Condition newCondition();
}

• ein wegen lockInterruptably() blockierter Thread kann durch interrupt() unterbrochen werden (\(\to\) InterruptedException)
• tryLock() liefert false, falls `Lock `-Instanz schon belegt ist

6.2.3 Nachteile von synchronized

• Durch synchronized blockierter Thread kann nicht mit interrupt() unterbrochen werden. interrupt() wirkt sich erst nach der Blockierung aus.
• kein Timeout
• keine Regel für Reihenfolge der Zuteilung an mehrere wartende Tasks
• nur Blockstruktur (Eintritt und Austritt in unterschiedlichen Methoden nicht möglich)

6.2.3.1 Vorteile von Lock-Implementierungen

• Unterbrechbarkeit
• Timeout
• Fairness
• “Non-Blockstruktur”

6.2.4 Benutzungsmuster von Lock-Interface und -Implementierungen

6.2.4.1 unlock() in finally-Block

Lock lock = new ReentrantLock();

lock.lock();
try {
    //... kritischer Abschnitt
} finally {
    lock.unlock();
}

• Durch try … finally wird sichergestellt, dass der Lock auf jeden Fall am Ende gelöst wird.
• lock() und unlock() können von unterschiedlichen Methoden aus aufgerufen werden.

6.2.4.2 Fairness und Acquisition Order

boolean fairness;
//...
Lock lock = new ReentrantLock(fairness);

lock.lock();
try {
    //... kritischer Abschnitt
} finally {
    lock.unlock();
}

• fairness-Parameter gibt an, ob als nächstes der am längsten wartende Thread entblockiert wird oder nicht.

6.2.4.2.1 Fairness Policy (optional)

• Non-fair mode (default)
  Reihenfolge, in der blockierte Threads entblockiert werden ist unbestimmt und kann nicht beeinflusst werden. Insbesondere ist es nicht unbedingt so, dass der Thread als nächstes den Zuschlag bekkommt, der am längsten warten musste.
• Fair mode
  Reihenfolge der Entblockierung entspricht der “Ankunftsreihenfolge” am Lock. Der Thread, der am längsten am Lock wartet, wird als nächstes entblockiert.

6.2.4.3 tryLock()

Lock lock = new ReentrantLock();

if(lock.tryLock()) {
    try {
        //... kritischer Abschnitt
    } finally {
        lock.unlock();
    }
} else {
    //... etwas anderes tun...
}

• mit tryLock() prüfen, ob Lock belegt und schließen oder entwas anderes tun

6.3 ReadWriteLock

6.3.1 Lock-Implementierungen und ihre Beziehungen

6.3.2 ReadWriteLock

• warum sollten nicht mehrere Threads gleichzeitig lesend auf eine Variable zugreifen dürfen, wenn ein gleichzeitiges Schreiben ausgeschlossen ist?
• Eine Lock-Variante, die ReadLock und WriteLock besitzt
  • ReadLock: mehrere dürfen in den kritischen Abschnitt, wenn der dazugehörende WriteLock nicht geschlossen ist (“nicht-exklusiver” Lock).
  • WriteLock: nur einer darf in den kritischen Abschnitt und auch nur, wenn der ReadLock nicht gerade benutzt wird (“exklusiver” Lock).
• Die Vergabe der Locks erfolgt in der Reihenfolge, wie sie angefordert wurden.

Besitzt ein Thread eine Lesesperre und versucht ein weiterer Thread, eine Schreibsperre zu erhalten, muss dieser warten. Die Frage ist nun, was passiert, wenn jetzt ein Thread kommt, der eine Lesesperre erwerben möchte. Aus Gründen des Durchsatzes bekommt er sie sofort. Eine solche Vergabestrategie kann aber dazu führen, dass ein Thread, der eine Schreibsperre anfordert, unter Umständen nie zum Zuge kommt (\(\to\) lock starvation).

public interface ReadWriteLock {
    public Lock readLock();
    public Lock writeLock();
}

ReadWriteLock lock = new ReentrantReadWriteLock(fairness);
Lock rLock = lock.readLock();
Lock wLock = lock.writeLock();

• rLock und wLock werden benutzt wie die bisherigen Lock-Implementierungen
• Sie verhalten sich aber anders (s.o.) und sind “miteinander verschränkt”.

6.3.3 Beispiel: Verschränkung Read/Write Lock

• Zu jeder Instanz einer Implementierung von ReadWriteLock wird je ein Read-Lock und ein Write-Lock erzeugt.
• Ihr Typ implementiert das Lock-Interface.
• Nutzer eines Read- oder Write-Locks müssen eine Referenz auf das ReadriteLock-Objekt bekommen. Das ist im Sequenzdiagramm nur durch new(lock) angedeutet. Natürlich erwartet der Konstruktor von Thread kein Lock-Objekt.
• Read-Lock und Write-Lock des selben ReadWriteLock sind miteinander “verschränkt” und wirken auf den sie erzeugenden ReadWriteLock zurück. Im Sequenzdiagramm ist das nur durch “namenlose Nachrichten” angedeutet.

• Im folgenden Sequenzdiagramm sind die Rückwirkungen von Aufrufen an rl und wl auf lock nicht dargestellt.

• t1 schließt zuerst den Read-Lock
  \(\to\) lock: gelb

• t2 darf am Read-Lock teilnehmen und wird nicht blockiert.

• t3 möchte den Write-Lock und wird blockiert.

• t3 wird erst entblockiert, wenn sowohl t1 als auch t2 den Read-Lock wieder freigegeben haben. Der Write-Lock ist nun von t3 gesperrt \(\to\) lock: blau

• t1 möchte den Read-Lock und wird blockiert. Erst wenn t3 den Write-Lock freigibt, bekommt t1 den Read-Lock
  \(\to\) lock: gelb

• t1 gibt am Ende den Read-Lock wieder frei.

• Read-Lock sperrt Lesen “non-exklusiv”

• Im folgenden Sequenzdiagramm sind die Rückwirkungen von Aufrufen an rl und wl auf lock nicht dargestellt.

• t1 schließt zuerst den Read-Lock
  \(\to\) lock: gelb

• t3 möchte den Write-Lock und wird blockiert.

• t2 darf nun wg. offener Lock-Anforderung von t3 nicht mehr am Read-Lock teilnehmen und wird blockiert.

• t3 wird wg. der Reihenfolge der Anforderung als nächstes entblockiert, wenn t1 freigibt. Der Write-Lock ist nun von t3 gesperrt \(\to\) lock: blau

• t2 wird erst entblockiert, wenn t3 den Lock freigibt. \(\to\) lock: gelb

• t2 gibt am Ende den Read-Lock wieder frei.

• Reihenfolge der lock() ist bestimmend

6.4 StampedLock

6.4.1 Lock-Implementierungen und ihre Beziehungen

• Falls die zu schützenden kritischen Abschnitte kurz sind, ist der erforderliche Verwaltungsaufwand für einen Lock relativ hoch. synchronized kann von der Laufzeit her schneller sein.
• StampedLock nützlich bei großem Leseanteil

Exkurs: StampedLock ist in Java 8 eingeführt worden, während Lock, ReentrantLock etc. schon seit Java 7 dabei sind.

6.4.2 StampedLock Modi

Ein StampedLock besteht aus Stamp und Modus

• Modus Writing (“exklusiver” Lock):
  writeLock() blockiert für exklusiven Schreibzugriff; liefert eine long ID (“stamp”), die für unlockWrite(long) benutzt werden kann.
  keine readLocks und tryOptimisticRead möglich.
• Modus Reading (“nicht-exklusiver” Lock):
  readLock() wartet auf nicht exklusiven-Zugriff; liefert eine long ID (“stamp”), die für unlockRead(long) benutzt werden kann.
• Modus Optimistic Reading (kein Lock, aber post-hoc Kollisionserkennung möglich):
  tryOptimisticRead() liefert nur dann eine long ID (“stamp”), falls der Lock gerade nicht im Modus “Writing” ist. validate(long) liefert true, falls der Lock nicht zum Schreiben gesperrt wurde, seit die ID vergeben wurde.

6.4.3 ReadLock beim StampedLock

var lock = new StampedLock();

var stamp = lock.readLock();
try {
    //... kritischer Abschnitt
} finally {
    lock.unlockRead(stamp);
}

6.4.4 WriteLock beim StampedLock

var lock = new StampedLock();

var stamp = lock.writeLock();
try {
    //... kritischer Abschnitt
} finally {
    lock.unlockWrite(stamp);
}

alternativ statt lock.unlockRead(stamp) und lock.unlockWrite(stamp) \(\to\) lock.unlock(stamp)

6.4.5 Beispiel für die Modi “exklusiver”/“nicht-exklusiver” Lock

public static void main(String... args) throws InterruptedException {
    var lock = new StampedLock();
    var t1 = new Thread(() -> {
        System.out.println("t1: trying readLock");
        var stamp1 = lock.readLock();
        System.out.printf("t1: acquired readLock (stamp1 = %d)\n", stamp1);
        // ... hier "non-exklusiv" ("ReadLock acquired")
        sleep(5);
        lock.unlock(stamp1);
        System.out.printf("t1: released readLock (stamp1 = %d)\n", stamp1);
        sleep(1);
        System.out.println("t1: trying readLock");
        var stamp4 = lock.readLock();
        System.out.printf("t1: acquired readLock (stamp4 = %d)\n", stamp4);
        // ... hier "non-exklusiv" ("ReadLock acquired")
        lock.unlock(stamp4);
        System.out.printf("t1: released readLock (stamp4 = %d)\n", stamp4);
    });
    t1.start();

    var t2 = new Thread(() -> {
        sleep(2);
        System.out.println("t2: trying readLock");
        var stamp2 = lock.readLock();
        System.out.printf("t2: acquired readLock (stamp2 = %d)\n", stamp2);
        // ... hier "non-exklusiv" ("ReadLock acquired")
        sleep(4);
        lock.unlock(stamp2);
        System.out.printf("t2: released readLock (stamp2 = %d)\n", stamp2);
    });
    t2.start();

    var t3 = new Thread(() -> {
        sleep(1);
        System.out.println("t3: trying writeLock");
        var stamp3 = lock.writeLock();
        System.out.printf("t3: acquired writeLock (stamp3 = %d)\n", stamp3);
        // ... hier exklusiv ("WriteLock acquired")
        sleep(5);
        lock.unlock(stamp3);
        System.out.printf("t3: released writeLock (stamp3 = %d)\n", stamp3);
    });a
}

… mit dem folgenden Trace:

t1: trying readLock
t1: acquired readLock (stamp1 = 257)
t3: trying writeLock
t2: trying readLock
t2: acquired readLock (stamp2 = 258)
t1: released readLock (stamp1 = 257)
t2: released readLock (stamp2 = 258)
t3: acquired writeLock (stamp3 = 384)
t1: trying readLock
t3: released writeLock (stamp3 = 384)
t1: acquired readLock (stamp4 = 513)
t1: released readLock (stamp4 = 513)

• t1 bekommt zuerst den “nicht-exklusiven” Lock (“Read-Lock”) \(\to\) lock ist gelb
• t3 möchte den “exklusiven” Lock (“Write-Lock”) und wird blockiert, bis der nicht-exklusive Lock endet \(\to\) t1 ist rot
• t2 kommt zu t1 in den “nicht-exklusiven” Lock
• t1 verlässt den “nicht-exklusiven” Lock
• t3 bleibt vorerst weiterhin blockiert, solange bis der letzte Thread den “nicht-exklusiven” Lock verlässt
• t2 tut dies, daraufhin bekommt
• t3 den “exklusiven” Lock \(\to\) lock ist blau
• t1 möchte wieder einen “nicht-exklusiven” Lock, wird aber wg. t3 blockiert \(\to\) t1 ist rot
• t3 gibt den “exklusiven” Lock zurück, erst dann wird
• t1 entblockiert und erhält den “nicht-exklusiven” Lock \(\to\) lock ist gelb

6.4.6 Optimistisches Lesen (Read-Lock) mit StampedLock

• keine Änderungen im kritischen Abschnitt, aber “nicht-exklusiv” lesend wie Read-Lock
• keine “technische” Durchsetzung des Locks, stattdessen:
  • Beginn des kritischen Abschnitts beim StampedLock-Objekt “markieren” (anmelden)
  • versuchen, den kritischen Abschnitt abzuarbeiten
  • am Ende beim StampedLock-Objekt nachfragen, ob es seit der Anmeldung Write-Locks gegeben hat (Read-Locks sind unkritisch)
  • falls ja: reagieren mit Roll-Back der Transaktion und erneutem Versuch
  • falls nein: kritischer Abschnitt erfolgreich
• da kein Blockieren: sehr geringer Overhead
• falls das Anwendungsprofil es zulässt (geringe Wahrscheinlichkeit für Verletzung des “nicht-exklusiven” Locks), die perfomanteste Lösung für konkurrierenden Zugriff:
  • bei Zugriff auf einzelne Variablen: Atomics-Wrapper
  • bei komplexeren kritischen Abschnitten: optimistische Nutzung von StampedLock

var lock = new StampedLock();

var stamp = lock.tryOptimisticRead();
//... kritischer Abschnitt ("nicht exklusiv")
if (!lock.validate(stamp)) {
    // nicht erfolgreich => das bisherige ist möglicherweise 
    // inkonsistent und muss zurückgerollt werden; eine mögliche
    // Strategie: nochmal pessimistisch "non-excl." gelockt probieren:
    stamp = lock.readLock();
    try {
        //... kritischer Abschnitt (ReadLock)
    } finally {
        lock.unlockRead(stamp);
    }
}

andere Muster denkbar (z.B. wie bei Atomics: weiter optimistisch versuchen, bis erfolgreich \(\to\) s. nächstes Beispiel)

6.4.7 Beispiel für optimistisches Lesen (“nicht-exklusiv”)

public static void main(String... args) throws InterruptedException {
    var lock = new StampedLock();
    var t1 = new Thread(() -> {
        long stamp1;
        do {
            System.out.println("t1: optimisitically trying...");
            // ... ggf. Rolback des vorigen optimist. Versuchs
            stamp1 = lock.tryOptimisticRead();
            System.out.printf("t1: begin opt. (stamp1 = %d)\n", stamp1);
            // ... hier optimistischer Versuch ("non-exklusiv")
            sleep(5);
            System.out.printf("t1: validate opt. (stamp1 = %d)\n", stamp1);
        } while (!lock.validate(stamp1));
        System.out.printf("t1: was valid (stamp1 = %d)\n", stamp1);
    });
    t1.start();

    var t2 = new Thread(() -> {
        sleep(7);
        System.out.println("t2: trying readLock");
        var stamp2 = lock.readLock();
        System.out.printf("t2: acquired readLock (stamp2 = %d)\n", stamp2);
        // ... hier "non-exklusiv" ("ReadLock acquired")
        sleep(4);
        lock.unlock(stamp2);
        System.out.printf("t2: released readLock (stamp2 = %d)\n", stamp2);
    });
    t2.start();

    var t3 = new Thread(() -> {
        sleep(1);
        System.out.println("t3: trying writeLock");
        var stamp3 = lock.writeLock();
        System.out.printf("t3: acquired writeLock (stamp3 = %d)\n", stamp3);
        // ... hier exklusiv ("WriteLock acquired")
        sleep(5);
        lock.unlock(stamp3);
        System.out.printf("t3: released writeLock (stamp3 = %d)\n", stamp3);
    });
}

… mit dem folgenden Trace:

t1: optimisitically trying...
t1: begin opt. (stamp1 = 256)
t3: trying writeLock
t3: acquired writeLock (stamp3 = 384)
t1: validate opt. (stamp1 = 256)
t1: optimisitically trying...
t1: begin opt. (stamp1 = 0)
t3: released writeLock (stamp3 = 384)
t2: trying readLock
t2: acquired readLock (stamp2 = 513)
t1: validate opt. (stamp1 = 0)
t1: optimisitically trying...
t1: begin opt. (stamp1 = 512)
t2: released readLock (stamp2 = 513)
t1: validate opt. (stamp1 = 512)
t1: was valid (stamp1 = 512)

• t1 versucht optimistisch lock zu nutzen
• t3 schließt lock exklusiv (t1 bekommt davon erstmal nichts mit und t3 wird auch nicht blockiert) \(\to\) lock blau
• t1 ist fertig, stellt aber Misserfolg fest und versucht es erneut opt. (t1 wird nicht blockiert, obwohl t3 exkl. Lock hat)
• t3 gibt lock wieder frei \(\to\) lock nicht mehr blau
• t2 fordert erfolgreich nicht-exkl. Lock an. lock ist frei, t2 blockiert nicht. lock nun nicht-exkl. vergeben \(\to\) lock gelb
• t1 ist fertig, stellt aber Misserfolg fest und versucht es erneut opt. (t1 wird nicht blockiert)
• t2 ist fertig \(\to\) lock ist nicht mehr gelb
• t1 ist fertig und stellt nun fest, dass das opt. Lesen endlich erfolgreich war

6.5 Semaphore: Koordination der konkurrierenden Nutzung von Ressourcen

Semaphore sind ein den Monitoren und Locks verwandtes Konzept. Im Gegensatz zu diesen haben sie aber eine Kapazität. Man kann damit den Grad der Parallelität steuern.

Für den konkurrierenden Zugriff auf Variablen sind sie nicht geeignet, da hier entweder beliebig viele parallele Zugriff erlaubt sind (ReadLock) oder nur exakt einer (gegenseitiger Ausschluss).

• Semaphore ermöglichen die Begrenzung der Nutzung einer Ressource auf eine bestimmte Anzahl Nutzer.
• Kapazität eines Semaphores (permitCount): Anzahl an noch erlaubten Nutzern.
• Operationen: release() und acquire() (blockiert, falls permitCount == 0)

Bildquelle: Hettel und Tran (2016, 120)

Semaphore, die mit der Kapazität 1 angelegt werden, verhalten sich wie Locks (haben aber bei Java eine andere Schnittstelle).

Allen, Jamie. 2013. Effective Akka. Sebastopol: O’Reilly.

Butcher, Paul. 2014. Seven Concurrency Models in Seven Weeks. When Threads Unravel. Dallas: The Pragmatic Programmers.

Hettel, Jörg und Manh Tien Tran. 2016. Nebenläufige Programmierung mit Java. Konzepte und Programmiermodelle für Multicore-Systeme. Heildelberg: dpunkt.verlag.

Tanenbaum, Andrew S. und Herbert Bos. 2016. Moderne Betriebssysteme. 4., aktualisierte Auflage. Pearson Studium.

Vernon, V. 2016. Reactive Messaging Patterns with the Actor Model. Applications and Integration in Scala and Akka. New York: Addison-Wesley.