f763.md

Back to questions

f763: Simulating garbage collection

This question was adapted, with permission, from a question originally written by Boris Motik.

Note: This question uses the GraphNode<E> class given in question 1171, but otherwise the questions are independent; you can do this one first if you like.

Garbage collection in Java can be understood by the following analogy:

• Java objects can be understood as instances of the GraphNode class from question 1171

• The fact that an object o1 holds a reference to some other object o2 can be understood as o2 being a successor of o1

• The heap memory can be represented as a set of GraphNode object references

• The active object roots, i.e. those objects to which references are stored in the stack or static area, can be represented as another set of GraphNode object references: a subset of the heap memory references

Implement a garbage collector method that is given two sets of GraphNode objects called heapMemory and activeNodes, respectively, and that removes from the first set all objects that are not reachable starting from the second set. You can assume that all of a node's successors are non-null. It does not matter whether you use the original GraphNode<E> class of question 1171 or the version you extended with a clone() method as part of question 1171.

Test your implementation as follows:

1. Create a set of heap objects and a set of active object roots that is a subset of the heap objects. Make sure the heap contains
   some unreachable objects. Since GraphNode<E> is a generic class, you will need to choose a concrete type for E. Use Integer, and set the key of each object to a unique id.

2. Iterate through the heap, displaying the key of each object followed by the key of all of the object's successors. Also indicate those objects that are active.

3. Run your garbage collection algorithm.

4. Repeat step 2, which should demonstrate that the garbage is gone.

An example of the output your program might produce is as follows:

Before garbage collection:
  Heap contents:
    18 -> ()
    13 -> ()
    11 -> ()
    20 -> ()
    16 -> (17, 18)
    1 -> (2, 5)
    2 -> (3, 4)
    12 -> (13, 14)
    15 -> (16, 19)
    9 -> (10, 11)
    3 -> ()
    19 -> (20, 21)
    6 -> ()
    7 -> ()
    5 -> (6, 7)
    21 -> ()
    0 -> (1, 8) (ACTIVE)
    17 -> ()
    8 -> (9, 12)
    10 -> ()
    4 -> ()
    14 -> ()

After garbage collection:
  Heap contents:
    13 -> ()
    11 -> ()
    1 -> (2, 5)
    2 -> (3, 4)
    12 -> (13, 14)
    9 -> (10, 11)
    3 -> ()
    6 -> ()
    7 -> ()
    5 -> (6, 7)
    0 -> (1, 8) (ACTIVE)
    8 -> (9, 12)
    10 -> ()
    4 -> ()
    14 -> ()