Wie bereits in Abschnitt 2.2.2 beschrieben, gibt es prinzipiell zwei Wege, um die Exaktheit der Garbage Collection zu garantieren: Markierung und Referenztabellen.
Implementierungen von Sprachen, die statisch nicht zwischen Referenz und Skalar unterscheiden, sind für Exaktheit auf die Verwendung von Markierungen angewiesen - Beispiele für solche Sprachen sind Smalltalk, Beta, Self und TL-2. Alle uns bekannten Implementierungen dieser Sprachen verwenden Markierungen, um Exaktheit zu erreichen.
Statisch getypte, monomorphe Sprachen können ohne Markierungen implementiert werden, wenn der Compiler dem Laufzeitsystem die entsprechenden Informationen zur Verfügung stellt. Handelt es sich um eine rein funktionale Sprache, so können sogar polymorphe Sprachen ohne Markierungen implementiert werden, wie [Appel, 1989a] gezeigt hat.
Java stellt eine statisch getypte, nicht funktionale und bezüglich der Unterscheidung von Skalaren und Referenzen monomorphe Sprache dar, die zur Laufzeit über die notwendigen Informationen verfügt, um exakte Garbage Collection ohne Markierungen realisieren zu können. Dies liegt darin begründet, daß der in [Lindholm and Yellin, 1996] spezifizierte Bytecode Operationen mit Skalaren und Referenzen ausreichend unterscheidet. Außerdem ist die Breite von Zahlenwerten durch die Sprachdefinition [Gosling et al., 1996] vorgegeben - so muß z.B. ein int in Java immer eine Breite von 32 Bit besitzen und vorzeichenbehaftet sein.
Diese beiden Gründe legen nahe, die Speicherverwaltung einer Java VM ohne Markierungen zu implementieren. Daraus folgt, daß zu jedem Zeitpunkt, an dem eine Garbage Collection stattfinden kann, Referenztabellen zur Verfügung stehen müssen, die die Typen der aktiven Stackinhalte und lokalen Variablen beschreiben4.2.
Wird der Bytecode in Maschinencode übersetzt, so findet zur Übersetzungszeit eine Zuordung der abstrakten lokalen Variablen zum Laufzeitstack oder Registern statt. Diese Zuordung muß vom Compiler in Form von Stack- und Registertabellen abgelegt werden; diese können bei der Garbage Collection verwendet werden, ohne die Integrität der Maschine zu gefährden. Wird der Bytecode interpretiert, so müssen die Tabellen auf eine andere Weise erstellt werden.
Unabhängig vom Ausführungsmodell sollte vermieden werden, für jede Instruktion eine eigene Referenztabelle zu erzeugen, da diese leicht mehr Platz einnehmen können, als der Code selbst. Daher werden vorausberechnete diese in der Regel nur für bestimmte Punkte - sogenannte ,,GC Points`` oder ,,Safepoints`` - ermittelt. Die hiermit verbundenen Probleme und deren Lösung werden in Abschnitt 5.3 näher beschrieben.
Eine bemerkenswerte Ausnahme stellt die Java-Implementierung der Intel Microprocessor Research Labs dar [Sichnoth et al., 1999]: Durch geschickte Komprimierung der Referenztabellen wird der Platzbedarf so stark eingeschränkt, daß für jede generierte Maschineninstruktion eine Tabelle zur Verfügung gestellt werden kann.
Im folgenden werden zwei Methoden beschrieben, um Referenztabellen für interpretierten Java-Bytecode zu erstellen: Das parallele Führen eines Markierung-Stack und die abstrakte Interpretation von Bytecode.