C1...ser unter Verwendung der auf dem FPGA verfügbaren internen Speicher umgesetzt und muss somit nicht vom Speichermanager verwaltet werden. Zur Beschleunigung der Kontextwechsel

TeI1DC1

C11D=

=1

T

Ie

Technische Universität DresdenFakultät Informatik

Institut für Technische Informatik (TeI)Professur für VLSI-Entwurfssysteme, Diagnostik und Architektur

Großer Beleg

Entwurf und Implementierung verschiedenerGarbage-Collector-Strategien für die Java-Plattform SHAP

Peter ReichelSommersemester 2007

Matrikelnummer: 3013586verantwortlicher Hochschullehrer: Prof. Dr.-Ing. habil R. G. SpallekBetreuer: Dipl.-Inf. Martin ZabelDatum: 5. Oktober 2007

Selbstständigkeitserklärung

Ich erkläre, dass ich die vorliegende Arbeit selbstständig, unter Angabe aller Zitate und nurunter Verwendung der angegebenen Literatur und Hilfsmittel angefertigt habe.

Dresden, den 5. Oktober 2007

Inhaltsverzeichnis

1 Einleitung 1

2 Vorbetrachtungen 32.1 SHAP-Plattform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2.1.1 Aufbau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.1.2 Objektbasierter Speicherzugriff . . . . . . . . . . . . . . . . . . . 42.1.3 Echtzeitverarbeitung . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.2 Garbage Collection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.2.1 Aufgabe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.2.2 Klassische Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . 72.2.3 Copying-Garbage-Collection . . . . . . . . . . . . . . . . . . . . . 92.2.4 Generational-GC . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.2.5 Tri-Color-Marking . . . . . . . . . . . . . . . . . . . . . . . . . . 112.2.6 Inkrementelle und Parallele Verfahren . . . . . . . . . . . . . . . . 122.2.7 Garbage Collection unter Echtzeitbedingungen . . . . . . . . . . . 122.2.8 Hardwareunterstützung . . . . . . . . . . . . . . . . . . . . . . . . 13

3 Entwurf 153.1 Anforderungen an den Speichermanager . . . . . . . . . . . . . . . . . . . 15

3.1.1 Benötigte Funktionen . . . . . . . . . . . . . . . . . . . . . . . . . 153.1.2 Vermeidung langer Unterbrechungen . . . . . . . . . . . . . . . . 153.1.3 Speicherreservierung in konstanter Zeit . . . . . . . . . . . . . . . 153.1.4 Bereitstellung von ausreichend freiem Speicher . . . . . . . . . . . 17

3.2 Grundkonzept der Garbage Collection . . . . . . . . . . . . . . . . . . . . 173.3 Objekte und Referenzen . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3.3.1 Indirektionskonzept . . . . . . . . . . . . . . . . . . . . . . . . . . 183.3.2 Verwaltung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193.3.3 Allokation neuer Objekte . . . . . . . . . . . . . . . . . . . . . . . 20

3.4 Segmentkonzept . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213.4.1 Teilung des Speichers . . . . . . . . . . . . . . . . . . . . . . . . 213.4.2 Verwaltung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213.4.3 Allokationssegment und Speicherreservierung . . . . . . . . . . . . 22

3.5 Phasen der Garbage Collection . . . . . . . . . . . . . . . . . . . . . . . . 223.5.1 Root-Scan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223.5.2 Heap-Scan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243.5.3 Überwachung des Stacks . . . . . . . . . . . . . . . . . . . . . . . 25

II Inhaltsverzeichnis

3.5.4 Markierungsphase eines Segments . . . . . . . . . . . . . . . . . . 263.5.5 Freigabephase eines Segments . . . . . . . . . . . . . . . . . . . . 27

3.6 Begrenzung der Objektanzahl im Segment . . . . . . . . . . . . . . . . . . 273.7 Auswahlfunktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283.8 GC-Triggering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

3.8.1 Speicherauslastung . . . . . . . . . . . . . . . . . . . . . . . . . . 293.8.2 Zeitabhängig . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

3.9 Zielsegment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293.10 Steuerung des Garbage Collectors . . . . . . . . . . . . . . . . . . . . . . 303.11 Segmentgröße und Fragmentierung . . . . . . . . . . . . . . . . . . . . . . 303.12 Variationen der Strategie . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

3.12.1 Frühere Freigabe der Referenzeinträge . . . . . . . . . . . . . . . . 313.12.2 Voralterung von Segmenten . . . . . . . . . . . . . . . . . . . . . 313.12.3 Generationen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

4 Implementierung 354.1 Speicherlayout und Strukturen . . . . . . . . . . . . . . . . . . . . . . . . 35

4.1.1 Referenzeinträge . . . . . . . . . . . . . . . . . . . . . . . . . . . 364.1.2 Segmenteinträge . . . . . . . . . . . . . . . . . . . . . . . . . . . 364.1.3 Alignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

4.2 Struktur des Speichermanagers . . . . . . . . . . . . . . . . . . . . . . . . 374.2.1 Memory-Access-Manager . . . . . . . . . . . . . . . . . . . . . . 384.2.2 Referenz-Manager . . . . . . . . . . . . . . . . . . . . . . . . . . 384.2.3 Segment-Manager . . . . . . . . . . . . . . . . . . . . . . . . . . 404.2.4 Allokationssegment . . . . . . . . . . . . . . . . . . . . . . . . . . 434.2.5 MMUCtrl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434.2.6 MMUStat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

4.3 Aufbau des Garbage Collectors . . . . . . . . . . . . . . . . . . . . . . . . 474.3.1 Struktur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474.3.2 Komponenten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474.3.3 Steuerung des Garbage Collectors . . . . . . . . . . . . . . . . . . 504.3.4 Varianten der Garbage Collection . . . . . . . . . . . . . . . . . . 51

4.4 Syntheseergebnisse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

5 Auswertung 555.1 Test-Applikationen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

5.1.1 Caffeine Benchmark . . . . . . . . . . . . . . . . . . . . . . . . . 555.1.2 Sudoku-Löser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 555.1.3 FScript . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

5.2 Vergleich der unterschiedlichen GC-Varianten . . . . . . . . . . . . . . . . 565.2.1 Latenz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 565.2.2 GC-Zyklendauer . . . . . . . . . . . . . . . . . . . . . . . . . . . 585.2.3 Belegte Ressourcen . . . . . . . . . . . . . . . . . . . . . . . . . . 595.2.4 Verschobene Objekte . . . . . . . . . . . . . . . . . . . . . . . . . 60

Inhaltsverzeichnis III

5.3 Schlussfolgerungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

6 Zusammenfassung 65

A Debug Schnittstelle 67A.1 USB-Komponente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67A.2 Auswahl der auszugebenden Zählerstände . . . . . . . . . . . . . . . . . . 67A.3 Aufbereitung zur Ausgabe . . . . . . . . . . . . . . . . . . . . . . . . . . 67

B Quelltexte 71B.1 Test-Applikationen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

B.1.1 Sudoku-Löser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71B.1.2 FScript-Interpreter . . . . . . . . . . . . . . . . . . . . . . . . . . 75

B.2 Aufbereitung der MMUStat-Ausgaben . . . . . . . . . . . . . . . . . . . . 77

Abbildungsverzeichnis

2.1 Übersicht über die SHAP-Mikroarchitektur (aus [Zab+07]). . . . . . . . . . 42.2 Schnittstelle zwischen CPU und Speichermanager. . . . . . . . . . . . . . 52.3 Schematische Darstellung des Reference-Countings. . . . . . . . . . . . . 72.4 Phasen in einem Mark-Sweep(-Compact) Collector. . . . . . . . . . . . . . 82.5 Tracing ausgehend von Root-Objekten. . . . . . . . . . . . . . . . . . . . 92.6 Verschiebung erreichbarer Objekte. . . . . . . . . . . . . . . . . . . . . . . 10

3.1 Darstellung der fortlaufenden Speicherreservierung. . . . . . . . . . . . . . 163.2 Aus Blöcken zusammengesetzter Speicherbereich (ähnlich [Sieb02]) . . . . 163.3 Die einzelnen Phasen der Garbage Collection. . . . . . . . . . . . . . . . . 183.4 Darstellung des Indirektionskonzepts. . . . . . . . . . . . . . . . . . . . . 193.5 Verkettung von Referenzeinträgen zu Listen. . . . . . . . . . . . . . . . . . 203.6 Aufteilung des Speichers in 4 Segmente gleicher Größe. . . . . . . . . . . 213.7 Listenstruktur zur Verwaltung der einzelnen Segmenteinträge. . . . . . . . 213.8 Der Stack als zentrales Element in der SHAP-Mikroarchitektur. . . . . . . . 253.9 Frühere Freigabe der Referenzeinträge. . . . . . . . . . . . . . . . . . . . 323.10 Erweiterte Listenstruktur zur Repräsentation verschiedener Gruppen. . . . . 33

4.1 Darstellung des Layouts des Speichers. . . . . . . . . . . . . . . . . . . . . 364.2 Darstellung der Daten eines Referenzeintrags und Aufteilung in zwei Worte. 364.3 Die einem Segmenteintrag zugeordneten Datensätze. . . . . . . . . . . . . 374.4 Darstellung der groben Struktur des Speichermanagers. . . . . . . . . . . . 384.5 Aufbau des Konfigurationswortes des Speichermanagers. . . . . . . . . . . 454.6 Struktur der Komponente MMUStat. . . . . . . . . . . . . . . . . . . . . . 464.7 Die einzelnen Komponenten des Garbage Collectors. . . . . . . . . . . . . 474.8 Aufbau der Komponente gc_algo. . . . . . . . . . . . . . . . . . . . . . 51

5.1 Latenz der einzelnen Operationen. . . . . . . . . . . . . . . . . . . . . . . 575.2 Dauer der einzelnen GC-Zyklen. . . . . . . . . . . . . . . . . . . . . . . . 585.3 Belegte Segmente und Referenzeinträge bei sudoku. . . . . . . . . . . . . 615.4 Belegte Segmente und Referenzeinträge bei sudoku. . . . . . . . . . . . . 625.5 Abzahl Verschobener Objekte. . . . . . . . . . . . . . . . . . . . . . . . . 63

A.1 Schnittstelle des erstellten USB-Moduls. . . . . . . . . . . . . . . . . . . . 69A.2 Auswahl auszugebender Zählstände. . . . . . . . . . . . . . . . . . . . . . 69

Tabellenverzeichnis

4.1 Maximale Dauer der nicht unterbrechbaren Teile der Operationen des Referenz-Managers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

4.2 Wartezeiten auf die Fertigstellung der einzelnen Operationen des Segment-Managers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

4.3 Auflistung der Ergebnisse der Synthese. . . . . . . . . . . . . . . . . . . . 53

A.1 Anschlussbelegung des USB-Moduls für das Spartan-3-Starterkit und Zu-ordnung zu den IO-Pins des FPGAs. . . . . . . . . . . . . . . . . . . . . . 68

A.2 Zuordnung der abrufbaren Zählerstände zu einem Bit im Konfigurationswort. 70

1 Einleitung

Java als objekt-orientierte Programmiersprache bietet dem Softwareentwickler zahlreicheMöglichkeiten zur effizienten und einfachen Entwicklung komplexer Applikationen. DieJava Virtual Machine (JVM) [LiYe97], welche bereits auf zahlreiche Systeme portiert wur-de, übernimmt nicht nur die Ausführung von Java Programmen, sondern bietet auch eineautomatische Speicherverwaltung sowie umfangreiche Sicherheitskonzepte.

Bereits relativ früh wurde damit begonnen, die Vorteile einer solchen modernen Laufzeit-umgebung auch für eingebettete Systeme nutzbar zu machen, welche zumeist nur begrenzteRessourcen zur Verfügung stellen können, gleichzeitig jedoch oft in sicherheitskritischenBereichen eingesetzt werden. Echtzeitgarantien bezüglich der Antwortzeit und des Daten-durchsatzes sind dazu unerlässlich, konnten jedoch lange Zeit, vor allem aufgrund der ver-wendeten Implementierungen zur Garbage Collection, nicht gegeben werden.

Mit der Real-Time Specification for Java (RTSJ) [Bol+00], wird die Nutzung von Javain zeitkritischen Anwendungen zwar prinzipiell möglich, jedoch können nicht alle der um-fangreichen objektorientierten Konzepte genutzt werden. Durch die Definition von Speicher-bereichen, welche nicht automatisch durch den Garbage Collector bereinigt, sondern stetsmanuell und nur im Ganzen freigegeben werden können, wird die Attraktivität der Sprachefür Systeme mit Echtzeitanforderungen weiter eingeschränkt.

Neben der Verwendung von Standardprozessoren oder -controllern, existieren auch eini-ge Ansätze, durch spezielle Prozessoren (z.B. [Uhri03], [Scho05]) den Java Bytecode direkt,d.h. ohne eine Software-Implementierung der JVM, auszuführen. Ein solcher Ansatz ist dieam Lehrstuhl entwickelte SHAP-Plattform [Pre+07], welche sämtliche objektorientiertenKonzepte sowie mehrere Threads unterstützt und insbesondere für Echtzeitanwendungengeeignet ist.

Da für die Durchführung der Garbage Collection ebenfalls Rechenzeit erforderlich ist,existieren verschiedene Ansätze diese mit Hilfe spezieller Erweiterungen der Hardware zuvereinfachen. Während [Stee75] oder [Pfe+04] dazu eigenständige Prozessoren vorsehen,setzen andere Ansätze lediglich auf eine Unterstützung für besonders zeitkritische Opera-tionen, wie das Erkennen bestimmter Schreib- oder Lesezugriffe, mittels entsprechenderSchreib- oder Lesebarrieren (z.B. [Meye06]).

Das Ziel dieser Arbeit ist der Entwurf und die Implementierung eines durch Hardwa-re unterstützten Garbage Collectors zur automatischen Freigabe nicht benötigter Speicher-bereiche in der SHAP-Plattform. Da zur Erfüllung von Echtzeitkriterien auch insbeson-dere die Speicherverwaltung bestimmte Bedingungen erfüllen muss, soll ein geeignetesGarbage-Collection-Konzept erarbeitet werden, durch welches auch weiterhin Vorhersagenüber die Ausführungszeit einzelner Methoden oder ganzer Programmabschnitte gegebenwerden können. Durch unterschiedliche Test-Applikationen soll ein Funktionsnachweis er-folgen und durch Erfassen verschiedener Messdaten, Variationen der gewählten Strategie

2 1 Einleitung

untereinander verglichen und bewertet werden.Zunächst soll in Kapitel 2 die SHAP-Mikroarchitektur vorgestellt sowie ein genereller

Überblick über Garbage-Collection-Verfahren gegeben werden. In Kapitel 3 wird ein Kon-zept zur Speicherverwaltung und insbesondere zur Garbage Collection erarbeitet, dessenImplementierung und Aufteilung in verschiedene Komponenten in Kapitel 4 beschriebenwird. Der Vergleich verschiedener Strategien sowie die Bewertung hinsichtlich der gestell-ten Forderungen erfolgt in Kapitel 5. Kapitel 6 gibt schließlich eine Zusammenfassung derArbeit sowie einen kurzen Ausblick auf eine mögliche Fortführung.

2 Vorbetrachtungen

2.1 SHAP-Plattform

Die SHAP-Mikroarchitektur bildet gemeinsam mit der zugehörigen Implementierung derJava Virtual Machine (JVM) die am Lehrstuhl entwickelte SHAP-Plattform [Pre+07]. DerMikrocode-gesteuerte 32-Bit-Prozessor ermöglicht die direkte Ausführung von Java-Byte-code ohne die Hilfe eines Betriebssystems. Die Architektur wurde vollständig in VHDLimplementiert und für die Verwendung auf FPGAs hin optimiert. Sie erlaubt die paralleleAusführung mehrerer, auch zur Laufzeit dynamisch erzeugbarer Tasks (Multithreading) undist grundsätzlich fähig zur Echtzeitverarbeitung, wodurch das System gerade für Aufgabenin der Mess-, Steuer- und Regelungstechnik besonders gut geeignet ist.

2.1.1 Aufbau

Der Aufbau der Architektur verfolgt einen strikt modularen Ansatz, wobei die einzelnenKomponenten (siehe Abb. 2.1) Funktionen auf hohem Abstraktionsniveau anbieten und par-allel zum eigentlichen Kern arbeiten.

Es folgt eine kurze Beschreibung der einzelnen Komponenten:

• CPUDie CPU bildet den Kern der Mikroarchitektur und besteht aus den beiden paral-lel arbeitenden Teilkomponenten Core, in dem die eigentliche Ausführung des Java-Bytecodes stattfindet, und dem für die JVM zwingend erforderlichen Stack. Innerher-halb des Cores befindet sich außerdem ein ROM, welches den eigentlichen Mikroco-de enthält, sowie ein kleiner lokaler Datenspeicher für JVM-interne Zwecke, welcherdie sog. Mikrocode-Variablen enthält.

Da der Stack eine besonders performanzkritische Komponente darstellt, wurde die-ser unter Verwendung der auf dem FPGA verfügbaren internen Speicher umgesetztund muss somit nicht vom Speichermanager verwaltet werden. Zur Beschleunigungder Kontextwechsel bei der Auswahl eines anderen Threads, wird jedem Thread eineigener Stack durch Verkettung elementarer Blöcke zur Verfügung gestellt [Zab+07,Pre+07]. Wächst der Stack eines Threads an, so können der Liste dynamisch weitereBlöcke hinzugefügt werden, nimmt die Tiefe des Stacks ab, werden die entsprechendfrei gewordenen Blöcke entfernt.

• Speichermanager (memory manager, MMU)Der Speichermanager kapselt die gesamte Funktionalität des Java-Heaps, in welchemalle durch den new Operator angelegten Objekte liegen. Der Funktionsumfang um-fasst sowohl das Erzeugen neuer Objekte, sämtliche Schreib- und Leseoperationen

4 2 Vorbetrachtungen

SHAP Microarchitecture3232

UART

PS/2

USB

WhishboneBridge

EthernetMAC

− SRAM− DDR−RAM

Memory

8

32

Con

trol

ler

DDR: 16

Inte

grat

ed D

evic

es B

us

SDR: 32

CPU

Core

Stack

MemoryManager

GarbageCollector

32

MethodCache

Abbildung 2.1: Übersicht über die SHAP-Mikroarchitektur (aus [Zab+07]).

sowie das automatische Freigeben aller nicht benötigten Objekte durch einen geeig-neten Garbage Collector.

• Methodencache (method cache)Der Methodencache dient zum Aufnehmen des ausführbaren Codes einzelner Metho-den, wodurch Wartezeiten in Folge länger andauernder Speicherzugriffe während derAusführung der Methode, vermieden werden.

• Integrierter Speicher-Controller (integrated memory controller)Diese Komponente stellt eine einheitliche, abstrakte Schnittstelle bereit, um verschie-denartigen externen Speicher ansprechen zu können. Gegenwärtig werden sowohlSRAM- als auch DDR-SDRAM-Typen unterstützt. Der Speicher-Controller erlaubtauch das Kopieren ganzer Blöcke in Abhängigkeit eines Alignments.

• Integrierter Geräte-Bus (integrated devices bus)Dieser intern verwendete Bus dient zur Ankopplung der I/O-Geräte an die CPU. Eskönnen sowohl interne als auch externe Geräte angeschlossen werden, wobei jedesGerät über eine eindeutige Adresse angesprochen werden kann.

2.1.2 Objektbasierter Speicherzugriff

Der Speichermanager besitzt eine abstrakte Schnittstelle (siehe Abb. 2.2), durch welche eindirekter Zugriff auf den physischen Speicher durch die CPU nicht möglich ist. Stattdessen

2.1 SHAP-Plattform 5

rdy

fail

Speichermanager

op_nw_ref

op_st_ref

op_st_ofs

op_st_wofs

op_st_val

data_in data_out

32 32

Abbildung 2.2: Schnittstelle zwischen CPU und Speichermanager.

werden bereits durch die MMU Objekte unterstüzt, auf die lediglich mit Hilfe eines Hand-les zugegriffen werden kann. Folgende Operationen werden durch den Speichermanagerbereitgestellt:

• Objekt anlegen (op_nw_ref)Es wird ein neues Objekt angelegt sowie ein Handle für den Zugriff zurückgegeben.

• Objekt auswählen (op_st_ref)Ein übergebenes Handle wird aufgelöst und das referenzierte Objekt für weitere Ope-rationen ausgewählt.

• Offset setzen (lesen) (op_st_ofs)Der Offset innerhalb des Speicherbereichs des Objektes wird gesetzt und der an dieserPosition gespeicherte Wert zurückgeliefert.

• Offset für folgende Schreiboperation setzen (op_st_wofs)Der Offset innerhalb des Speicherbereichs des Objektes wird für eine folgende Schreib-operation gesetzt, wobei der gespeicherte Wert nicht gelesen wird.

• Daten schreiben (op_st_val)Der übergebene Wert wird an das zuvor gespeicherte Offset geschrieben.

Das Signal rdy zeigt an, ob der Speichermanager für die Ausführung einer Operationbereit ist, bzw. die letzte angeforderte Operation beendet hat. Schlägt die Ausführung fehl,so wird das Signal fail gesetzt und die CPU kann entsprechend reagieren.

2.1.3 Echtzeitverarbeitung

Bei weichen Echtzeitforderungen (soft real-time) genügt es bereits, die meisten Ereignisseinnerhalb einer bestimmten Zeit zu behandeln, so dass im Mittel die Antwort schnell genugbereitsteht. Auch größere Abweichungen von diesem Mittelwert sind erlaubt und führennicht zwangsläufig zu einem Fehler [Kope97].

Bei der SHAP-Plattform sollen hingegen harte Echtzeitgarantien (hard real-time) gege-ben werden können, welche inbesondere bei Aufgaben in der Steuer- und Regelungstechnik


eine wichtige Rolle spielen. Dabei muss garantiert sein, dass die zu einem Ereignis gehören-de Antwort immer spätestens nach Ablauf einer festgesetzten Schranke bereitsteht, welcheoft im Bereich von Millisekunden oder darunter liegt. Eine zu spät gelieferte Antwort wirdals Fehler gewertet.

Damit Aussagen über die Ausführungszeit einzelner Methoden oder auch der gesamtenApplikation getroffen werden können, müssen die Ausführungszeiten aller Bytecodes kon-stant sein oder dürfen zumindest nur von bekannten statischen Werten, wie z.B. der Größeeines Objektes, abhängen. Zu diesem Zweck müssen alle zum Core parallel arbeitendenKomponenten (2.1.1) nach Ablauf einer festgelegten Zeit, die angeforderte Operation ga-rantiert beendet haben.

2.2 Garbage Collection

Im Bereich der Speicherverwaltung wird unter Garbage Collection im Allgemeinen dasautomatische Freigeben nicht länger benötigter Speicherbereiche verstanden. Obwohl Gar-bage Collection keineswegs ausschließlich für objektorientierte Programmiersprachen an-gewendet wird, soll in Anlehnung an die allgemeine Nomenklatur der Begriff Objekt alsSynonym für einen solchen Speicherbereich verwendet werden.

2.2.1 Aufgabe

Die Aufgabe eines Garbage Collectors – oft auch nur Collector – besteht zunächst dar-in, nicht benötigte Speicherbereiche aufzufinden und diese für die eigentliche Anwendungwieder nutzbar zu machen. Beide Teilaufgaben lassen sich sehr unterschiedlich lösen undhängen sehr stark von der Architektur des zugrundeliegenden Systems ab [Peti], [Jone96].Insbesondere hierarchische Speicherkonzepte, virtueller Speicher oder aber Forderungenbezüglich der Antwortzeit bzw. des Datendurchsatzes, haben großen Einfluss auf die Ar-beitsweise eines Garbage Collectors.

Die Entscheidung, ob ein bestimmtes Objekt von der Anwendung benötigt wird, lässtsich bei allen bekannten Garbage-Collection-Verfahren zurückführen auf die Feststellung,ob Referenzen auf das Objekt existieren. Zu diesem Zweck wurden in der Vergangen-heit zahlreiche Strategien entwickelt, welche im Kern im Wesentlichen auf zwei Herange-hensweisen zurückzuführen sind: Reference-Counting und Tracing-Algorithmen [Jone96].Während Tracing-Algorithmen auf der Menge der lebenden Objekte operieren, könnenmittels Reference-Counting tote, d.h. nicht erreichbare Objekte direkt identifiziert werden[Bac+04]. Eine eingehendere Untersuchung beider Ansätze erfolgt in 2.2.2.

Auch alle modernen Ansätze wie Incremental- und Concurrent-GC (2.2.6), oder auchGenerational-GC (2.2.4) bauen auf diesen klassischen Verfahren und im speziellen auf derin 2.2.3 beschriebenen Copying-Garbage-Collection auf.

2.2 Garbage Collection 7

��

��

1 B

1 A 0

xy free_list

F2D C21

E2 ��

��

��

��

��

��

0

E1

F1

0

0

1

free_list

y

CD1

Abbildung 2.3: Schematische Darstellung des Reference-Countings, analog einem Beispielaus [Jone96].

2.2.2 Klassische Verfahren

Reference Counting

Bei diesem Verfahren, welches von Collins im Jahre 1960 [Coll60] für die Programmier-sprache LISP entwickelt wurde, wird jedem Objekt ein Zähler zugeordnet. Die Aufgabe derSpeicherverwaltung ist es dafür zu sorgen, dass dieser Zähler stets die Anzahl der Referen-zen auf das jeweilige Objekt widerspiegelt (Invariante).

Die notwendige Aktualisierung des Zählers kann mit Hilfe des Compilers durch Einfü-gen entsprechenden Codes erfolgen. Kommt eine neue Referenz auf ein Objekt hinzu, sowird der entsprechende Zähler inkrementiert, umgekehrt erfolgt beim Löschen einer Re-ferenz eine Dekrementierung des Zählers. Erreicht dieser den Wert 0, so existieren keineweiteren Referenzen, das Objekt wurde als Garbage erkannt und der belegte Speicher wirdfreigegeben und damit der Liste der freien Speicherblöcke zugeordnet. Da dabei auch Re-ferenzen auf andere Objekte gelöscht werden können, müssen auch die zugehörigen Zähleraktualisiert werden, wodurch rekursive Freigaben und damit verbundene lange Pausezeitenentstehen können.

Der größte Vorteil des Verfahrens besteht im sofortigen Erkennen von nicht erreichbarenObjekten. Die zur Garbage Collection notwendige Zeit wird über die gesamte Applikationverteilt und eine explizite Suche nach nicht erreichbaren Objekten ist nicht erforderlich. DerAnsatz versagt jedoch bei zyklischen Strukturen [McBe63], wodurch im Zyklus enthalte-ne Objekte nicht freigegeben werden können. Ein weiteres Problem stellt die Größe desZählers und der mit der Aktualisierung verbundene Overhead dar.

In Abbildung 2.3 ist das Reference-Counting schematisch dargestellt. Nach Löschen derReferenz x auf das Objekt A ist dieses nicht länger referenziert und der Zähler erreicht denWert 0. Bei der folgenden Freigabe geht auch die letzte Referenz auf Objekt B verloren,so das auch dieses als Garbage erkannt und freigegeben wird. Die Objekte C und D bildeneine zyklische Struktur und können, obwohl keine weitere äußere Referenz existiert, nichtfreigegeben werden. Das Objekt E ist durch eine andere Referenz y weiterhin erreichbar.Die beiden freigegebenen Objekte A und B wurden der Liste der freien Speicherbereichehinzugefügt und können zum Anlegen neuer Objekte verwendet werden.


Root−Scanning

Mark

Sweep

Compact

Abbildung 2.4: Darstellung der einzelnen Phasen in einem Mark-and-Sweep bzw. Mark-Sweep-Compact Collector (nach [Sieb02]).

Traversierung des Objektgraphen

Der auf der Traversierung des Objektgraphen (Tracing) basierende Mark-and-Sweep Algo-rithmus war das erste Verfahren zur automatischen Speicherverwaltung [Jone96] und wur-de ebenfalls im Jahre 1960 vorgestellt [McCa60]. Der Ansatz macht sich zunutze, dass imAllgemeinen kein wahlfreier Zugriff auf den Speicher erfolgt, sondern stets Zeiger (Re-ferenzen) auf entsprechende Objekte existieren. Ein jedes Programm kann daher zunächstlediglich mit Objekten arbeiten, für die eine Referenz existiert, auf die direkt zugegriffenwerden kann. Derartige Referenzen werden als roots bezeichnet und können in den Regis-tern des Prozessors, den globalen oder lokalen Variablen oder aber auf dem Stack liegen.Natürlich können auch innerhalb eines Objekts weitere Referenzen auf andere Objekte exis-tieren, was vor allem bei objektorientierten Programmiersprachen von Bedeutung ist, beidenen die angelegten Objekte durch Referenzen untereinander eine Baum- oder gar belie-bige Graphenstruktur besitzen.

Tracing-Algorithmen arbeiten grundsätzlich in mehreren aufeinanderfolgenden Phasen[Sieb02], welche in Abbildung 2.4 dargestellt sind und zyklisch durchlaufen werden.

Während des Root-Scannings werden zunächst alle Root-Referenzen gesammelt und dieentsprechenden Objekte markiert. Die darauffolgende Mark-Phase beginnt nun ausgehendvon diesen Root-Objekten mit der Traversierung des Objektgraphen, was auch als Bildungder transitiven Hülle bezüglich der Root-Objekte aufgefasst werden kann. Dabei wird derInhalt eines jeden Objektes hinsichtlich ausgehender Referenzen auf andere, noch nichtmarkierte Objekte überprüft. Die Phase wird beendet, wenn alle erreichbaren Objekte mar-kiert und überprüft worden. Daraufhin schließt sich die Sweep-Phase an, in welcher al-le nicht markierten und damit nicht erreichbaren Objekte freigegeben werden. Tracing-Algorithmen führen die Frage, ob ein Objekt noch benötigt wird, auf die Erreichbarkeitdes Objekts im Graphen zurück.

Die Compact-Phase kommt nur in sog. Mark-Sweep-Compact Algorithmen [Edwawn]vor und dient der Kompaktierung der freien Speicherbereiche. Dadurch wird die Fragmen-


I E

DH

G

Roots A

B C

F

Abbildung 2.5: Schematische Darstellung des Tracings ausgehend von den Root-Objekten(nach [Jone96]).

tierung des Speichers verhindert und das Suchen von freiem Speicher zum Anlegen neuerObjekte vereinfacht.

In Abbildung 2.5 ist das Tracing schematisch dargestellt. Alle von den Root-Objektenausgehend erreichbaren Objekte sind grau markiert, die nicht markierten Objekte sind nichterreichbar und können freigegeben werden.

Tracing-Verfahren sind grundsätzlich in der Lage auch zyklische Strukturen sicher zu er-kennen, allerdings ist durch die Suche nach lebenden Objekten ein sofortiges Erkennen vonGarbage nicht möglich. Objekte die nicht referenziert werden, aber durch die Sweep-Phasenoch nicht als Garbage erkannt worden, werden als floating garbage bezeichnet und bele-gen daher Speicher. In der originalen Implementierung von [McCa60] wird die Applikationfür die Dauer der Garbage Collection angehalten (stop-the-world GC), wodurch je nachGröße des Heaps und der Zahl der erreichbaren Objekte, unterschiedlich lange Wartezeitenentstehen können [Jone96].

2.2.3 Copying-Garbage-Collection

Der in [FeYo69] beschriebene Ansatz arbeitet sehr ähnlich zu dem in 2.2.2 beschriebenenMark-and-Sweep-Verfahren und verwendet Tracing zum Auffinden aller erreichbaren Ob-jekte. Der Speicher wird in zwei gleichgroße Partitionen aufgeteilt, welche als semi-spacebezeichnet werden. Stets enthält einer der Bereiche die aktuellen und der andere die „veral-teten“ Daten.

Zu Beginn der Garbage Collection wird zunächst das eigentliche Programm angehaltenund die Rolle der beiden semi-spaces getauscht. Daraufhin wird analog 2.2.2 ausgehendvon den Root-Objekten mit der Traversierung des Objektgraphen begonnen. Anstelle je-doch ein erreichtes Objekt zu markieren, wird dieses direkt aus from-space nach to-spacekopiert. An der alten Position in from-space wird zudem ein forwarding-pointer hinterlegt,welcher auf die neue Position zeigt. Außerdem werden alle gefundenen Referenzen mit Hil-fe des forwarding-pointers aktualisiert, anhand dessen auch entschieden wird, ob ein Objektbereits verschoben wurde.

Nach einem Zyklus befinden sich im to-space daher alle erreichbaren Objekte, welche


��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

Roots nicht referenziertes Objekt

referenziertes Objekt

new objects

from−space to−space

Abbildung 2.6: Darstellung der Verschiebung erreichbarer Objekte aus from-space nach to-space bei der Copying-Garbage-Collection.

durch das Verschieben unmittelbar hintereinander abgelegt worden (siehe Abbildung 2.6).Dadurch beginnt der freie Speicherbereich direkt nach dem letzten Objekt in to-space undein umständliches Suchen nach freiem Speicher beim Anlegen neuer Objekte kann entfal-len. Alle nicht erreichbaren Objekte wurden nicht mit verschoben und deren Speicher istsomit automatisch freigegeben. Der beste bekannte (nach [Jone96]) Copying-Algorithmusist in [Chen70] beschrieben und kommt anders als [FeYo69] ohne ein rekursives Verhaltenbeim Verschieben der Objekte aus.

2.2.4 Generational-GC

Je nach Größe des zu verwaltenden Speichers oder der Anzahl der erreichbaren Objekte,kann die durch den GC verursachte Unterbrechung sehr lang werden, wodurch GarbageCollection vor allem für interaktive Anwendungen unbrauchbar [Jone96] wird.

Grundlage der Generational-Garbage-Collection [LiHe83, Moon84] bildet die sog. weak-generational-hypothesis [Wils94], in welcher ausgesagt wird, das die meisten Objekte be-reits kurz nach ihrer Allokation nicht mehr erreichbar und damit Garbage sind („most ob-jects die young“). Dies kann ausgenutzt werden, indem der Collector nicht ständig dengesamten Speicher betrachtet, sondern seine Aktivitäten vor allem auf junge Objekte kon-zentriert.

Der Speicher wird in mindestens zwei Bereiche geteilt – einen für jede Generation. NeueObjekte werden zunächst in der jüngsten Generation angelegt und, wenn sie lang genugüberleben, entsprechend in den Speicherbereich der nächstälteren Generation verschoben.Dadurch wird erreicht, das jüngere von älteren Objekten unterschieden werden könnenund dem Speicher der jüngsten Generation besondere Beachtung geschenkt werden kann.Der Bereich der jungen Objekte wird oft als nursery-space bezeichnet, wobei aufgrundder weak-generational-hypothesis häufig von infant-mortality gesprochen wird [Bake93],wodurch noch einmal verdeutlicht wird, dass junge Objekte bereits nach kurzer Zeit zuGarbage werden.

Auch die Generational-Garbage-Collection basiert auf dem in 2.2.2 beschriebenen Tra-


cing, jedoch wird zwischen einer vollständigen Collection und einer Minor-Collection un-terschieden, bei welcher nicht der gesamte Objektgraph traversiert wird. Ausgangspunkt fürdie Traversierung bilden zum Einen die von Mark-and-Sweep bekannten Root-Referenzenund zum Anderen das sog. remembered-set. In diesem befinden sich Referenzen auf al-le Objekte der alten Generation, die eine Referenz auf ein Objekt der jüngeren Generati-on enthalten. Wird eine solche Referenz angelegt, so wird das entsprechende Objekt demremembered-set hinzugefügt. Kann während einer vollständigen Collection in einem Objektder alten Generation keine Referenz auf ein junges Objekt gefunden werden, so wird die zu-gehörige Referenz aus dem remembered-set entfernt. Alle Objekte der älteren Generation,die nicht im remembered-set enthalten sind, werden während einer Minor-Collection nichtbeachtet.

Da auch Objekte der älteren Generation nicht mehr erreichbar sein können und damitGarbage darstellen, muss auch deren Speicherbereich überprüft werden, was durch einevollständige Collection erreicht wird.

Damit die Vorteile der Generational Garbage Collection genutzt werden können, ist esnotwendig, Referenzen zwischen verschiedenen Generationen sicher zu erkennen. Die dazuerforderlichen Schreib-Barrieren können z.B. vom Compiler eingefügt werden, verschlech-tern jedoch durch ihren Overhead die Performanz der Applikation [Jone96]. Durch die sel-tene Betrachtung der älteren Generationen werden nicht mehr erreichbare Objekte mituntererst nach längerer Zeit freigegeben, woraus deutlich mehr floating-garbage resultiert.

2.2.5 Tri-Color-Marking

Das Tri-Color-Marking wurde erstmalig in [Dij+78] beschrieben. Dabei wird jedem Objektim Zuge der Garbage Collection eine der Farben weiß, grau oder schwarz zugeordnet. ZuBeginn des Garbage Collection Zyklus wird zur Initialisierung zunächst allen Objekte eineweiße Markierung zugeordnet.

Ein weiß markiertes Objekt konnte im Zuge des Scans (noch) nicht erreicht werden. Wur-de ein Objekt erreicht, d.h. es wurde ausgehend von den Root-Referenzen oder ausgehendvon einem anderen Objekt, eine Referenz gefunden, so wird das Objekt grau markiert. Wäh-rend der Durchsuchung des Objektgraphen wird stets ein graues Objekt ausgewählt, diesesnach ausgehenden Referenzen durchsucht und schließlich eine schwarze Markierung zuge-wiesen. Dieser Scan-Prozess wird solange fortgestetzt, bis keine weiteren grauen Objekteexistieren, d.h. alle erreichbaren Objekte wurden nach ausgehenden Referenzen durchsuchtund sind somit schwarz markiert, alle nicht erreichbaren Objekte tragen hingegen eine wei-ße Markierung und können freigegeben werden.

Im Zuge des Tri-Color-Markings muss sichergestellt werden, dass ein weißes Objekt nie-mals direkt von einem Schwarzen ausgehend referenziert wird, da dieses ansonsten fälsch-lich als nicht erreichbar und damit als Garbage gewertet werden könnte [Sieb02]. Eine Mög-lichkeit zur Garantie dieser Invariante besteht in der Einführung einer Schreibbarriere. Diesemuss sicherstellen, dass bei jeder Speicherung in einem schwarzen Objekt, das zugewieseneObjekt grau markiert und folglich ebenfalls im weiteren Verlauf des Scans betrachtet wird.


2.2.6 Inkrementelle und Parallele Verfahren

Die meisten Tracing-basierten Verfahren arbeiten nach dem sog. Stop-the-World-Prinzip,d.h. die Applikation wird für die Dauer der Garbage Collection angehalten, wodurch sichwährend der Collection keine Änderungen im Objektgraphen ergeben. Zwar können dieseUnterbrechungen mittels der Generational Garbage Collection (siehe 2.2.4) deutlich ver-kürzt werden, jedoch bleibt durch die Notwendigkeit einer vollständigen Collection dieDauer der Unterbrechung im Worst-Case gleich [Jone96].

Damit übermäßig lange Pausen generell ausgeschlossen werden können, muss entwe-der der Collector unterbrechbar konstruiert werden (incremental GC), oder aber parallelzur eigentlichen Applikation ablaufen (concurrent GC). Da die Applikation nicht für diegesamte Dauer eines Garbage-Collection-Zyklus angehalten wird, können Veränderungendes Objektgraphen auftreten. Aufgrund dieser Mutation des Heaps wird die eigentliche Ap-plikation oft als Mutator bezeichnet [Wils94]. Obwohl das Reference-Counting von Naturaus inkrementell arbeitet [Jone96], basieren die meisten modernen Collectoren auf Tracing-Algorithmen [Sieb02].

Ein Incremental-GC versucht die durch die Garbage Collection entstehenden Pausen zuverkürzen, indem der Collection Zyklus in mehrere kleine Teile aufgeteilt wird, für derenAbarbeitung der Mutator nur kurz unterbrochen werden muss. Hingegen läuft der GarbageCollector bei einem Concurrent-GC parallel zum Mutator in einem separatem Thread odergar auf einem eigens dafür zuständigen Prozessor im Falle eines Multiprozessorsystems.

Sowohl für Incremental- als auch für Concurrent-GC sind verschiedene Techniken zurSynchronisation erforderlich, da der Mutator während seiner Abarbeitung den Objektgra-phen ständig verändert und ein Objekt keinesfalls fälschlich als Garbage erkannt und freige-geben werden darf. Außerdem muss garantiert werden, dass stets genügend freier Speicherzur Verfügung steht, d.h. es darf nicht mehr Speicher angefordert werden, als vom GarbageCollector freigegeben werden kann. Der GC muss also ausreichend schnell arbeiten oderggf. dynamisch an die Bedürfnisse der Applikation angepasst werden.

Der in [Sieb02] vorgestellte Incremental-GC führt sog. Synchronisationspunkte ein, anwelchen der Mutator zur Ausführung der Garbage Collection für eine gewisse Zeit unter-brochen wird. Bei jeder Unterbrechung wird ein kleiner Teil des Heaps untersucht und nichterreichbare Bereiche freigegeben und wieder nutzbar gemacht. Es kann garantiert werden,dass, solange insgesamt im System genügend Speicher vorhanden ist, stets ausreichend frei-er Speicher zur Verfügung steht.

Zum Erkennen von Änderungen des Objektgraphen werden zumeist sog. Schreib- oderLesebarrieren [Wils94] eingesetzt, welche sowohl in Software als auch mit Hardwareun-terstützung (2.2.8) implementiert werden können. Wird ein Zugriff auf eine so beobachteteRegion des Speichers festgestellt, so werden entsprechende Routinen des Garbage Collec-tors aufgerufen.

2.2.7 Garbage Collection unter Echtzeitbedingungen

Ansätze, welche den Mutator für die gesamte Dauer der Garbage Collection unterbrechen,sind für Echtzeitsysteme nicht geeignet. Zum Einhalten von Echtzeitforderungen muss die


Worst-Case-Zeit im Allgemeinen sehr klein sein. Dies betrifft sowohl die Wartezeit zumAufruf einer Routine, als auch die Geschwindigkeit ihrer Abarbeitung [Wils94].

Der erste inkrementelle, grundsätzlich echtzeitfähige Garbage Collector ist in [Bake78]beschrieben und basiert auf der von [Chen70] beschriebenen Copying-Garbage-Collection.Der Algorithmus verwendet eine Lesebarriere, mit deren Hilfe ein Objekt aus from-spacenach to-space verschoben wird, wenn der Mutator auf dieses zugreift. Dieser Ansatz ist sehrteuer und kommt praktisch nicht ohne Hardwareunterstützung aus [Jone96].

[Sieb02] verwendet ebenfalls einen inkrementellen Ansatz, jedoch wird eine Schreibbar-riere eingesetzt, welche wesentlich einfacher umzusetzen ist. Auch wird auf das Verschie-ben von Objekten im Speicher verzichtet, indem Objekte aus kleinen Blöcken zusammen-gesetzt werden.

In [Meye05] wird hingegen ein Concurrent-GC verwendet, welcher ebenfalls auf demin [Bake78] dargestellten Ansatz basiert. Da der Garbage Collector mit Hilfe eines sepa-raten Coprozessors realisiert wird, kann dieser tatsächlich parallel zum Mutator ablaufen.Zur Synchronisation kann der Garbage Collector Speicherbereiche sperren, wodurch einexklusiver Zugriff ermöglicht wird. Versucht die CPU auf einen gesperrten Speicherbereichzuzugreifen, so wird der Zugriff unterbrochen und auf die Entsperrung durch den GarbageCollector gewartet. Es ist garantiert, das eine solche Unterbrechung niemals 500 Taktzyklenüberschreitet.

2.2.8 Hardwareunterstützung

Da Garbage Collection insbesondere unter Einhaltung von Echtzeitbedingungen (2.2.7) re-lativ aufwändig ist, existieren verschiedene Ansätze, diese durch spezielle Hardware zuunterstützen. Im einfachsten Fall kann für den Garbage Collector ein extra Prozessor vor-gesehen werden, wodurch die Garbage Collection vollständig parallel zur eigentlichen Ap-plikation ausgeführt wird [Jone96].

Der in [Meye05] beschriebene und bereits in 2.2.7 kurz erwähnte Concurrent-GC siehteinen Garbage-Collection-Coprocessor vor. Der Mikrocode des Prozessors beinhaltet al-le für die Garbage Collection notwendigen Funktionen und führt diese selbstständig aus.Auch zum Erkennen von Referenzen ist in diesem System spezielle Hardware vorgesehen[Meye04, Meye06], so existieren z.B. separate Register für gewöhnliche Daten und Refe-renzen. Auch steht jeweils ein separater Stack zur Verfügung.

Neben der vollständigen Umsetzung der Garbage Collection durch speziell dafür vorge-sehene Hardware, ist auch die Unterstützung von bestimmten, besonders kritischen Ope-rationen denkbar. [Pfe+04] sieht z.B. auf dem Stack zusätzliche Bits zur Kennzeichnungvon Referenzen vor, wodurch Referenzen sicher erkannt und gemeinsam mit gewöhnlichenDaten im gleichen Speicherbereich abgelegt werden können.

3 Entwurf

3.1 Anforderungen an den Speichermanager

3.1.1 Benötigte Funktionen

Die SHAP-Mikroarchitektur verwendet, wie bereits in 2.1.2 beschrieben, ein objektbasier-tes Speichermodell. Die MMU muss daher alle Funktionen anbieten, die zur Verwaltung vonObjekten dienen. Dies umfasst neben den in 2.1.2 genannten Operationen zum Datenzugriffsowie zum Anlegen neuer Objekte, zusätzlich die automatische Freigabe und Wiedernutz-barmachung nicht benötigter Speicherbereiche, wofür ein Garbage Collector benötigt wird.

3.1.2 Vermeidung langer Unterbrechungen

Für alle durch die CPU angeforderten MMU-Operationen muss eine feste obere Schrankebezüglich der Ausführungszeit existieren (siehe 2.1.3), um Garantien bezüglich der Ant-wortzeit geben zu können. Dies erfordert, das zum Einen für die Ausführung der Operatio-nen selbst nur kurze Zeit benötigt wird und zum Anderen, dass notwendige Verwaltungs-aufgaben der MMU mit diesen nicht interferieren oder aber unter Einhaltung einer oberenSchranke unterbrechbar sind.

Dies hat insbesondere Auswirkungen auf die auszuwählende Garbage-Collection-Strategie(siehe 3.2) sowie die Reservierung von Speicher (3.1.3) zum Anlegen neuer Objekte.

3.1.3 Speicherreservierung in konstanter Zeit

Zur Reservierung von Speicher können verschiedene Verfahren eingesetzt werden. Im ein-fachsten Fall kann eine fortlaufende Reservierung erfolgen (bump-pointer-allocation). DasReservieren von Speicher für neue Objekte erfolgt dabei stets am Ende des bereits reser-vierten Bereichs (siehe Abbildung 3.1), wobei der Zeiger auf die Endposition (der bump-pointer) entsprechend aktualisiert wird. Obwohl dieses Verfahren besonders leicht umge-setzt werden kann, ist die Freigabe des Speichers nicht länger benötigter Objekte sehr kom-pliziert. Da freier Speicher nur am Ende des bereits reservierten Bereiches genutzt werdenkann, ist eine mitunter sehr aufwändige Kompaktierung erforderlich.

Ein anderer Ansatz besteht in der Teilung des Speichers in kleine Blöcke, wobei lediglichfür jeden Block hinterlegt wird, ob dieser in Benutzung ist. Ein zu reservierender Speicher-bereich wird aus einem oder auch aus mehreren derartigen Blöcken gebildet.

In Linux müssen beispielsweise die einzelnen Blöcke zum Aufbau größerer Speicherbe-reiche unmittelbar hintereinander liegen, wodurch ein Zugriff in konstanter Zeit möglich ist.Der Buddy-Allocator [Maue04] fast dabei stets zwei freie benachbarte Blöcke gleicher Grö-ße zu einem größeren zusammenhängenden Bereich zusammen. Wird ein Speicherbereich

16 3 Entwurf

bump pointer

bump pointer

new object

new object

Abbildung 3.1: Darstellung der fortlaufenden Reservierung von Speicher. Der Zeiger(bump-pointer) zeigt stets auf das Ende des reservierten Speicherbereichs.

k−1 k1 2 3 4 5 6 7 8

Link Link

Data

Abbildung 3.2: Ein aus drei Blöcken zusammengesetzter Speicherbereich. Die Position derBlöcke innerhalb des Speichers spielt keine Rolle (ähnlich [Sieb02]).

einer bestimmten Größe benötigt, so wird stets der kleinste zusammenhängende Bereichgesucht, welcher gerade groß genug ist. Ist ein solcher Bereich nicht direkt verfügbar, sowird ein größerer Bereich ausgewählt und dieser in zwei Teilbereiche aufgebrochen. DasReservieren von Speicher ist dadurch nicht in konstanter Zeit möglich.

In [Sieb02] werden größere Speicherbereiche durch Verkettung von freien Blöcken anbeliebigen Adressen gebildet (siehe Abbildung 3.2). Der Zugriff auf ein bestimmtes Offsetist somit jedoch nicht in konstanter Zeit möglich. Soll ein Speicherbereich freigegeben wer-den, so sind lediglich alle zu dem Bereich gehörenden Blöcke freizugeben. Der in [Sieb02]gegebene Ansatz ermöglicht durch die Verkettung beliebiger Blöcke zu einem Bereich ent-sprechender Größe auch eine effektive Verwaltung aller nicht belegten, wodurch das Reser-vieren von Speicher zumindest in linearer Zeit ermöglicht wird.

Da auch die Reservierung von Speicher zum Anlegen neuer Objekte die in 3.1.2 genann-te Forderung erfüllen muss, ist das bei Bedarf angestoßene Suchen von Bereichen entspre-chender Größe, oder gar die bedarfsmäßige Freigabe nicht benötigter Ressourcen durch denGarbage Collector, unpraktikabel. Das Reservieren von Speicher muss in konstanter Zeitmöglich sein, weshalb nur eine fortlaufende Reservierung in Betracht kommt.

Ein Kompromiss besteht in der Teilung des Speichers in einzelne Segmente (siehe 3.4),wobei in einem Segment solange fortlaufend reserviert werden kann, wie genügend freierSpeicher verfügbar ist. Auch kann damit die Speicherbereinigung auf einzelne Segmentebezogen werden, wodurch eine Kompaktierung des gesamten Speichers vermieden werdenkann. Durch die Begrenzung der Reservierung auf den Umfang eines Segments, ist diemaximale Größe eines Objektes durch die Segmentgröße vorgegeben.

3.2 Grundkonzept der Garbage Collection 17

3.1.4 Bereitstellung von ausreichend freiem Speicher

Jede Applikation benötigt für ihre Ausführung eine bestimmte Menge Speicher, welcherzunächst im System vorhanden sein muss. Da jedoch der Speicher nicht mehr benötigterObjekte nicht sofort freigegeben werden kann (siehe 3.2), ist die Menge des erforderlichenSpeichers entsprechend höher. Es muss daher sichergestellt werden, dass Speicheranforde-rungen durch die CPU stets erfolgreich verlaufen, weshalb die Verzögerung der GarbageCollection und der damit verbundene floating-garbage (siehe 2.2.2) entsprechend begrenztwerden muss.

3.2 Grundkonzept der Garbage Collection

Das auszuwählende Garbage Collection Verfahren muss den in 3.1 genannten Forderungenentsprechen und darf die eigentliche Arbeit der CPU nicht durch lange Pausen beeinflussen.Ein Stop-the-World Ansatz kommt aufgrund der Forderung nach konstanter Laufzeit füralle der CPU zur Verfügung stehenden Operationen nicht in Frage.

Obwohl Verfahren auf Basis der Referenzenzählung von Natur aus inkrementell arbeitenund auch das rekursive Freigeben von Objekten verhindert werden kann [Weiz63], wodurcheine Zeigerzuweisung prinzipiell in kostanter Zeit möglich wäre, sind diese Verfahren weniggeeignet.

In der SHAP-Mikroarchitektur können auch im Stack und den Mikrocode-Variablen Re-ferenzen auf Objekte liegen. Da auch diese in der Zählung berücksichtigt werden müss-ten, würde ein immenser Overhead entstehen. Zwar besteht die Möglichkeit, Stack undMikrocode-Variablen durch Verwendung von Deferred-Reference-Counting [DeBo76] zu-nächst von der Zählung auszuschließen, der dadurch notwedige Scan erfordert jedoch erneutPausen unvorhersagbarer Dauer.

Alle Tracing-Verfahren können durch die vollständige Traversierung des Objektgraphen,auch zyklische Strukturen problemlos erkennen [Jone96]. Während der Traversierung unddem damit verbundenen Heap-Scan, müssen Referenzen von gewöhnlichen Datensätzen un-terschieden werden können. Wird der Mutator nicht für die gesamte Dauer eines GarbageCollection Zyklus angehalten, so ist außerdem die permanente Veränderung des Objektgra-phen zu berücksichtigen, da keinesfalls fälschlich Objekte als Garbage erkannt und derenSpeicher freigegeben werden darf. Die dazu notwendige Synchronisation wird meist durchLese- bzw. Schreibbarrieren erreicht [Wils94], welche auch durch spezielle Hardware un-terstützt werden können [Meye06].

Grundlage für das gewählte Garbage-Collection-Konzept bildet ein Tracing-Verfahren,welches zur Vermeidung langer Pausen parallel zur eigentlichen Applikation arbeitet. Diedazu notwendigen Root-Referenzen (siehe 3.5.1) können in der SHAP-Mikroarchitektur so-wohl auf dem Stack, als auch in den Mikrocode-Variablen liegen. Zur Markierung der Root-Referenzen sowie während der Traversierung des Baumes, wird das Tri-Color-Marking (sie-he 2.2.5) eingesetzt.

Sowohl das Erkennen als auch die Freigabe nicht markierter Objekte soll lediglich auf be-stimmte Speicherbereiche bezogen werden, wofür ebenfalls die bereits in 3.1.3 erwähntenSegmente dienen. Bei allen belegten Segmenten werden die enthaltenen Objekte, welche

18 3 Entwurf

Next Seg?

Idle

Root−Scan

Clean Seg

Profit?

trigger

Heap−Scan

Mark Seg

yes

no

no

yes

Abbildung 3.3: Die einzelnen Phasen der Garbage Collection.

während der Traversierung des Baumes nicht erreicht worden und damit nicht mehr refe-renziert sind, als Garbage markiert. Schließlich werden all jene Segmente bereinigt, für dieanhand einer Auswahlfunktion ein Gewinn an freiem Speicher zu erwarten ist. Dafür istauch die Verschiebung von Objekten erforderlich.

Da der Collector parallel zur CPU arbeitet, ist eine Synchronisation notwendig, welchedurch eine Überwachung des Stacks erreicht wird. Länger andauernde Operationen des Col-lectors müssen außerdem unterbrechbar implementiert werden.

Das beschriebene Konzept lässt sich in die in Abbildung 3.3 dargestellten Phasen auf-teilen. Ein vollständiger Garbage Collection Zyklus besteht damit aus einem Durchlauf dereinzelnen Phasen. Diese sind sauber getrennt und können weitgehend unabhängig vonein-ander umgesetzt werden (mehr dazu in 3.5).

3.3 Objekte und Referenzen

3.3.1 Indirektionskonzept

Wird ein Objekt im physischen Speicher verschoben, so ist aufgrund der geänderten Adresseeine Aktualisierung sämtlicher auf das Objekt zeigender Referenzen erforderlich [FeYo69,Chen70]. Da dies jedoch in der SHAP-Mikroarchitektur aufgrund der Mikrocode-Variablenund der Architektur des Stacks sehr aufwändig wäre, ist ein Indirektionskonzept (siehe Ab-bildung 3.4) vorgesehen, durch welches nach einer Änderung der tatsächlichen Objektadres-se, lediglich das Ziel des zugehörigen Indirektionszeigers aktualisiert werden muss. Diephysische Adresse eines Objektes ist dabei nur im Inneren der MMU bekannt. Die CPU

3.3 Objekte und Referenzen 19

Obj A*Obj A

...

Adr B

Adr A (A*)Handle A

Obj B

Abbildung 3.4: Darstellung des Indirektionskonzeptes. Wird Objekt A an eine andere Posi-tion verschoben (Objekt A*), so wird auch der zugehörige Indirektionszei-ger aktualisiert. Das Handle (Handle A) bleibt für die gesamte Lebensdauerdes Objekts konstant.

kennt ausschließlich das beim Anlegen zugewiesene Handle, welches für die gesamte Le-bensdauer des Objektes konstant bleibt und für alle Zugriffe genutzt wird. Die Auflösungdieses Handles muss von der MMU in konstanter Zeit möglich sein, weshalb lediglich einIndex-Zugriff anhand des Handles in Frage kommt.

3.3.2 Verwaltung

Zu speichernde Informationen

Neben dem Zeiger auf die tatsächliche Position im physischen Speicher, ist für jedes Handledie Größe und der Zustand des verknüpften Objektes zu speichern. Der Zustand des Hand-les wird verwendet, um Handles erreichbarer und damit benötigter Objekte von bereits alsGarbage erkannten sowie von nicht zugewiesenen zu unterscheiden. Der Zustand kann da-her einen der Zustände free, alive und dead annehmen. Außerdem ist auch für diebenötigte Verkettung der Handles zu Listen Speicher erforderlich. Die Gesamtheit dieservier Datensätze wird im Folgenden als Referenzeintrag bezeichnet.

Indexzugriff

Damit eine schnelle Auflösung der objektspezifischen Daten ermöglicht wird, werden die-se beginnend ab einer bestimmten Speicheradresse aufsteigend hinterlegt. Das Offset zudieser Basisadresse kann somit direkt als Handle verwendet und der CPU beim Anlegeneines Objekts zurückgegeben werden. Da die Größe einer solchen Tabelle begrenzt ist, istauch die Zahl der Referenzeinträge und damit die Anzahl gleichzeitig existierender Objektebegrenzt. Dies ist jedoch grundsätzlich unkritisch, da die Größe der Tabelle und damit dieAnzahl allokierbarer Objekte bei Bedarf vor der Synthese variiert werden kann.

20 3 Entwurf

Position des Objekts

Verkettung der Referenzeintr.

Seg

free list

...

Ref−Entry

Abbildung 3.5: Verkettung von Referenzeinträgen zu Listen für die Zuordnung zu Speicher-bereichen. Dem Segment ist ein Zeiger auf die Referenzeinträge der enthal-tenen Objekte zugeordnet. Nicht verwendete Referenzeinträge sind in derfree-list zusammengefasst.

Verkettung zu Listen

Durch Betrachten des zu jedem Referenzeintrags gehörenden Indirektionszeigers kann so-fort die Position des Objektes im Speicher festgestellt werden. Im Hinblick auf das ange-dachte Garbage-Collection-Konzept (siehe 3.2 und 3.4) ist es jedoch notwendig, von einemgegebenen Speicherbereich (=Segment, siehe 3.4) auf die enthaltenen Objekte schließen zukönnen.

Zu diesem Zweck werden alle in einem Segment befindlichen Objekte in Form einer ein-fach verketteten Liste miteinander verknüpft und der Listenkopf dem Segment zugeordnet(siehe Abb. 3.5).

Freispeicherverwaltung

Ist einem Referenzeintrag kein Objekt zugeordnet, so ist dieser in die Liste der freien Re-ferenzen eingegliedert. Durch dieses Vorgehen kann beim Anlegen eines Objektes (3.3.3)sofort ein freier Referenzeintrag mit zugehörigem Handle gefunden und diesem die Datenund die Speicheradresse des neuen Objekts zugeordnet werden. Nach der Initialisierungsind zunächst alle Referenzeinträge als free markiert und der free-list zugeordnet.

3.3.3 Allokation neuer Objekte

Zunächst wird ein freier Referenzeintrag benötigt, wobei direkt der Kopf der Liste der frei-en Referenzen ausgewählt wird. Die Basisadresse des freien Speicherbereichs am Ende desAllokationssegments (siehe 3.4.3) wird gemeinsam mit der Größe des Objekts dem Refe-renzeintrag zugewiesen und der Zustand der Referenz entsprechend auf alive gesetzt.Nachdem der Referenzeintrag der segmentspezifischen Objektliste zugeordnet wurde, wirdder CPU das zugehörige Handle zurückgegeben.

3.4 Segmentkonzept 21

2 3 4Segment 1

Abbildung 3.6: Aufteilung des Speichers in 4 Segmente gleicher Größe.

free pointer

Segment

next

previous

...

Abbildung 3.7: Listenstruktur zur Verwaltung der einzelnen Segmenteinträge.

3.4 Segmentkonzept

3.4.1 Teilung des Speichers

Wie bereits in 3.1.3 kurz erwähnt, wird der Speicher in einzelne Segmente gleicher Größeaufgeteilt (siehe Abbildung 3.6). Anzahl und Größe der Segmente orientieren sich dabeizum Einen an der Größe des verfügbaren Speichers und zum Anderen an der gewünschtenmaximalen Größe eines Objektes. Dabei muss auch die entstehende Fragmentierung desSpeichers sowie Forderungen des Garbage Collectors berücksichtigt werden, da dieser, jenach Strategie, mit mehreren Segmenten arbeiten kann.

3.4.2 Verwaltung

Freie und belegte Segmente

Der Austausch des Allokationssegments (3.4.3) erfordert das Auffinden eines freien Seg-ments in möglichst kurzer Zeit. Analog dem Vorgehen bei der Verwaltung der Referenzein-träge (siehe 3.3.2), werden auch die für die Segmentverwaltung erforderlichen Informa-tionen in einer Tabelle hinterlegt, wodurch ein indexierter Zugriff auf die Daten eines je-den Segments ermöglicht wird. Die einzelnen Segmenteinträge werden außerdem zu einerListenstruktur zusammengefasst, welche in Abbildung 3.7 schematisch dargestellt ist. DieReihenfolge der Segmenteinträge muss dabei keinesfalls der physischen Reihenfolge derSegmente im Speicher entsprechen.

Der in Abbildung 3.7 dargestellte free-pointer zeigt auf den Eintrag des ersten freienSegments, wobei sich die Einträge aller weiteren freien Segmente links von diesem befin-den. Der Eintrag des Allokationssegments, sowie alle Einträge weiterer Segmente, in denenbereits Speicher reserviert wurde, befinden sich hingegen rechts des free-pointers. Bei derInitialisierung werden zunächst alle Segmenteinträge als frei markiert.

Wird im Zuge des Austausches des Allokationssegments (3.4.3) oder für das bei derGarbage Collection benötigte Zielsegment (siehe 3.9), ein weiteres freies Segment benötigt,so wird der free-pointer lediglich um einen Eintrag in der Liste nach links verschoben unddie Adresse des Segmenteintrags kann verwendet werden.

22 3 Entwurf

Da die Garbage Collection (3.2) die Speicherbereinigung auf Ebene der Segmente durch-führt, ist auch die Freigabe ganzer Segmente notwendig. Der Eintrag eines Segments, wel-ches keinerlei reservierten Speicher mehr beinhaltet, wird von der Liste der belegten zurListe der freien Einträge verschoben, d.h. es bildet den Kopf der in Abbildung 3.7 darge-stellten Listenstruktur.

Zuordnung der Objekte

Jedem Segmenteintrag werden außerdem alle im Segment enthaltenen Objekte zugeordnet,was der Garbage Collection als Basis zur Bereinigung dient. Dies geschieht durch Zuord-nung des Kopfes einer Liste von Referenzeinträgen (siehe 3.3.2), wobei bei freien Segmen-ten keine Liste (Null-Zeiger) hinterlegt ist (siehe auch Abbildung 4.3).

Segmentspezifische Daten

Einem jeden Segmenteintrag müssen neben der Liste der im Segment enthaltenen Objekte(L), einige weitere spezifische Daten zugeordnet werden können. Diese hängen vom ver-wendeten Garbage Collection Konzept (3.2) ab und umfassen im Wesentlichen die Anzahlder belegten (W) und der nicht länger benötigten, d.h. toten Speicherworte (D) sowie dieZahl der nicht referenzierten Objekte (R). Auch für die Verknüpfung der Segmenteinträgezu einer doppelt verketteten Liste werden entsprechende Speicherstellen benötigt. Außer-dem wird ein frei wählbarer Datensatz hinzugefügt, welcher eine unterschiedliche Bedeu-tung zukommen kann.

3.4.3 Allokationssegment und Speicherreservierung

Zur möglichst schnellen Reservierung (siehe 3.1.3) von Speicher, wird stets ein Segmentals sog. Allokationssegment betrachtet. Alle folgenden Allokationen finden fortlaufend stetsin diesem Segment statt. Wird erkannt, dass der noch freie Speicher innerhalb des Allokati-onssegmentes nicht ausreicht, um Speicher für ein Objekt maximaler Größe zu reservieren,so wird ein anderes freies Segment als Allokationssegment gewählt. Durch dieses Verfahrenist garantiert, dass für die eigentliche Allokation stets genügend freier Speicher zur Verfü-gung steht und diese in konstanter Zeit durchgeführt werden kann. Auch der Austausch desAllokationssegmentes muss in konstanter Zeit erfolgen, da währendessen keine Allokationmöglich ist. Die Minimierung der dabei auftretenden Fragmentierung durch nicht belegtenSpeicher am Ende des Segments, ist im Nachhinein Aufgabe des Garbage Collectors (3.2).

3.5 Phasen der Garbage Collection

3.5.1 Root-Scan

Vorgehen

Die Root-Referenzen können in der SHAP-Mikroarchitektur sowohl auf dem Stack, alsauch in den Mikrocode-Variablen liegen. Beide Speicherbereiche müssen daher zum Auf-

3.5 Phasen der Garbage Collection 23

finden aller Root-Referenzen durchsucht, das heißt gescannt werden, wobei auch dieserProzess nicht zu einer Unterbrechung des Cores führen darf und vollkommen parallel zudiesem abläuft.

In [Sieb02] werden zur Lösung dieses Problems sämtliche Root-Referenzen automatischin ein extra dafür vorgesehenes Objekt im Heap kopiert, so dass das Finden sämtlicherRoot-Referenzen ebenfalls durch die normale Traversierung des Objektgraphen behandeltwerden kann und lediglich eine einzige Root-Referenz existiert. Dieser Ansatz kann inder SHAP-Mikroarchitektur jedoch nicht umgesetzt werden, da das Kopieren zu einem zugroßen Overhead führen würde. Aufgrund der Tatsache, dass Daten z.B. niemals direkt vomHeap in die Mikrocode-Variablen transferiert werden können, sondern jeder Datenfluss stetsüber den Stack geschieht, genügt mit Hilfe der Stack-Überwachung das einmalige Durch-suchen der Mikrocode-Variablen und des Stacks. Die Root-Scan-Phase wird daher in zweiTeilphasen aufgegliedert.

Da anders als in [Meye04] für gewöhnliche Daten und Referenzen die gleichen Speicher-bereiche (Mikrocode-Variablen) sowie der gleiche Stack verwendet werden, muss eine ge-eignete Unterscheidungsmöglichkeit bereitstehen. Sowohl der Stack als auch die Mikrocode-Variablen wurden unter Verwendung der im FPGA vorhandenen internen Speicher reali-siert. Diese ermöglichen grundsätzlich auch „ungerade“ Breiten, d.h. für jeweils 8 Bit exis-tiert ein zusätzliches 9. sog. parity bit [xap05]. Durch Anpassungen an der Hardware sowieim Mikrocode lässt sich ein solches zusätzliches Bit zur Kennzeichnung von Referenzennutzen. Die Mikrocode-Implementierungen der einzelnen Bytecodes müssen erweitert wer-den, so dass diese Informationen stets korrekt hinterlegt werden.

Mikrocode-Variablen

Der Scan der Mikrocodevariablen beschränkt sich auf die ersten 16 Datensätze des mikrocode-data-memorys, welches Bestandteil des Cores (siehe 2.1.1) ist. Dieses kann linear bei Adres-se null beginnend durchlaufen und nach Referenzen durchsucht werden. Alle gefundenenReferenzen werden grau markiert.

Stack

In der SHAP-Mikroarchitektur wird jedem Thread durch die Stack-Komponente ein eigenerStack zugeordnet, welcher durch eine Liste verketteter Blöcke fester Größe gebildet wird(siehe 2.1.1). Durch dieses Vorgehen und die Tatsache, dass lediglich für den aktuellenThread der Anfang einer solchen Liste direkt bekannt ist, ist ein direkter Scan über dentatsächlich gewachsenen Stack schwierig.

Stattdessen soll zunächst ein einfacherer Ansatz gewählt und lediglich alle belegten Blö-cke gescannt werden, unabhängig von der tatsächlichen Position des Stack-Pointers. Dabeiwerden die Blöcke linear durchlaufen und jeweils der gesamte Block überprüft, wenn die-ser als benutzt markiert ist. Somit werden noch im Block befindliche, jedoch noch nichtüberschriebene Daten ebenfalls beachtet, obwohl möglicherweise nur ein Teil des Blocksbenutzt ist. Befinden sich somit unter diesen Daten auch Referenzen, so werden diese graumarkiert, wodurch eigentlich nicht mehr benötigte Objekte nicht als Garbage erkannt wer-

24 3 Entwurf

den könnten. Diese Unschärfe kann vor allem dann gefährlich werden, wenn das fälschlichreferenzierte Objekt Bestandteil eines größeren Teilgraphen ist, dessen Objekte daraufhinals Ganzes bestehen bleiben.

3.5.2 Heap-Scan

Vorgehen

Während dieser Phase findet die Traversierung des Objekgraphen statt (siehe 2.2.2). Da-zu wird zunächst ein grau markierter (2.2.5) Referenzeintrag gewählt, dieser schwarz unddamit als gescannt markiert und der Speicher des Objektes nach weiteren Referenzen durch-sucht. Alle dabei gefundenen Referenzen werden, so lange dies noch nicht bereits gesche-hen ist, ebenfalls grau markiert. Dieses Verfahren wird so lange fortgesetzt, bis keine graumarkierten Referenzeinträge mehr existieren und somit alle Objekte durchsucht worden.

Veränderungen des Objektgraphen, d.h. sowohl neu angelegte Objekte als auch Ände-rungen bezüglich der Kanten zwischen bestehenden Objekten, werden dabei nur bedingtberücksichtigt (siehe dazu 3.5.3).

Erkennen von Referenzen

Beim Durchsuchen des Speichers eines Objektes ist es notwendig, Referenzen von gewöhn-lichen Daten unterscheiden zu können. Anders als bei den Mikrocode-Variablen und demStack (vgl. 3.5.1), kann dem Heap jedoch kein zusätzliches Markierungsbit hinzugefügtwerden.

Eine Möglichkeit dies sicher, d.h. exakt zu erkennen würde darin bestehen, am Anfangeines jeden Segments einen Bereich vorzusehen, in dem für jedes Wort ein entsprechendesBit zur Kennzeichnung vorhanden ist. Da ein Wort eine Breite von 32 Bit besitzt, würde dies1

32 eines jeden Segments oder gut ≈ 3,1% beanspruchen. In [Sieb02] wird ein derartigerAnsatz verfolgt, indem für jedes Wort im nutzbaren Speicher, eine solche Kennzeichnungvorgesehen ist. Bei jeder Schreiboperation müssen die Bits zur Kennzeichnung aktualisiertwerden, wodurch ein großer Overhead durch zusätzliche Speicherzugriffe entsteht.

Ein ähnlicher Ansatz besteht darin, diese Kennzeichnungsbits beim Anlegen eines Ob-jektes einmalig zu setzen und schließlich für die gesamte Zeit, die sich ein Objekt in einemSegment befindet, konstant zu halten. Dies ist möglich, da in Java die Struktur eines Ob-jekts bekannt ist und somit jedem Feld ein bestimmter Typ zugeordnet werden kann. Auchkönnten den Klassenobjekten [Pre+07], welche sowohl die Methoden als auch die Struktureines Objektes beschreiben, Informationen bezüglich der Positionen enthaltener Referen-zen zugeordnet werden. Dadurch müssten diese Daten für jede Klasse lediglich einmalighinterlegt werden, allerdings gestaltet sich das Traversieren des Objektgraphen recht auf-wändig, da für jedes zu überprüfende Objekt auch der Type und daraufhin die Positionender Referenzen ermittelt werden müsste.

Der in [Meye04] bzw. [Meye05] verfolgte Ansatz sieht vor, die Speicherbereiche fürReferenzen von denen für gewöhnliche Daten zu trennen, d.h. die Struktur eines Objektesvon vornherein entsprechend so zu organisieren, das die Positionen der Referenzen bekannt

3.5 Phasen der Garbage Collection 25

stackmemory

Microcode datamemory

Memory manager

TOS

NOS

Stack

Abbildung 3.8: Der Stack als zentrales Element in der SHAP-Mikroarchitektur.

sind. Dadurch wären allerdings umfangreiche Änderungen am Klassenlayout der SHAP-Plattform notwendig, jedoch könnte auf zusätzliche Bits zur Referenzmarkierung gänzlichverzichtet werden.

Die sog. konservativen Ansätze gehen nach [Wils94, Jone96] zur Erkennung von Re-ferenzen einen anderen Weg und nehmen eine gewisse Unschärfe in Kauf. Anstelle dersicheren Erkennung wird lediglich gefordert, dass eine Referenz nicht fälschlich verlorengehen darf. Umgekehrt kann jedoch ein nicht referenziertes Objekt durchaus fälschlich alsreferenziert erkannt werden, wodurch dieses nicht als Garbage markiert und entsprechendauch nicht freigegeben werden würde. Ein solcher konservativer Ansatz ist nach [Sieb02]zur Einhaltung von Echtzeitbedingungen ungeeignet, lässt sich jedoch wesentlich einfacherumsetzen.

Für die Realisierung des Garbage Collectors soll – ungeachtet der Nachteile – zunächstein konservativer Ansatz verfolgt werden. Dazu wird dem beim Anlegen eines Objektes(3.3.3) vergebenen Handle (siehe 3.3.1) in den oberen Bits eine Signatur hinzugefügt. Diesist möglich, da ein Handle wesentlich kürzer als 32 Bit ist. Wird diese Signatur beim Scanerkannt, so wird der entsprechende Datensatz als Referenz betrachtet.

3.5.3 Überwachung des Stacks

In der SHAP-Mikroarchitektur bildet der Stack eine zentrale Komponente, da jeglicher Da-tenfluss aufgrund der Stack-Architektur der virtuellen Maschine stets über diesen abläuft(vgl. Abb. 3.8). So ist es beispielsweise nicht möglich, ein Datum direkt von den Mikrocode-Variablen zu lesen und im Heap zu speichern.

Die oberen beiden Elemente des Stacks werden in den Registern TOS (top of stack) bzw.NOS (next of stack) gehalten [Pre+07]. Da ein Objekt auf keinen Fall fälschlich als Garbageerkannt werden darf, ist es unerlässlich, das keine Referenz „verloren“ geht.

Wird im Zuge der Stack-Überwachung daher Änderungen des NOS- und TOS-Registersbeobachtet und geprüft, ob es sich um Referenzen handelt, so kann dies zur Synchronisationzwischen Mutator und Garbage Collector verwendet werden. Da sowohl gelesene als auch

26 3 Entwurf

zu schreibende Werte zunächst in einem dieser beiden Register abgelegt werden, kann dieStack-Überwachung sowohl als Lese- als auch als Schreibbarriere aufgefasst werden.

Im Falle einer Push-Operation, wird das Datum, ganz gleich woher dieses kommt, inTOS abgelegt. Umgekehrt wird bei einer Pop-Operation ein Datum vom Stack genommenund in das NOS-Register verschoben, wobei der bisherige Wert des NOS-Registers in TOSabgelegt wird. Ist die Stack-Überwachung aktiviert und wird anhand des Markierungsbitseine Referenz erkannt, so wird das entsprechende Objekt grau markiert.

Dieses Vorgehen deckt auch ungünstige Konstellationen ab. So wird selbst dann, wenneine Referenz unmittelbar vor der Ausführung des Scans der Mikrocode-Variablen auf denStack kopiert und an der ursprünglichen Position überschrieben wird, diese durch die Stack-Überwachung bemerkt und grau markiert. Ähnliche Szenarien lassen sich z.B. auch zwi-schen Heap und Stack konstruieren, bei denen jedoch ebenfalls keine Referenz verlorengehen kann.

Soll eine nicht mehr benötigte Referenz vom Stack entfernt werden, ohne das diese imHeap oder den Mikrocode-Variablen abgelegt wird, so entsteht erneut eine Unschärfe. Dasentsprechende Objekt wird markiert und kann folglich nicht als Garbage erkannt werden.Jedoch ist davon nur der aktuelle Garbage Collection Zyklus betroffen, denn das bereitsverworfene Handle lässt sich nicht zurückgewinnen, weshalb hierbei floating-garbage ent-steht.

Da in einem neu angelegten Objekt zunächst keine ausgehenden Referenzen existierenkönnen, werden diese normalerweise direkt schwarz markiert. In der SHAP-Mikroarchitekturwerden die zugehörigen Handles jedoch immer bereits nach einer nur sehr kurzen Zeit aufden Stack gelegt, weshalb auch neue Referenzen automatisch von der Stack-Überwachungbehandelt und folglich grau markiert werden. Auch wenn durch das Anlegen des neuen Ob-jekts der Austausch des Allokationssegments notwendig sein sollte (wodurch das Bisherigevon der Markierungsphase behandelt werden kann), wird das neue Objekt durch die Stack-Überwachung grau markiert, da das Laden des Handles durch den Mikrocode bereits vorder Fertigstellung des Austauschs des Allokationssegments abgeschlossen ist.

3.5.4 Markierungsphase eines Segments

Vorgehen

Diese Phase wird für jedes belegte Segement (siehe 3.4.2) durchlaufen. Es wird jeweilsuntersucht, ob dieses nicht erreichbare Objekte enthält. Dazu dienen die bereits in 3.3.2eingeführten Listen von Referenzeinträgen, durch welche jedem Segment alle enthaltenenObjekte zugeordnet werden können. Das aktuelle Allokationssegment wird von dieser Pha-se nicht betrachtet.

Wird ein Objekt gefunden, welches ein weißes Markierungsflag besitzt, so wird diesesdurch Setzen des Zustands als Garbage (dead) markiert. Außerdem wird die Größe desObjektes zum Wert der toten Worte des Segmentes hinzuaddiert und der Zähler der totenReferenzen inkrementiert.

Nachdem diese Phase für ein Segment abgeschlossen wurde, wird mit Hilfe einer Aus-wahlfunktion (3.7) entschieden, ob durch die Bereinigung dieses Segmentes ein Gewinn an

3.6 Begrenzung der Objektanzahl im Segment 27

freiem Speicher erzielt werden kann. Ggf. wird daraufhin die Freigabephase (3.5.5) gestar-tet und andernfalls mit der Markierung des nächsten Segmentes fortgefahren. Nachdem alleSegmente die Markierungs- und ggf. die Freigabephase durchlaufen haben, ist der GarbageCollection Zyklus beendet.

Besonderheiten

Aufgrund der Synchronisation mit Hilfe der Stack-Überwachung (3.5.3), können auch nachAbschluss der Heap-Scan-Phase (3.5.2) noch grau markierte Referenzen existieren. Diesbetrifft jedoch nur neu angelegte Objekte, deren Handle erst nach Beendingung der Heap-Scan-Phase auf den Stack gelegt wurde. Grau markierte Objekte werden daher stets genauwie Schwarze behandelt 1.

3.5.5 Freigabephase eines Segments

Diese Phase wird im Anschluss an die Markierungsphase für ein Segment stets dann durch-laufen, wenn durch das Verschieben der referenzierten Objekte in ein anderes Segment unddie darauffolgende Freigabe des Segments ein Gewinn an freiem Speicher zu erzielen ist.

Dazu werden erneut alle enthaltenen Objekte betrachtet. Ist ein Objekt durch seinen Zu-stand als Garbage markiert, so wird der Referenzeintrag der Liste der freien Referenzein-träge hinzugefügt (3.3.2), die Größe auf 0 sowie der Zustand auf „frei“ gesetzt. Andernfallswird das Objekt noch benötigt und muss zur Freigabe des Segments in ein anderes – dasZielsegment (3.9) – verschoben werden. Dabei wird der Referenzeintrag auch in die entspre-chende Liste des Zielsegmentes eingegliedert und die Zahl der belegten Worte aktualisiert.Nachdem alle Objekte freigegeben oder verschoben worden, ist das Segment leer und kannals Ganzes freigegeben werden (3.4.2). Dabei werden auch die zum Segment gehörendenDatensätze zurückgesetzt.

3.6 Begrenzung der Objektanzahl im Segment

Durch die Bereinigung des Speichers auf Segmentebene während der Freigabephase, istneben dem Speicher eines als Garbage markierten Objektes, auch der dem Objekt zugeord-nete Referenzeintrag, nicht nutzbar. Ist die Zahl der freien Referenzeinträge erschöpft, soschlägt das Anlegen eines neuen Objekts fehl. Der Garbage Collector muss daher auch fürausreichend freie Referenzen sorgen, ein Segment also auch dann freigeben, wenn viele alsGarbage markierte Objekte enthalten sind, jedoch kein großer Gewinn an freiem Speichererzielbar ist (siehe 3.7).

Da das Allokationssegment sowohl von der Markierungs- (3.5.4) als auch von der Freiga-bephase (3.5.5) nicht beachtet wird, könnten durch das Anlegen einer großen Zahl kleinerObjekte sehr viele Referenzeinträge gebunden werden, obwohl die zugehörigen Objektebereits nicht mehr erreichbar sind. Dies wird verhindert, indem die Anzahl der Objekteim Allokationssegment begrenzt wird. Das Segment wird daher bei Erreichen einer oberen

1Entspricht der bereits erwähnten automatischen Graumarkierung neuer Objekte.

28 3 Entwurf

Grenze enthaltener Objekte ebenfalls ausgetauscht und kann daher im nächsten GarbageCollection Zyklus behandelt werden.

Eine derartige Begrenzung ist prinzipiell auch für alle Segmente möglich, wobei die Be-trachtung der Zahl als Garbage markierter Objekte in der Auswahlfunktion entfallen kann.Andererseits würden, gerade bei sehr kleinen Objekten, große Teile eines Segments nichtverwendet werden können. Dennoch soll zunächst dieser Ansatz implementiert und die An-zahl der Objekte pro Segment generell begrenzt werden.

3.7 Auswahlfunktion

Nach der Bereinigung eines Segements wird dieses als Ganzes freigegeben und alle nicht alsGarbage markierten Objekte in ein anderes Segment (siehe 3.9) verschoben. Dadurch kanndie Anzahl der freien Segmente nie geringer sein als vor der Bereinigung. Allerdings sollein Segment nur dann freigegeben werden, wenn dadurch ein Gewinn an freiem Speicherzu erzielen ist, wodurch ein unnötiges Verschieben von Objekten vermieden werden soll.

Bei der Konstruktion einer darauf aufbauenden Auswahlfunktion muss berücksichtigtwerden, dass durch die Austauschbedingung des Allokationssegmentes, in diesem zumeistvon vornherein zahlreiche Worte nicht belegt sind. Befinden sich in einem Segment alsGarbage markierte Objekte, so stehen auch die diesen zugeordneten Referenzeinträge nichtfür neue Objekte zu Verfügung.

Prinzipiell stehen für jedes Segment drei wichtige Kennzahlen zur Verfügung (vgl. 3.4.2):die Anzahl der belegten Worte (W ), die Anzahl der Worte in nicht benötigten und damitnicht erreichbaren Objekten (D) sowie die Anzahl der als Garbage markierten Objekte selbst(R).

In die Auswahlfunktion können neben statischen Parametern natürlich auch dynamisch,zur Laufzeit berechnete Werte einfließen, wie z.B. die momentane Anzahl freier Referen-zen, die Anzahl freier Segmente oder auch Abschätzungen bezüglich der Allokationsrateeiner Anwendung. Im Folgenden soll jedoch lediglich eine Auswahlfunktionen angegebenwerden, welche nur von den Kennzahlen des Segments abhängt:

fauswahl(W,D,R) =

true : W ≤ sWmin

true : D≥ sDmax

true : R≥ sRmax

f alse : sonst

3.8 GC-Triggering

Das unter 3.2 angegebene Garbage Collection Konzept arbeitet wie alle Verfahren auf Basisdes Tracings, zyklenbasierend. Es existieren zahlreiche Strategien die bestimmen, wann miteinem Garbage Collection Zyklus zu beginnen ist.

Zur Abschätzung der Effizienz soll sowohl ein Verfahren anhand der Auslastung desSpeichers implementiert werden, als auch zeitabhängige Verfahren, wobei die jeweiligenGrenzen konfigurierbar sein sollen.

3.9 Zielsegment 29

3.8.1 Speicherauslastung

Der einfachste Ansatz, welcher auch ursprünglich von [McCa60] angegeben wurde, berei-nigt den Speicher, wenn eine Anforderung nicht erfüllt werden kann. Aufgrund der Forde-rung nach konstanter Laufzeit und der mit dem Ansatz einhergehenden Unterbrechung derApplikation, kommt dieses Verfahren nicht in Frage.

Ein etwas allgemeinerer Ansatz startet den Garbage Collector nicht erst bei vollständigerErschöpfung des freien Speichers, sondern, wie in [Pfe+04], bereits vorher, bei erreicheneiner bestimmten Auslastung. Das Festlegen einer solchen Grenze ist nach [Sieb02] jedochstark abhängig vom Verhalten der Anwendung (Allokationsrate) und der Größe des verfüg-baren Speichers. Außerdem muss die Dauer des Garbage Collection Zyklus berücksichtigtwerden, da Freigaben lediglich segmentweise erfolgen und zunächst die Traversierung desObjektgraphen durchgeführt werden muss.

Als mögliche Kennzahlen stehen sowohl die Anzahl der freien Referenzeinträge, als auchdie Zahl der freien Segmente zur Verfügung. Letztere kann näherungsweise mit der Größedes freien, zur Reservierung nutzbaren Speichers gleichgesetzt werden. Es soll daher diefolgende Funktion verwendet werden, um einen Zyklus zu starten:

ftrigger(Cre f ,Cseg) =

true : Cre f ≤ Tre fmin

true : Cseg ≤ Tsegmin

f alse : sonst

Cre f und Cseg spiegeln dabei die aktuelle Anzahl freier Referenzeinträge bzw. freier Seg-mente wieder. Die Werte zur minimalen Anzahl freier Referenzeinträge Tre fmin bzw. Seg-menteinträge Tsegmin sollen konfigurierbar sein.

3.8.2 Zeitabhängig

Eine andere Möglichkeit ist, den Collector zeitabhängig zu starten, wodurch jedoch dermomentane Zustand des Systems nicht berücksichtigt wird. Das Verhalten einer Anwen-dung bezüglich der Speicherreservierung ist jedoch ohnehin bekannt, wodurch auch dieserAnsatz möglich wird.

Der Garbage Collector soll daher periodisch, mit einer Periodendauer Ttrig ausgeführtwerden, wobei Ttrig ebenfalls konfigurierbar ist.

3.9 Zielsegment

Wird ein Segment bereinigt, so werden alle enthaltenen, nicht als Garbage markierten Ob-jekte in ein anderes Segment verschoben (vgl. 3.2). Der Garbage Collector fordert dazu einfreies Segment an, welches als Zielsegment verwendet wird. Jedes nun zu verschiebendeObjekt soll, unabhängig vom bisherigen Segment, in dieses Zielsegment verschoben wer-den.

Ist für eine solche Verschiebung nicht genügend freier Speicher vorhanden, so wird einanderes freies Segment als Zielsegment ausgewählt. Damit dies immer garantiert ist unddie Bereinigung eines Segments stets vollständig abgeschlossen werden kann, muss stets

30 3 Entwurf

ein Segment als Reserve bereitstehen. Dieses kann nicht zum Austausch des Allokations-segments (siehe 3.4.3) verwendet werden.

Da das Zielsegment stets ausgetauscht wird, sobald der freie Speicher für das Verschiebeneines Objektes nicht ausreicht, kann ein Teil des Speichers am Ende des Segmentes nichtgenutzt werden. Die Größe dieses Bereiches ist dabei abhängig von der Auslastung desSegments, kann jedoch nie die maximale Objektgröße erreichen (vgl. dazu 3.11).

3.10 Steuerung des Garbage Collectors

Die Steuerung des Garbage Collectors soll sowohl durch einen in Hardware implementier-ten Steuerautomaten, als auch durch ein in Java realisiertes Programm erfolgen, welches ineinem separatem Thread parallel zur eigentlichen Applikation ausgeführt wird.

Der grobe Ablauf eines Collection-Zyklus ist dabei in beiden Realisierungen gleich. Al-lerdings können bei Verwendung einer Software-Steuerung, kleinere Änderungen sehr vielleichter umgesetzt werden. Außerdem ist es möglich, sehr viel detailierter auf das Verhaltender Anwendung und den aktuellen Zustand des Systems zu reagieren und gewisse Eigen-schaften des Garbage Collectors geeigent anzupassen. Da die Software-Steuerung jedochparallel zur eigentlichen Applikation auf der gleichen CPU ausgeführt wird, wird auch einTeil der zur Verfügung stehenden Rechenzeit benötigt.

3.11 Segmentgröße und Fragmentierung

Die Größe und die Anzahl der Segmente orientiert sich vor allem am zur Verfügung stehen-den Speicher, jedoch müssen einige weitere Bedingungen erfüllt sein. Sowohl die maximaleObjektgröße Sob jmax = 2n, als auch die Größe der Segmente Ssegment = 2m, sind stets an Zwei-erpotenzen ausgerichtet.

Ein Objekt kann sich nicht über die Grenzen eines Segments hinweg erstrecken, wodurchein Segment mindestens ein Objekt maximaler Größe aufnehmen können, also

Ssegment ≥ Sob jmax

gelten muss. Da das Allokationssegment ausgetauscht wird (siehe 3.4.3), sobald der freieSpeicher für das Anlegen eines Objekts maximaler Größe nicht ausreicht, kann als untereGrenze jedoch mindestens das Doppelte der maximalen Objektgröße angegeben werdenund es muss

Ssegment ≥ 2Sob jmax

und damit m≥ n+1 gelten.Genügt der freie Speicher in einem Segment nicht zur Aufnahme eines Objekts, so kann

aufgrund des Austausches des Segments, der entsprechende Speicher nicht belegt werden.Die Größe des nicht nutzbaren Speichers wird maximal, wenn ein Objekt maximaler Größeangelegt werden soll, der freie Speicher aber gerade nicht genügt, um das Objekt aufzuneh-men:

S f reemax = Sob jmax−1

3.12 Variationen der Strategie 31

Der maximale Anteil u des nicht nutzbaren Speichers am Segment kann wie folgt berech-net werden:

u =S f reemax

Ssegment=

Sob jmax−1Ssegment

=2n−1

2m

u≈ 12m−n , m,n� 1,m≥ n

Dieser ist also umso kleiner, je größer die Differenz m− n ist, je mehr Objekte maxi-maler Größe also in ein Segment hineinpassen. Die Größe der Segmente sollte folglichnicht zu klein gewählt werden, um einer übermäßigen Fragmentierung durch nicht nutzbareSpeicherbereiche vorzubeugen.

Allerdings muss auch berücksichtigt werden, dass der Garbage Collector durch die Mar-kierungs- und Freigabephase auf Segmentebene arbeitet und beide Phasen bei sehr großenSegmenten wesentlich aufwändiger sind. Außerdem wird der Anteil von floating-garbagedurch große Segmente deutlich vergrößert.

3.12 Variationen der Strategie

3.12.1 Frühere Freigabe der Referenzeinträge

Da die Bereinigung des Speichers auf Segmentebene erfolgt, muss auch die Anzahl derals Garbage markierten Objekte in einem Segment beachtet werden (siehe 3.6). Dadurchkönnen jedoch auch Segmente freigegeben werden, für die nur ein geringer Gewinn anfreiem Speicher zu erwarten ist.

Während der Freigabe werden nur alle nicht als Garbage markierten Objekte in ein an-deres Segment verschoben, alle anderen werden freigegeben. Da ein jeder Referenzeintrageinen Zeiger auf die tatsächliche Position des Objektes im Speicher enthält, sind die alsGarbage markierten Referenzeinträge für die Segmentfreigabe nicht notwendig. Da dannauch die Freigabe der Referenzeinträge entfallen kann, würde sich diese Phase sogar ver-einfachen.

Die in 3.2 beschriebene Trennung der Phasen zur Markierung und zur Freigabe, soll da-her, bezogen auf die Referenzeinträge, aufgehoben werden. Dazu wird in der Markierungs-phase, anstelle ein Objekt als Garbage zu markieren, der zugehörige Referenzeintrag direktaus der entsprechenden Liste des Segments entfernt und freigegeben (siehe Abbildung 3.9).Die übrigen im Segment verbleibenden Objekte verändern ihre Position dabei nicht.

3.12.2 Voralterung von Segmenten

Wird das Allokationssegment ausgetauscht, so enthält dieses nur junge Objekte, welchenach der weak-generational-hypothesis (siehe 2.2.4) jedoch oft nur eine sehr begrenzte Le-bensdauer aufweisen. Wird ein solches Segment sofort zur Bereinigung ausgewählt, so wer-den mitunter zahlreiche junge Objekte in ein anderes Segment verschoben, obwohl diese

32 3 Entwurf

��

��

��

��

��

��

��

��

seg pointer

free

free

free

freefree

poi

nter

...

seg pointer

...

free

free

garb

garb

free

poi

nter

Abbildung 3.9: Nicht erreichbare Referenzen werden in der Markierungsphase sofort frei-gegeben (rechts), anstelle sie zunächst als Garbage zu markieren (links). Diezugehörigen Speicherbereiche sind dadurch nicht mehr durch Indirektions-zeiger referenziert.

vermutlich bereits nach kurzer Zeit nicht mehr benötigt werden.Ein möglicher Ansatz besteht in der Voralterung dieser Segmente, indem nicht unmit-

telbar durch die Markierungs- bzw. Freigabephase behandelt werden. Dies wird erreicht,indem mit Hilfe des zusätzlichen Datensatzes (siehe 3.4.2), jedem Segment ein Flag zu-geordnet wird, welches zunächst nicht gesetzt ist. Während der Markierungsphase und da-durch auch während der Freigabephase (siehe 3.5.5), werden nur die Segmente behandelt,bei welchen das entsprechende Flag gesetzt ist, andernfalls wird das Flag gesetzt. Ein sol-ches Segment wird dadurch erst im darauffolgenden Garbage Collection Zyklus behandelt,wodurch jedoch vermutlich zahlreiche junge Objekte bereits nicht mehr erreichbar sind undfolglich nicht umsonst umkopiert werden.

Da sowohl der freie, als auch der allokierte, jedoch nicht erreichbare Speicher eines sol-chen Segments erst verzögert freigegeben wird, steht dem System allerdings weniger Spei-cher zur Verfügung.

3.12.3 Generationen

Die in 3.12.2 vorgestellte Voralterung von Segmenten verhindert das unnötige Verschiebenbesonders junger Objekte. Dieser Ansatz kann erweitert werden, indem allgemein Objekteetwa gleichen Alters in bestimmten Segmenten zusammengefasst werden. Ältere Segmentewerden daraufhin von der Garbage Collection seltener betrachtet als jüngere, weshalb derOverhead der Markierungs- und damit auch der Freigabephase, für diese Segmente zumeistentfällt. Wird ein Segment erst nach k Zyklen der Garbage Collection von der Markierungs-phase behandelt, so haben alle erreichbaren Objekte mindestens k Zyklen überlebt.

Zur Realisierung dieses Konzepts wird jeder Generation eine Gruppe von Segmentenzugeordnet. Das in 3.4.2 beschriebene Konzept zur Verwaltung der Segmenteinträge wirddahingehend erweitert, dass eine solche doppelt verkettete Liste für jede Gruppe existiert

3.12 Variationen der Strategie 33

free pointer

Segment

next

previous

...

grp[0]

...

...

grp[1]

grp[2]

Abbildung 3.10: Erweiterte Listenstruktur zur Repräsentation verschiedener Gruppen.

(siehe Abbildung 3.10). Das Allokationssegment wird stets der Gruppe 0 zugeordnet, derenKopf stets der Segmenteintrag unmittelbar rechts des free-pointers ist, wodurch der Aus-tausch des Allokationssegments unverändert bleibt.

Wird ein neues Zielsegment für die Garbage Collection benötigt, so kann dieses in einebeliebige Gruppe eingegliedert werden. Dazu wird der Segmenteintrag aus der ursprüngli-chen Liste entfernt und der Neuen hinzugefügt, wobei dieser daraufhin den Kopf der Listebildet. Eine nachträgliche Änderung der Gruppenzugehörigkeit ist jedoch nicht möglich.

Der Garbage Collector wählt für jede Gruppe ein separates Zielsegment aus, wodurch beiG Gruppen genau G−1 Zielsegmente benötigt werden. Erfolgt die Freigabe eines Segmentsaus Gruppe i mit (0≤ i≤ G−2), so werden die überlebenden Objekte in das Zielsegmentder Gruppe i + 1 verschoben. Hingegen werden Objekte aus Segmenten der ältesten Grup-pe (i = G− 1) auch beim Verschieben dem Zielsegment der gleichen Gruppe zugewiesen.Durch dieses Vorgehen sind der Gruppe i = 0 lediglich Segmente zugeordnet, welche be-sonders junge Objekte enthalten. Während der erste Eintrag der Gruppe i = 0 stets dasAllokationssegment darstellt, entsprechen die Listenköpfe der anderen Gruppen den aktuellgewählten Zielsegmenten. Ein freizugebendes Segment wird, unabhängig seiner Gruppen-zuordnung, stets aus der bisherigen Liste ausgegliedert und der Liste der freien Segmen-teinträge hinzugefügt.

4 Implementierung

Der Garbage Collector wurde als Teil des Speichermanagers realisiert und in VHDL imple-mentiert. Dazu wurden zunächst wichtige Grundfunktionen wie die Verwaltung der Objektebzw. Referenzeinträge, das Management der Segmente oder die Bereitstellung des Alloka-tionssegmentes extrahiert und in entsprechenden Grundkomponenten umgesetzt.

Von diesen Grundkomponenten bereitgestellte Funktionen zur Arbeit mit Objekte undSegmenten, werden durch Teilkomponenten des Garbage Collectors zu komplexeren Opera-tionen kombiniert und schließlich zum Auffinden nichtbenötigter Objekte sowie zur Berei-nigung des Speichers genutzt. Die Steuerung des gesamten Ablaufes zur Garbage Collectionkann schließlich sowohl durch einen ebenfalls in VHDL implementierten Steuerautomatenoder durch ein Java-Programm erfolgen.

4.1 Speicherlayout und Strukturen

Das Layout des Speichers ist in Abbildung 4.1 dargestellt. Die Daten zur Verwaltung derObjekte bzw. Referenzeinträge befinden sich am Anfang des physischen Speichers. Diebeiden zu einem Referenzeintrag gehörenden Worte werden dabei unmittelbar hintereinan-der gespeichert, wodurch sich deren Adressen in nur einem Bit unterscheiden. Insgesamtwerden Sre f Worte benötigt. Diese Zahl orientiert sich stets an Zweierpotenzen, wobei derExponent direkt die Bitbreite des Handles bestimmt.

Unmittelbar nach der Tabelle der Referenzeinträge schließt sich die Tabelle zur Speiche-rung der Segmenteinträge an, für welche Sseg Worte benötigt werden. Auch hier werden allezu einem Eintrag gehörenden Worte unmittelbar nacheinander abgelegt, weshalb sich diezugehörigen Adressen in den beiden letzten Bits unterscheiden.

Die Gesamtgröße des Speichers für Verwaltungsinformationen ist somit

Sverw = Sre f tab +Ssegtab

Dieser Speicher darf durch das Anlegen von Objekten keinesfalls überschrieben werden.Das Ausblenden von Speicher ist auf Ebene der Segmente (siehe 3.4) besonders einfachmöglich, weshalb die ersten u Segmente, mit

uSsegment ≥ Sverw, u ∈ N+

ausgeblendet werden und folglich nicht zur Reservierung von Speicher zur Verfügung ste-hen. Durch dieses Vorgehen kann, je nach Anzahl der Referenz- und Segmenteinträge sowie

36 4 Implementierung

Ref 1: Word 0

Ref 1: Word 1

Ref 2: Word 1

Ref 2: Word 0

0x00

0x01

0x02

0x03...

Ref−Data Seg−Data usable spacefreer0x00 r+s

r+0x00 Seg−Entry 0

...

r+0x08

r+0x0a

Seg−Entry 1

Seg−Entry 2

Seg−Entry 3

r+0x04

u*s (k−u)*s

Abbildung 4.1: Darstellung des Layouts des Speichers. Die Verwaltungsinformationen be-finden sich am Anfang beginnend bei Adresse 0x00.

��

��

statesizenext pointer (L)

base address (A)not used

Word 0:

Word 1:��

��

not used

Abbildung 4.2: Darstellung der Daten eines Referenzeintrags und Aufteilung in zwei Worte.

abhängig von der Größe der Segmente, ein gewisser Speicherbereich der Größe

Snn = uSsegment −Sverw

nicht verwendet werden.

4.1.1 Referenzeinträge

Die Daten eines Referenzeintrages werden unterschiedlich häufig benötigt. So muss dieAdresse eines Objektes immer dann abgerufen werden, wenn das entsprechende Objekt vonder CPU ausgewählt wird (op_st_ref, siehe 2.1.2). Diese Adresse kann, je nach Größedes Speichers, außerdem unterschiedlich breit sein, weshalb diese in einem separaten Wortabgespeichert wird. Die anderen Informationen (Zustand, Zeiger auf nächsten Referenzein-trag und Größe des Objektes) werden in einem 32-Bit-Wort zusammengefasst und lediglichbeim Anlegen des Objektes bzw. während der Garbage Collection benötigt oder verändert.Da für die Speicherung des Zustands 2 Bit erforderlich sind, können die Felder für die Grö-ße eines Objektes sowie für den Zeiger auf den nächsten Referenzeintrag, zusammen 30 Bitumfassen (siehe 4.2).

4.1.2 Segmenteinträge

Die einem Segmenteintrag zugeordneten Datensätze W, D, R und L werden jeweils in ei-nem separaten Wort im Speicher abgelegt (siehe Abb. 4.3). Dies ermöglicht einen beson-ders einfachen Zugriff und ist, aufgrund der begrenzten Anzahl von Segmenten, problemlos

4.2 Struktur des Speichermanagers 37

��

��

��

��

��

��

��

��

��

unused

dead refs (R)

obj list (L)

used words (W)

dead words (D)

Abbildung 4.3: Die einem Segmenteintrag zugeordneten Datensätze. Während L, D, W undR direkt im Speicher hinterlegt werden können, werden die für die Listen-struktur notwendigen Zeiger (next und previous) gemeinsam mit dem freiwählbaren Datensatz (seg_data) in internen Speicherblöcken des FPGAsabgelegt.

möglich. Da der Zugriff auf die Verkettungsinformationen besonders schnell möglich seinmuss, werden diese, gemeinsam mit dem frei wählbaren Datensatz, nicht im externen Spei-cher untergebracht (vgl. 4.2.3).

4.1.3 Alignment

Der Speicher-Controller der SHAP-Mikroarchitektur unterstützt das blockweise Kopierenvon Datensätzen, wobei die Blockgröße durch den Controller vorgegeben wird und auchvom Typ des verwendeten Speichers abhängt. Damit dies möglichst effektiv eingesetzt wer-den kann, werden Objekte im Speicher anhand dieses vorgegebenenen Alignments ausge-richtet.

4.2 Struktur des Speichermanagers

Der Speichermanager, dessen Struktur in Abbildung 4.4 dargestellt ist, besteht aus einerReihe von Teilkomponenten, die jeweils spezifische Funktionen kapseln. Die beiden Kom-ponenten refman und segman, welche zur Verwaltung der Objekte bzw. der Segmentedienen, können mit Hilfe des Memory-Access-Managers (memaccman) auf den darunter-liegenden Speicher zugreifen. Alle die der CPU angebotenen Operationen werden durchden Referenz-Manager bearbeitet.

Der Memory-Access-Manager ermöglicht dabei einer der beiden Komponenten mehrereSpeicherzugriffe nacheinander auszuführen (atomar), ohne dass diese durch eine Anforde-rung der jeweils anderen Komponente unterbrochen werden. Sowohl der Referenz-Managerals auch der Segment-Manager, stellen für den Garbage Collector (gc) Funktionen zur Ar-beit mit Objekten bzw. Segmenten bereit, wodurch eine direkte Verbindung des GarbageCollectors zum Memory-Access-Manager entfält. Der Garbage Collector benötigt daherkeine Kenntnisse über die interne Verwaltung von Objekten oder Referenzen. Die Kompo-nente allocsegs beinhaltet die Daten des aktuellen Allokationssegmentes, das aktuelle


memaccman

CP

U

Memory Controller

refman segman

gc

alloc_seg

MMUCtrl

MMUStat

IO−Bus

Abbildung 4.4: Darstellung der groben Struktur des Speichermanagers.

Zielsegment der Garbage Collection wird durch die Komponente gcsegs bereitgestellt.Die Steuerung des Speichermanagers sowie die Abfrage bestimmter Informationen, erfolgtmit Hilfe der Komponente MMUCtrl. Zur Beobachtung während der Entwicklung sowiezur Bewertung des Systems wurde die Komponente MMUStat hinzugefügt.

4.2.1 Memory-Access-Manager

Der Memory-Access-Manager steuert den Speicherzugriff verschiedener Komponenten un-ter wechselseitigem Ausschluss. Die Anzahl der Zugriffsports ist konfigurierbar, jedochbenötigen derzeit nur der Referenz- sowie der Segment-Manager Zugriff auf den Speicher.

Beabsichtigt eine Komponente einen einzelnen oder auch mehrere aufeinanderfolgen-de, nicht unterbrechbare Speicherzugriffe durchführen, so wird dies dem Memory-Access-Manager angezeigt. Führt keine andere Komponente bereits einen Zugriff aus, so wird derSpeicher der anfordernden Komponente exklusiv zugeordnet. Diese kann daraufhin ohneden Einfluss anderer Komponenenten arbeiten. Nach Abschluss des letzten Zugriffs gibtdie Komponente dem Memory-Access-Manager bekannt, dass keine weiteren Speicherzu-griffe notwendig sind, woraufhin die Zuordnung aufgehoben wird.

Jeder Komponente wird außerdem eine Priorität zugewiesen, wobei der Referenz-Managerbei gleichzeitigem Bedarf nach Speicherzugriffen gegenüber dem Segment-Manager bevor-zugt wird.

4.2.2 Referenz-Manager

Aufgabe

Der Referenz-Manager stellt alle Funktionen bereit, die zur Verwaltung von Objekten undReferenz-Einträgen dienen. Dazu werden die in 3.3 beschriebenen Verfahren umgesetzt undimplementiert. Außerdem werden alle, der CPU bereitgestellten Funktionen zum Anlegen


neuer sowie zum Zugriff auf bestehende Objekte, durch den Referenz-Manager bearbeitetsowie verschiedene Operationen zur Arbeit mit Objekten und Referenzeinträgen für denGarbage Collector bereitgestellt.

Bereitgestellte GC-Operationen

Gegenüber dem Garbage Collector werden eine Reihe von Operationen angeboten, durchwelche dieser keinerlei Kenntnis über die Interna der Referenzeintrags- und Objektverwal-tung benötigt. Die einzelnen Operationen sind im Folgenden kurz aufgelistet:

• RMCMD_REFDATA:Die Daten (siehe 3.3.2) eines anhand seines Handles bestimmten Referenzeintrageswerden gelesen und zurückgegeben.

• RMCMD_GARBAGE:Das Verhalten dieser Operation unterscheidet sich je nachdem, ob Referenzeinträ-ge bereits in der Markierungsphase freigegeben werden (siehe 3.12.1), oder nicht.Erfolgt die Freigabe erst in der Freigabephase, so wird lediglich der Zustand des Ob-jektes geändert und auf dead gesetzt. Wird ein Referenzeintrag hingegen bereits inder Markierungsphase freigegeben, so wird das als Garbage zu markierende Objektaus der zum Segment gehörenden Liste entfernt.

• RMCMD_SCANREF:Die Daten des zum Objekt gehörenden Referenzeintrags werden geladen und derInhalt des Objekts nach enthaltenen ausgehenden Referenzen untersucht. GefundeneReferenzen werden in ein FIFO (siehe 4.3.2) geschrieben, von welchem ausgehenddie Markierung erfolgt.

• RMCMD_MOVEREF:Diese Operation lädt ebenfalls zunächst die Daten eines zu einem Objekt gehören-den Referenzeintrags. Außerdem wird der Operation ein Zielsegment übergeben, inwelches die Daten des Objektes verschoben werden. Nachdem die Daten verscho-ben worden, wird der Indirektionszeiger auf die neue physische Adresse des Objek-tes gesetzt. Zum Verschieben wird die durch den Speicher-Controller bereitgestellteOperation zum Kopieren von Blöcken verwendet, welche sich an der vorgegebenenBlockgröße orientiert.

• RMCMD_FREEREF:Der zum Objekt gehörende Referenzeintrag wird freigegeben, indem er der Liste derfreien Einträge hinzugefügt wird. Dabei wird auch der Zähler freier Referenzen in-krementiert.

Unterbrechbarkeit langer Operationen

Die Operationen zum Scannen sowie zum Kopieren eines Objektes können je nach Grö-ße des betrachteten Speichers sehr unterschiedliche Zeiten benötigen. Damit für die Bear-beitung der gegenüber der CPU bereitgestellten Operationen weiterhin eine obere Grenze


bezüglich der Ausführungszeit angegeben werden kann, sind diese Operationen unterbrech-bar implementiert. Bei Zugriff der CPU unterbricht der Speichermanager diese Operationenzum frühestmöglichen Zeitpunkt und bearbeitet zunächst die Anfrage der CPU. Erfolgt einZugriff auf ein Objekt, dessen Verschiebung unterbrochen wurde, so werden sowohl Lese-als auch Schreiboperationen in Abhängigkeit des Fortschritts der Verschiebung, auf entwe-der die alte oder die neue Position des Objektes geleitet. Inkonsistente Zugriffe sind daherausgeschlossen. Alle anderen, dem Garbage Collector bereitgestellten Funktionen könnenin konstanter Zeit bearbeitet werden und sind nicht unterbrechbar.

Dauer der einzelnen Operationen

Während der Bearbeitung einer CPU- oder GC-Operation kann der Referenz-Manager kei-ne anderen Tätigkeiten ausführen. Obwohl die lang andauernden Operationen unterbrechbarimplementiert sind, resultiert dennoch eine gewisse Verzögerung, bis mit der Bearbeitungeiner anstehenden Anfrage der CPU begonnen werden kann. In Tabelle 4.1 sind die ma-ximal benötigten Zeiten aufgelistet. Die Variablen dwr, drd und dcopy sind abhängig vomverwendeten Speicher-Typ und geben die benötigte Anzahl Taktzyklen für eine Schreib-,Lese- oder Kopieroperation an. dcopy ist dabei abhängig von der vorgegebenen Blockgröße(siehe 4.1.3).

Für das Spartan-3-Starter-Kit (S3SK) ergeben sich die Werte dwr = 1 sowie drd = 2.Beträgt die vorgegebene Blockgröße lediglich k = 1 Worte, so ergibt sich dcopy = drd +dwr =3. Dieser Wert wächst mit steigender Blockgröße k linear an und für das Spartan-3-Starter-Kit gilt Allgemein:

dcopy(k) = drd +(k−1)+dwr +(k−1)dcopy(k) = 2k +1

Priorität der CPU-Operationen

Tritt sowohl eine Anfrage der CPU zum Speicherzugriff, als auch der Aufruf einer der demGarbage Collector bereitgestellten Operationen gleichzeitig auf, so wird stets die Anfrageder CPU prioritär behandelt.

4.2.3 Segment-Manager

Aufgabe

Der Segment-Manager bietet nur innerhalb des Speichermanagers Dienste an und über-nimmt die Verwaltung der einzelnen Segmente wie in 3.4 beschrieben. Die wichtigste Auf-gabe liegt im Austausch des Allokationssegmentes, sobald erkannt wird, dass das Anlegeneines Objektes mit maximaler Größe fehlschlagen würde. Außerdem werden dem GarbageCollector eine Reihe von Funktionen zur Verfügung gestellt.


Operation Wartezeit D DS3SK

RMCMD_REFDATA 2+drd 4RMCMD_GARBAGE 2+dwr bzw. 2+dwr +drd 3 bzw. 5RMCMD_MOVEREF 1+2dwr +dcopy 12a

RMCMD_FREEREF 2+dwr 3RMCMD_SCANREF 2+2drd 6op_nw_ref 2+drd +2dwr 6op_st_ref 2+drd 4op_st_ofs 1+drd 3op_st_wofs 1 1op_st_val 1+dwr 2

Tabelle 4.1: Maximale Dauer der nicht unterbrechbaren Teile der Operationen desReferenz-Managers. Der Speicher ist jeweils während der gesamten Dauer blo-ckiert.

aAusgehend von einer Blockgröße von 4 Worten ergibt sich dcopy = 9

GC Operationen

• gcseg_op_nwseg:Ein neues Zielsegment für die Garbage Collection wird bereitgestellt. Wird die in3.12.3 beschriebene Variation verwendet, so wird das angeforderte Segment auch indie im Zielsegment ausgewählte Gruppe einsortiert.

• gcctrl_op_grp_set:Es wird eine Gruppe von Segmenten ausgewählt, auf welche sich alle folgenden Aus-wahloperationen beziehen. Die Operation ist nur verfügbar, wenn die in 3.12.3 be-schriebene Variation verwendet wird.

• gcctrl_op_first:Das erste Segment der gewählten Gruppe wird ausgewählt und die zusätzlich abge-legten Daten seg_data werden zurückgegeben.

• gcctrl_op_next:Das nächste Segment der gewählten Gruppe wird ausgewählt sowie die zusätzlichabgelegten Daten seg_data zurückgegeben.

• gcctrl_op_setdata:Der zusätzlich verfügbare Segmentdatensatz seg_data wird gesetzt.

• gcctrl_op_load:Die in 3.4.2 beschriebenen Daten eines Segmentes (W, D, R und L) werden geladenund dem Garbage Collector bereitgestellt. Da die Informationen stets direkt aus demSpeicher geladen werden, stehen diese Informationen für das aktuelle Allokations-segment (4.2.4) nicht zur Verfügung.


• gcc_op_set_D, gcc_op_set_R, gcc_op_set_L:Die dem Segment zugeordneten Datensätze (D, R und L) werden geschrieben. Der W-Datensatz kann nur während der Reservierung von Speicher im Allokationssegmentoder beim Verschieben eines Objekts in das Zielsegment geändert werden.

• gcc_op_freeseg:Das Segment wird aus der aktuellen Gruppe ausgegliedert und der Liste der freienSegmente hinzugefügt. Dabei werden auch sämtliche, dem Segment zugeordnete Da-tensätze auf ihre Standardwerte zurückgesetzt.

• gcseg_op_wb:Die W- und L-Datensätze des GC-Zielsegments werden, abhängig von der aktuellgewählten Zielsegment-Gruppe, in den Speicher geschrieben. Dies ist insbesonderebei der Auswahl eines neuen Zielsegments wichtig.

• gcseg_op_ld_L:Abhängig von der aktuell gewählten Zielsegment-Gruppe, wird der L-Datensatz ausdem Speicher neu geladen.

Die Zielsegment-Gruppe wird direkt in der zugehörigen Komponente gesetzt. Das gewählteSegment wird dabei dem Segment-Manager bei Ausführung der Operation mitgeteilt.

Umsetzung

Wie in 3.4.2 und 3.12.3 beschrieben, werden die einzelnen Segmenteinträge in doppelt ver-ketteten Listen organisiert und die Köpfe dieser Listen einer Gruppe zugeordnet. Da insbe-sondere die Freigabe eines Segments auch das Umketten des zugehörigen Segmenteintrageserfordert und dazu zahlreiche, nicht unterbrechbare Einzeloperationen notwendig sind, wer-den diese Verkettungsinformationen in einem im Inneren des FPGAs befindlichen Speicher[xap05] abgelegt. Dadurch wird ein wesentlich schnellerer Zugriff möglich, ohne den ei-gentlichen Speicher unnötig lange zu blockieren. Neben den beiden Listenzeigern werdenaußerdem einige Bits an Zusatzinformationen (seg_data) hinterlegt (siehe 3.4.2), welcheebenfalls ohne Zugriff auf den eigentlichen Speicher verwendet werden können.

Sowohl auf die Verkettungsdaten und die Zusatzinformationen, als auch auf die Segmen-tinformationen im eigentlichen Speicher, ist ein Indexzugriff anhand der Nummer des Seg-ments möglich. Die Nummer eines Segments entspricht dabei direkt den höchstwertigstenBits der Segment-Anfangsadresse im Speicher.

Dauer der einzelnen Operationen

Auch die meisten der vom Segment-Manager durchgeführten Operationen benötigen einenatomaren Speicherzugriff, weshalb der Speicher für die gesamte Dauer der Operation blo-ckiert ist. In dieser Zeit können auch keine Anfragen der CPU durch den Referenz-Managerbearbeitet werden. In Tabelle 4.2 sind die maximal benötigten Zeiten aufgelistet.


Operation Wartezeit D DS3SK

gcseg_op_nwseg* 6(19) 6(19)gcseg_op_wb 2+2dwr 4gcseg_op_ld_L 2+drd 4gcc_op_set_D, R, L 2+dwr 3gcc_op_freeseg 13+2dwr 15gcctrl_op_grp_set* 1 1gcctrl_op_first* 6 6gcctrl_op_next* 7 7gcctrl_op_setdata* 6 6gcctrl_op_load 2+4drd 10Austausch des Allokationssegments 8+2dwr 10

Tabelle 4.2: Wartezeiten auf die Fertigstellung der einzelnen Operationen des Segment-Managers. Die mit *markierten Operationen benötigen keine Speicherzugriffe,weshalb die sonst notwendige Blockierung entfällt. Der in Klammern angege-bene Wert gilt, wenn die in 3.12.3 angegebene Variation verwendet wird.

4.2.4 Allokationssegment

Nach 3.4.3 wird stets ein Segment ausgewählt, in welchem alle neuen Objekte angelegtwerden. Damit das Anlegen eines neuen Objektes nicht durch zusätzliche Speicherzugriffeder Segment-Verwaltung verlangsamt wird, werden alle notwendigen Informationen durchdiese Komponente in Registern gehalten. Erst wenn das Allokationssegment durch ein an-deres ausgetautscht wird, werden die Werte dieser Register durch den Segmentmanager inden eigentlichen Speicher geschrieben. Die folgenden Daten sind dazu erforderlich:

• Nummer des Segments

• Anzahl bereits belegter Worte (W)

• Nummer des letzten hinzugefügten Referenzeintrages (L)

Beim Anlegen eines neuen Objektes wird aus der Nummer des Segments und der Zahl be-reits belegter Worte die Basisadresse des neuen Objektes gebildet, wozu die Konkatenationbeider Werte ausreicht. Die Nummer des zuletzt hinzugefügten Referenzeintrages dient zumAufbau der Liste der im Segment enthaltenen Objekte.

4.2.5 MMUCtrl

Da neben verschiedenen Statusinformationen auch gewisse Funktionen des Speichermana-gers und insbesondere des Garbage Collectors gesteuert und beeinflusst werden müssen, isteine Schnittstelle zur Kommunikation unerlässlich. In der SHAP-Mikroarchitektur (siehe2.1) wird dies durch den integrierten Geräte-Bus ermöglicht, wodurch der Speichermanageran diesen angekoppelt werden muss. Zu diesem Zweck dient die Komponente MMUCtrl.


Allgemeine Statusinformationen

Die folgenden Informationen werden bereitgestellt:

• Anzahl freier Referenzeinträge

• Anzahl der Referenzeinträge, die als Garbage markiert, jedoch noch nicht freigegebenworden.

• Anzahl freier Segmente

• aktuelle Konfiguration des Speichermanagers

Die aktuelle Konfiguration wird dargestellt durch ein 32 Bit Wort, dessen Aufbau in Ab-bildung 4.5 dargestellt ist. Die einzelnen Felder haben dabei die folgende Bedeutung:

• ADDR_SPACE:Adressbreite des verwendeten Speichers.

• SEG_BITS:Anzahl der notwendigen Adressbits zur Verwaltung der Segmente. Der Speicher istalso in 2SEG_BIT S Segmente unterteilt.

• UNUSABLE_SEGS:Enthält die Anzahl der nicht nutzbaren, ausgeblendeten Segmente am Anfang desSpeichers.

• SEG_OFFS:Gibt die Breite der Offset-Adresse in einem Segment an. Ein Segment umfasst also2SEG_OFFS Worte.

• REF_BITS:Die Breite der Adressen innerhalb der Tabelle der Referenzeinträge. Die Tabelle um-fasst also 2REF_BIT S Einträge, was gleichzeitig der maximalen Anzahl gleichzeitigexistierender Objekte entspricht.

• OBJ_OFFS:Die maximale Größe eines Objektes errechnet sich aus 2OBJ_OFFS.

• STATISTICS:Dieses Bit spielt für die Bewertung des Speichermanagers eine Rolle und ist gesetzt,wenn die Statistiken aktiviert worden (siehe 4.2.6), andernfalls ist es gelöscht.

• HW-GC:Dieses Bit ist gesetzt, wenn die Steuerung des Garbage Collectors durch einen inHardware implementierten Steuerautomaten erfolgt, andernfalls ist es gelöscht.


ADDR_SPACE SEG_BITS UNUSABLE_SEGS SEG_OFFS REF_BITS OBJ_OFFS STAT HW−GC

12611162631 21 0

Abbildung 4.5: Aufbau des Konfigurationswortes des Speichermanagers.

Setzen von Parametern

Wird der Garbage Collector durch einen in Hardware implementierten FSM gesteuert (siehe4.3.3), so können die folgenden Daten gesetzt bzw. abgerufen werden:

• Allgemein:– aktivieren bzw. deaktivieren des Collectors– Abfrage, ob der Collector aktiviert ist

• Auswahlfunktion:– Grenze für sWmin

– Grenze für sDmax

– Grenze für sRmax

• Trigger:– Setzen des Zeit-Triggers Ttrig

– Grenze anhand der Anzahl freier Segmente (Tre fmin)– Grenze anhand der Anzahl freier Referenzeinträge (Tsegmin)

Software-Steuerung des GCs

Wird der Garbage Collector durch ein Java-Programm gesteuert, so wird eine Schnittstellebereitgestellt, um die entsprechenden Operationen auszuführen bzw. bestimmte Daten oderZwischenergebnisse abzurufen. Die einzelnen elementaren Operationen werden durch dieKomponente gc_ctrl bereitgestellt, welche in 4.3.2 beschrieben ist.

4.2.6 MMUStat

Während der Entwicklung und insbesondere während der Auswertung (siehe Kapitel 5),ist das Aufnehmen verschiedener Statistik-Informationen unerlässlich. Die KomponenteMMUStat erlaubt zu diesem Zweck die Beobachtung verschiedener Signale, indem so-wohl die Zählung von Ereignissen als auch das Addieren von Registerinhalten zu internenZählern beim Auftreten eines Ereignisses möglich ist. Damit der Zustand der Zähler für allebeobachteten Signale zum gleichen Zeitpunkt abgerufen weden kann, werden nach Ablaufeiner konfigurierbaren Anzahl von Taktzyklen, die Werte aller Zähler in zusätzliche Regis-ter kopiert und daraufhin zurückgesetzt („Schnappschuss“). Sowohl die Zähler, als auchdie zusätzlichen Register, sind in den Komponenten statreg_counter zur Ereignis-zählung und statreg_accu zur Summation von Werten bei auftretenden Ereignissen,zusammengefasst. Die Struktur der Komponente ist in Abbildung 4.6 dargestellt.


Control word

...

Control FSM

statreg_counter

statreg_accu

snapshot

Output

USB

IO−Bus

Abbildung 4.6: Struktur der Komponente MMUStat.

Beobachtete Ereignisse

Die folgenden Informationen können abgerufen werden und stellen stets den Wert der Zäh-ler zum Zeitpunkt des letzten Schnappschusses dar:

• Anzahl Takt-Zyklen

• Anzahl op_nw_ref-, op_st_ref-, op_st_ofs-, op_st_wofs- und op_st_val-Operationen

• Summe von Worten in neu angelegten Referenzen

• Anzahl Warte-Zyklen zur Bearbeitung von op_nw_ref-, op_st_ref-, op_st_ofs-und op_st_val-Operationen

• Anzahl GC-Zyklen

• Anzahl verschobener Objekte und Summe der dabei verschobenen Worte

• Anzahl freigegebener Referenzeinträge und Summe des von den entsprechenden Ob-jekten belegten Speichers

• Anzahl freigegebener Segmente

• Anzahl benötigter GC-Zielsegmente

• Anzahl Taktzyklen in den einzelnen Phasen der Garbage Collection

• Anzahl freier Referenz- und Segmenteinträge

• Anzahl der Takt-Zyklen, in denen Referenz- bzw. Segment-Manager den Speicherbeanspruchen

4.3 Aufbau des Garbage Collectors 47

gc_listgc_ctrl

gc_algo

gc_swiface

MMUCtrl Segment manager

gc_microscan gc_stackscan gc_stackmon gc_heapscan

gc_fifogc_segs gc_collect

Reference manager

Abbildung 4.7: Die einzelnen Komponenten des Garbage Collectors.

Konfiguration und Ausgabe

Die Ausgabe der Zählerstände erfolgt unmittelbar nach einem Schnappschuss mittels der inAnhang A.1 beschriebenen Komponente. Da die Ausgabe der Werte Bandbreite und damitZeit beansprucht und nicht für jede Messung alle Zählerstände benötigt werden, könneneinzelne Zähler zur Ausgabe ausgewählt werden. Dazu ist jedem Zähler ein Bit in einem 32Bit umfassenden Wort zugeordnet (siehe auch A.2). Der Zählerstand wird nur ausgegeben,wenn das zugehörige Bit gesetzt ist.

Das Setzen des Konfigurationswortes zur Auswahl der Zähler sowie das Festlegen derZeitschranke zur Aufnahme der Schnappschüsse, erfolgt während des Betriebs mit Hilfedes integrierten Geräte-Busses (siehe 2.1) der SHAP-Mikroarchitektur.

4.3 Aufbau des Garbage Collectors

4.3.1 Struktur

Das in 3.2 beschriebene Konzept der Garbage Collection wurde mit Hilfe der durch denReferenz- und Segment-Manager bereitgestellten Operationen realisiert. Dabei wurden ein-zelne Komponenten geschaffen, welche jeweils über eine genau abgegrenzte Funktionalitätverfügen. In Abbildung 4.7 ist die Gesamtstruktur des Garbage Collectors dargestellt. Dabeiist auch erkennbar, welche Komponenten miteinander kommunizieren.

4.3.2 Komponenten

Im Folgenden werden die Funktionen der einzelnen Teilkomponenten des Garbage Collec-tors kurz erklärt und dabei auch implementierungsspezifische Besonderheiten dargestellt:

• Komponente gc_list:In dieser Komponente wird das in 2.2.5 beschriebene Tri-Color-Marking realisiert.


Bei der Überwachung des Stacks darf es nicht zu Verzögerungen kommen, da poten-tiell in jedem Taktzyklus eine neue, zu markierende Referenz vorliegen kann. Dieserfordert, dass die Komponente gc_list die durch die Stack-Überwachung einge-henden Referenzen garantiert in einem Takt bearbeiten können muss. Hingegen istdie Markierung der durch den Scan der Mikrocode-Variablen, des Stacks oder desHeaps gefundenen Referenzen weniger kritisch. Für diese Komponenten wird da-her ein Handshaking-Protokoll implementiert, welches die Fertigstellung der jewei-ligen Markierungsoperation mitteilt. Die Dauer dieser Operationen kann variieren,da durch die Stack-Überwachung gefundene Referenzen prioritär behandelt werdenmüssen.

Würden die Daten im normalen Speicher abgelegt werden, so würde ein Zugriff in nureinem Takt nicht garantiert werden können. Aus diesem Grund wird in den im Innerendes FPGAs vorhandenen BlockRAMs eine Markierungstabelle angelegt, was durchdie ohnehin begrenzte Anzahl der Referenzen möglich ist. Für jeden Referenzeintragwerden 2 Bit benötigt, wobei sich die folgende Zuordnung zu Farben ergibt: weiß(00), grau (10) und schwarz (-1). Beide Bits werden jeweils in getrenntenDual-Port-Speichern [xap05] abgelegt, weshalb mindestens zwei derartige Speicherbenötigt werden, in denen auf der Spartan-3-Architektur Markierungen für maximal214 Referenzeinträge vorhanden sind.

Neben den Operationen zur Markierung und zur Überwachung des Stacks, ist auchdas Auslesen der Markierung eines Eintrags sowie das Suchen eines grau markier-ten Eintrags möglich. Damit vor allem die Suche effektiver gestaltet werden kann,wurden BlockRAMs mit asymetrischer Portbreite gewählt. Während der jeweils zurMarkierung vorgesehene Port lediglich eine Breite von 1 Bit besitzt, hat der zum Su-chen und Lesen verwendete Port eine Breite von 32 Bit, wodurch sich insbesonderedas Suchen von grauen Objekten deutlich beschleunigen lässt. Außerdem wird dieAnzahl der grau markierten Objekte gezählt.

• Komponente gc_fifo:Ein einfaches FIFO konfigurierbarer Größe, welches zur Aufnahme der während desScans eines Objektes gefundenen Referenzen dient. Gegenwärtig ist die Größe auf 4Einträge begrenzt, weshalb von einer Umsetzung mit Hilfe der im FPGA vorhande-nen BlockRAMs verzichtet wurde und stattdessen LUT-RAM zum Einsatz kam.

• Komponente gc_collect:In dieser Komponente sind die Phasen zur Markierung und zur Freigabe eines Seg-ments zusammengefasst. Die Implementierung unterscheidet sich je nachdem, ob diein 3.12.1 beschriebene Variation verwendet wird, geringfügig.

Vor der Ausführung der Freigabephase wird der L-Datensatz des Zielsegments neugeladen, da sich dieser während der Markierungsphase verändert haben kann. Au-ßerdem werden nach Abschluss der Freigabe die Daten des Zielsegments zurückge-schrieben.

• Komponente gc_segs:


Diese Komponente beinhaltet die Daten (W und L) des momentan als Zielsegmentausgewählten Segments. Wird die in 3.12.3 beschriebene Variation verwendet, soexistiert für jede Gruppe ein separates Zielsegment. Jeweils eine Gruppe wird aus-gewählt, wodurch bestimmt wird, in welche Gruppe und damit in welche Generationein verschobenes Objekt eingeordnet wird.

Genügt der freie Platz innerhalb des Zielsegments nicht zur Aufnahme des zu ver-schiebenden Objekts, oder ist die maximale Anzahl an Objekten erreicht, so werdendie Daten des betroffenen Segments zurückgeschrieben und ein neues Zielsegmentausgewählt.

• Komponente gc_ctrl:Diese Komponente dient der Abstraktion der einzelnen, von verschiedenen Kom-ponenten angebotenen Operationen und stellt eine einheitliche Schnittstelle für dieKontrollkomponenten (siehe 4.3.3) zur Verfügung. Die einzelnen dabei angebotenenOperationen sind im Folgenden kurz aufgelistet:

– GCCMD_SCAN:Zunächst ist die Überwachung des Stacks deaktiviert und die Initialisierungwird durchgeführt, bei der alle Markierungen zurückgesetzt werden. Darauf-hin werden nacheinander die Phasen zum Scan der Microcode-Variablen, desStacks und des Heaps ausgeführt. Diese Operation ist beendet, wenn der Scandes Heaps abgeschlossen wurde.

– GCCMD_FIRST:Siehe gcctrl_op_first in 4.2.3. Das Allokationssegment kann dabei nichtgewählt werden und wird ggf. automatisch übersprungen.

– GCCMD_NEXT:Siehe gcctrl_op_next in 4.2.3. Das Allokationssegment kann dabei nichtgewählt werden und wird ggf. automatisch übersprungen.

– GCCMD_LOAD:Siehe gcctrl_op_load in 4.2.3.

– GCCMD_SETDATA:Siehe gcctrl_op_setdata in 4.2.3.

– GCCMD_MARK:Für das zuvor mittels GCCMD_FIRST bzw. GCCMD_NEXT ausgewählte Seg-ment wird die Markierungs-Phase ausgeführt.

– GCCMD_CLEAN:Für das zuvor mittels GCCMD_FIRST bzw. GCCMD_NEXT ausgewählte Seg-ment wird die Freigabe-Phase ausgeführt.

– GCCMD_SET_G_GROUP:Die Zielsegment-Gruppe wird gesetzt. Diese bestimmt, in welches Zielsegmentwährend der Bereinigung eines Segments ein verschobenes Objekt abgelegtwird.

– GCCMD_SET_S_GROUP:Siehe gcctrl_op_grp_seg in 4.2.3.


• Komponente gc_microscan:Diese Komponente übernimmt das Scannen der Mikrocode-Variablen während derPhase des Root-Scans (siehe 3.5.1), weshalb ein Zugriff auf das microcode-data-memory notwendig ist. Gefundene Referenzen werden der Komponente gc_listübergeben, wo die zugehörigen Objekte grau markiert werden. Der Scan wird durchgc_ctrl gestartet und die Beendingung entsprechend mitgeteilt.

• Komponente gc_stackscan:Diese Komponente realisiert den in 3.5.1 beschriebenen Scan des aus einzelnen Blö-cken aufgebauten Stacks. Alle gefundenen Referenzen werden der Komponente gc_listübergeben, wo die entsprechenden Objekte eine graue Markierung erhalten. Dazu be-nötigt die Komponente lesenden Zugriff auf den Speicher des Stacks. Der Scan wirddurch gc_ctrl gestartet und die Beendingung entsprechend mitgeteilt.

• Komponente gc_stackmonitor:Das in 3.5.3 dargestellte Verfahren zur Überwachung des Stacks wird von dieserKomponente realisiert. Dazu ist zum Einen ein Zugriff auf die Register NOS bzw.TOS des Stacks erforderlich, andererseits werden Änderungen der Register bei Push-bzw. Pop-Operationen durch den Stack mitgeteilt. Werden dabei Referenzen entdeckt,so werden diese der Komponente gc_list zur Markierung übergeben. Die Stack-Überwachung wird durch gc_ctrl aktiviert und bleibt für die gesamte Dauer desGarbage Collection Zyklus aktiv. Zu Beginn der Überwachung wird der momentaneWert der Register NOS bzw. TOS gesichert. Sind die gesicherten Daten Referen-zen, so werden diese, wenn keine Push- oder Pop-Operation stattfindet, ebenfalls derKomponente gc_list übergeben.

• Komponente gc_heapscan:Diese Komponente realisiert den eigentlichen Scan des Objektgraphen. Dazu wirdzunächst von gc_list das Handle eines grau markierten Objektes angefordert, wo-durch die Markierung automatisch auf schwarz geändert wird. Daraufhin wird mitHilfe des Referenz-Managers der Scan des Objekts veranlasst (RMCMD_SCANREF)und gc_list mitgeteilt, das in gc_fifo Handles auf zu markierende Objekte lie-gen können. Nachdem ein Objekt vollständig gscannt wurde, wird überprüft, ob dasFIFO bereits leer ist, d.h. alle gefundenen Referenzen markiert worden. Ist dies derFall, so erfolgt erneut die Anforderung eines Handles für ein grau markiertes Objekt.Sind keine weiteren grau markierten Objekte vorhanden, so ist die Traversierung desObjektgraphen beendet.

4.3.3 Steuerung des Garbage Collectors

Komponente gc_swiface

Die Komponente gc_swiface dient als Schnittstelle zur Steuerung des Garbage Collec-tors mit Hilfe eines Java-Programms. Die Kommunikation erfolgt dabei mit Hilfe der Kom-ponente MMUCtrl über den integrierten Geräte-Bus. Den durch gc_ctrl bereitgestell-ten Funktionen werden zu diesem Zweck Adressen zugeordnet, außerdem werden einige


Trigger

gc_algo

FSM Config

Select func

gc_ctrl status MMUCtrl

Abbildung 4.8: Aufbau der Komponente gc_algo.

Statusinformationen bereitgestellt. Sämtliche Operationen können durch eine Schreibope-ration auf die entsprechende Adresse gestartet werden, wobei gc_swiface für die Dauerder Abarbeitung einer Operation alle weiteren IO-Zugriffe blockiert. Da der Scheduler derSHAP-Mikroarchitektur im Falle einer Blockierung einen anderen Thread auswählt, wirdwährend der Wartezeit auf die Abarbeitung einer Operation keine Rechenzeit verschwendet.

Sowohl die Auswahlfunktion zur Segmentfreigabe, als auch das Triggering des GarbageCollectors, werden direkt in Software implementiert, wobei zunächst die gleichen Funktio-nen wie bei der Hardwaresteuerung verwendet werden. Auch die Voralterung von Segmen-ten (3.12.2) und die Unterstützung mehrerer Generationen durch die Bildung von Gruppen(3.12.3) ist in Software implementiert.

Komponente gc_algo

Diese Komponente realisiert die Steuerung des Garbage Collectors durch einen in Hardwa-re implementierten Steuerautomaten. Dabei werden ebenfalls die durch gc_ctrl bereitge-stellten Operationen aufgerufen. Die Struktur der Komponente ist dargestellt in Abbildung4.8. Die Parameter für die Auswahlfunktion sowie für Festsetzung des Trigger-Verhaltenskönnen über die Komponente MMUCtrl gesetzt werden. Die in 3.12.2 beschriebene Varia-tion der Strategie wird in dieser Komponente umgesetzt.

4.3.4 Varianten der Garbage Collection

Im Folgenden sind die verschiedenen implementierten Varianten der Garbage Collectionkurz aufgelistet:

• gc_hw_base:Die einfachste Implementierung der Garbage Collection nach dem in 3.2 beschriebe-nen Konzept.


• gc_hw_pm:Verwendung der Voralterung von Segmenten nach 3.12.2.

• gc_hw_fri:Verwendung der früheren Freigabe von Referenzeinträgen bereits während der Mar-kierungsphase nach 3.12.1.

• gc_hw_pm_fri:Kombination der Voralterung von Segmenten und der früheren Freigabe von Refe-renzeinträgen.

• gc_sw_fri:Verwendung des Software-Interfaces gc_swiface, wobei ebenfalls eine frühereFreigabe der Referenzeinträge erfolgt. Der in Java implementierte Algorithmus ver-wendet auch die in 3.12.3 beschriebene Variation, für welche insgesamt 4 Gruppenbereitgestellt werden.

Junge Segmente der Gruppe 0, d.h. Segmente die gerade erst Allokationssegment wa-ren, werden von diesem Algorithmus in jedem Zyklus behandelt. Alle überlebendenObjekte werden in ein Segment der Gruppe 1 verschoben, welches nur alle 16 Zyklenbetrachtet wird. Segmente der Gruppe 2 werden alle 128 und Segmente der Gruppe 3sogar nur alle 512 Zyklen von der Markierungsphase behandelt.

4.4 Syntheseergebnisse

In Tabelle 4.3 sind die Ergebnisse der Synthese der SHAP-Mikroarchitektur unter Verwen-dung der verschiedenen Garbage Collection Varianten (siehe 4.3.4) dargestellt. Die Synthe-se erfolgte für das Spartan-3-Starterkit mit XC3S-1000-FPGA. Dabei wurde die folgendeKonfiguration verwendet:

Größe des Stacks: 8 kByteGröße des Methoden-Caches: 2 kByteexterner Speicher: 1 MByte SRAMTiming-Constraint: 50 MHzAnzahl Referenz-Bits (REF_BITS): 11 (2048 Referenzeinträge)Anzahl Segment-Bits (SEG_BITS): 5 (32 Segmente)Größe des Objekt-Offsets (OFS_BITS): 12 (max. Objektgröße: 4096 Worte)Segmentgröße: 8192 WorteAlignment: 4-Wort-GrenzenMaximale Anzahl Referenzen pro Segment1: 128

Die festgesetzte Timing-Constraint von 50MHz konnte in jedem Fall eingehalten werden.Die vier vollständig in Hardware implementierten Varianten unterscheiden sich hinsicht-

lich der benötigten Ressourcen nur sehr geringfügig. Das zur Steuerung mittels Software

4.4 Syntheseergebnisse 53

Variante: gc_hw_base

gc_hw_pm

gc_hw_fri

gc_hw_pm_fri

gc_sw_fri

Flip-Flops 1697 (3139) 1697 1709 1709 17554 input LUTs 4337 (6588) 4345 4384 4392 4504- used as logic 4071 (6328) 4079 4115 4123 4235- used as route-through 180 (174) 180 183 183 183- used for Dual Port RAMs 86 (86) 86 86 86 86

Tabelle 4.3: Auflistung der Ergebnisse der Synthese. Die in Klammern angegebenen Werterepräsentieren exemplarisch die Ergebnisse bei aktiviertem MMUStat.

notwendige Interface sowie die Hinzunahme von Gruppen in der Segmentverwaltung, be-dingen≈ 2,7% mehr Flip-Flops und LUTs für die Variante gc_sw_fri. Das zur Auswer-tung erforderliche Module MMUStat vergrößert die Anzahl LUTs um ≈ 52%, die Anzahlbelegter Flip-Flops sogar um ≈ 85%.

5 Auswertung

5.1 Test-Applikationen

Zum Test des Garbage Collectors wurden drei Test-Applikationen ausgewählt, welche sichsehr stark in ihrem Verhalten bezüglich der Speichernutzung unterscheiden. Bei der Aus-wahl der Applikationen musste berücksichtigt werden, dass zum Zeitpunkt der Entwicklungauf dem verwendeten Prototypingboard, Ein- und Ausgaben nur bedingt und sehr langsammöglich waren. Eine weitere starke Einschränkung stellte der begrenzte Speicher von nur 1MByte oder 256 kWort dar, weshalb größere und vor allem speicherintensive Anwendun-gen, nicht ausgeführt werden können. Außerdem existierte keine Dateisystemimplementie-rung, weshalb auch derartige Anwendungen nicht in Frage kamen.

5.1.1 Caffeine Benchmark

Der bekannte Caffeine Benchmark1 bietet mehrere einzelne Tests an, welche den Heap sehrunterschiedlich nutzen. Während der String-Test sehr viele Objekte anlegt, in diesem Zu-sammenhang relativ viel Garbage produziert und damit auf die Bereitstellung von freiemSpeicher durch den Garbage Collector angewiesen ist, genügt der im System verfügbareSpeicher für die anderen Tests auch ohne Bereinigung. Allerdings muss berücksichtigt wer-den, dass der Caffeine Benchmark keine reale Applikation darstellt, sondern als Benchmarklediglich einige kleine Testalgorithmen abarbeitet.

5.1.2 Sudoku-Löser

Das Programm sudoku löst ein gegebenes Sudoku mittels Backtracking auf, wobei dergesamte Suchraum nach möglichen Lösungen durchsucht wird. Dabei werden alle gefunde-nen Belegungen gesichert, wofür jeweils ein Array entsprechender Größe angelegt werdenmuss. Da ein gewöhnliches Sudoku lediglich eine Lösung besitzt, wurde ausgehend von ei-nem beliebigen Rätsel einige Zahlen gestrichen und dieses schließlich nach allen Lösungendurchsucht.

Die Ausgabe der Ergebnisse erfolgt über die serielle Schnittstelle mittels eines separatenThreads. Nachdem eine Belegung ausgegeben wurde, wird die Referenz auf das zugehörigeArray gelöscht, wodurch dessen Speicher vom Garbage Collector freigegeben werden kann.Auch durch die Ausgabe werden zahlreiche Objekte angelegt, welche bereits nach kurzerZeit nicht mehr benötigt werden.

Der Java-Quellcode der einzelnen Klassen ist dargestellt im Anhang B.1.1.

1Caffeine Mark 3.0, ©1997 Pendragon Software Corporation

56 5 Auswertung

5.1.3 FScript

Für die Test-Applikation fscript wurde die Script-Sprache FScript [fsc] ausgewählt,welche als FScriptME auch für CLDC-Implementierungen geeignet ist. Während des Par-sens sowie während der Ausführung der einzelnen Operationen, werden sehr viele Objekteangelegt, welche zumeist nur eine relativ kurze Lebensdauer haben, weshalb diese Appli-kation besonders viel Garbage produziert (siehe Listing B.4 im Anhang B.1.2).

Auch in dem von der Applikation interpretierten Script muss mit Ausgaben besonderssparsam umgegangen werden. Der implementierte Algorithmus berechnet daher für allen ∈ N,2 ≤ n ≤ 25 zunächst das n-te Glied der Fibonacci-Folge ( f ib(n)). Für dieses wirddaraufhin die Collatz-Folge berechnet und die Anzahl der Schritte bis zum Erreichen desEndwertes von 1 gespeichert. Ausgegeben werden lediglich das aktuelle n sowie f ib(n) unddie Länge der berechneten Collatz-Folge. Der FScript-Quellcode des Skriptes ist dargesteltin Listing B.5.

5.2 Vergleich der unterschiedlichen GC-Varianten

Zum Vergleich der einzelnen Varianten der Garbage Collection wurden, unter Verwendungder in 5.1 beschriebenen Test-Applikationen, verschiedene Messungen durchgeführt. Dabeiwurde stets die gleiche Auswahlfunktion (siehe 3.7), mit den Parametern

SWmin = Ssegment −256

SDmax = 256

SRmax = 2047

verwendet. Dadurch wird ein Segment stets dann zur Freigabe ausgewählt, wenn mehr als256 Worte frei oder als Garbage markiert sind. Die Zahl der als Garbage markierten Objek-te im Segment wird nicht beachtet. Für die Auswertung wurden die in 4.3.4 beschriebenenimplementierten Varianten des Garbage Collectors mit dem in 4.4 angegebenen Setup ver-wendet.

5.2.1 Latenz

Zur Messung der durchschnittlichen Latenz der einzelnen Operationen wurde die Zeit ge-messen, die vom Anlegen der Operation bis zu deren Fertigstellung vergeht. Außerdem wur-den jeweils die längsten möglichen (worst-case) Zeiten sowie die Latenz ohne Garbage Col-lector bestimmt. Aus den ermittelten Ergebnissen der unterschiedlichen Test-Applikationenwurde schließlich das arithmetische Mittel gebildet. Diese Messungen wurden für die in4.3.4 beschriebenen Varianten der Garbage Collection durchgeführt und die Ergebnisse inAbbildung 5.1 dargestellt. Der Trigger des Garbage Collectors wurde für diese Messungenso eingestellt, dass der GC ständig läuft, was dem schlimmsten anzunehmenden Fall ent-spricht. Die Operation st_wofs ist im Diagramm nicht enthalten, da diese stets in genaueinem Taktzyklus bearbeitet werden kann, unabhängig von der verwendeten GC-Variation.

5.2 Vergleich der unterschiedlichen GC-Varianten 57

22

20

18

16

14

12

10

8

6

4

2

0st_valst_ofsst_refnw_ref

Late

ncy

[clo

ck c

ycle

s]

Operations

without GCworst case

hw_basehw_pmhw_fri

hw_pm_frisw_fri

Abbildung 5.1: Latenz der einzelnen Operationen bei Verwendung verschiedener Variantender GC.

Aus dem Diagramm wird deutlich, dass die durchschnittliche Latenz weit unter demworst-case Wert liegt, dieser also nur sehr selten eintritt. Ein Vergleich der unterschiedlichenVarianten zeigt, dass diese die Latenz gegenüber der einfachsten Variante gc_hw_basez.T. deutlich verbessern und in keinem Fall eine Verschlechterung hervorrufen. Das bessereErgebnis von gc_hw_pm gegenüber der einfachsten Variante wird erreicht, da das Ver-schieben von jungen Objekten hinausgezögert wird und, aufgrund der weak-generational-hypothesis, oftmals vermieden werden kann. Durch gc_hw_fri werden Referenzeinträ-ge eher freigegeben, wodurch die Begrenzung der Objekte pro Segment entfällt und einebessere Auslastung der Segmente erreicht wird. Dadurch werden weniger Segmente durchdie Freigabephase behandelt. Das gute Ergebnis von gc_sw_fri hat mehrere Ursachen:Zunächst verwendet der implementierte Algorithmus die in 3.12.3 beschriebene Variation,weshalb Segmente mit älteren Objekten zumeist von der Garbage Collection nicht beachtetwerden. Außerdem müssen bei der Software-Steuerung zusätzliche Pausen zwischen deneinzelnen Phasen berücksichtigt werden, welche vor allem durch die Auswahl des laufen-den Threads (Scheduling) entstehen. Da dadurch die Operationen des Garbage Collectorsseltener aufgerufen werden, ist auch die entstehende Latenz der CPU-Operationen geringer.

58 5 Auswertung

1

10

100

1000

10000

100000

SumCleanMarkHeapScanStackScanMicScanInit

Dur

atio

n [c

lock

cyc

les]

Phases

hw_basehw_pm

hw_frihw_pm_fri

sw_fri

Abbildung 5.2: Dauer der einzelnen GC-Zyklen bei Verwendung verscheidener Variationenim logarithmischen Maßstab.

5.2.2 GC-Zyklendauer

Zum weiteren Vergleich der einzelnen Varianten wurde die durchschnittliche Dauer dereinzelnen Phasen sowie die durchschnittliche Gesamtdauer eines GC-Zyklus bestimmt. Dadiese Werte sehr stark vom Verhalten der jeweiligen Applikation abhängen (z.B. Anzahl derObjekte, Größe des belegten Speichers), dienen die Ergebnisse lediglich als Anhaltspunktzum Vergleich der einzelnen Varianten. Auch hier wurde jeweils das arithmetische Mittelaus den Ergebnissen aller drei Test-Applikationen gebildet sowie der Trigger abgeschaltet,wodurch der Garbage Collector ständig läuft. Die Ergebnisse sind in Abbildung 5.2 darge-stellt, wobei ein logarithmischer Maßstab verwendet wird, wodurch die Größenordnung derDauer der einzelnen Phasen gut abgelesen werden kann.

Die Dauer der Scan-Phasen unterscheidet sich zwischen den einzelnen Varianten derGarbage Collection nicht, da stets die gleichen Test-Applikationen verwendet worden. Ge-ringe Schwankungen entstehen lediglich durch das veränderte Zeitverhalten. Alle in 3.12beschriebenen Variationen verändern ausschließlich die Zeiten der Markierungs- bzw. Frei-gabephase sowie die Gesamtzeit eines GC-Zyklus.

Aus dem Diagramm wird deutlich, dass bereits die Verwendung von gc_hw_pm eineVerkürzung der Freigabephase um≈ 2 bewirkt. Die Varianten gc_hw_fri, gc_hw_pm_friund gc_sw_fri verkürzen die durchschnittliche Dauer dieser Phase um mehr als 2 Grö-ßenordnungen, was vor allem durch die frühere Freigabe der Referenzeinträge und die damit

5.2 Vergleich der unterschiedlichen GC-Varianten 59

verbundene bessere Auslastung der Segmente erreicht wird.Die Verkürzung der durchschnittlichen Dauer der Markierungsphase um mehr als eine

Größenordnung durch die Variante gc_sw_fri, entsteht durch die Verwendung der in3.12.3 beschriebenen Gruppen von Segmenten, wodurch Segmente mit älteren Objektenwesentlich seltener behandelt werden.

Die Gesamtdauer eines Garbage Collection Zyklus ergibt sich im Allgemeinen aus derSumme der Dauer der einzelnen Phasen. Bei der Variante gc_sw_fri ist dies jedoch nichtder Fall, da zwischen den einzelnen Phasen Pausen entstehen (vgl. 5.2.1).

5.2.3 Belegte Ressourcen

Die Freigabe nicht benötigter Speicherbereiche und Referenzeinträge ist im Folgenden fürdie Test-Applikationen sudoku und fscript angegeben. Dabei wurde der Trigger soeingestellt, dass ein neuer GC-Zyklus stets dann gestartet wird, wenn mehr als 20 Segmentebelegt sind, was einer Auslastung des Speichers von ≈ 65% entspricht.

Sudoku

In Abbildung 5.3 ist der Verlauf der Anzahl der belegten Referenzeinträge und Segmente fürverschiedene Varianten der Garbage Collection dargestellt. Im linken Teil des Diagrammskonnten von der Test-Applikation noch keine Lösungen gefunden und dementsprechendkeine Objekte angelegt werden. Das Diagramm stellt lediglich einen Ausschnitt aus demAblauf der gesamten Test-Applikation dar, da sich die Verläufe nach dem gleichen Musterweiter fortsetzen und das Diagramm nur schwerer lesbar werden würde.

Deutlich zu erkennen ist, dass der Garbage Collector durch den Trigger sofort bei errei-chen des Schwellwertes gestartet wird und sich die Anzahl belegter Ressourcen daraufhinreduziert. Aus dem Anstieg der Geraden im Diagramm kann außerdem bestimmt werden,das etwa alle 43000 Takte eine Allokation durchgeführt wird.

Während sich gc_hw_fri und gc_sw_fr kaum unterscheiden, wird die schlechtereAuslastung der Segmente durch die Begrenzung der Anzahl der Objekte (siehe 3.6) beigc_hw_base besonders deutlich. So sind selbst unmittelbar nach der Freigabe wesentlichmehr Segmente benutzt, als bei den beiden anderen Varianten, weshalb der Schwellwertbereits eher erreicht und der GC dementsprechend häufiger gestartet wird.

FScript

Abbildung 5.4 zeigt den Verlauf der Anzahl belegter Ressourcen für die Test-Applikationfscript. Im Gegensatz zu sudoku werden wesentlich mehr Objekte angelegt und eskann ermittelt werden, das etwa alle 3700 Takte eine Allokation durchgeführt wird. Die Be-grenzung der Anzahl der Objekte in einem Segment für gc_hw_base wird hier nochein-mal besonders deutlich.

60 5 Auswertung

5.2.4 Verschobene Objekte

Zur Bestimmung der Anzahl verschobener Objekte bei den verschiedenen Varianten derGC wurde erneut der Trigger abgeschaltet und der Garbage Collector damit in dauerhaftenBetrieb versetzt. Die Abbildung 5.5 zeigt den Verlauf der Anzahl verschobener Objekte fürdie Test-Applikation fscript.

Deutlich zu erkennen ist, dass sich die Zahl verschobener Objekte durch Verwendung vongc_hw_pm um≈ 1

3 gegenüber gc_hw_base reduziert, was die Verkürzung der Freigabe-phase in 5.2.2 nocheinmal bestätigt. Wird hingegen die Variante gc_hw_fri verwendet,so erfolgt eine deutliche Reduzierung der Anzahl verschobener Objekte, was erneut durchdie bessere Auslastung der Segmente begründet ist.

5.3 Schlussfolgerungen

Alle angegebenen Varianten kommen ohne eine Unterbrechungen der CPU aus und da stetsdie in Hardware implementierten Grundoperationen verwendet werden, können in jedemFall Garantien bezüglich der maximalen Latenz der CPU-Operationen gegeben werden.

Durch die gewählte Implementierung der Voralterung junger Segmente und die damitverbundene Verzögerung um einen vollständigen Garbage Collection Zyklus, kann das Ver-fahren nur dann sinnvoll eingesetzt werden, wenn der Garbage Collector sehr oft oder sogarständig läuft. Durch Verwendung der früheren Freigabe der Referenzeinträge (gc_hw_fri)erfolgt eine drastische Verbesserung der Segmentauslastung, wodurch wesentlich wenigerSegmente zur Freigabe ausgewählt werden. Bei der Kombination der früheren Freigabevon Referenzeinträgen mit der Voralterung junger Segmente (gc_hw_pm_fri), konntebei den verwendeten Test-Applikationen jedoch keine weitere Verbesserung erzielt werden.Von den implementierten Varianten in Hardware empfiehlt sich daher gc_hw_fri beson-ders.

Erfolgt die Steuerung des Garbage Collectors durch ein Java Programm, so können kom-pliziertere Algorithmen leichter implementiert werden. Obwohl durch das Scheduling zwi-schen den einzelnen aufgerufenen Operationen der Garbage Collection Pausen entstehen,welche den GC-Zyklus verlängern, konnte durch die Einführung von Gruppen in der Seg-mentverwaltung und der dadurch zumeist möglichen Begrenzung der Markierungs- undFreigabephase auf jüngere Segmente, die durchschnittliche Dauer dieser Phasen deutlichverkürzt werden. Insgesamt ist die durch Software gesteuerte Variante nicht wesentlichlangsamer als die reinen Hardware-Implementierungen.

5.3 Schlussfolgerungen 61

0

5

10

15

20

25

30

0 1e+08 2e+08 3e+08 4e+08 5e+08 6e+08

used

seg

men

ts

clock cycles

hw_base (sudoku)hw_fri (sudoku)sw_fri (sudoku)

0

500

1000

1500

2000

0 1e+08 2e+08 3e+08 4e+08 5e+08 6e+08

used

ref

eren

ces

clock cycles

hw_base (sudoku)hw_fri (sudoku)sw_fri (sudoku)

(Trigger bei 21 belegten Segmenten)

Abbildung 5.3: Belegte Segmente und Referenzeinträge bei der Test-Applikation sudokumit verschiedenen Varianten der GC.

62 5 Auswertung

0

5

10

15

20

25

30

0 2e+07 4e+07 6e+07 8e+07 1e+08 1.2e+08 1.4e+08

used

seg

men

ts

clock cycles

hw_base (fscript)hw_fri (fscript)sw_fri (fscript)

0

500

1000

1500

2000

0 2e+07 4e+07 6e+07 8e+07 1e+08 1.2e+08 1.4e+08

used

ref

eren

ces

clock cycles

hw_base (fscript)hw_fri (fscript)sw_fri (fscript)

(Trigger bei 21 belegten Segmenten)

Abbildung 5.4: Belegte Segmente und Referenzeinträge bei der Test-Applikationfscript mit verschiedenen Varianten der GC.

5.3 Schlussfolgerungen 63

0

10

20

30

40

50

60

0 5e+06 1e+07 1.5e+07 2e+07

mov

ed r

efer

ence

s

clock cycles

hw_base (fscript)hw_pm (fscript)

hw_fri (fscript)

Abbildung 5.5: Vergleich der Anzahl verschobener Objekte durch verschiedene Variantender GC.

6 Zusammenfassung

In dieser Arbeit wurde ein Garbage Collector für die SHAP-Mikroarchitektur entworfenund implementiert, der parallel zur eigentlichen Applikation arbeitet. Alle wesentlichenBestandteile des Collectors wurden direkt in Hardware implementiert und können sowohldurch einen ebenfalls in Hardware realisierten Steuerautomaten, oder durch ein in Java im-plementiertes Programm gesteuert werden, welches in einem separaten Thread abläuft.

Während der auf auf der Traversierung des Objektgraphen basierente Collector Referen-zen auf dem Stack und in den Mikrocode-Variablen sicher erkennen kann, wird auf demHeap ein konservativer Ansatz mit Hilfe einer Signatur verwendet. Dadurch können jedochObjekte fälschlich als referenziert erkannt werden, weshalb im ungünstigsten Fall nicht ge-nügend Speicher freigegeben werden könnte. An dieser Stelle gibt es Bedarf für Optimie-rungen, da ein konservativer Ansatz zur Einhaltung von Echtzeitbedingungen ungeeignetist.

Mit ausgewählten Test-Applikationen wurde die korrekte Arbeitsweise des Collectorsnachgewiesen sowie dessen Effizienz und Einfluss auf die eigentliche Applikation anhandverschiedener gemessener Größen ermittelt. Dazu wurde der SHAP-Mikroarchitektur aucheine USB-Schnittstelle hinzugefügt.

Für alle der CPU angebotenen Operationen, insbesondere für das Anlegen neuer Objekte,können Garantien bezüglich der maximalen Latenz gegeben werden. Im Mittel liegt dietatsächlich erzielte Latenz jedoch weit unter dem maximal möglichen Wert.

Ausgehend von einer ausgewählten Grundstrategie wurden verschiedene Variationen um-gesetzt und miteinander verglichen. Außerdem erfolgte ein Vergleich von Software- undHardwaresteuerung. Die frühere Freigabe der Referenzeinträge erwies sich dabei als sinn-voll, da durch die wesentlich bessere Auslastung der Segmente, deutlich weniger Objekteverschoben werden. Die Dauer eines Garbage Collection Zyklus lässt sich dadurch starkreduzieren.

Eine weitere Optimierung der Grundstrategie könnte in der parallelen Abarbeitung dereinzelnen Scan-Phasen bestehen, wodurch eine weitere Verkürzung der Zyklenzeit erzieltwerden kann. Durch das sofortige Verschieben von Objekten aus vorher ausgewählten Seg-menten während der Phase des Heap-Scans, kann nochmals eine Verkürzung der Zyklenzeiterreicht und außerdem Speicherzugriffe eingespart werden. Den größten Anteil an der Ge-samtdauer eines Garbage Collection Zyklus hat die Phase des Heap-Scans, die gegenwärtigden gesamten belegten Speicher aller erreichbaren Objekte nach Referenzen durchsucht.Wird der konservative Ansatz durch einen exakten ausgetauscht, so sollte auch die Dauerdieser Phase verkürzt werden.

A Debug Schnittstelle

A.1 USB-Komponente

Die SHAP-Mikroarchitektur sieht zur Ausgabe lediglich die serielle Schnittstelle vor, wel-che eine maximale Übertragungsrate von 115 kBaud realisiert, was zur Ausgabe der Statistik-Informationen jedoch nicht ausreicht, da jeder der auszugebenden Zählerstände 4 Byte um-fasst und somit zu wenige Messwerte ausgegeben werden könnten.

Das in [Desi02] beschriebene USB-Interface ermöglicht eine Übertragungsrate von biszu 486kByte pro Sekunde und kann durch ein paralleles Interface relativ problemlos an-gesteuert werden. Alle notwendigen Komponenten befinden sich bereits auf dem Modul,weshalb nur eine geringe externe Beschaltung erforderlich ist. Für die Ausgabe der Statistik-Informationen wurde ein solches Modul verwendet. Die Anschlussbelegung sowie die Zu-ordnung zu den IO-Pins des Spartan-3-FPGAs ist in Tabelle A.1 dargestellt, die Schnittstelledes in VHDL erstellten Moduls zeigt Abbildung A.1.

Das Modul wird mit einem gewöhnlichen USB-Kabel mit dem Rechner verbunden, aufwelchem die Aufzeichnung der Daten vollzogen werden soll. Der für die Ansteuerung desModuls benötigte Treiber ist im aktuellen Linux-Kernel bereits enthalten und legt einen sog.virtuellen COM-Port an, von dem die Daten schließlich gelesen werden können.

A.2 Auswahl der auszugebenden Zählerstände

Jedem der Zähler innerhalb der Komponente MMUStat ist ein Bit in einem 32 Bit umfas-senden Wort zugeordnet (siehe 4.2.6). Die Zuordnung der Zählerstände zu den Wertigkeitendes jeweiligen Bits ist Dargestellt in Tabelle A.2.

Durch Addition der jeweiligen Wertigkeiten können beliebige Kombinationen von aus-zugebenden Zählerständen realisiert werden. Da dies jedoch manuell relativ aufwändig ist,wurde mit Hilfe eines Shell-Scripts und des Programms xdialog eine einfache Benutzerober-fläche geschaffen (siehe Abb. A.2), welche die Auswahl der auszugebenden Zählerständeauf grafischem Wege erlaubt und das entsprechende Konfigurationswort in hexadezimalerForm ausgibt.

A.3 Aufbereitung zur Ausgabe

Die durch MMUStat gesendeten Daten sind lediglich 32 Bit Werte, welche zur Ausgabeaufbereitet werden müssen. Dies geschieht mit Hilfe des in B.2 beschriebenen Perl-Scripts,welchem ebenfalls durch das Konfigurationswort mitgeteilt werden muss, welche Informa-tionen im Datenstrom enthalten sind. Durch Eingabe von

68 A Debug Schnittstelle

Signal Pin am A2-Connector IO-Pin am FPGARSTO 31 A12SND 29 B11D0 27 B10D1 25 A8D2 23 A7D3 21 B6D4 19 B5D5 17 B4D6 15 D10D7 13 D8RD 11 D7WR 9 E7TXE 7 D6RXE 5 D5VCC-IO 3 -GND 1 -

Tabelle A.1: Anschlussbelegung des USB-Moduls für das Spartan-3-Starterkit und Zuord-nung zu den IO-Pins des FPGAs.

$ cat /dev/ttyUSB0 | ./gc_expand.pl 0x1e001

werden die Daten vom virtuellen COM-Port gelesen und an das Perl-Script übergeben,welches den Datenstrom anhand des angegebenen Konfigurationswortes aufbereitet undausgibt.

A.3 Aufbereitung zur Ausgabe 69

clkreset

send_opsend_data

rec_opflush_op

usb_rxfusb_txe

usb_rsto

ready

send_rdysend_donesend_failrec_avlrec_donerec_failrec_dataflush_done

usb_rdyusb_wrusb_send

usb_data

USB

Abbildung A.1: Darstellung der Schnittstelle der in VHDL implementierten Komponentezur Ansteuerung des DLP-245M USB-Moduls.

Abbildung A.2: Darstellung der mit Hilfe von xdialog realisierten grafischen Benutzerober-fläche zur Auswahl der auszugebenden Zählerstände.

70 A Debug Schnittstelle

Zählerstand Bit WertigkeitTaktzyklen 0 0x1Anzahl op_nw_ref’s 1 0x2Summe reservierter Worte 2 0x4Anzahl op_st_ref’s 3 0x8Anzahl op_st_ofs’s 4 0x10Anzahl op_st_wofs’s 5 0x20Anzahl op_st_val’s 6 0x40Warte-Zyklen op_nw_ref 7 0x80Warte-Zyklen op_st_ref 8 0x100Warte-Zyklen op_st_ofs 9 0x200Warte-Zyklen op_st_val 10 0x400Warte-Zyklen während GC-Operation (in refman) 11 0x800Anzahl GC-Zyklen 12 0x1000Anzahl verschobener Objekte 13 0x2000Anzahl freigegebener Objekte 14 0x4000Anzahl verschobener Worte 15 0x8000Anzahl freigegebener Worte 16 0x10000Anzahl freigegebener Segmente 17 0x20000Anzahl benötigter Zielsegmente 18 0x40000Summe der Takte für Init-Phase 19 0x80000Summe der Takte für zum scannen der Mikrocode-Variablen 20 0x100000Summe der Takte für Stack-Scan 21 0x200000Summe der Takte für Heap-Scan 22 0x400000Summe der Takte in Markierungsphase 23 0x800000Summe der Takte in Freigabephase 24 0x1000000Anzahl freier Referenzeinträge 25 0x2000000Anzahl freier Segmente 26 0x4000000

Tabelle A.2: Zuordnung der abrufbaren Zählerstände zu einem Bit im Konfigurationswort.

B Quelltexte

B.1 Test-Applikationen

B.1.1 Sudoku-Löser

/ ** S i mp le Sudoku−S o l v e r* P e t e r R e i c h e l < p e t e r @ p e t e r r e i c h e l . i n f o >* /

5package i t e . t e s t . sudoku ;import j a v a . u t i l . Ve c to r ;import j a v a . i o . * ;import i t e . s y s . MMUStat ;

10 import i t e . s y s . MMUCtrl ;import i t e . s y s .GC;import i t e . s y s . BaseGC ;import i t e . s y s .HWGC;import i t e . s y s . SimpleGC ;

15 import i t e . s y s . AdvGC ;import i t e . s y s . N o t A v a i l a b l e E x c e p t i o n ;

p u b l i c c l a s s Sudoku {/ / S t a r t and i n i t i a l i z e t h e HW GC

20 p u b l i c s t a t i c boolean initHWGC ( ) {HWGC gc ;t r y { gc = new HWGC( ) ; } / / new SimpleGC ( ) ; }catch ( N o t A v a i l a b l e E x c e p t i o n e ) {

System . e r r . p r i n t l n ( e ) ;25 re turn f a l s e ;

}

/ / gc . s e t _ t i m e _ t r i g g e r ( 0 ) ; / / n e v e r/ / gc . s e t _ r t r i g _ l e v e l ( 1 0 0 ) ; / /100% => n e v e r t r i g g e r

30 / / gc . s e t _ s t r i g _ l e v e l ( 6 5 ) ; / / t r i g g e r a t 65% u t i l i z a t i o ngc . s e t _ s e l _ f n ( 0 , MMUCtrl . ge tRe fCoun t ()−1 , MMUCtrl . g e t S e g S i z e ()−256 , 2 5 6 ) ;

/ / gc . s e t _ s e l _ f n ( 0 , 128 , MMUCtrl . g e t S e g S i z e ()−256 , 2 5 6 ) ;

35 / / a l l w a y s run GC ( no t r i g g e r )gc . s e t _ t i m e _ t r i g g e r ( 0 ) ;gc . s e t _ r e f _ t r i g g e r ( i t e . s y s . MMUCtrl . ge tRe fCoun t ( ) −1 ) ;gc . s e t _ s e g _ t r i g g e r ( 0 ) ; / / 10

40 GC. setGC ( gc ) ;re turn true ;

}

/ / S t a r t t h e s i m p l e SW−GC45 p u b l i c s t a t i c boolean initSWGC ( ) {

BaseGC gc ;t r y { gc = new AdvGC ( ) ; }catch ( N o t A v a i l a b l e E x c e p t i o n e ) {


}GC. setGC ( gc ) ;re turn true ;

}55

/ / t r y t o s t a r t HW or SW−GCp u b l i c s t a t i c boolean i n i tGC ( ) {

System . o u t . p r i n t l n ( " I n i t i a l i z i n g GC . . . " ) ;boolean r e s = initHWGC ( ) ;

60 i f ( ! r e s ) {System . o u t . p r i n t l n ( " T r y i ng SW GC . . . " ) ;r e s = initSWGC ( ) ;

}i f ( ! r e s ) {

72 B Quelltexte

65 System . o u t . p r i n t l n ( " S t a r t o f GC f a i l e d ! " ) ;re turn f a l s e ;

}i f ( !GC. g e t S t a t u s ( ) ) {

System . e r r . p r i n t l n ( "GC n o t s t a r t e d ! " ) ;70 re turn f a l s e ;

}e l s e {

System . o u t . p r i n t l n ( "GC s t a r t e d ! " ) ;re turn true ;

75 }}

p u b l i c s t a t i c vo id i n i t T r a c i n g ( ) {i t e . s y s . MMUStat . doSnapsho t ( ) ;

80/ / s e t gc−t r i g g e r−c o n d i t i o n ( a l l w a y s run )i t e . s y s . MMUStat . se tTraceMode (0 x f f b ) ;i t e . s y s . MMUStat . s e t T r a c e C n t (100000−1) ;i t e . s y s . MMUStat . s e t T r a c e E n a b l e d ( t rue ) ;

85 }

p u b l i c s t a t i c vo id main ( S t r i n g [ ] a rgv ) {main ( ) ;

}90

p u b l i c s t a t i c vo id main ( ) {/ / s t a r t gci f ( ! i n i tG C ( ) ) re turn ;

95 / / s t a r t t r a c i n gi n i t T r a c i n g ( ) ;

/ / g e n e r a t e and i n i t i a l i z e sudoku f i e l d100

SudokuFeld f = new SudokuFeld ( 3 ) ;

/ / Fe ld 2 (128 l o e s u n g e n )105 f . s e t ( 6 , 0 , 1 ) ;

f . s e t ( 3 , 0 , 2 ) ;f . s e t ( 2 , 0 , 4 ) ;f . s e t ( 8 , 0 , 5 ) ;f . s e t ( 7 , 2 , 3 ) ;

110 f . s e t ( 4 , 2 , 6 ) ;f . s e t ( 1 , 2 , 8 ) ;f . s e t ( 9 , 3 , 0 ) ;f . s e t ( 6 , 3 , 5 ) ;f . s e t ( 3 , 3 , 6 ) ;

115 / / f . s e t ( 6 , 4 , 0 ) ; / / d e l e t e df . s e t ( 2 , 4 , 1 ) ;f . s e t ( 7 , 4 , 4 ) ;f . s e t ( 4 , 4 , 8 ) ;f . s e t ( 8 , 5 , 2 ) ;

120 f . s e t ( 1 , 5 , 3 ) ;f . s e t ( 7 , 5 , 8 ) ;f . s e t ( 8 , 6 , 0 ) ;f . s e t ( 9 , 6 , 2 ) ;f . s e t ( 1 , 6 , 5 ) ;

125 f . s e t ( 9 , 8 , 3 ) ;/ / f . s e t ( 6 , 8 , 4 ) ; / / d e l e t e d

f . s e t ( 2 , 8 , 6 ) ;f . s e t ( 4 , 8 , 7 ) ;

130 / / S t a r t p r i n t e r i n s e p a r a t t h r e a dV ec to r s o l u t i o n s = new Ve c to r ( ) ;S u d o k u P r i n t sp = new S u d o k u P r i n t ( s o l u t i o n s , f . l e n g t h ( ) ) ;sp . s t a r t ( ) ;

135 / / s o l v e f i e l df . s o l v e ( s o l u t i o n s ) ;

synchronized ( s o l u t i o n s ) {s o l u t i o n s . n o t i f y ( ) ;

140 }

/ / q u i t p r i n t e r t h r e a dsp . done ( ) ;

145 t r y { sp . j o i n ( ) ; }ca tch ( I n t e r r u p t e d E x c e p t i o n e ) {}

System . o u t . p r i n t l n ( " Done ! " ) ;

B.1 Test-Applikationen 73

System . o u t . p r i n t l n ( " Coun te r " + f . s o l C n t ( ) ) ;150

GC. setGC ( n u l l ) ;}

}

Listing B.1: Ein einfaches Programm zum Lösen der beliebten Sudoku-Räsel.

/ ** D a r s t e l l u n g des Sudoku−S p i e l f e l d e s* P e t e r R e i c h e l < p e t e r @ p e t e r r e i c h e l . i n f o >* /

5package i t e . t e s t . sudoku ;import j a v a . u t i l . Ve c to r ;import j a v a . i o . * ;

10p u b l i c c l a s s SudokuFeld {

p r i v a t e i n t mCount ;p r i v a t e i n t [ ] mData ;p r i v a t e i n t mK;

15 p r i v a t e i n t mSize ;p r i v a t e i n t mLength ;p r i v a t e i n t mSol ;

p u b l i c SudokuFeld ( i n t s i z e ) {20 mK = s i z e ;

mLength = mK * mK;mSize = mLength * mLength ;mData = new i n t [ mSize ] ;mCount = 0 ;

25 mSol = 0 ;}

p u b l i c i n t l e n g t h ( ) {re turn mLength ;

30 }

p u b l i c i n t s o l C n t ( ) {re turn mSol ;

}35

/ / c r e a t e a copy o f t h e data− f i e l dp u b l i c i n t [ ] c o p y F i e l d ( ) {

i n t [ ] f = new i n t [ mSize ] ;System . a r r a y c o p y ( mData , 0 , f , 0 , mSize ) ;

40 re turn f ;}

p u b l i c boolean s e t ( i n t va l , i n t row , i n t c o l ) {i f ( mData [ mLength*row+ c o l ] != 0 ) {

45 mData [ mLength*row+ c o l ] = 0 ;mCount−−;

}

i f ( v a l == 0) re turn true ;50

i f ( check_row ( va l , row ) && c h e c k _ c o l ( va l , c o l ) && c h e c k _ f i e l d ( va l , row , c o l ) ) {mData [ mLength*row+ c o l ] = v a l ;mCount ++;re turn true ;

55 }e l s e re turn f a l s e ;

}

p u b l i c i n t g e t ( i n t row , i n t c o l ) {60 re turn mData [ mLength*row+ c o l ] ;

}

p u b l i c boolean i sEmpty ( i n t row , i n t c o l ) {re turn mData [ mLength*row+ c o l ] == 0 ? t rue : f a l s e ;

65 }

p u b l i c boolean i s S o l v e d ( ) {re turn mCount == mSize ? t rue : f a l s e ;

}70

p r i v a t e boolean check_row ( i n t va l , i n t row ) {f o r ( i n t i = 0 ; i < mLength ; i ++) {

i f ( mData [ mLength*row+ i ] == v a l ) re turn f a l s e ;

74 B Quelltexte

}75 re turn true ;

}

p r i v a t e boolean c h e c k _ c o l ( i n t va l , i n t c o l ) {f o r ( i n t i = 0 ; i < mLength ; i ++) {

80 i f ( mData [ mLength* i + c o l ] == v a l ) re turn f a l s e ;}re turn true ;

}

85 p r i v a t e boolean c h e c k _ f i e l d ( i n t va l , i n t row , i n t c o l ) {i n t b a s e _ c o l = mK * ( c o l / mK) ;i n t base_row = mK * ( row / mK) ;

f o r ( i n t c = b a s e _ c o l ; c < b a s e _ c o l +mK; c ++) {90 f o r ( i n t r = base_row ; r < base_row +mK; r ++) {

i f ( mData [ mLength* r +c ] == v a l ) re turn f a l s e ;}

}re turn true ;

95 }

p u b l i c vo id s o l v e ( Ve c t o r s o l u t i o n s ) {i f ( i s S o l v e d ( ) ) {

synchronized ( s o l u t i o n s ) {100 s o l u t i o n s . addElement ( c o p y F i e l d ( ) ) ;

mSol ++;s o l u t i o n s . n o t i f y ( ) ;

}re turn ;

105 }i n t row = 0 , c o l = 0 ;boolean done = f a l s e ;whi le ( ! done && row < mLength ) {

whi le ( ! done && c o l < mLength ) {110 i f ( i sEmpty ( row , c o l ) ) done = t rue ;

e l s e c o l ++;}i f ( ! done ) {

c o l = 0 ;115 row ++;

}}

i f ( done ) {120 f o r ( i n t i = 1 ; i <= mLength ; i ++) {

i f ( s e t ( i , row , c o l ) ) s o l v e ( s o l u t i o n s ) ;}s e t ( 0 , row , c o l ) ;

}125 }

}

Listing B.2: Klasse zur Beschreibung eines Sudoku-Feldes.

/ ** Ausgabe der Sudoku−F e l d e r i n einem separa t em Thread* P e t e r R e i c h e l < p e t e r @ p e t e r r e i c h e l . i n f o >* /

5package i t e . t e s t . sudoku ;import j a v a . u t i l . * ;import j a v a . i o . * ;

10 c l a s s S u d o k u P r i n t ex tends Thread {p r i v a t e V ec to r m S o l u t i o n s ;p r i v a t e boolean mDone ;p r i v a t e i n t mLen ;

15 p u b l i c S u d o k u P r i n t ( V e c t o r vec , i n t l e n ) {m S o l u t i o n s = vec ;mDone = f a l s e ;mLen = l e n ;

}20

p u b l i c vo id done ( ) {mDone = t rue ;

}

25 p u b l i c vo id run ( ) {

B.1 Test-Applikationen 75

i n t [ ] f i e l d ;i n t found = 0 ;whi le ( ! mDone ) {

synchronized ( m S o l u t i o n s ) {30 t r y { m S o l u t i o n s . w a i t ( ) ; }

ca tch ( I n t e r r u p t e d E x c e p t i o n e ) { }}

whi le ( m S o l u t i o n s . s i z e ( ) > 0 ) {35 t r y { f i e l d = ( i n t [ ] ) m S o l u t i o n s . f i r s t E l e m e n t ( ) ; }

ca tch ( NoSuchElementExcept ion e ) { f i e l d = n u l l ; }

i f ( f i e l d != n u l l ) {found ++;

40 m S o l u t i o n s . removeElement ( f i e l d ) ;System . o u t . p r i n t l n ( " S o l u t i o n n r . " + found ) ;p r i n t F i e l d ( f i e l d ) ;

}}

45 }System . o u t . p r i n t l n ( " Found " + found + " s o l u t i o n s ! " ) ;

}

p u b l i c vo id p r i n t F i e l d ( i n t [ ] f ) {50 f o r ( i n t row = 0 ; row < mLen ; row ++) {

f o r ( i n t c o l = 0 ; c o l < mLen ; c o l ++) {System . o u t . p r i n t ( f [ mLen * row + c o l ] + " " ) ;

}f o r ( i n t i = 0 ; i < mLen * 3 ; i ++) System . o u t . p r i n t ( " " ) ;

55 System . o u t . p r i n t l n ( " " ) ;}System . o u t . p r i n t l n ( " " ) ;

}}

Listing B.3: Klasse zur Ausgabe eines Sudoku-Feldes.

B.1.2 FScript-Interpreter

/ ** S i mp le Tes t−A p p l i c a t i o n i n s t a n t i a t i n g t h e F S c r i p t−I n t e r p r e t e r .* * /

package i t e . t e s t . f s c r i p t ;5 import murlen . u t i l . f s c r i p t M E . * ;

import j a v a . u t i l . Ve c to r ;import j a v a . l a n g . S t r i n g B u f f e r ;import j a v a . i o . * ;

10 import i t e . s y s . MMUStat ;import i t e . s y s . MMUCtrl ;import i t e . s y s .GC;import i t e . s y s . BaseGC ;import i t e . s y s .HWGC;

15 import i t e . s y s . SimpleGC ;import i t e . s y s . AdvGC ;import i t e . s y s . N o t A v a i l a b l e E x c e p t i o n ;

20 / / As f s c r i p t M E doesn ’ t have a Bas ic IO c l a s s l i k e f s c r i p t we have t o make/ / or owm ( j u s t l i f t e d from F S c r i p t )c l a s s Bas ic IO ex tends F S c r i p t {

p u b l i c O b j e c t c a l l F u n c t i o n ( S t r i n g name , V ec t o r param ) throws FSExcep t ion {i f ( name . e q u a l s ( " p r i n t " ) ) {

25 i n t n ;S t r i n g s=" " ;f o r ( n =0; n<param . s i z e ( ) ; n ++) s=s+ param . e l emen tAt ( n ) ;System . o u t . p r i n t ( s ) ;

}30 e l s e i f ( name . e q u a l s ( " p r i n t l n " ) ) {

i n t n ;S t r i n g s=" " ;f o r ( n =0; n<param . s i z e ( ) ; n ++) s=s+ param . e l emen tAt ( n ) ;System . o u t . p r i n t l n ( s ) ;

35 }e l s e super . c a l l F u n c t i o n ( name , param ) ;re turn new I n t e g e r ( 0 ) ;

}}

76 B Quelltexte

40p u b l i c c l a s s FSTest {

p r i v a t e s t a t i c V ec to r r e a d I n p u t ( ) {V ec to r v = new V ec to r ( 3 2 ) ;/ * l o a d i n g t h e s c r i p t i s done here

45 ( each l i n e as a s e p a r a t e e n t r y i n t h e v e c t o r * /re turn v ;

}

/ / S t a r t and i n i t i a l i z e t h e HW GC50 p u b l i c s t a t i c boolean initHWGC ( ) {

HWGC gc ;t r y { gc = new HWGC( ) ; } / / new SimpleGC ( ) ; }ca tch ( N o t A v a i l a b l e E x c e p t i o n e ) {


}/ * gc . s e t _ t i m e _ t r i g g e r ( 0 ) ; / / n e v e r

gc . s e t _ r t r i g _ l e v e l ( 1 0 0 ) ; / /100% => n e v e r t r i g g e rgc . s e t _ s t r i g _ l e v e l ( 6 5 ) ; / / t r i g g e r a t 65% u t i l i z a t i o n * /

60 gc . s e t _ s e l _ f n ( 0 , MMUCtrl . ge tRe fCoun t ( ) − 1 , MMUCtrl . g e t S e g S i z e ( ) − 256 , 2 5 6 ) ;/ / gc . s e t _ s e l _ f n ( 0 , 128 , MMUCtrl . g e t S e g S i z e ()−256 , 2 5 6 ) ;

/ / a l l w a y s run GC ( no t r i g g e r )gc . s e t _ t i m e _ t r i g g e r ( 0 ) ;

65 gc . s e t _ r e f _ t r i g g e r ( i t e . s y s . MMUCtrl . ge tRe fCoun t ( ) −1 ) ;gc . s e t _ s e g _ t r i g g e r ( 0 ) ; / / 10

GC. setGC ( gc ) ;re turn true ;

70 }

/ / S t a r t t h e s i m p l e SW−GCp u b l i c s t a t i c boolean initSWGC ( ) {

BaseGC gc ;75 t r y { gc = new AdvGC ( ) ; }

ca tch ( N o t A v a i l a b l e E x c e p t i o n e ) {System . e r r . p r i n t l n ( e ) ;re turn f a l s e ;

}80 GC. setGC ( gc ) ;

re turn true ;}

/ / t r y t o s t a r t HW or SW−GC85 p u b l i c s t a t i c boolean i n i tG C ( ) {

System . o u t . p r i n t l n ( " I n i t i a l i z i n g GC . . . " ) ;boolean r e s = initHWGC ( ) ;i f ( ! r e s ) {

System . o u t . p r i n t l n ( " T r y i ng SW GC . . . " ) ;90 r e s = initSWGC ( ) ;

}i f ( ! r e s ) {

System . o u t . p r i n t l n ( " S t a r t o f GC f a i l e d ! " ) ;re turn f a l s e ;

95 }i f ( !GC. g e t S t a t u s ( ) ) {

System . e r r . p r i n t l n ( "GC n o t s t a r t e d ! " ) ;re turn f a l s e ;

}100 e l s e {

System . o u t . p r i n t l n ( "GC s t a r t e d ! " ) ;re turn true ;

}}

105p u b l i c s t a t i c vo id i n i t T r a c i n g ( ) {

i t e . s y s . MMUStat . doSnapsho t ( ) ;

/ / s e t gc−t r i g g e r−c o n d i t i o n ( a l l w a y s run )110 i t e . s y s . MMUStat . se tTraceMode (0 x f f b ) ;

i t e . s y s . MMUStat . s e t T r a c e C n t (100000−1) ;i t e . s y s . MMUStat . s e t T r a c e E n a b l e d ( t rue ) ;

}

115 p u b l i c s t a t i c f i n a l vo id main ( ) throws FSExcept ion , IOExcep t i on {Thread . y i e l d ( ) ;System . o u t . p r i n t l n ( " Wait f o r s c r i p t . . . " ) ;

/ / Read s c r i p t from s t d−i n120 V ec to r v = r e a d I n p u t ( ) ;

System . o u t . p r i n t l n ( " S c r i p t r e c e i v e d . . . " ) ;

/ / add s c r i p t t o p a r s e r and f r e e r e f t o i n p u t v e c t o r

B.2 Aufbereitung der MMUStat-Ausgaben 77

Bas ic IO f s = new Bas ic IO ( ) ;125 f o r ( i n t i = 0 ; i < v . s i z e ( ) ; i ++) f s . a d d L i n e s ( ( S t r i n g ) v . e l emen tAt ( i ) ) ;

v = n u l l ;

/ / S t a r t t h e GCi f ( ! i n i tG C ( ) ) re turn ;

130/ / s t a r t t r a c i n gi n i t T r a c i n g ( ) ;

/ / s t a r t s c r i p t e x e c u t i o n135 System . o u t . p r i n t l n ( " S t a r t i n g s c r i p t e x e c u t i o n . . . " ) ;

f s . runCode ( ) ;System . o u t . p r i n t l n ( " S c r i p t done ! " ) ;

GC. setGC ( n u l l ) ;140 }

}

Listing B.4: Programm zum Instantiieren des FScript-Interpreters.

func c o l l a t z _ l e n ( i n t c o l )i n t c o u n t =0whi le c o l != 1

c o u n t = c o u n t + 15 i f c o l % 2 == 0

c o l = c o l / 2e l s e

c o l = 3 * c o l + 1e n d i f

10 endwhi lere turn c o u n t

endfunc

func f i b ( i n t k )15 i n t f1 =0

i n t f2 =1i n t f3whi le k>0

f3 = f1 + f220 f1 = f2

f2 = f3k = k − 1

endwhi lere turn f1

25 endfunc

i n t a=2i n t f , cwhi le a < 26

30 p r i n t ( " f i b ( " + a + " ) = " )f = f i b ( a )p r i n t ( f + " => c = " )c = c o l l a t z _ l e n ( f )p r i n t ( c + " . . . \ n " )

35a = a + 1

endwhi le

Listing B.5: Einfaches Test-Script, welches mit Hilfe des in Listing B.4 instantiierten Inter-preters ausgeführt wird.

B.2 Aufbereitung der MMUStat-Ausgaben

# ! / u s r / b i n / p e r l −w

# ################## Tab le c o n t a i n i n g t h e names o f d i f f e r e n t v a l u e s

5 my @elements ;$ e l e m e n t s [ 0 ] = " C yc l e s " ;$ e l e m e n t s [ 1 ] = " NwRefs " ;$ e l e m e n t s [ 2 ] = " Al loc−Count " ;$ e l e m e n t s [ 3 ] = " S t R e f s " ;

78 B Quelltexte

10 $ e l e m e n t s [ 4 ] = " S tOfs " ;$ e l e m e n t s [ 5 ] = " StWOfs " ;$ e l e m e n t s [ 6 ] = " S tVa l " ;$ e l e m e n t s [ 7 ] = "NwRef−Cy c l e s " ;$ e l e m e n t s [ 8 ] = " StRef−Cy c l e s " ;

15 $ e l e m e n t s [ 9 ] = " StOfs−Cy c l e s " ;$ e l e m e n t s [ 1 0 ] = " StVal−Cy c l e s " ;$ e l e m e n t s [ 1 1 ] = " Wait−f o r−GC−Cy c l e s " ;$ e l e m e n t s [ 1 2 ] = "GC−Runs " ;$ e l e m e n t s [ 1 3 ] = "Moved r e f s " ;

20 $ e l e m e n t s [ 1 4 ] = " Freed r e f s " ;$ e l e m e n t s [ 1 5 ] = "Moved words " ;$ e l e m e n t s [ 1 6 ] = " Freed words " ;$ e l e m e n t s [ 1 7 ] = " Freed s e g s " ;$ e l e m e n t s [ 1 8 ] = " Needed s e g s " ;

25 $ e l e m e n t s [ 1 9 ] = " I n i t −Phase−Cy c l e s " ;$ e l e m e n t s [ 2 0 ] = " MicScan−Phase−Cy c l e s " ;$ e l e m e n t s [ 2 1 ] = " StackScan−Phase−Cy c l e s " ;$ e l e m e n t s [ 2 2 ] = " HeapScan−Phase−Cy c l e s " ;$ e l e m e n t s [ 2 3 ] = " Mark−Phase−Cy c l e s " ;

30 $ e l e m e n t s [ 2 4 ] = " Clean−Phase−Cy c l e s " ;$ e l e m e n t s [ 2 5 ] = " Free−Refs " ;$ e l e m e n t s [ 2 6 ] = " Free−Segs " ;$ e l e m e n t s [ 2 7 ] = " Refman−Bound−C yc l e s " ;$ e l e m e n t s [ 2 8 ] = " Refman−NOP−Cy c l e s " ;

35 $ e l e m e n t s [ 2 9 ] = " Segman−Bound−C yc l e s " ;$ e l e m e n t s [ 3 0 ] = " Segman−NOP−Cy c l e s " ;

my $mle = 0 ;l e n g t h $ e l e m e n t s [ $_ ] < $mle o r $mle = l e n g t h $ e l e m e n t s [ $_ ] foreach 0 . . $ # e l e m e n t s ;

40# #################sub c n t o n e s {

my $ c n t = 0 ;my $ s t r = $_ [ 0 ] ;

45 my $ l e n = l e n g t h $ s t r ;f o r (my $ i = 0 ; $ i < $ l e n ; $ i ++) {

i f ( s u b s t r ( $ s t r , $ i , 1 ) == ’ 1 ’ ) { $ c n t ++; }}re turn $ c n t ;

50 }

sub d e c 2 b i n {my $ s t r = unpack ( " B32 " , pack ( "N" , s h i f t ) ) ;re turn $ s t r ;

55 }

sub a l i g n _ s i z e {my $a = $_ [ 0 ] ;

60 my $b = $_ [ 1 ] ;

i f ( l e n g t h $a < $b ) {re turn " " x ( $b − l e n g t h $a ) . $a ;

}65 e l s e {

re turn $a ;}

}

70 sub p r i n t _ s e t u p {my $a = $_ [ 0 ] ;my $f = 1 ;f o r (my $ i = 0 ; $ i < $# e l e m e n t s ; $ i ++) {

i f ( s u b s t r ( $a , $ i , 1 ) == ’ 1 ’ ) {75 i f ( $ f != 1 ) { p r i n t ’ , ’ ; }

e l s e { $f = 0 ; }p r i n t a l i g n _ s i z e ( $ e l e m e n t s [ $ i ] , $mle ) ;

}

80 }p r i n t " \ n " ;

}

sub p r i n t _ v a l u e {85 my $a = $_ [ 0 ] ;

my $f = $_ [ 1 ] ;my $ c u r v a l = 0 ;f o r (my $ j = 0 ; $ j < 4 ; $ j ++) {

$ c u r v a l += (256**(3− $ j ) ) * ord ( s u b s t r ( $a , $ j , 1 ) ) ;90 }

i f ( $ f != 1 ) { p r i n t ’ , ’ ; }p r i n t a l i g n _ s i z e ( $ c u r v a l , $mle ) ;

}

B.2 Aufbereitung der MMUStat-Ausgaben 79

95 # g e t mask from cmd−arg$mask = ($ARGV[ 0 ] =~ / ^ 0 / ) ? o c t ($ARGV[ 0 ] ) : $ARGV[ 0 ] o r d i e " Mask i s n o t a p r o p e r i n t e g e r ! \ n " ;$binmask = r e v e r s e d e c 2 b i n ( $mask ) ;$ o n e c n t = c n t o n e s ( $binmask ) ;

100 # P r i n t s e t u pp r i n t _ s e t u p ( $binmask ) ;

# e v a l u a t e i n p u tmy $ r e a d _ v a l = " " ;

105 whi le ( 1 ) {my $f = 1 ;my $ i = 0 ;whi le ( l e n g t h $ r e a d _ v a l < 4 * $ o n e c n t ) {

my $ l ;110 read ( STDIN , $l , 4 0 9 6 ) ;

$ r e a d _ v a l = $ r e a d _ v a l . $ l ;}

whi le ( $ i < $ o n e c n t ) {115 p r i n t _ v a l u e ( s u b s t r ( $ r e a d _ v a l , 0 , 4 ) , $ f ) ;

i f ( $ f == 1) { $ f = 0 ; }$ r e a d _ v a l = s u b s t r ( $ r e a d _ v a l , 4 ) ;$ i ++;

}120 p r i n t " \ n " ;

}

Listing B.6: Programm zur Aufbereitung der durch MMUStat gewonnenen Daten.

Literaturverzeichnis

[Bac+04] BACON, D. F.; CHENG, P.; RAJAN, V.: A Unified Theory of Garbage Collection.In: OOPSLA’04 ACM Conference on Object-Oriented Systems, Languages andApplications. Vancouver: ACM Press, Oktober/2004 ACM SIGPLAN Notices

[Bake78] BAKER, H. G.: List Processing in Real-Time on a Serial Computer. In: Com-munications of the ACM, Vol. 21 #4 (1978), S. 280–94. – Also AI LaboratoryWorking Paper 139, 1977

[Bake93] BAKER, H. G.: ‘Infant Mortality’ and Generational Garbage Collection. In:ACM SIGPLAN Notices, Vol. 28 #4 (April/1993)

[Bol+00] BOLLELLA, G.; GOSLING, J.; BROSGOL, B.; DIBBLE, P.; FURR, S.; HARDIN,D.; TURNBULL, M.: The Real-Time Specification for Java. The Java Series,Addison Wesley, 2000. – ISBN 0–201–70323–8

[Chen70] CHENEY, C. J.: A Non-Recursive List Compacting Algorithm. In: Communica-tions of the ACM, Vol. 13 #11 (November/1970), S. 677–8

[Coll60] COLLINS, G. E.: A Method for Overlapping and Erasure of Lists. In: Commu-nications of the ACM, Vol. 3 #12 (Dezember/1960), S. 655–657

[DeBo76] DEUTSCH, L. P.; BOBROW, D. G.: An Efficient Incremental Automatic GarbageCollector. In: Communications of the ACM, Vol. 19 #9 (September/1976),S. 522–526

[Desi02] DESIGN, D.: DLP-USB245M User Manual, 2002

[Dij+78] DIJKSTRA, E. W.; LAMPORT, L.; MARTIN, A. J.; SCHOLTEN, C. S.; STEFFENS,E. F. M.: On-The-Fly Garbage Collection: An exercise in Cooperation. In:Communications of the ACM, Vol. 21 #11 (November/1978), S. 965–975

[Edwawn] EDWARDS, D. J.: Lisp II Garbage Collector. MIT AI Laboratory, AI Memo 19,Date unknown. – 2 S

[FeYo69] FENICHEL, R. R.; YOCHELSON, J. C.: A Lisp Garbage Collector for VirtualMemory Computer Systems. In: Communications of the ACM, Vol. 12 #11(November/1969), S. 611–612

[fsc] FScript

82 Literaturverzeichnis

[Jone96] JONES, R. E.: Garbage Collection: Algorithms for Automatic Dynamic MemoryManagement. Chichester: Wiley, Juli/1996. – With a chapter on DistributedGarbage Collection by R. Lins.. – ISBN 0–471–94148–4

[Kope97] KOPETZ, H.: Real-Time Systems Design Principles for Distributed EmbeddedApplications. Kluwer Academic Publishers, 1997. – ISBN 0792398947

[LiHe83] LIEBERMAN, H.; HEWITT, C. E.: A Real-Time Garbage Collector Based onthe Lifetimes of Objects. In: Communications of the ACM, Vol. 26(6) (1983),S. 419–429. – Also report TM–184, Laboratory for Computer Science, MIT,Cambridge, MA, July 1980 and AI Lab Memo 569, 1981

[LiYe97] LINDHOLM, T.; YELLIN, F.: The Java Virtual Machine Specification. The JavaSeries, Addison Wesley, 1997. – ISBN 0–201–63452–X

[Maue04] MAUERER, W.: Linux Kernelarchitektur. Carl Hanser Verlag München Wien,2004. – ISBN 3–446–22566–8

[McBe63] MCBETH, J. H.: On the Reference Counter Method. In: Communications of theACM, Vol. 6 #9 (September/1963), S. 575

[McCa60] MCCARTHY, J.: Recursive Functions of Symbolic Expressions and their Com-putation by Machine. In: Communications of the ACM, Vol. 3 (1960), S. 184–195

[Meye04] MEYER, M.: A Novel Processor Architecture with Exact Tag-free Pointers. In:IEEE Micro, Vol. 24 #3 (May–June/2004), S. 46–55

[Meye05] MEYER, M.: An On-chip Garbage Collection Coprocessor for Embedded Real-time Systems. In: Proceedings of the 11th IEEE International Conference onEmbedded and Real-Time Computing Systems and Applications. Hong Kong,China, August/2005, S. 517–524

[Meye06] MEYER, M.: A True Hardware Read Barrier. In: MOSS, J. E. B. (Hrsg.):ISMM’06 Proceedings of the Fourth International Symposium on Memory Ma-nagement. Ottawa: ACM Press, Juni/2006, S. 3–16

[Moon84] MOON, D. A.: Garbage Collection in a Large LISP System. In: STEELE, G. L.(Hrsg.): Conference Record of the 1984 ACM Symposium on Lisp and FunctionalProgramming. Austin, TX: ACM Press, August/1984, S. 235–245

[Peti] PETIT-BIANCO, A.: No Silver Bullet - Garbage Collection for Java in EmbeddedSystems

[Pfe+04] PFEFFER, M.; UNGERER, T.; FUHRMANN, S.; KREUZINGER, J.; BRINKSCHUL-TE, U.: Real-Time Garbage Collection for a Multithreaded Java Microcontroller.In: Real-Time Syst., Vol. 26 #1 (2004), S. 89–106. – ISSN 0922–6443

Literaturverzeichnis 83

[Pre+07] PREUSSER, T. B.; ZABEL, M.; REICHEL, P.: The SHAP Microarchitecture andJava Virtual Machine. Technische Universität Dresden, Forschungsbericht, 2007

[Scho05] SCHOEBERL, M.: JOP: A Java Optimized Processor for Embedded Real-TimeSystems, Vienna University of Technology, Dissertation, 2005

[Sieb02] SIEBERT, F.: Hard Realtime Garbage Collection in Modern Object OrientedProgramming Languages. aicas Books, 2002

[Stee75] STEELE, G. L.: Multiprocessing Compactifying Garbage Collection. In: Com-munications of the ACM, Vol. 18 #9 (September/1975), S. 495–508

[Uhri03] UHRIG, S.: Der Komodo Mikrocontroller. Institute of Computer Science, Uni-versity of Augsburg, Forschungsbericht 2003-03, 2003

[Weiz63] WEIZENBAUM, J.: Symmetric List Processor. In: Communications of the ACM,Vol. 6 #9 (September/1963), S. 524–544

[Wils94] WILSON, P. R.: Uniprocessor Garbage Collection Techniques. University ofTexas, Forschungsbericht, 1994. Expanded version of the IWMM92 paper

[xap05] Using Block RAM in Spartan-3 Generation FPGAs. Online, März/2005

[Zab+07] ZABEL, M.; PREUSSER, T. B.; REICHEL, P.: Secure, Real-Time and Multi-Threaded General-Purpose Embedded Java Microarchitecture. In: 10th EURO-MICRO conference on Digital System Design, #10 (August/2007), S. 59–62

Documents

C1...ser unter Verwendung der auf dem FPGA verfügbaren internen Speicher umgesetzt und muss somit nicht vom Speichermanager verwaltet werden. Zur Beschleunigung der Kontextwechsel