| |
– 1 –
1
Einleitung und Motivation
Einige Programmiersprachen, wie z.B. Lisp oder Java™, bieten bereits eine automati-
sche Speicherverwaltung (Garbage Collection) in ihrer Grundfunktionalität an. Auch in
anderen Sprachen, in denen sowohl die Allokation als auch die Deallokation von Spei-
cher ursprünglich nur explizit von Programmiern vorgenommen werden konnte, bei-
spielsweise in C, wächst das Interesse an automatischer Speicherwaltung [Kap.9, Jo96].
Die rasante Entwicklung in den Bereichen der Hardwaretechnologie (z.B. leistungsfähi-
gere, preisgünstigere Komponenten, zunehmende Vernetzung, mobile Einheiten) und
Anwendungen (z.B. örtlich verteilt, sicherheitskritisch, paralleles Rechnen) führt dazu,
dass die Entwicklung paralleler und verteilter Systeme immer bedeutender wird. Des-
halb werden in dieser Arbeit verschiedene Ansätze betrachtet, wie Garbage Collection
(GC) in parallelen und verteilten Systemen realisiert werden kann.
Zunächst werden dazu im nächsten Kapitel Grundlagen der GC kurz vorgestellt, wobei
neben einer Definition für GC auch allgemeine Fragestellungen und Probleme bei der
GC geschildert werden. Außerdem wird Arbeitsweise von drei unterschiedlichen Klas-
sen von GC-Algorithmen (Reference Counting, Mark-Sweep und Copying GC) erläu-
tert.
Das dritte Kapitel bildet mit dem Thema GC in parallelen Systemen den Schwerpunkt
der Arbeit. Dort wird zunächst erklärt, was unter inkrementellen und konkurrenten Ver-
fahren zu verstehen ist und welche Besonderheiten, insbesondere wegen der Nebenläu-
figkeit von Prozessen, bei der GC in parallelen Systemen zu beachten sind. Hierbei wer-
den Read- und
W
rite-Barrier-Methoden behandelt und verbreitete Mark-Sweep-
Algorithmen, Bakers
k
opierender Algorithmus, der Appel-Ellis-Li-Algorithmus und
Bakers Treadmill-Verfahren beispielhaft dargelegt und dabei Vorteile und Problembe-
reiche genannt.
Im vierten Kapitel wird GC in verteilten Systemen betrachtet, in denen Applikationen
auf mehreren Rechnerknoten verteilt ablaufen. Hierbei werden verschiedene Aspekte
der verteilten GC in Bezug auf die Netzwerkebene und auf einen virtuellen gemeinsa-
men Speicher angesprochen. Ferner wird erklärt, warum manche Basisalgorithmen (z.B.
Reference Counting) nicht ohne Modifikation für verteilte GC geeignet sind. Als
Beispiele für verteilte GC-Algorithmen werden Hudak und Kellers Distributed Mark-
Tree-Algorithmus und das Verfahren von Lang et al. beschrieben.
Als Abschluss gibt das letzte Kapitel eine Zusammenfassung und einen Ausblick über
parallele und verteilte GC.
|  |
|
| |
|
|
