next up previous contents
Next: Exakte Garbage Collection für Up: Implementierung der Speicherverwaltung Previous: Implementierung der Speicherverwaltung   Inhalt


Allokation und Objektrepräsentation

Sowohl in objektorientierten als auch in funktionalen Sprachen werden Heapobjekte üblicherweise mit einer sehr hohen Frequenz angelegt. [Appel, 1989b] nennt für SML/NJ, eine Implementierung der funktionalen Sprache ML, eine durchschnittliche Rate von einem Speicherwort pro 30 Assemblerinstruktionen bzw. eine Allokation alle 90 Instruktionen -- die Optimierung der Allokationsroutine erscheint also lohnend. Wird ein Algorithmus verwendet, der unterschiedliche Segmente verwendet (z.B. ein generationaler Algorithmus), so ist zwischen Allokation in der jüngsten und den älteren Generationen zu unterscheiden. Die o.g. Allokationsfrequenzen treten nur in der jüngsten Generation auf, weshalb nur diese hier betrachtet wird.

Ein wichtiges Entwurfsziel ist es, den häufig gewählten Pfad der Allokation so kompakt zu implementieren, daß der betreffende Code vom Compiler direkt im Code (inline) eingesetzt werden kann. Weiterhin sollten nur wenige Instruktionen ausgeführt werden müssen, der betreffende Code sollte also keine Schleifen enthalten. Es sind daher Algorithmen vorzuziehen, die den Speicher aus einem linearen Bereich beziehen, d.h. kompaktierende Algorithmen. Varianten, die bei variabler Objektgröße und hoher Allokationsfrequenz eine Freispeicherliste verwenden, sind nicht konkurrenzfähig, da diese nach einem Bereich passender Größe durchsucht werden muß4.1. Bei einem generationalen Algorithmus kann dies für ältere Generationen jedoch durchaus gerechtfertigt sein, da Speicher hier mit deutlich geringerer Frequenz angelegt wird.

Bei Verwendung eines Algorithmus, dem ein linearer Bereich zur Verfüng steht, kann die Allokation folgendermaßen dargestellt werden: der Speicher wird von ,,unten nach oben`` vergeben, d.h. free wird bei jeder Allokation inkrementiert. Das Objekt liegt aber in negativer Richtung zu seiner Adresse, d.h. das erste Wort eines Objektes obj liegt bei obj, das zweite bei obj - wordsize. Zur Allokation von n Bytes werden die folgenden Operationen ausgeführt:

1.
Inkrementiere free um n
2.
Vergleiche free mit der Freispeichergrenze
3.
Falls diese erreicht wurde, rufe den Garbage Collector
4.
Schreibe den Objektkopf nach free

Das Ergebnis der Allokation liegt nun in free vor. Der entsprechende Assembler-Code für einen SPARC-Prozessor besteht aus nur 5 Instruktionen und wird in Abbildung 4.1 dargestellt.

Abbildung 4.1: Einfache nicht thread-sichere Allokation durch Inkrementierung von free
\begin{figure}
\begin{center}
\begin{verbatim}! %g1 = free, %g2 = Freispeicherg...
...] ! schreibe Metadaten in das neue Objekt\end{verbatim} \end{center}\end{figure}

Um diesen Algorithmus thread-sicher zu machen, müßten im Prinzip die ersten beiden Operationen atomar ausgeführt werden. Dies ist so zwar nicht möglich, identisches Verhalten läßt sich jedoch mit Hilfe der SPARC-Operation CAS (,,Compare-And-Swap``) [Herlihy, 1991]) erreichen. Dabei ist zu bedenken, daß der Speicherbus für alle Prozessoren für die Dauer der CAS-Operation blockiert ist -- die Operation stellt also eine Form der Synchronisierung dar. Da die Register prozessorlokal sind, kann free im Fall einer Multiprozessorumgebung nicht mehr in einem Register geführt werden. Stattdessen wird free im Hauptspeicher abgelegt und ein Zeiger darauf im Register gehalten. Das Ergebnis ist in Abbildung 4.2 dargestellt - zur Implementierung werden 9 Instruktionen benötigt. Diese Lösung entspricht prinzipiell dem Algorithmus, der in der Sun ,,HotSpot Performance Engine`` [Sun Microsystems, 1999] verwendet wird.

Abbildung 4.2: Erweiterung von 4.1 zu einer thread-sicheren Allokation durch Verwendung von CAS
\begin{figure}
\begin{center}
\begin{verbatim}![%g1] = free, [%g2] = Freispeich...
...] ! schreibe Metadaten in das neue Objekt\end{verbatim} \end{center}\end{figure}

[Appel, 1989b] schlägt eine weitere Optimierung des Algorithmus vor, bei der der Vergleich mit der Freispeichergrenze entfällt. Stattdessen wird die Speicherseite oberhalb des Freispeichers durch Betriebssystemmechanismen schreibgeschützt. Durch das Schreiben in den Objektkopf wird eine Speicherschutzverletzung ausgelöst. Dies bedeutet, daß der freie Speicher erschöpft ist und eine Garbage Collection ausgeführt werden muß. Der Assemblercode für die Allokation verkürzt sich also auf 7 Instruktionen (s. Abb. 4.3). Die enthaltene Schleife wird nur im relativ seltenen Fall durchlaufen, wenn zwei Threads zeitgleich eine Allokation ausführen.

Abbildung 4.3: Bei der Verwendung von Speicherschutzmechanismen kann der Vergleich mit der Freispeichergrenze entfallen.
\begin{figure}
\begin{center}
\begin{verbatim}![%g1] = fsp, [%g2] = Freispeiche...
... ! schreibe headerword in das neue Objekt\end{verbatim} \end{center}\end{figure}

Voraussetzung für die Verwendung des Schutzmechanismus zur Allokation ist die Initialisierung des neue Speicherbereiches direkt in der Allokationsroutine. Ein späteres Auftreten des Fehlers würde die Behandlung erheblich verkomplizieren. Appel schlägt seine Methode zur Implementierung funktionaler Sprachen vor, die überwiegend wertbasiert arbeiten und diese Werte auch bei der Allokation initialisieren. Bei objektorientierten Sprachen findet die Initialisierung jedoch vorwiegend im Anwendungscode statt und kann daher nicht in der Allokationsroutine ausgeführt werden. In diesem Beispiel wird deshalb ,,rückwärts`` adressiert (s. Abb. 4.4), da die Objektmetadaten auf jeden Fall in den Objektkopf geschrieben werden müssen. Durch die Plazierung des Kopfbereichs hinter das Objekt wird die Schutzverletzung auch dann ausgelöst, wenn das neue Objekt nur teilweise in den geschützten Bereich hineinragt.

Abbildung: Mögliche Objekrepräsentation eines objektorientierten Systems bei der Verwendung von Speicherschutzmechanismen
\begin{figure}
\begin{center}
\epsfig{file=garbage-collection/figures/object-layout1,width=10cm} \end{center}\end{figure}

Die Jalapeño Virtual Machine von IBM Research[Alpern et al., 2000] nutzt ähnlich wie [Appel, 1989b] den Speicherschutz des Betriebssystems. Hier wird er allerdings nicht bei der Allokation sondern zur effizienten Implementiertung des Null-Zeiger-Tests verwendet. Eine Java-VM muß vor der Dereferenzierung eines Objektverweises (also bei jedem invoke und jedem getfield/putfield) testen, ob der Verweis null ist. Ist dies der Fall, so muß die Maschine eine NullPointerException auslösen [Lindholm and Yellin, 1996].

Dieser Test wird in der für das Betriebssystem AIX implementierten Jalapeño Virtual Machine durch den Speicherschutz des Betriebssystems, also in der Regel durch die memory management unit im Prozessor ausgeführt. Um dies zu erreichen wird die in Abbildung 4.5 dargestellte Objektrepräsentation für Skalare und Arrays verwendet. Weiterhin wird die höchste Speicherseite im virtuellen Speicherbereich, beispielsweise der Bereich von FFFF F000 - FFFF FFFF im Falle eines 32 Bit Adressraumes und einer Seitengröße von 4K, gegen Lesezugriffe durch die VM geschützt.

Wird bei dem gewählten Layout eine Null-Referenz dereferenziert, und danach ein Feld des Objektes gelesen, so bedeutet dies effektiv einen Lesevorgang aus dem geschützten Speicherbereich. Dies löst eine Ausnahme aus, die die VM in eine NullPointerException umwandelt.

Da vor jedem Array-Zugriff eine Indexüberprüfung durchgeführt werden muß, ist es ausreichend, die Längeninformation des Arrayobjektes an einem negativen Offset zur Objektadresse abzulegen plaziert werden. Die Maschine muß also, um den Test ausführen zu können, vor jedem Zugriff die Längeninformation lesen und erreicht somit auf gleiche Weise den Null-Test.

Abbildung: Objektrepräsentation für (i) Objekte und (ii) Arrays in IBMs Jalapeño Virtual Machine
\begin{figure}
\begin{center}
\epsfig{file=garbage-collection/figures/object-layout2,width=13cm} \end{center}\end{figure}

Der in Abb. 4.2 dargestellte Allokations-Algorithmus ist zwar thread-sicher, verwendet jedoch die SPARC-Operation CAS. Da diese aufgrund der notwendigen Sychronisation zwischen den vorhandenen Prozessoren relativ teuer ist, verwenden die Sun Research VM [White and Garthwaite, 1998] und die IBM Virtual Machine [Gu et al., 2000] einen zweistufigen Mechanimus: jeder Thread legt zunächst einen lokalen Speicherbereich (,,Local Allocation Buffer``, LAB) an, aus dem er dann Speicher ohne jegliche Synchronisation vergeben kann. Die Allokation im LAB kann also nach dem Algorithmus aus Abb. 4.1 erfolgen. Ist dieser Bereich erschöpft, so wird unter Verwendung von CAS oder eines anderen Synchronisationsmechanismus ein neuer LAB erworben. Da unter Umständen sehr viele Threads gleichzeitig aktiv sein können (in Serversystemen können dies mehrere 100 sein), dürfen die LAB bei einer großen Anzahl Threads nicht zu groß sein. Die Größe der neu erzeugten LAB wird daher in der Sun Research VM abhängig von der Anzahl der Threads dynamisch angepaßt.

[Shivers et al., 1999] schlagen als eine weitere Optimierung die ,,Static Allocation Arena`` vor. Hierbei wird am Anfang jedes vom Compiler erzeugten basic block bereits der gesamte benötigte Speicher angelegt. An den ursprünglichen Allokationspunkten werden die einzelnen Objekte lediglich initialisiert. Bei dieser Methode fällt also pro basic block nur eine Allokation an.

Eine effiziente Implementierung des Allokations-Algorithmus zeigt sich also die enge Verzahnung mit dem Compiler aufgrund der Plazierung des Codes inline. Weiterhin wird offenbar, daß ein Multiprozessorsystem als zu unterstützende Zielplatform eine effiziente Implementierung erheblich erschwert.


next up previous contents
Next: Exakte Garbage Collection für Up: Implementierung der Speicherverwaltung Previous: Implementierung der Speicherverwaltung   Inhalt

2001-02-28