Use copying collection, but rather than stop
when you run out of memory and then
do all the GC work in one shot,
do a little bit whenever a
pointer variable is referenced
or when a new object is allocated.
We start out by forwarding (copying)
the objects pointed to by global
variables.
Then, instead of continuing forwarding
recursively, we resume the program.
Every time a pointer is referenced
we check to see whether it is
pointing into from-space.
If it is, we forward that object
too.
Even objects which are not explicitly
referenced have to be checked, to see
if they have become garbage. Therefore,
every time we allocate a new object
we forward pointers.
A good value for has to be
determined by experimentation.
Eventually scan will catch
up with next and we switch
from-space and to-space
and start an new cycle.
Baker's algorithm (on the next slide) is a variant of
copying collection.
Why is generational collection more appropriate for
functional and logic languages (such as LISP and Prolog),
than for object-oriented languages (such as Eiffel and Modula-3)?
The heap in the figure on the next slide holds 7 objects. All objects
have one integer field and one or two pointer fields
(black dots). The only roots are the three global variables
X, Y, and Z. Free space is shaded.
Show the state of To-Space after a copying garbage
collection has been performed on From-Space. Note
that several answers are possible, depending on the visit
strategy (Depth-First or Breadth-First Search) you chose.
Topics in advanced language implementation,
Chapter 4, Andrew Appel, Garbage Collection.
Chapter 5, David L. Detlefs, Concurrent Garbage
Collection for C++. ISBN 0-262-12151-4.
Aho, Hopcroft, Ullman. Data Structures and Algorithms,
Chapter 12, Memory Management.