[CST-2] Advanced Algorithms

[Jon Clayden]

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