TWiki> CS361fall13 Web>Homework3 (2013-09-12, Main.jakob)EditAttach

Homework 3: a garbage collector for C

In this homework, we build a basic, conservative garbage collector for C programs. Starting from the set of root pointers present in the stack and global variables, we traverse the "object graph" (in the case of malloc, a chunk graph) to find all chunks reachable from the root. These are marked using the third lowest order bit in the size field of each chunk.

Your template provides supporting code for finding the limits of the global variable area in memory, as well as for the stack and heap areas. It also demonstrates very basic marking and sweeping. Your task is to complete the garbage collector, so that it frees all garbage, and leaves every other chunk intact.

To compile the template, type "make", and run it with ./hw3.

Performance requirements

For full points, your program should pass all tests in main.c. At present, these are not coded as actual tests, they simply output the heap size and number of free and in-use chunks. Nevertheless, your program should produce the correct values.

Runtime performance is not a major goal for this homework. However, the program should finish well within 2 seconds.

Turn-in instructions

Make all your changes to hw3.c. As in previous homeworks, export the hw3 template to your turn-in directory, add it and commit.

Topic revision: r4 - 2013-09-12 - 03:35:03 - Main.jakob
Copyright 2016 The Board of Trustees
of the University of
Helping Women Faculty Advance
Funded by NSF