[CST-2] Advanced Algorithms
Jon Clayden
jdc31@cam.ac.uk
Fri, 17 May 2002 14:37:10 +0100
I have a question about the real-time garbage collection algorithm
mentioned in the notes. The processes for mutator and collector are, as I
understand them, as follows.
Mutator:
- All nodes start white.
- Shade (i.e. make grey if white, else leave alone) the target of the
previously redirected edge.
- Redirect an outgoing edge of a reachable node towards another reachable
node (with the understanding that nodes on the free list are reachable from
special free list root nodes).
Collector:
- Shade all roots (except free list ones, I suppose).
- [Marking phase] Work through the other nodes in some order (does the
order matter?). If node i is grey, shade its left successor, shade its
right successor, and then make i black.
- [Appending phase] Work through the nodes again. If node i is black, make
it white; if it is white, append it to the free list.
I don't quite see how this solves the problem. This may be because I've got
something wrong (please correct!), or missed something important.
- How is the free list maintained? In particular, if node i has an outgoing
edge redirected towards a node on the free list j, how/when is the free
list pointer updated to indicate that the node is no longer free?
- If a black node can point to a white node, what's to stop the collector
from treating that target node as garbage, even though it's reachable? Or
can a black node only point to a white node while the collector is still in
the marking phase?
It's quite likely that I'm just having trouble seeing the wood for the
trees, but any help would be appreciated! Also, I'd like to check that the
results for big-number arithmetic mentioned in the notes (and the
appropriate methods behind them) are the only ones we need to know -- I
don't remember any others being explained in lectures, but my memory's not
brilliant!
Thanks,
Jon Clayden