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.
Garbage Collection
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 Layout
Your 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 Closures
One 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 functionprocedure-roots
, which returns all the cells referenced by the
given closure as root
objects; they are returned as
root
s 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 Collectors
Because 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
Module
language level. - Add the following line to the top of your collector file:
#lang plai/collector
- Add the following line to the top of your mutator file:
#lang plai/mutator
Sample Code
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.)
Notes
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.
Handin
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.