home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Amiga MA Magazine 1998 #6
/
amigamamagazinepolishissue1998.iso
/
coders
/
collector
/
collector.doc
< prev
next >
Wrap
Text File
|
1995-03-02
|
9KB
|
226 lines
Collector 1.0
Management and Garbage Collection of elemental objects.
Copyright © 1993-1994 by Lars Düning
All rights reserved.
Permission granted for non-commercial use.
Introduction
------------
Oberon possesses a feature called 'garbage collection' easening the handling
of free allocated structures. Unfortunately the GC of Oberon has just a
restrained usability because:
- it doesn't know 'weak pointers' (pointers being too weak to keep an
element alive)
- elements are deallocated without notification (no destructor mechanism)
- it can't be switched off.
Additionally, the incremental garbage collector of Amiga-Oberon adds a
significant overhead to the program.
'Collector' is the attempt to implement a GC on a 'higher level'. Though it
must be operated manually, it can exploit the programmers knowledge about
the program. It also features implicitely 'weak pointers' and destructor
methods. Operation is incremental to scatter the workload more even over
the total run of the program.
'Collector' comes in two flavours: for once 'Collector' itself, using
double-linked lists internally, and then 'CollectorS' using single-linked
lists. The interface to both is (almost) identical.
'Collector' needs a bit more memory and is busier during the usage of
the elements, but is able to do the actual collection more straightforward.
'CollectorS' needs less memory and usage cycles, but more time for the
collection.
Contents
--------
The complete 'Collecter' archive contains these files:
Collector.mod : the source of Collector
CollectorS.mod : the source of CollectorS
Collector.txt : the 'definition' of Collector(S)
Mark.inline : inline source of CollectorS.Mark()
Check.inline : inline source of CollectorS.Check()
CollTest.mod : a simple test and demonstration program
CHANGELOG : what was changed when how by whom
Collector.dok : this documentation (german)
Collector.doc : this documentation (english)
The files should, but needn't be equipped with icons.
'Collector' was developed and tested using Amiga-Oberon 3.11.
Installation
------------
Compile both modules and copy the created binaries into the approbiate
directories.
Both modules may be used with and without the compilers garbagecollection.
Usage
-----
To make usage of Collector, the to be managed data structures need to
fullfill three requirements:
- all structures must be derived of Collector[S].Element.
- at the runtime of the collector routine all living data must be
reachable from the 'rootset' data set.
- in general. no local pointers and elements must be kept over the
call of the collector routine.
The elements managed by Collector are divided into the 'normal' and
the 'root' elements. Root elements are the base of the data web: they
are by definition alive, and server as anchors for the normal elements.
All elements which may be reached starting from a root element are
alive as well, the others are detected by Collector and deallocated.
To let an own data structure be managed by Collector, it must inherit
Collector[S].Element, and be registrated with Collector by a call to
.RegisterType(). .RegisterType() gets as most important parameter a
function, which on call returns a freshly allocated element of the
registered structure. Other parameters determine, if the registered
structure is of root type, and how long the list of free elements
may grow.
Result is a type number, which has to be used to request new instances
of the registered type using .New().
It is possible to use a data structure as normal as well as root, but
it must be registered twice with the Collector.
If a given structure is root or not is flagged by 'Collector.Root' in
the imported field '.ecFlags'.
To each element two functions are bound, which are called by the collector:
mark()
This function is called when the collector acknowledged an element
as alive. The element now has to mark all from it reachable elements
using Collector[S].Mark(),
free()
The collector decided that this element is dead and would like to
deallocate it. The element now has the opportunity to perform
cleanup operations, or to deny the deallocation.
The result value determines the further action of the collector:
.keep : the element stays alive.
.enlist : the element is freed, but kept in the free list of its
type.
.dispose: the element is deallocated.
Note that .free() is called for unreferenced root elements as well - this
way these have the opportunity to commit suicide after long idling.
'Freed' elements are normally not deallocated, but instead kept in a
free list, so that later requests for elements of the same type are
fulfilled quicker.
The maximal number of elements in a free list is set at the registration
of the type - but it is possible to deallocate free elements of a certain
age (counted in GC runs) by a call to .ShortenLists().
The incremental operation of the GC (if one uses it at all) has the effect
that the type bound function .mark() is not sufficient to mark all
living elements as soon as a new allocated element is assigned to an
already marked element.
Therefore all new references between two elements must be notified to
the collector by calling .Check().
The actual garbage collection is done by a call to .GC(). Parameter is
the planned number of calls for one complete collection. Using '1' as
value, a complete collection is enforced (or at least the already begun
collection completed).
Is CollectorS used, the marking of an element is just the setting of a flag
in the element structure, so that the associated routines are better
programmed 'inline'. Suiting templates are given in the files 'Check.inline'
and 'Mark.inline'.
Algorithm
---------
The gargabe collector is a variant of Dijkstra's Incremental Update Collector,
implement using a description in "Uniprocessor Garbage Collection Techniques".
All existing elements are colored with one of three colours:
black: the living, during the GC run already processed elements.
grey : the living, yet unprocessed elements.
white: the unprocessed, potentially dead elements.
The collector walks through the list of grey elements. For each grey element
all from it reachable elements are colored grey as well, then the element
itself is colored black. Starting from the root elements, which are statically
colored 'grey', all living elements are first colored grey, then black.
If no grey element is left, the current GC run is complete, and all elements
still colored white are dead and therefor deallocatable.
Elements allocated during a GC run are colored white, so that elements with
a life span shorter than the GC run may be deallocated already at the end
of the current run.
Changes in the relations between elements during a GC run are detected using
a 'write barrier': if an element pointer is assigned to an already blackened
element, the element pointed to is colored grey during the assignment.
The implementation used in Collector distinguishes root elements from normal
elements to be able to detect unreferenced rootelements. For this a new
color 'dark' is used, marking the processed but unreferenced rootelements.
Besides that, all elements are managed in rings, with a separate ring for
each color (in CollectorS the 'white' ring also contains the 'grey' elements).
In Collector these rings are implemented using double linked lists, in
CollectorS by using single linked lists.
This means for Collector, that each recoloring of an element must be
accompained by a transfer of that element into another ring, whereas
CollectorS just has to set a flag. On the other hand this enables Collector
to process each element just once for a complete collection, whereas
CollectorS has to process the 'white' ring several times to detect elements
which were colored grey late.
Disclaimer
----------
It runs on my machine - everything else is beyond my sphere of influence.
The module including ideas, algorithms and files is freeware: meant for
the benefit of many, but not for someone making profit (money or glory)
on my expenses. Infringement is a call for trouble.
Permission granted for non-commercial use, distribution, replication and
development, as long as the 'meaning' remains the same, every change is
clearly documented, and all files are included in the package
Distribution as part of commercial software libraries is permitted, as long
as the package is just 'one among many'.
Participants
------------
Lars Düning; Am Wendenwehr 25; D-38114 Braunschweig; Germany
duening@ibr.cs.tu-bs.de
Literature
----------
Paul R. Wilson: Uniprocessor Garbage Collection Techniques
1992 International Workshop on Memory Management
Springer-Verlag, Lecture Notes
"Das Konzept ist einfach erstaunlich. Sinnlos, aber erstaunlich."
(Der Doktor)