next up previous contents
Next: Variable Monitordarstellungen Up: Eine fortgeschrittene Metasperrenimplementierung Previous: Eine fortgeschrittene Metasperrenimplementierung   Inhalt

Die Struktur der Metasperre

Besitzer und Bewerber einer Metasperre bilden eine verkettete Liste. Jeder Thread referenziert dabei den Thread, der sich zuvor in die Liste eingetragen hat, in einer lokalen Variable. Die Eintragung findet durch einen atomaren Tausch des bisherigen Wortes im Objektkopf mit der Referenz auf das Thread-Objekt statt (SPARC-V9-Instruktion SWAP [SPARC, 1998]).

Nach dem Tausch kann der Thread anhand der Markierungsbits des vorherigen Wertes entscheiden, ob er die Metasperre erwerben konnte, oder ob diese bereits den Verweis auf einen Vorgänger-Thread enthält und damit ein Konflikt beim Erwerb der Metasperre besteht.

Wurde die Metasperre erfolgreich erworben, so kann die Monitorstruktur manipuliert werden und in den Objektkopf zurückgeschrieben werden -- vorausgesetzt, kein anderer Thread hat sich für die Metasperre angemeldet (siehe Abbildung 5.6). Der Besitzer kann eine etwaigen Konflikt anhand des aus dem Objektkopf getauschten Wertes erkennen: enthält er noch die Adresse des jetzigen Metasperrenbesitzers, so kann die Monitorstruktur geschrieben werden -- diese Operationsfolge wird atomar durch die SPARC-V9-Instruktion CAS realisiert.

Abbildung 5.6: Metasperre nach [Agesen et al., 1999] -- keine Konflikt
\includegraphics{nebenlaeufigkeit/util/metalock-uncontended}

Schlägt CAS fehl, so hat sich bereits ein anderer Thread in die Bewerberliste eingetragen. Die Metasperre und die neue Monitorstruktur werden direkt an diesen weitergereicht (wie in Abbildung 5.7). Beide Threads vollziehen dazu ein Rendezvous, welches mit Hilfe von POSIX Synchronisierungsprimitiven realisiert wird. Dazu enthält jede Thread-Struktur je eine Betriebssystem-Sperre und -Ereignisvariable.

Abbildung 5.7: Metasperre nach [Agesen et al., 1999] -- Konflikt beim Erwerb der Metasperre
\includegraphics{nebenlaeufigkeit/util/metalock-contended}

Diese Implementierung von Metasperren ist extrem speichereffizient, denn sie erfordert nur zwei freie Bits im Objektheader für den Fall eines nicht erworbenen Monitors. Trotzdem wird die Laufzeitperformanz nicht negativ beeinflußt: Erwerb und Freigabe eines Monitors erfolgen in wenigen SPARC-Instruktionen, darunter je zwei atomare Instruktionen -- mit einer weiteren Optimierung können letztere auf je eine atomare Instruktion für den Fall ohne Monitor-Koflikt reduziert werden.

Wird ein Monitor erworben oder zum Warten verwendet, so müssen Sperrstrukturen alloziert werden, die jedoch sofort nach Benutzung wiederverwendet oder freigegeben werden können. Der dafür benötigte Platz ist vernachlässigbar (< 100k), wie Messungen von [Agesen et al., 1999] ergeben. Die Allokation findet in thread-lokalen Bereichen statt, so daß hier keine Synchronisation vonnöten ist.


next up previous contents
Next: Variable Monitordarstellungen Up: Eine fortgeschrittene Metasperrenimplementierung Previous: Eine fortgeschrittene Metasperrenimplementierung   Inhalt

2001-02-28