Compilerbau/Kapitel 6: Garbage Collection

Aus Halloserv Wiki

Wechseln zu: Navigation, Suche

In einem fertigen Programm ist die Garbage Collection (Müllentsorgung, GC) dafür zuständig, nicht mehr benutzte Objekte aus dem Speicher zu entfernen, um Platz für neue zu schaffen. Sie ist nicht automatisch Teil jeden Programms, sondern eine Optimierung, respektive Automatisierung.

Die Speicherverwaltung kann man in zwei Bereiche unterteilen:

  • lokale Variablen, Rücksprungadressen
    • Lebensdauer entspricht Funktionsaufruf
    • Anlegen auf dem Stack, Freigabe ist billig (Zurücksetzen des Stackpointers)
  • Closures, Vektoren, Objekte, dynamische Datenstrukturen
    • Lebensdauer unabhängig von Funktionsaufruf
    • Ablage auf Stack nicht möglich
    • Stattdessen Ablage im Heap

Bei der GC werden wir uns deshalb mit den im Heap abgelegten Objekten beschäftigen. Im Gegensatz zur manuellen Heapverwaltung (malloc/free, mit Gefahr von memory leaks, bzw. Fehlerpointern) legt man bei der GC die Objekte lediglich an, und die GC erledigt das Verwerfen automatisch.

Wir beginnen das Kapitel mit einer allgemeinen Einführung in die GC und werden dann einige Algorithmen vorstellen, um sie zu realisieren.

Inhaltsverzeichnis

Allgemein

Die Garbage Collection hat zwei Aufgaben:

  1. Feststellen, welche Objekte im Heap noch lebendig (werden noch benutzt) sind.
  2. Freigeben der toten Obejkte.

Aufgabe 1 ist leider unentscheidbar (nach dem Satz von Rice). Wir können allerdings eine Approximation verwenden: Alle Objekte, die vom Stack und globalen Variablen (zusammen: Wurzeln) erreichbar sind, werden noch verwendet (sind lebendig). Dies ist eine sichere Approximation, da alle anderen Objekte nicht mehr durch eine Zeigerkette von der Wurzel aus erreicht werden können.

Um festzustellen, ob ein Objekt lebendig ist, müssen wir demnach den Zeigern folgen. Allerdings folgt daraus ein Problem: Wir müssen die Zeiger kennen. Das ist ein Problem, weil nicht jede Speicherzelle einen Zeiger enthält und bei manchen Sprachen die Eigenschaft, Zeiger zu sein, nicht statisch vorhersagbar ist (bei polymorphen Funktionen in OCaml beispielsweise).

Die Lösung für das Zeigererkennungsproblem nennt sich Tagging und verwendet 1-2 Bits zur Angabe des Typs:

Verfahren: Tagging

Ein Wort hat folgende Form: Image:6-Procedure-Word.png

Wir führen nun die Invariante ein, dass die letzten zwei Bits nicht benutzt werden. Dann gelingt die Darstellung von Zeigern und Zahlen so:

  • Zeiger: Image:6-Procedure-Pointer.png l r,s(-2), Adressierung mit Offset -2
  • Zahlen: Image:6-Procedure-Number.png Anpassen der Operationen auf 30-Bit Zahlen

Objektrepräsentation kann dann so gelöst werden:

Image:6-Procedure-Object.png

Mark & Sweep

Mark & Sweep benutzt eine sogenannte Freelist um freie Speicherbereiche zu markieren. Neue Objekte werden in einen freien Speicherbereich eingefügt, Adressen nicht mehr benutzter Objekte bei der Garbage Collection der Freelist hinzugefügt. Mark & Sweep (inklusive nichtrekursiver Tiefensuche) wurde schon in Lisp eingesetzt, es ist eine Technik der 60er Jahre.

Allokation

Wir gehen davon aus, dass alle aktuell freien Speicherbereiche bereits in der Freelist verkettet sind. Wir suchen dann einen passenden Bereich in der Freelist und entfernen ihn aus dieser, nachdem das Objekt dort eingefügt wurde.

Bei der Allokation können zwei Probleme auftauchen, wenn kein passender Speicherbereich vorhanden ist:

  • Alle Speicherbereiche sind zu klein, obwohl in der Summe ausreichend Speicher vorhanden ist (externe Fragmentierung). In diesem Fall führt man Garbage Collection mit Verschmelzen von benachbarten Speicherbereichen durch. Dies muss aber nicht zum Ziel führen, da Mark & Sweep nicht kompaktifiziert.
  • Alle Speicherbereiche sind zu gross. Tritt dieser Fall ein, muss man einen Speicherbereich aufspalten und nur teilweise verwenden. Es bleibt ein ungenutzter Rest (interne Fragmentierung), die Aufspaltung provoziert auch externe Fragmentierung.

Garbage Collection

Die Garbage Collection läuft in zwei Schritten ab:

  1. Tiefendurchlauf beginnend mit den Wurzeln, markiere alle besuchten Objekte (mark).
  2. linearer Durchlauf des Heaps (sweep):
    • nichtmarkierte Objekte kommen in die Freelist
    • bei markierten Objekten wird die Markierung entfernt

Ein Nachteil von Mark / Sweep ist die kostspielige rekursive Tiefensuche: sie verbraucht Stackplatz proportional zur Heapgröße - zu einer Zeit, wo der Heap voll ist. Man nutzt deshalb die Technik der nichtrekursiven Tiefensuche (Schorr-Waite). Die nichtrekursive Tiefensuche codiert den Stack in den Objekten durch Zeigerumkehrung mit zwei Zeigern:

Beispiel: Nichtrekursive Tiefensuche

Image:6-Nonrecursive-DFS.png

Mark & Sweep benötigt mit nichtrekursiver Tiefensuche konstanten Platz und eine lange Laufzeit.

Reference Count

Genau wie beim Mark & Sweep Algorithmus benutzt Reference Count eine Freelist. Beim Reference Count-Algorithmus besitzt jedes Objekt ausserdem einen Zähler, der die Anzahl der Zeiger auf das Objekt nachhält. Bei Operationen auf den Zeigern wird der Zähler angepasst:

  • jedes Kopieren eines Zeigers führt zur Inkrementierung des Zählers
  • jedes Verwerfen eines Zeigers führt zur Dekrementierung des Zählers

Falls der Zähler eines Objektes auf 0 fällt, wird das Objekt in die Freelist eingehängt.

Diese Verfahren ist langsam, benötigt zusätzlichen Code und Speicherzugriffe. Ein weiteres Problem ist, dass es zyklische Datenstrukturen nicht verarbeiten kann:

Beispiel: zykliche Datenstruktur

Image:6-Reference-Count.png

Um das Problem der zyklischen Datenstrukturen zu beheben, kann man zusätzliche Läufe von Mark & Sweep einsetzen.

Copying Collection

Die Copying Collection nutzt keine Freelist, sondern teilt den Heap in zwei Hälften gleicher Größe auf: FROMSPACE und TOSPACE. Der Algorithmus läuft dann wie folgt:

Image:6-Copying-Collection.png
  • Allokation wird linear fortlaufend im FROMSPACE vorgenommen.
  • Ist der FROMSPACE gefüllt, wird die Garbage Collection durchgeführt:
    • Beginnend bei den Wurzeln werden erreichbare Objekte in den TOSPACE kopiert.
    • Danach ist der FROMSPACE leer, die Rollen von FROMSPACE und TOSPACE werden getauscht.

Beim Kopieren der Objekte vom FROMSPACE zum TOSPACE während der Garbage Collection ändern sich alle Adressen, dies wird mit Hilfe von Umleiten gelöst. Der Algorithmus zum Anpassen eines Objektes (verschiebt Kind-Objekte) lässt sich so ausdrücken:

<div style="padding-left:4px;" id="Verfahren: forward">Verfahren: forward
forward(p) =
  if p \in TOSPACE then
    return p 
  else
    if p -> f_1 \in TOSPACE then
      return p -> f_1
    else
      foreach  f_i:
        next -> f_i = p -> f_i
      p -> f_1 = next
      next += size(p)
      return p -> f_1

</div>

Cheneys Algorithmus

Cheneys Algorithmus stellt eine Verbesserung der Copying Collection dar:

Algorithmus: Cheney
  1. foreach\ w \in \mbox{Wurzeln}
    \,\!w = forward(w)
  2. \,\!scan = \mbox{TOSPACE}
  3. \,\!while\ scan < next\ do
    foreach\ f_i
    scan \to f_i = forward(scan \to f_i)
    \,\!scan += size(scan)
  4. vertausche FROMSPACE und TOSPACE

Auch mit Cheneys Algorithmus gibt es Nachteile beim Einsatz von Copying Collection. Sie hat doppelten Speicherbedarf und zerstört durch das Kopieren (Breitensuche!) die Lokalität, was das Caching schwierig macht.

Generationed Collection

Generational Collection nutzt ein ähnliches Prinzip wie die Copying Collection, nur werden aufgrund einiger Beobachtungen mehr als zwei Speicherbereiche genutzt:

  • die meisten Objekte sind jung
  • Objekte, die schon mehrere GC überlebt haben, leben vermutlich noch länger

Damit die Garbage Collection effektiver wird, werden bei Generational Collection die jüngeren Objekte häufiger getestet, und der Heap in eine Reihe von Speicherbereichen G_0, \ldots, G_n aufgeteilt, die dem Alter der Objekte entsprechen.

Neue Objekte werden in G0 alloziert. Falls G0 voll ist, führt man eine Copying Collection auf G0 aus, mit G1 als TOSPACE. Wurde G0 häufig genug geleert oder sind G0 und G1 voll, führt man die Garbage Collection auf G0 und G1 aus: GC(G_0 + G_1 \to G_2).

Die Größe der Gi wird oft exponentiell größer gesetzt.

Garbage Collection

Wurzeln sind alle Objekte im Stack, globale Variablen sowie alle Objekte, die in "älteren" Generationen (als diejenigen im FROMSPACE) liegen, und "junge" Objekte referenzieren.

Beobachtung zeigt, dass alte Objekte selten auf junge zeigen, da dies nur durch "späte Zuweisung" möglich ist. Um herauszufinden, welche Objekte aus "älteren" Generationen referenziert werden, gibt es verschiedene Methoden:

  • Remembered Set: Jedes Update eines alten Objekts trägt die geschriebene Adresse in ein Remembered Set ein.
  • Card Marking: Teile die Gi in Blöcke der Größe 2k ein. Beim Update markiere in einem Bitvektor den betroffenen Block, bei GC betrachte alle Altobjekte des markierten Blocks als Wurzeln.
  • Page Marking: Verwende die Blöcke des virtuellen Speichers; markiere Blöcke aus alten Generationen als schreibgeschützt. Wird ein altes Objekt verändert, gibt es einen memory fault: fange diesen ab und markiere Block im Bitvektor.

Inkrementelle Garbage Collection

Alle bisher betrachteten Versionen von Garbage Collection haben das Problem, dass sie bei der Durchführung das laufende Programm anhalten müssen. Dieses Verhalten ist insbesondere in Echtzeitumgebungen unerwünscht. Eine Abhilfe schafft die inkrementelle Garbage Collection. Sie nutzt zwei Teile:

  • den Mutator, ein Programm, das die Arbeit macht, Objekte anlegt und verändert und
  • den Collector, der den Speicher bereinigt.

Es gibt zwei Varianten der inkrementellen Garbage Collection, die erste heisst einfach inkrementelle Garbage Collection: Hier stößt der Mutator den Collector an, der einen Teil der Garbage Collection erledigt. Die zweite Version ist die nebenläufige Garbage Collection, in der Mutator und Collector gleichzeitig arbeiten.

Grundlage aller inkrementeller Garbage Collection bildet ein 3-Farben Markierungsschema, das den Verarbeitungsstatus eines Objektes aus Sicht des Collectors beschreibt:

  • weiß bedeutet, dass das Objekt noch nicht besucht wurde,
  • ein graues Objekt wurde besucht, aber noch nicht alle seiner Kinder (bei Mark & Sweep etwa: Objekt befindet sich auf dem Stack, bei Cheney: in j-ter Queue, also zwischen scan und next),
  • ein schwarzes Objekt wurde besucht und ebenso alle seine direkten Kinder (d.h diese sind entweder grau oder schwarz).

Allokation

Zur Allokation eines Objektes mit N Worten kann man folgendes Schema nutzen:

Schema: Allokation in inkrementeller GC

Overhead für GC:

  1. Aufruf alloc(N)
  2. teste next + N < limit (sonst GC anstossen)
  3. lösche im Speicher M: M[next], ..., M[next + N - 1]
  4. result = next
  5. next += N
  6. return result

In jedem Fall notwendige Schritte für die Allokation:

  1. Verschiebe result in ein anderes Register
  2. Initialisiere Objekt

Das Schema kann noch optimiert werden, indem man einzelne Schritte zusammenfasst:

  • 1/6: inlining
  • 4/A: verschmelzen
  • 3/B: verschmelzen
  • 2/5: können für mehrere Allokationen in einem linearen Stück Code (Basic Block: Codestück ohne Sprünge) zusammengefasst werden.

Garbage Collection

Es gelten zwei Invarianten für den Mutator und den Collector:

  • ein schwarzes Objekt zeigt nie auf ein weißes
  • jedes graue Objekt ist in der Datenstruktur des Collectors
Collector

Es gilt: Alle Objekte sind weiß, Wurzeln befinden sich in grauen Wurzelobjekten.

Dann verfolgt der Collector dieses Vorgehen:

Verfahren: Collector

while\ \exists\ \mbox{graues Objekt}

p = ein graues Objekt

folgender Part muss atomar erfolgen:

foreach\ f_i
if\ p \to f_i\ \mbox{ist weiß}
färbe fi grau (in Datenstruktur des Collectors)
färbe p schwarz
Mutator

Für den Mutator gibt es verschiedene Möglichkeiten:

  • Jedes Update wird instrumentiert mit einem Test, ob ein weißes Objekt in ein schwarzes Objekt geschrieben wird: wenn dies geschieht, muss man das schwarze Objekt in der Datenstruktur des Collectors grau färben (write barrier: Software oder Hardware).
  • Der Collector markiert Seiten, die nur schwarze Objekte enthalten. Bei Schreibzugriff wird die ganze Seite grau gefärbt.
  • Wenn der Mutator auf Objekt b zugreift, färbt er es grau und verschiebt es in die Datenstruktur des Collectors, also kann Invariante 1 nie verletzt werden (read barrier).

Bahrers Algorithmus

Der Algorithmus von Bahrer ist eine inkrementelle Version von Cheneys Algorithmus. Er hat eine zusätzliche Invariante zu den beiden inkrementellen Invarianten:

  • Der Mutator benutzt nur TOSPACE Zeiger.

Die Garbage Collection läuft dann folgendermassen ab:

Verfahren: Bahrers Algorithmus
Image:6-Bahrers-Algorithm.png

Die Allokation findet findet im TOSPACE in einem zusammenhängenden Speicherbereich statt, der durch next und limit begrenzt ist (siehe Illustration).

  1. FLIP:
    • vertausche FROMSPACE und TOSPACE
    • leite alle Wurzeln um (in den TOSPACE)
  2. bei jeder Allokation:
    • leite einige Zeiger um (inkrementeller Part)
    • lege neues Objekt am Ende des TOSPACE ab
  3. bei jedem Feldzugriff könnte ein Zeiger auf ein weißes Objekt benutzt werden - falls der Wert des Feldzugriffs in den FROMSPACE zeigt, wird das Objekt in den TOSPACE umgeleitet.
  4. pausiere, falls scan = next (siehe Illustration)

Interface zum Compiler

Die Garbage Collection wird im Compiler vorbereitet. Er kümmert sich um die Anpassung von

  • Allokation
  • Datenlayout von Heapobjekten (zum Finden/Markieren von Zeigern)
  • Wurzeln
  • Code für read/write Barrieren
Von „http://www.halloserv.de/wiki/index.php/Compilerbau/Kapitel_6:_Garbage_Collection“