Phase 4: Garbage Collection

Your goal for this phase is to introduce support for Garbage Collection into your VM from Phase 3.

Mark and Sweep

The main starter code for this assignment is in the cpp-skeleton/gc/gc.h file. This file defines two key classes that you will be working with for this assignment. The first one is called ‘Collectable’. All objects tracked by the Garbage collector must be ‘Collectable’ objects, and any fields in the ‘Collectable’ class can be thought of as part of the header that will be used by the garbage collector to store metadata relevant to this object.

The second key class is called ‘CollectedHeap’. This is the class that keeps track of all the objects managed by the garbage collector and implements the actual garbage collection algorithm.

In addition to these classes, your skeleton code includes a ‘main.cpp’ method that you can use to test your garbage collector before you connect it to your VM, as well as a file ‘timerclass.h’ that you can use to time your implementation.


Your VM should support a command line argument of the form "-mem N", where ‘N’ is the maximum amount of memory (in MB) that the VM can use. You can assume that ‘N’ will be at least twice as large as the maximum amount of memory that will ever be required by the program you are running. You can also assume that N will always be at least 4. Your garbage collector should make sure that the VM never uses more than this amount of memory.

Credit for this assignment will depend exclussively on the ability of your implementation to stay within the memory limits given by "-mem N’.

Implementation Notes

For a very basic implementation strategy, you could do the following:

If you follow this approach, be aware of the following challenges.


Below are some suggested enhancements on top of the basic implementation strategy.


Each team must submit a working VM together with 10 stress tests that allocate enough objects to stress the garbage collector.
None of your tests should require a memory limit greater than 20MB.

Additionally, your documentation must explain at least the following: