Fall 2013
Program 6
Due Sunday November 17

Multithreaded Garbage Collector for C

Program Specifications

Extend the library you wrote for Program 6 so it is able to collect the garbage in parallel.

Scanning for roots in parallel

When scanning the stack to mark the roots of the garbage collection, it is possible to have more than one thread examining the stack. This is done by partitioning the stack into a number of disjoint parts, and then scanning each part in a separate thread.

Looking for holes in parallel

When looking for a chunk of memory, it is possible to use more than one thread to scan the heap. One thread should search from the front to the back, and the other thread should search from the back to the front. If either thread finds something, it must signal the other thread to stop looking. If the threads ever pass one another, they should also stop looking.

Scanning the heap in parallel

It is possible to scan the heap in parallel using a multithreaded depth first search. Each time the depth first search would move to a different node, it should first attempt to launch another thread on the child.

Note that the number of children threads should be bounded by a constant, so it is possible that there won't be any children threads available. If this is the case, the parent thread simply does whatever it wanted to make a child thread do.


For this program, you may implement the new functionality in any order you wish. I have put the items in order of what I believe to be their difficulty. In addition, remember, you may lose points if your program is not properly structured or adequately documented. Coding guidelines are given on the course overview webpage.

In addition to that, it is important that your program not print anything out to either standard out or standard error unless specifically called for in the specifications. Programs that have extra or otherwise incorrect output will lose points.

Your programs will be graded using agate.cs.unh.edu so be sure to test in that environment.

Remember: as always you are expected to do your own work on this assignment. Copying code from another student or from sites on the internet is explicitly forbidden!


Your programs should be submitted for grading from agate.cs.unh.edu. In order to turn in the program, first make sure you are SSH'd in to agate. To turn in this program, type:
% ~cs520/bin/DoSubmission.py prog7 gc_lib.c

This submission script is new. It passed what testing I have done on it, but it may still have issues. If there are any problems, please contact me via email and I will do my best to assist you. If I cannot be reached, please send me a copy of your assignment via email, and we will deal with the submission script later.

Due Date

This assignment is due Sunday December 8. The standard late policy concerning late submissions will be in effect.

Last modified: Sun Nov 3 08:00:00 EDT 2013