CS520
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.
Grading
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.
- 70 points will be awarded for submitting a program that would get
a 100 on Program 6.
- 5 points will be awarded for implementing a multithreaded version
of find_roots that searches the stack in parallel.
- 10 points will be awarded for being able to run gc_malloc using 2
threads.
- 15 points will be awarded for being able to search the heap in parallel.
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!
Submission
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