Mit dem JDK 1.5 gibt es für die Synchronisation von Threads Erweiterungen um sogenannte explizite Sperren und eine Semaphor-Abstraktion.  Diese Erweiterungen wollen wir in diesem Artikel vorstellen. .  Zu den neuen Synchronisationsmitteln gehören eine explizite Sperre (im Gegensatz zum impliziten Objekt-Mutex), eine spezielle Sperre für konkurrierende Lesezugriffe und ein Semaphor.
 

Einleitung

 synchronized(lockObject) {

    ... in diesem Block ist die mit lockObject assozierte Sperre aktiv ...

 }

Die Benutzung der Sperre ist starr an Blockgrenzen gebunden. Das bringt funktionale Einschränkungen mit sich: so ist es zum Beispiel nicht möglich, eine zweite Sperre nach einer ersten Sperre so zu aktivieren, dass diese nach der ersten deaktiviert wird. Einen solchen Vorgang nennt man Hand-Over-Hand Locking (siehe Abb. 1).

Abbildung 1: Hand-Over-Hand Locking

Ein Hand-Over-Hand-Locking braucht man beispielsweise in folgender Situation: nehmen wir einmal an, wir wollen in einer Collection nach einem bestimmten Element suchen.  Dieses Element wollen wir anschließend bearbeiten.  Wenn die Collection von mehreren Threads gleichzeitig benutzt werden kann, dann werden wir unsere Zugriffe auf die Collection und das zu bearbeitende Element synchronisieren müssen.  Wir werden also die gesamte Collection für den Vorgang der Suche gegen konkurrierende Zugriffe sperren, damit sich die Collection nicht während der Suche durch die Aktionen anderer Threads ändert.  Wenn das gesuchte Element gefunden ist, dann können wir im Prinzip die Sperre für die Collection aufheben.  Wir wollen jetzt nur noch das gefundene Element bearbeiten und es genügt daher, nur dieses eine Element gegen konkurrierende Zugriffe zu schützen.

An dieser Stellen wollen wir die Sperre auf der Collection aufgeben und eine neue Sperre für das einzelne Element anfordern.  Wenn wir das in dieser Reihenfolge tun (Collection-Sperre aufgeben + Element-Sperre anfordern), dann kann es passieren, das unser Thread unterbrochen wird, nachdem die Collection-Sperre aufgegeben und bevor die Element-Sperre zugeteilt ist.  Andere Threads könnte dann die Collection und auch das gefundene Element ändern oder gar löschen, ehe unser Thread die Element-Sperre bekommt und das gefundene Element bearbeiten kann. Das ist natürlich unerwünscht.  Also wollen wir erst die Element-Sperre anfordern, ehe wir die Collection-Sperre aufgeben.  Nur so ist sichergestellt, dass uns kein anderer Thread in Quere kommt.

Das ist nun eine Hand-Over-Hand-Locking-Sitution, die sich mit dem klassischen Java-Mittel des synchronized-Block nicht angemessen behandeln läßt.  In pre-1.5 Java hat man nur eine Möglichkeit: der gesamte Vorgang des Suchens in der Collection und der Bearbeitung des gefundenen Elements muß in einen großen synchronized -Block gepackt werden.  Damit werden alle anderen Thread  wesentlich länger blockiert, als nötig ist. Während wir längst mit der Collection fertig sind und nur noch an einem einzigen Element interessiert sind, müssen alle anderen Threads warten, auch diejenigen, die auf das eine Element gar nicht zugreifen wollen.  Diese unschöne Situation läßt sich nun mit den neuen Synchronisationsmitteln im JDK 1.5 auflösen.

Als Lösung für das Hand-Over-Hand-Locking-Problem kann man nun eine explizite Sperre verwenden, die nicht an Blockgrenzen gebunden ist, sondern die nach Belieben angefordert und freigegeben werden kann.  Die explizite Sperre hat außerdem funktionale Ergänzungen verglichen mit dem impliziten Objekt-Mutex.  Daneben gibt es noch andere Synchronisationsmittel: ein Read-Write-Lock und ein Semaphor. Sehen wir uns die Neuerungen im Detail an.

Sperren (englisch: Locks)

void lock() - Aktiviert die Sperre, falls sie verfügbar ist. Falls nicht, wartet der aktuelle Thread bis sie verfügbar wird.

void lockInterruptbibly() - Aktiviert die Sperre, falls sie verfügbar ist. Falls nicht, wartet der aktuelle Thread bis sie verfügbar wird. Falls der Thread während des Wartens unterbrochen wird (d.h. interrupted() ist auf der Threadinstanz aufgerufen worden), wirft die Methode eine InterruptedException und der Unterbrechungszustands des Threads wird zurückgesetzt. Die Exception wird auch geworfen, falls der Unterbrechungszustand des Threads aktiv ist, wenn die Methode aufgerufen wird. Was es mit dem Unterbrechen von Threads im Detail auf sich hat werden wir noch genauer in einem zukünftigen Artikel diskutieren.

boolean tryLock() - Aktiviert die Sperre, falls sie verfügbar ist und gibt true zurück. Falls die Sperre nicht verfügbar ist wird false zurückgegeben.

boolean tryLock(long timeout, TimeUnit granularity) - Aktiviert die Sperre, falls sie verfügbar ist und gibt true zurück. Falls sie nicht verfügbar ist, wartet der aktuelle Thread die mit Hilfe der Parameter spezifizierte Zeitspanne. Sollte die Sperre währenddessen verfügbar werden, aktiviert er sie und gibt true zurück. Sollte sie nicht verfügbar werden, gibt er false zurück. Während des Wartens kann der Thread unterbrochen werden, so dass die Methode mit der InterruptedException abgebrochen wird. Die Exception wird auch geworfen, falls der Unterbrechungszustand des Threads aktiv ist, wenn die Methode aufgerufen wird.

void unlock() - Gibt die Sperre frei. Je nach konkretem Type der Sperre kann es Beschränkungen geben, wer diese Methode aufrufen darf. Zum Beispiel könnte es so sein, dass nur der Besitzer (d.h. der Thread, der auch das lock() gerufen hat) die Sperre freigeben darf. Falls die Einschränkungen konkreter Sperren nicht berücksichtigt werden, wird die Methode eine Runtime-Exception werfen (z.B. IllegalMonitorStateException).

Condition newCondition() - Factory Methode, die eine neues Condition Objekt erzeugt, das mit dem aktuellen Mutex assoziiert ist. Was eine Condition in der Multithread-Programmierung ist und wie sie benutzt wird, werden wir in einem zukünftigen Artikel noch genaurer diskutieren. Da es ein recht umfassendes Thema ist, dass sich auch mit wenigen Worten nicht erklären lässt, wollen wir das Thema in diesem Artikel ganz ausklammern.

Als erstes springt die Vielzahl von Methoden ins Auge, mit denen eine Sperre aktiviert werden kann. Da es sich dabei im wesentlichen nicht um reine Convenience-Methoden handelt, ergibt sich daraus ein breites Spektrum unterschiedlicher Funktionalität, das bisher so nicht in Java verfügbar war. Es ist nun möglich, mit einem Timeout auf eine Sperre zu warten, sowie beim Warten auf eine Sperre unterbrochen zu werden. Beides ist beim Warten auf ein implizites Objekt-Mutex  am Anfang eines synchronized-Blocks nicht möglich.

Mit der expliziten Sperre ist man nun deutlich flexibler beim Aktivieren einer Sperre. Man ist überhaupt nicht mehr an die Blockstrukturen gebunden, sondern kann die Sperre anfordern und freigeben, wann immer es nötig ist.  Damit ist das oben beschriebene Hand-Over-Hand-Locking-Problem gelöst.  Man wird zwei explizite Sperren verwenden, anstelle des Objekt-Mutex der Collection – eine Sperre für die Suche auf der Collection und eine andere für die Bearbeitung des gefundenen Element. Die beiden Sperren kann man überkreuz anfordern und freigeben, genau so wie es gebraucht wird.

Auf der anderen Seite gibt es bei der neuen wesentlich flexibleren Lösung auch potentielle Nachteile gegenüber dem klassischen synchronized-Block (bzw. der synchronized-Methode). Zum einen kann die Unterbrechung beim Warten auf eine Sperre je nach Typ der Sperre und Systemplattform eine teure Operation sein. Konkrete Implementierungen sind daher aufgefordert, dies in der JavaDoc zu lockInterruptbibly() und tryLock(long timeout, TimeUnit granularity) genauer zu beschreiben. Zum anderen kann es dem Programmierer nun passieren, dass er die Aufhebung der Sperre, also den Aufruf von myLock.unlock(), versehentlich vergißt. Die Freigabe eines impliziten Objekt-Mutex kann man nicht vergessen, weil die Freigabe automatisch beim Verlassen des Blocks geschieht.  Bei Verwendung der expliziten Sperren im JDK 1.5 ist der Programmierer nun selber Verantwortlich für die Freigabe. Damit hat man jetzt das klassische Ressourceanforderungs- und freigabeproblem, bei dem man die Freigabe nicht vergessen darf. Leider bietet Java abgesehen vom finally-Block kaum Sprachmittel, die die Ressourcefreigabe unterstützen würden.

Als Implementierung des Lock Interface gibt es eine konkrete Klasse: ReentrantLock. Das Verhalten von ReentrantLock ist das gleiche wie das einer mit einem Objekt assoziierten Mutexsperre. Dieses Verhalten haben wir bereits ausführlich in / KRE2 / diskutiert. Zusätzlich zur Funktionalität des Lock Interface bietet die Klasse ReentrantLock folgende Funktionalität:

• Mit isLocked() kann ermittelt werden, ob die Sperre von irgendeinem Thread gehalten wird.
• Mit isHeldByCurrentThread() kann geprüft werden, ob der aktuelle Thread die Sperre bereits selbst hält. Die gleiche Funktionalität bietet seit dem JDK 1.4 die Methode Thead.holdsLock(Object o) für die mit einem Objekt o assoziierten Mutexsperre an.
• Mit getHoldCount() kann ermittelt werden, wie häufig man die reentrant Sperre bereits akquiriert hat.

public class NonReentrantLock implements Lock {
 private ReentrantLock myLock = new ReentrantLock();

 public void lock() {
  if (myLock.isHeldByCurrentThread())
   throw new RepeatedLockAcquisitionException();
  else
   myLock.lock();
 }

 // lockInterruptibly() und tryLock() entsprechend

 public void unlock() {
   myLock.unlock();
 }

 Condition newCondition() {
  Return myLock.newCondition();
 }

}

Neben einem argumentlosen Konstruktor bietet ReentrantLock die Möglichkeit, eine Instanz mit ReentrantLock(boolean fair) zu erzeugen. Über das Boolsche Argument des Konstruktors wird die Vergabereihenfolge beeinflußt. Bei einer mit einem Objekt assoziierten Mutexsperre gibt es keine verlässliche Aussage darüber, in welcher Reihenfolge Threads, die auf die Sperre warten, diese bekommen. Bei einer mit ReentrantLock(true) erzeugten Sperre ist das anders. Sie wird nach dem FIFO-Prinzip (first in, first out) vergeben, d.h. der Thread, der bereits am längsten gewartet hat, bekommt die Sperre. Dabei ist nicht vollständig sichergestellt, dass der Thread, der als erster lock() aufgerufen hat, auch als erster die Sperre bekommt. Denn entscheidend für die Reihenfolge ist nicht der Aufruf von lock(), sondern das Erreichen der internen Verwaltungsfunktionalität des ReentrantLock. Die Vergabereihenfolge ist aber zumindest „annähernd fair“.  Allerdings hat die zusätzliche FIFO-Verwaltungsfunktionalität den Nachteil, dass sie Performance kostet: das faire ReentrantLock(true) ist etwas langsamer macht als das normale ReentrantLock.
 

Read-Write-Locks

public class IntStack {
 private final int[] array;
 private volatile int cnt = 0;

 public IntStack (int sz) { array = new int[sz]; }

 synchronized public void push (int elm) {
   if (cnt < array.length) array[cnt++] = elm;
   else throw new IndexOutOfBoundsException();
 }

 synchronized public int pop () {
   if (cnt > 0) return(array[--cnt]);
   else throw new IndexOutOfBoundsException();
 }

 synchronized public int peek() {
   if (cnt > 0) return(array[cnt-1]);
   else throw new IndexOutOfBoundsException();
 }

 public int size() { return cnt; }

 public int capacity() { return (array.length); }
}

Bisher gab es in Java keine einfache Möglichkeit, diese Einschränkung zu umgehen. Man hatte nur die Alternative, ein Read-Write-Lock selber zu implementieren; das ist aber recht aufwändig, wie man zum Beispiel bei Doug Lea (siehe / LEA /) nachlesen kann. Mit dem JDK  1.5 gibt es jetzt ein Interface ReadWriteLock und eine konkrete Klasse ReentrantReadWriteLock, die dieses Interface implementiert. Das Interface bietet nur zwei Methoden: readLock() und writeLock(), die die Lese- bzw. Schreibsperre vom Typ Lock zurückliefern.

Schauen wir uns an wie die Implementierung unseres Stacks aussieht, wenn wir ein ReadWriteLock nutzen, so dass peek() gleichzeitig von mehreren parallelen Threads ausgeführt werden kann:

public class IntStackWithRWLock {
 private volatile int cnt = 0;
 private final ReadWriteLock myLocks = new ReentrantReadWriteLock();

 public IntStack (int sz) { array = new int[sz]; }

 public void push (int elm) {
   myLocks.writeLock().lock();
   try {
     if (cnt < array.length) array[cnt++] = elm;
     else throw new IndexOutOfBoundsException();
   } finally {
     myLocks.writeLock().unlock();
   }
 }

 public int pop () {
   myLock.writeLock().lock();
   try {
   if (cnt > 0) return(array[--cnt]);
   else throw new IndexOutOfBoundsException();
   } finally {
     myLocks.writeLock().unlock();
   }
 }

 public int peek() {
   myLock.readLock().lock();
   try {
   if (cnt > 0) return(array[cnt-1]);
   else throw new IndexOutOfBoundsException();
   } finally {
     myLocks.writeLock().unlock();
   }
 }

 public int size() { return cnt; }

 public int capacity() { return (array.length); }
}

Anstelle der impliziten Sperre des Stack-Objekts verwenden wir ein explizites Read-Write-Lock für die Synchronisation. Lesende Methoden wie peek() synchronisieren sich über das Read-Lock und verändernde Methoden wie push() und pop() synchronisieren sich über ein Write-Lock.  Da das Read-Write-Lock so angelegt ist, dass es konkurrierende Reader zuläßt, kann nun peek() von mehreren Threads gleichzeitig ausgeführt werden.  Die früher schwer zu vermeidende Situation, dass ein peek() alle anderen peek()-Aufrufe blockiert, ist damit eliminiert.

Ist die Performance eines Multithread-Systems, in dem wir den IntStackWithRWLock statt des IntStack nutzen, besser? Vermutlich nicht - eher schlechter. Die Aufrufe von lock() bzw. unlock() sind für eine Sperre, die Teil eines ReadWriteLocks ist, performanceaufwändiger als für eine einfache Sperre. Warum das so ist, erklären wir später in diesem Artikel, wenn wir die Sperrpolitik des ReentrantReadWriteLocks im Detail diskutieren. Somit wird unser System durch die Nutzung des IntStackWithRWLock erst einmal langsamer. Diese Performanceeinschränkung kann nun durch die höhere Parallelität des Systems (peek()-Aufrufe können nun in parallelen Threads gleichzeitig ausgeführt werden) kompensiert oder sogar überkompensiert werden. Bei der typischen Nutzung eines Stacks werden aber im allgemeinen push() und pop() häufig aufgerufen, peek() eher nur selten, wenn überhaupt.  Mit einer Performanceverbesserung ist daher beim Stack nicht zu rechnen.

Das soll aber nun nicht heißen, dass die Nutzung des ReadWriteLocks grundsätzlich nicht sinnvoll ist. Es kommt vielmehr auf die Abstraktion an, in der man es nutzt. Wenn der Lesemethoden sehr häufig genutzt werden und synchronisiert werden müssen, dann ist die Nutzung des ReadWriteLocks durchaus sinnvoll. Wir haben zum Beispiel in der eigenen Praxis die Erfahrung gemacht, dass die Umstellung eines threadsicheren String-Typs vom herkömmlicher Synchronisierung auf ein Read-Write-Lock die Performance in einem Multiprozessorsystem mehr als verdoppelt hat.  Das war zwar ein String-Typ in C++, wo der String im Gegensatz zu Java modifizierende Methoden hat und veränderlich ist, aber es ist ein Beispiel einer Abstraktion, deren lesende Methoden viel häufiger aufgerufen werden als die verändernden Methoden.  In solchen Fällen kann ein Read-Write-Lock einen deutlichen Performance-Gewinn bringen.
 

ReentrantReadWriteLock

Es war relativ einfach, das Verhalten des ReentrantLock mit einem Verweis auf das mit einem Objekt assoziierte Mutexlock zu beschreiben, weil es sich ein ReentrantLock praktisch genauso verhält wie ein implizites Mutexlock. Mit dem ReentrantReadWriteLock haben wir es nicht so leicht. Das Verhalten eines Read-Write-Lock ist deutlich komplexer als das eines Mutex, was seine Ursachen im wesentlichen in der Korrelation zwischen Lese- und Schreibsperre hat. Fangen wir daher unsere Diskussion mit den Aspekten im Verhalten einer Sperre an, die uns schon vom Mutex her bekannt sind.
 

Mehrfaches Aktivieren einer Sperre

Freigabe der Sperre

Vergabepolitik der Sperre

Bei der Vergabereihenfolge des ReentrantReadWriteLock gibt es weder eine Bevorzugung von wartenden Lese- noch von Schreib-Threads. Die Vergabepolitik ist in der Reihenfolge der Anfrage. Wie wir aber bereits unter Freigabe der Sperre diskutiert haben, können entweder alle Lese-Threads oder ein Schreib-Thread die Sperre bekommen. Deshalb konkurrieren alle wartenden Lese-Threads gegen jeden wartenden Schreib-Thread. Das heißt, jeder Schreib-Thread und alle wartenden Lese-Threads bilden je einen Eintrag in der Warteschlange für die Sperre. Alle Lese-Threads bekommen die Sperre, wenn sie dem Lese-Thread zusteht, der sich als erster in die Schlange eingereiht hat.

Wenn die Lese-Threads die Sperre bereits haben, bekommen neue Lese-Threads die Sperre ohne zu warten, solange kein Schreib-Thread in der Warteschlange steht. Wenn aber bereits ein oder mehrere Scheib-Threads in der Warteschlange stehen, müssen die neuen Lese-Threads einen neuen Eintrag in der Warteschlange hinter den wartenden Schreib-Threads bilden.
 

Upgrades und Downgrades

myLock.writeLock().lock();
 ...
myLock.readLock().lock();    // leite Downgrade ein - durch Aktivieren der Lesesperre
myLock.writeLock().unlock(); // gebe Schreibsperre frei -  damit ist der Downgrade durchgeführt

// ab hier hat der Thread nur noch die Lesesperre !!!
 ...
myLock.readLock.unlock()

Wie bereits oben im Abschnitt „Mehrfaches Aktivieren einer Sperre“ beschrieben, muss der Thread beim Aufruf myLock.readLock().lock() nicht warten, da er bereits die Schreibsperre hat.

Es ist nicht möglich eine Lesesperre heraufzustufen (engl. upgrade). Das ergibt sich aus der bereits diskutierten Tatsache, dass ein Thread, der bereits eine Lesesperre hat, nicht mehr die Schreibsperre erhalten kann. Wie bereits oben beschrieben, führt der Versuch eines Upgrade zu einem Deadlock.
 

Semaphor

Die ersten vier Methodennamen sind so sprechend gewählt worden, dass ihre Funktionalität recht offensichtlich ist, wenn man sie mit den Methoden des Lock vergleicht.  Lediglich die Namen sind anders: hier heißt es acquire statt lock beim Lock. Die release() Methode entspricht der unlock() Methode des Lock.  Die Klasse Semaphore nimmt, wie auch die Klassen ReentrantLock und ReentrantReadWriteLock, ein fair-Flag als Konstruktor-Argument, welches bewirkt, dass die Permits an wartende Threads nach dem FIFO-Prinzip vergeben werden.  Neben den oben genannten Methoden hat das Semaphor noch Methoden für die Anforderung und Freigabe mehrerer Permits auf einmal.  Daneben gibt es Debugging und Monitoring-Methoden wie zum Beispiel getQueueLength() und hasQueuedThreads().

Das Semaphor hat ein Freigabeverhalten wie die Lesesperre des ReentrantReadWriteLock: das Semaphor ist nicht an den Thread gebunden, der es angefordert hat, sondern jeder Thread kann eine Erlaubnis (englisch: permit) freigeben, nicht nur der Thread, der die Erlaubnis vorher z.B. mit acquire() angefordert hat. Wie bei der Lesesperre des ReadWriteLock besteht auch hier die dahinterliegende Implementierung nur aus einem Zähler der verfügbaren Permits. Dieser Zähler wird beim Aufruf von release() um eins erhöht.
Das Semaphor ist nicht reentrant. Das heißt, wenn ein Thread wiederholt acquire() aufruft, ohne vorher release()  aufgerufen zu haben, so erhält er jedes mal eine neue Erlaubnis. Falls dem Semaphor dabei die Permits ausgehen, muss der anfordernde Thread am Ende auf frei werdende Permits warten. Auf diese Weise kann sich der Thread versehentlich in eine Art selbst provoziertes Dead-Lock bringen.

Fall man also eine Sperre benötigt, die von anderen Threads wieder freigegeben werden kann und die nicht reentrant ist, sollte man ein Semaphore mit genau einer möglichen Erlaubnis verwenden. Das folgende Beispiel zeigt den bereits bekannten Stack auf Basis eines Semaphore:

public class IntStackWithRWLock {
 private volatile int cnt = 0;
 private final Semaphore myLock = new Semaphore(1);

 public IntStack (int sz) { array = new int[sz]; }

 public void push (int elm) {
   myLock.acquireUninterruptibly();
   try {
     if (cnt < array.length) array[cnt++] = elm;
     else throw new IndexOutOfBoundsException();
   } finally {
     myLock.release();
   }
 }

 public int pop () {
   myLock.acquireUninterruptibly();
   try {
     if (cnt > 0) return(array[--cnt]);
     else throw new IndexOutOfBoundsException();
   } finally {
     myLock.release();
   }
 }

 public int peek() {
   myLock.acquireUninterruptibly();
   try {
     if (cnt > 0) return(array[cnt-1]);
     else throw new IndexOutOfBoundsException();
   } finally {
     myLock.release();
   }
 }

 public int size() { return cnt; }

 public int capacity() { return (array.length); }
}

Im Konstruktor des Semaphore wird die Anzahl der Erlaubnisse mitgegeben wird. In unserem Fall also 1.
 

Zusammenfassung

• eine explizite Sperre (siehe Interface Lock und Klasse ReentrantLock),
• eine spezielle Sperre für konkurrierende Lesezugriffe (siehe Interface ReadWriteLock und Klasse ReentrantReadWriteLock) und
• ein Semaphor (siehe Klasse Semaphore).

Literaturverweise

If you are interested to hear more about this and related topics you might want to check out the following seminar:

Seminar   Concurrent Java - Java Multithread Programming 4 day seminar ( open enrollment and on-site)