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
Write your garbage collector using #lang plai/collector
. This
language defines an interface to a program's stack and heap that you will use
to implement garbage collection. The PLAI
manual specifies the functions that your collectors must define.
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
Your collectors will allocate closures on the heap, and closure environments
contain pointers to heap-allocated values. The function procedure-roots
returns all pointers in the closure's environment as a list of roots. If your
collector moves objects in memory, do update these roots accordingly.
Testing your Garbage Collectors
To test your collector, write programs using #lang
plai/mutator
, which is a subet of Racket that uses a custom garbage
collector (i.e., yours) instead of Racket's own collector.
Debugging your Garbage Collectors
If both a mutator and its collector are open in adjacent tabs, you can use breakpoints and DrRacket's debugger to step between them.
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. (With the sample mutator, it does signal an error.)
Notes
You may store 2-3 atomic values, such as addresses, as global variables in your collector. We will assume they represent machine registers. However, all compound data structures and allocated values must be on the heap.
For example, in the mark-and-sweep collector, the free list must be on the heap, since its size is indeterminate and cannot fit in registers. You can variables to point to the beginning/end of the free list, but the list itself cannot legitimately reside in variables (registers).
Some final words of advice:
- Test your program with small heaps, 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 Racket 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.
- To help debugging, consider zero-filling freed memory.
Handin
Turn in the following files:
copy.rkt
, your stop-and-copy collector.ms.rkt
, 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.