Das Expansionsprotokoll nach Onodera und Kawachiya

Im Falle eins Konfliktes muß eine Monitorstruktur für das betroffene Objekt alloziert werden. Dies geschieht über eine globale Tabelle; diese Struktur ist eindeutig dem Objekt zugeordnet, d.h. mehrfache Anfragen für das Objekt liefern immer die gleiche Struktur. Die Lösungs beruht darauf, die Monitorstruktur selbst zur Koordination des Expansionsprotokolls zu verwenden. Sie wird also selbst in zwei Modi verwendet -- zunächst als Koordinationspunkt für das Expansionsprotokoll. Ist dieses beendet, übernimmt sie die Rolle des Monitors selbst. In der Monitorstruktur werden Betriebssystemobjekte für die Synchronisierung genutzt.

Abbildung 5.9: Expansion eines Monitors nach [Onodera and Kawachiya, 1999]

Der Expansionsalgorithmus funktioniert folgendermaßen, entsprechend der 5 Phasen in Abbildung 5.9.

1.

Ein Thread erwirbt den leichtgewichtigen Monitor, indem er (Thread-Id, 1) in das Monitorfeld des Objektkopfes schreibt.

2.

Weitere Threads scheitern beim Erwerb. Über die globale Tabelle wird eine Monitorstruktur angelegt. Alle Threads erwerben nun die Sperre der Monitorstruktur und warten auf der Ereignisvariable der Monitorstruktur. Zuvor wird dem Monitorbesitzer der Wunsch nach Monitor-Expansion durch das Setzen eines freien Bits im Objektkopf außerhalb des Monitorfeldes (FLC-Bit nach Onodera und Kawachiya) kommuniziert.

3.

Der Monitorbesitzer gibt den Monitor frei, indem er das Monitorfeld auf 0 setzt. Danach prüft er das FLC-Bit und stellt fest, daß das Expansionsprotokoll initiiert wurde. Daraufhin erwirbt er die Sperre der Monitorstruktur, die er aus der globalen Tabelle erfragt, und signalisiert die Ereignisvariable.

4.

Ein wartender Thread wacht auf und erwirbt wieder den Mutex der Monitorstruktur. Er stellt fest, daß der Monitor freigegeben ist und installiert den Verweis auf die Monitorstruktur im Objektkopf. Er benachrichtigt alle anderen auf Expansion wartenden Threads; diese können allerdings nicht sofort auch den Mutex erwerben. Der erste Thread kann nun in die kritische Region eintreten.

5.

Bei der Monitorfreigabe gibt der Thread die Sperre der Monitorstruktur frei, und ein anderer Thread kann diesen erwerben.

Treten keine Konflikte beim Monitorerwerb auf, so ist dieses Sperrprotokoll extrem effizient. Insbesondere verzichtet der Algorithmus auf atomare Instruktionen bei der Monitorfreigabe im gemeinen Fall. Daraus resultiert allerdings eine race condition zwischen freigebendem Thread (Phase 3) und erwerbendem Thread (Phase 2), die dazu führen kann, daß der freigebende Thread den Monitor zu erwerben sucht, nachdem der nachfolgende Thread ihn bereits erwerben konnte. Dadurch könnte der freigebende Thread unnötig blockiert werden, als sei er unfair vom Scheduler verzögert worden [Onodera, 2000].

Synchronisierung basierend auf thin locks wird von IBM in den aktuellen Java 2 Development Kits sowie in der Jalapeño VM eingesetzt.