Version 2, 2002-11-2 23:55
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
|
You will almost certainly want to use numbers for the
loc
type above, but you're allowed to choose some other representation.
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.)