home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Amiga MA Magazine 1998 #6
/
amigamamagazinepolishissue1998.iso
/
coders
/
collector
/
collector.dok
< prev
next >
Wrap
Text File
|
1995-03-02
|
10KB
|
245 lines
Collector 1.0
Verwaltung und Garbage-Collection elementarer Objekte
Copyright © 1993-1994 by Lars Düning
Alle Rechte vorbehalten.
Nichtkommerzielle Nutzung gestattet.
Einführung
----------
Oberon besitzt bekanntermaßen eine NÜtzlichkeit genannt "Garbagecollector",
die das Handling mit frei allokierten Strukturen stark vereinfacht und
sicherer macht. Leider ist in Oberon der GC in seiner NÜtzlichkeit doch
eingeschränkt, denn
- er kennt keine 'Weak Pointer' (Zeiger, die zu schwach sind, ein Element
am Leben zu erhalten)
- Strukturen werden ohne Notifikation deallokiert (kein Destruktor-
Mechanismus)
- man kann ihn nicht abschalten.
In Amiga-Oberon kommt zudem der zeitliche Overhead für den inkrementellen
Garbagecollector hinzu.
'Collector' ist nun ein "higher level" Ansatz eines GC, der zwar manuell
bedient werden muß, aber dafür Wissen des Programmierers über das Programm
ausnutzen kann. Er bietet zudem implizit 'Weak Pointer' und Destruktor-
methoden für die Objekte. Er arbeitet inkrementell, da so die Arbeitslast
gleichmäßiger auf die gesamte Programmlaufzeit verteilt wird.
'Collector' existiert in zwei Varianten: einmal 'Collector' selber, der
intern mit doppelt-verketteten Listen arbeitet, und 'CollectorS', der
mit nur einfach-verketteten Listen operiert. Das Interface zu beiden
ist (fast) völlig identisch.
'Collector' benötigt neben etwas mehr Speicher mehr Aufwand während der
Verwendung der Objekte, kann dafür aber die eigentliche Collection
zielstrebiger durchführen.
'CollectorS' dagegen benÖtigt weniger Speicher und Verwendungsoverhead,
benötigt aber mehr Zeit für eine Collection.
Paketumfang
-----------
Das komplette 'Collector'-Archiv enthält folgende Dateien:
Collector.mod : der Quellcode von Collector
CollectorS.mod : der QuellCode vom CollectorS
Collector.txt : das 'Definitionsmodul' von Collector(S)
Mark.inline : Inlinetext von CollectorS.Mark()
Check.inline : Inlinetext von CollectorS.Check()
CollTest.mod : ein simples Test- und Beispielprogramm
CHANGELOG : was sich wann warum änderte
Collector.dok : diese Dokumentation (Deutsch)
Collector.doc : diese Dokumentation (Englisch)
Die Dateien sollten, müssen aber nicht unbedingt mit Icons versehen sein.
Entwickelt und getestet wurde 'Collector' unter Amiga-Oberon 3.11.
Installation
------------
Zur Installation mÜssen beide Module schlicht compiliert und die erzeugten
Dateien in die passenden Directories kopiert werden.
Beide Module können mit und ohne Garbagecollection compiliert werden.
Benutzung
---------
Zur Benutzung von Collector müssen die zu verwaltenden Datenstrukturen
drei Rahmenbedingungen erfüllen:
- alle Strukturen müssen von Collector[S].Element abgeleitet werden
- die lebenden Daten müssen sich zur Laufzeit der Collectionroutine
vollständig aus der "rootset" Teilmenge erreichen lassen.
- es dürfen idR keine lokalen Zeiger auf Elemente über den Aufruf der
GC-Routine hinweg verwendet werden.
Die vom Collector verwalteten Elementen teilen sich in die 'normalen'
und die 'Root'elemente. Rootelemente sind die Basiselemente des
Datengeflechts: sie sind per definition lebendig, und dienen als Anker
für die normalen Elemente. Alle Elemente, die sich von den Rootelementen
aus erreichen lassen, gelten ebenfalls als lebend, die anderen werden
vom Collector erkannt und deallokiert.
Um eine eigene Datenstruktur vom Collector verwalten zu lassen, muß sie
von Collector[S].Element abgeleitet werden, und dem Collector mit
.RegisterType() mitgeteilt werden. .RegisterType() erhält als primären
Parameter eine Funktion, die bei Aufruf eine frisch allokierte
Datenstruktur zurückliefert, sowie die Angabe, ob es sich um eine Root-
datenstruktur handelt, und wie lang die Freeliste werden darf.
Resultat von RegisterType() ist eine Typnummer, die verwendet werden
muß, um vom Collector neue Instanzen dieser Datenstruktur mittels
.New() anzufordern.
Es ist möglich, eine Datenstruktur sowohl normal als auch als Root zu
verwenden, muß sie dafür aber zweimal beim Collector registrieren.
Ob eine reale Datenstruktur dann Root oder nicht ist, läßt sich am
Flag 'Collector.Root' im importierten Feld '.ecFlags' feststellen.
An ein Element sind zwei Funktionen gebunden, die vom Collector aufgerufen
werden:
mark()
Diese Funktion wird aufgerufen, wenn der Collector ein Element als
lebendig erkannt hat, damit dieses Element die von ihm aus
erreichbaren Elemente mit Collector(S).Mark() markiert.
free()
Der Collector hat dieses Element als 'nicht lebendig' erkannt und
möchte es deallokieren. Das Element hat die Möglichkeit, Aufräum-
arbeiten zu erledigen, oder eine Deallokation zu verweigern.
Der Resultatwert bestimmt die Aktion des Collectors:
.keep : das Element bleibt weiter lebendig.
.enlist : das Element wird freigegeben, aber in seiner Freelist
gehalten.
.dispose: das Element wird freigegeben.
Zu beachten ist, daß .free() auch für nicht-referenzierte Rootelemente
aufgerufen wird - diese haben so die Gelegenheit, sich nach langer
Nichtbenutzung selbst aus dem Speicher zu entfernen.
Zurückgegebene Elemente werden in der Regel nicht sofort deallokiert,
sondern zunächst in einer Freelist zwischengespeichert, so daß nachfolgende
Anforderungen von Elementen selben Typs schneller erledigt werden können.
Die maximale Anzahl von Elementen in einer Freelist wird bei der
Registrierung eines Typs festgelegt - zwischenzeitlich lassen sich Elemente
eines gewissen Alters (gemessen in GC-Läufen) mit ShortenLists() aus
den Freelists freigeben.
Die inkrementelle Arbeitsweise des GC (sofern man sie ausnutzt) hat zur
Folge, daß die typgebundene Funktion .mark() nicht zur vollständigen
Markierung aller lebenden Elemente ausreicht - sobald neu allokierte
Elemente an bereits bearbeitete Elemente zugewiesen werden.
Daher muß generell bei jeder neuen Referenzierung eines Elementes
der Collector mit Check() informiert werden.
Die eigentliche Garbagecollection wird durch den Aufruf der Funktion GC()
ausgeführt. Parameter ist die Anzahl der geplanten Aufrufe, die zur
Vervollständigung der GC nötig sein sollen. Gibt man hier '1' als Wert an,
wird eine vollständige GC erzwungen (bzw. die soweit angefangene GC
vervollständigt).
Verwendet man CollectorS, beschränkt sich die 'Markierung' eines Elementes
lediglich auf das Setzen eines Flags in der Elementstruktur, so daß
die entsprechenden Routinen besser 'inline' programmiert werden (passende
Templates sind in den Files 'Check.inline' and 'Mark.inline').
Algorithmus
-----------
Der Garbagecollector ist eine Variante von Dijkstra's Incremental Update
Collector, implementiert nach einer Beschreibung in "Uniprocessor
Garbage Collection Techniques".
Die existierenden Elemente werden mit einer von drei Farben gekennzeichnet:
schwarz: die lebenden, in diesem GC-Lauf bereits vom GC bearbeiteten
Elemente.
grau : die lebenden, noch nicht bearbeiteten Elemente.
weiß : die potentiell toten, noch nicht bearbeiteten Elemente.
Der Collector arbeitet sich durch die Liste der grauen Elemente.
Bei jedem grauen Element werden die von diesem aus erreichbaren Elemente
ebenfalls grau markiert, das bearbeitete Element dann schwarz gefärbt.
Ausgehend von den Root-Elementen, die statisch 'grau' markiert werden,
werden so nach und nach alle lebenden Elemente erst grau, dann schwarz
markiert. Ist kein graues Element mehr vorhanden, ist der aktuelle GC-Lauf
vollständig, und die jetzt weißen Elemente sind als 'tot' deallokierbar.
Während des GC-Laufs allokierte neue Elemente werden zunächst weiß gefärbt,
so daß nur kurzzeitig lebende Elemente möglichst schnell wieder freigegeben
werden können.
Änderungen in den Beziehungen zwischen den Elementen während des GC-Laufs
werden durch eine 'Write Barrier' abgefangen: wird ein Elementzeiger einem
bereits geschwärztem Element zugewiesen, wird das referenzierte Element
ebenfalls grau gefärbt.
Die in Collector verwendete Implementation trennt Rootelemente scharf von
normalen Elementen, um den Fall von nicht direkt referenzierten Rootelementen
erkennen zu können. Dazu wird neben den zusätzlichen Listen für die
Rootelemente eine weitere Schattierung 'dunkel' verwendet, die die vom
GC bereits bearbeiteten, aber nicht direkt referenzierten Rootelemente
kennzeichnet.
Ansonsten werden die Elemente in Ringlisten verwaltet, wobei jeder Farbe
ein Ring entspricht (in CollectorS enthält die 'weisse' Liste auch die
grauen Elemente). In Collector werden diese Listen durch doppelte Verkettung
realisiert, in CollectorS nur durch einfache Verkettung.
Als Folge bedeutet für Collector jede Umfärbung eines Elementes, daß das
Element seinen Ring wechselt, während in CollectorS lediglich ein Flag
gesetzt werden muß. Dafür muß Collector für eine vollständige GC jedes
Element nur einmal abarbeiten, während CollectorS mehrere Durchläufe durch
die 'weiße' Liste benötigt, um nachträglich grau markierte Elemente zu
finden.
Disclaimer
----------
Es funktioniert auf meinem Rechner - alles andere ist ausserhalb meines
Einflußbereiches.
Das Modul samt Ideen, Algorithmen und Dateien ist Freeware: gedacht zum
Nutzen vieler, aber nicht damit es jemand dazu benutzt, auf meine
Kosten Geld und/oder Ruhm zu ernten. Wenn es dennoch jemand tut, gibt's
Ärger.
Die nichtkommerzielle Verwendung, Vertrieb, Vervielfältigung und
Weiterentwicklung von Programm und Dokumentation ist gestattet, solange
der Wesensgehalt ungeändert bleibt, jede Änderung rekonstrierbar
dokumentiert wird, und das Paket stets alle Dateien enthält.
Der Vetrieb in kommerziellen Softwaresammlungen ist gestattet, wenn
innerhalb der Sammlung das Paket lediglich 'eines unter vielen' ist.
Mitwirkende
-----------
Lars Düning; Am Wendenwehr 25; D-38114 Braunschweig; Germany
duening@ibr.cs.tu-bs.de
Literaturtip
------------
Paul R. Wilson: Uniprocessor Garbage Collection Techniques
1992 International Workshop on Memory Management
Springer-Verlag, Lecture Notes
"The concept is simply staggering. Pointless, but staggering."
(The Doctor)