Complete this assignment with the same team you worked with for Continuations (Written). You and your partner must each understand the answers to all the problems, so don't just split up the work.
In this assignment, you will implement two garbage collectors: mark-and-sweep, and stop-and-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.
Writing your Garbage Collectors
Your garbage collectors must be written in the GC Collector Scheme language level. This language defines an interface to a program's stack and heap that you will use to implement garbage collection.
Consult the PLAI manual for more information on the interface provided by GC Collector Scheme and the functions you must define to write a garbage collector.
Memory LayoutYour allocator must use the following cell sizes when allocating blocks:
- mark-and-sweep: 3 cells for flat values, 4 cells for cons values
- stop-and-copy: 2 cells for flat values, 3 cells for cons values
Dealing with ClosuresOne or both of your garbage collectors will need to occasionally move around cells in memory. If that cell is referenced by a closure, then the pointer in the closure will need to be updated to point to the new location in memory. We've given you the function
procedure-roots, which returns all the cells referenced by the given closure as
rootobjects; they are returned as
roots not because they are necessarily roots of the reference hierarchy, but because that is a convienient data structure allowing you to update the closure without explicit access to its internal representation.
Testing your Garbage Collectors
You may write programs that exercise your garbage collectors using the GC Mutator Scheme language. This language is a subset of Scheme that uses a garbage collector that you specify. Consult the PLAI manual for more information.
Debugging your Garbage CollectorsBecause of certain peculiarities in the GC language level, to debug your collector you must follow the following steps:
- Open your collector and your mutator side-by-side in tabs in a DrScheme window.
- In both files, select the
- Add the following line to the top of your collector file:
- Add the following line to the top of your mutator file:
To get you started, we've provided a sample mutator and a trivial collector that signals an error when the heap fills up. (In fact, our collector does signal an error with the mutator we've provided, if you don't increase the size of the heap.)
You must store bookkeeping data on the heap provided by GC Collector Scheme. You may store 2-3 atomic values, such as addresses into the heap as variables in your garbage collector. We will assume they represent machine registers. However, all compound data structures must be on the heap.
In particular, in the mark-and-sweep collector, 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!
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.
- 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-and-copy collector. This will save you the trouble of unboxing the heap every time you use it.
Turn in the following files:
copy.ss, your stop-and-copy collector.
ms.ss, your mark-and-sweep collector.
- You will need to write multiple mutators to test your collectors. Include as many as you need to test your code thoroughly.