2.2 Tracing Algorithmen

• Lebendigkeit von Objekten wird über die potentielle Erreichbarkeit dieser vom Root Set festgestellt

2.2.1 Mark-Sweep

1. führe Tiefen- oder Breitensuche startend mit dem Root Set aus und markiere alle durch Referenzbeziehungen erreichbaren Objekte (Bitmap, Tabelle oder internes Bit)
2. durchsuche ganzen Speicher nach unmarkierten Objekten und gib diese frei

Probleme:

• Heap Fragmentierung, da Objekte nie verschoben werden
• Allokationsprobleme von unterschiedlich großen Objekten (In welche Lücke paßt Objekt xy am besten?)
• zeitliche Kosten sind proportional zur Heapgröße, weil alle lebendigen Objekte markiert und alle Garbage Objekte gesammelt werden
• zeitliche und räumliche Lokalitätsunterschiede von Objekten (Mit der Zeit häufen sich lebendige Objekte unterschiedlichen Alters auf den einzelnen Speicherseiten. Somit erstreckt sich der Working Set [=Menge der aktuell benutzten Objekte] auf viele verschiedene Speicherseiten, was zu vielen Cache Miss oder im Extremfall zu intensiven Paging führen kann.)

2.2.2 Mark-Compact

1. markiere alle lebendigen Objekte (siehe Mark-Sweep)
2. verschiebe alle markierten Objekte so, das ein kontinuierlicher, freier Speicherbereich entsteht (meist wird der gesamte Heap linear nach lebendigen Objekten abgesucht und ein gefundenes Objekt wird so verschoben, daß es direkter Nachbar des zuletzt verschobenen Objektes werden)

Vorteile gegenüber Mark-Sweep:

• Heap Fragmentierung wird total umgangen
• Allokation von Speicher ist simpel
• Garbage Objekte müssen nicht gesondert beachtet werden (Kompaktierung wirft Garbage einfach raus, keine Freispeicherliste notwendig)

Probleme:

• Laufzeitkosten sind groß (1. Markieren, 2. neue Speicheradresse bestimmen und alte Referenzen updaten, 3. Objekt verschieben)