Garbage Collection
This is the last assignment you will complete with your first team. You will use a new team for the next assignment. Please remember to follow the style and testing guidelines outlined in the syllabus.
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 have written such a program for you. You will implement the actual garbage-collection algorithms.
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->list 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 ~a~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.