cs173: Assignment 4
Version 2, 2002-11-2 23:55
FAQ
In this assignment, you will write two garbage collectors. First, though, you need to write a function that will generate garbage:
- Write the function tree-add1, which consumes a binary tree of numbers, and returns a similar tree where each number is incremented by one.
- Convert this code to CPS, and then an explicit stack representation. The code for tree-sum from the 2002-10-21 notes should be helpful.
- Convert the function to use low-level representations of the stack and heap, as done in the 2002-10-23 notes. You will need to make one small change as compared to the notes: any value on the stack that refers to a heap location should be stored in a box, since the garbage collector may need to change its value.
Next, you will implement two garbage collectors: mark & sweep, and stop & copy. The garbage collector should run whenever a memory allocation fails, so you need to modify the functions that allot cells on the heap.
You should submit two files, one for each garbage collector. Each file should define the following variables and functions so that we can evaluate your implementation:
| HEAP-SIZE : number | number of cells in the heap |
| alloc/empty-tree : (listof loc) -> loc | consumes a list of extra roots (see second bullet below), allocates an empty tree on the heap, returns its location |
| alloc/node : number loc loc (listof loc) -> loc | consumes a list of extra roots (see second bullet below) allocates an tree node on the heap, returns its location |
| tree-add1 : loc -> loc | consumes the location of a tree, and returns the location of the result tree |
| location->tree : loc -> sexp | consumes the location of a tree, and returns some representation of the tree |
Finally, you should print a representation of the heap before and after every garbage collection. You can use the Scheme printf function:
(printf "Before: 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.
- The garbage collector consumes a root set of live references that includes both references on the stack and variables in scope. Although we're explicitly modeling the stack, we don't model variables explicitly. Therefore, you will need to pass any variables containing heap references as an argument to the garbage collector. Furthermore, since the garbage collector may change the values of these references, you should pass them as a list of boxed locations.
- 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
- Is it ok to maintain the freelist as a list of pairs?
You are supposed to maintain the 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 free list.) You may need to adjust your allocation accordingly to have enough space to maintain free list pointers!
- Do we have to compact memory in mark-and-sweep?
No.
- Can we assume that there will always be enough heap space
to allocate the initial input tree?
No, you can't 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.
- What changed between versions 1 and 2?
The interface to alloc/empty-tree and alloc/node. They now accept one more parameter: a list of extra roots. Note that we will still allow submissions that conform to the previous interface.
- How should we signal an out-of-memory error?
Call the Scheme function error. (If you're following the newsgroup, please ignore any messages on using let/cc for this assignment.)