[CST-2] Advanced Algorithms

[Matej Pfajfar]

> 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.
No. Not all nodes need to be white for the mutator to be able to change
the data structure.

> - 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).
>
Yes.

> 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.
No the order doesn't matter but I suppose it should be something naturally
related to how you store the nodes internally. The stopping condition is
to make an entire cyle cthrough the nodes without encountering any grey
ones.

> - [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?
It's implicitly assumed that redirecting an edge to a free node also fixes
the edges in the free list to exclude that node. Someone double-check
that?

> - 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?
This is explained in the last "PROOF" of section 5 of Dijkstra's (et al)
paper.

Hope this helps. Someone read through this and correct me if I am wrong
...

Mat

Matej Pfajfar
St John's College, University of Cambridge, UK

GPG Public Key @ http://matejpfajfar.co.uk/keys
Most people are good people, the rest of us are going to
run the world. -- badbytes