[2021] CS3214 Computer Systems - Exercise 4: Mark-and-Sweep Garbage Collection
Exercise 4
Due: Seewebsiteforduedate. Whattosubmit: Seewebsite.
The theme of this exercise is automatic memory management and leak detection. Part 3 requires the installation of software on your personal machine.
1. Mark-and-Sweep Garbage Collection
The first part of the exercise involves a small programming exercise that is intended to deepen your understanding of how a garbage collector works. You are asked to imple- ment a variant of a mark-and-sweep collector using a synthetic heap dump given as input. Ontheheap,therearenobjectsnumbered0...n−1withsizess0 ...sn−1. Alsogivenare r roots and m pointers, i.e., references stored in objects that refer to other objects.
Write a program that performs a mark-and-sweep collection and outputs the total size of the live heap as well as the total amount of memory a mark-and-sweep collector would sweep if this heap were garbage collected.
In addition, report the retained heap size for each of the roots. The retained heap size is the additional number of bytes that could be freed if this (and only this) root were removed from the graph and the garbage collection were repeated. Note that removing a root will also remove all of its outgoing edges.
We will do this problem programming competition style. Write a program - in any lan- guage you choose1 – that reads a heap description and outputs the size of the live heap and the amount of garbage swept if a garbage collection is performed. Then output the retained heap size for each root in the order in which they are given in the input.
As is customary for Unix programs, your program should read from its standard input stream. Each invocation of your program should process a single test case. The first line contains three non-negative 32-bit integers n, m, r such that r ≤ n. The second line contains n positive 32-bit integers si that denote the size si of object i. Following that are m lines with tuples i, j for which 0 ≤ i, j < n, each of which denotes a pair of object indices. A tuple (i,j) means that object i stores a reference to object j, keeping it alive (provided si is reachable from a root). The description of the references is followed by a single line with r integers denoting the roots of the reachability graph R0 . . . Rr−1. Nodes designated as roots do not have incoming edges that point to them.
Your program should write to its standard output stream R + 1 lines. On the first, it should output two numbers l s, where l represents the total size of the live heap and s represents the amount of garbage that would be swept if the heap were collected. On the following lines, for each root, it should output how much (additional) memory could be freed if this root were removed, in the order in which the roots appear in the input. In
Figure 1: The reachability graph given in the sample input. Roots are shown using double circles. The numbers in parentheses are the sizes of individual nodes. Here, root 9 keeps alive object 8, which keeps 1 and 6 alive, which in turn keep 14. Root 12 keeps object 7 alive from which objects 0, 3, 10, and 11 are reachable. Note that in this example each root spans a different, disjoint subtree. This is not the case in general. Be sure you create test cases for which the sets of nodes that are reachable from each root overlap.
other words, compute the size of the additional garbage that would be produced if said root were removed.
Sample Input:
15 15 2
8 10 27 21 13 35 33 18 33 0 25 36 0 20 13 11 10
6 14
5 14
70
11 7
81
2 11
86
48
12 7
98
13 6
1 14
7 11
03
9 12
Sample Output:
197 95 89
108
Figure 1 shows the reachability graph for the sample input/output.
We will test your program on additional inputs. Your algorithm should have a complexity of at most O(R × (m + n)) where R is the number of roots, n is the number of nodes,
and m is the number of edges. You should further implement your algorithm under the 2
assumption that the graph is sparse, that is, m ≪ n .
Extra credit: Write an algorithm with a complexity of no worse than O((m + n) × log n)
where n is the number of nodes and m is the number of edges.
FAQ
• Can I use graph library X, Y, or Z?
You may consult such code for reference, but do not use it directly. Keep in mind that tasks like these are tasks you may be asked during a programming interview where you also would need to be able to produce this code without the aid of aux- iliary libraries.
