Garbage Collection FAQ

Notes: This project is a team project to be completed in pairs. Please see the main assignments webpage for more details. Also, you will need to set the language level to CS173 Advanced.

In this assignment, you will implement two garbage collectors: mark & sweep, and stop & copy. As we have seen, garbage collection involves starting from a root set of references, which reside in local variables and stack frames, and searching for reachable values on the heap. Hence, to write a garbage collector, you need a program that exposes this information. For this assignment, we will write such a program for you, so you can focus on implementing the actual garbage-collection algorithms.

Specifically, you should download the source code for the function tree-add1, which consumes a binary tree of numbers and returns a similar tree where each number is incremented by one. This function is written to use low-level routines for memory allocation and an explicit stack. It comes with dummy allocation routines that never collect garbage. You will need to write a replacement allocator that collects garbage when the heap is full. We provide a function called get-stack-roots that returns the current root set as a list of boxed locations (so you can move objects around). We also provide a function called location->tree that returns an S-expression representing the given heap-allocated tree. For each garbage collector, you will need to redefine the following:

`alloc/empty-tree : () -> loc`	allocates an empty tree on the heap
`alloc/node : number loc loc -> loc`	allocates and initializes a node on the heap (each of the three fields must be stored in a separate heap cell)
`HEAP-SIZE : number`	number of cells in the heap (the TAs will change this while grading, so don't hard-code any assumptions about it)

In addition, if you choose to change the representation of values in the heap, you will need to redefine the following:

`empty-tree? : loc -> boolean`	returns `true` iff loc points to an empty tree
`node? : loc -> boolean`	returns `true` iff loc points to a tree node
`node-val : loc -> number`	returns the value of a tree node
`node-left : loc -> loc`	returns the left child of a node
`node-right : loc -> loc`	returns the right child of a node

As a part of this conversion, you should maintain a free list in the heap. That is, you should not use any auxiliary data structure; instead, use the available space in the heap to keep track of the free list. (You may use one extra box ("register") to point to the start of the free list.) You may need to adjust your allocation accordingly to have enough space to maintain free list pointers!

You will probably want to use numbers to represent locations, but you may use another representation if it eases your implementation. Also, to help see what is happening, you might want to print a representation of the heap before and after every garbage collection. You can use the Scheme printf function:

(printf "Heap is ~s~n" Heap)

Some final words of advice:

You will want to test your program with small heap sizes, so that the garbage collector runs frequently.
You do not need to compact memory in mark-and-sweep.
The last two arguments to alloc/node (the child nodes) are roots, which means you must include them when searching and (in the case of stop & copy) update them.
You can assume there will be enough heap space for the initial tree. Of course, any time there is not enough free memory to allocate the number of cells needed (after garbage collection), the program should terminate with an "out of memory" error by calling the Scheme function error.
You may find it convenient to use the Scheme construct set!, which allows you to mutate a variable without using boxes. We recommend you use this feature only in one instance: when swapping the semispaces in the stop & copy collector. This will save you the trouble of unboxing the heap every time you use it.

FAQ

For this assignment you will need to use the CS173 Advanced language in DrScheme for the support code to function correctly
Please redownload the support code to correct an error with the heap-ptr definition.
Updated to reflect that you can assume enough space to allocate the initial tree
You should reset the heap between top level calls to tree-add1