Design und Implementierung eines Garbage-Collectors für Programmcode

Student:Matthias Hampel
Title:Design und Implementierung eines Garbage-Collectors für Programmcode
Type:study thesis
Advisors:Schell, D.; Philippsen, M.
State:submitted on January 13, 2006
Prerequisits:

Bei eingebetteten Systemen ist Speicher ein wertvolles Betriebsmittel und muss deswegen sorgfältig verwaltet werden. Aus diesem Grund wurde am Lehrstuhl ein Speichermanager für Programmcode entwickelt, welcher den Code nicht seitenbasiert in den Speicher lädt, sondern maximale Basisblöcke als Granulat verwendet. Da Basisblöcke die Eigenschaft besitzen, dass ihr Code immer vollständig ausgeführt wird, kann garantiert werden, dass niemals unnötiger Programmcode geladen wird.
Im Falle eines Speicherengpasses soll aktuell nicht mehr benötigter Code aus dem Speicher verdrängt werden, um Platz für neu zu ladenden Code zu machen (Garbage Collection). Die aktuelle Implementierung verwendet zu diesem Zweck einen einfachen Mark-Sweep Garbage Collector.

Topic:

Im Verlauf der Arbeit sollen folgende Punkte untersucht werden und einige Speicherbereiniger (Garbage-Collectoren, GC) implementiert werden:

  • Welche Eigenschaften unterscheiden Basisblöcke von Objekten wie sie z.B. in Java erzeugt werden? (z.B. viele Schleifen (Zyklen), kleine Größe, Blattfunktionen, Lebenszeit, etc.)
  • Können diese Eigenschaften den Speicherbereinigungsprozess unterstützen, welche Informationen sollen also dem Speicherbereiniger zur Verfügung gestellt werden?
  • Schleifen im Code ergeben Zyklen zwischen Basisblöcken. Ist es für den Speicherbereiniger möglich Zyklen im Code zu erkennen? Kann der GC diese Informationen nutzen?
  • Der aktuell implementierte GC verwendet eine blockorientierte Verwaltungsstruktur, in welcher der komplette Speicher in gleich große Blöcke aufgeteilt ist. Da dies zu Speicherverschnitt führt, soll untersucht werden, welche Vorteile an dieser Stelle eine Freispeicherliste liefert (d.h. eine Liste/Baum, in der alle freien Speicherbereiche gespeichert werden)?
  • Kann ein inkrementeller Speicherbereiniger wie z.B. der "Train"-Algorithmus [3] eingesetzt werden, wobei bei jeder Speicherallokation ein kleiner Teil des Speichers aufgeräumt wird?
  • Implementierung einiger Speicherbereiniger und Evaluation in Hinsicht auf Performanz, Code-Größe, etc.

Literatur:
[1] Hans Boehm, A garbage collector for C and C++, http://en.wikipedia.org/wiki/Boehm_garbage_collector
[2] Richard Jones and Rafael Lins, Garbage Collection: Algorithms for Automatic Dynamic Memory Management, ISBN: 0471941484
[3] Matthias Ernst, Daniel Schneider: Inkrementelle und nebenläufige Garbage Collection, http://www.virtualmachine.de/2000-ernst-schneider/node54.html

watermark seal