Garbage Collector

Eine Sammlung verfolgen

Vollsammlung oder Sammlung nur junger Objekte, einen Heap und ein Wurzelobjekt oder keine Wurzel wählen. Heap vorbereiten erzeugt die vollständige unveränderliche Zeitleiste und zeigt Schritt 0. Die gewählte Wurzel bleibt erhalten. Beim Zufallsheap sind 8–32 Objekte und ein ganzzahliger Seed von 0 bis 4294967295 wählbar. Anzahl und Seed werden beim festen Heap mit zwei Zyklen nicht verwendet.

Genaues Schrittfeld, Zeitleistenregler, Zurück, Weiter, Anfang und Ende zeigen dieselben gespeicherten Zustände. Die Wiedergabe läuft mit 1, 3 oder 10 Schritten je realer Sekunde und stoppt am Ende; Abspielen am Ende startet wieder bei Schritt 0. Manuelle Schrittwahl und Tempoänderung pausieren. Eine verdeckte Ansicht friert den Schritt ein und setzt nur eine zuvor laufende Wiedergabe fort. Navigation erhält ein pausiertes Ergebnis; Neuladen oder Sprachwechsel stellt gültige Einstellungen wieder her und wartet auf Heap vorbereiten.

Vollsammlung

Die Wurzeln füllen eine FIFO-Arbeitsliste. Jeder Markierschritt besucht ein Objekt, markiert es und reiht zulässige unbesuchte Ziele ein. Ist die Arbeitsliste leer, prüft die Freigabephase jedes Objekt: Markierte bleiben, unmarkierte werden freigegeben. Ein unerreichbarer Referenzzyklus wird damit auch dann gesammelt, wenn seine Mitglieder aufeinander verweisen.

Konservative Sammlung nur junger Objekte

Nur junge Objekte gehören zur Sammlungsmenge. Junge Wurzeln und sämtliche Verweise von alten auf junge Objekte liefern Einstiege. Diese Remembered-Kanten erscheinen als gestrichelte gerichtete Verweise und werden ausdrücklich aufgelistet. Das Durchlaufen bleibt innerhalb junger Objekte. Alte Objekte bleiben immer erhalten, auch wenn sie global unerreichbar sind; ihre jungen Ziele können daher ebenfalls konservativ überleben.

Die Freigabe betrifft nur unmarkierte junge Objekte. Ein eigener Beförderungsschritt ändert alle überlebenden jungen Objekte nach alt. Diese bewusst vereinfachte Regel nach einmaligem Überleben ist keine Altersregel einer JVM oder CLR. Die genaue Liste der Alt-zu-Jung-Kanten ist hier weder eine Card-Table-Näherung noch ein G1-Nachbau.

Heap-Beispiele

Der feste Heap hat acht Objekte und die Verweise 0→1, 1→2, 2→1, 3→4, 4→5 und 5→4. Objekte 6 und 7 haben keine ausgehenden Verweise. Objekte 0, 3 und 7 sind alt, die übrigen jung. Eine Vollsammlung mit Wurzel 0 behält nur 0, 1 und 2. Ohne Wurzeln wird alles freigegeben. Die Sammlung nur junger Objekte mit Wurzel 0 oder ohne Wurzeln behält 0, 1, 2, 3, 4, 5 und 7 und gibt 6 frei: Die Kanten 0→1 und 3→4 schützen beide jungen Zyklen.

Der Zufallsheap verwendet den deterministischen mulberry32-Generator. Jedes Objekt hat bis zu zwei unterschiedliche zufällige Zielverweise; Selbstverweise sind möglich. Durch 3 teilbare IDs sind alt, die übrigen jung. Gleicher Seed und gleiche Einstellungen ergeben denselben Heap und dieselbe Zeitleiste.

Die Grafik lesen

Kreise mit J stehen für junge Objekte, Quadrate mit A für alte. R bezeichnet eine Wurzel, ein gestrichelter Ring ein eingereihtes Objekt und ein durchgezogener Außenring das aktive Objekt. Ein Haken bedeutet markiert, ein durchgestrichenes Objekt freigegeben. Aktive ausgehende Verweise werden betont. Freigegebene Objekte und blasse frühere Verweise bleiben zur Erklärung an ihren Positionen; eine Kompaktierung wird nicht dargestellt. Die Tabelle zeigt die tatsächliche Generation, gespeicherte Ziel-IDs und den Zustand jedes Objekts. Die Arbeitsliste steht in FIFO-Reihenfolge.

Umfang und Aufwand

Dies ist ein kleines Stop-the-world-Lehrmodell. Während eines Laufs werden keine Objekte angelegt; Finalizer, schwache Verweise, Kompaktierung und nebenläufige Write-Barriers fehlen. Der Sammlungsalgorithmus benötigt O(V + E) Arbeit für V Objekte und E Verweise. Ein vollständiger Zustandsabzug nach jedem Schritt benötigt für diese Lehrzeitleiste O(V² + VE) Speicher. Das ist keine Aussage zum Speicherbedarf oder zur Leistung eines realen Garbage Collectors.

Quellen

Microsoft: Grundlagen der Garbage Collection und Oracle: G1 und Remembered Sets.