University of Virginia, Department of Computer Science
CS201J: Engineering Software, Fall 2002

Notes: Tuesday 5 November 2002

Garbage Collection

Mark and Sweep
active = all objects on stack
while (!active.isEmpty ()) 
    newactive = { }
    foreach (Object a in active) 
        mark a as reachable 
        foreach (Object o that a points to) 
           if o is not marked
              newactive = newactive U { o }
    active = newactive  
sweep () // remove unmarked objects on heap       
What are the advantages of Stop and Copy over Mark and Sweep?

What are the disadvantages of Stop and Copy?

What are the advantages of Reference Counting?

Why does multi-threading make garbage collection difficult?

If we had unlimited memory, is garbage collection still important?

Code excerpt for GC example:

public class Phylogeny {
   static public void main (String args[]) {
      SpeciesSet ss = new SpeciesSet ();
      ... (open file for reading) 
      while (not end of file) {
         Species current = new Species (name from file, genome from file);
         ss.insert (current);

public class SpeciesSet { 
   private Vector els; 
   public void insert (/*@non_null@*/ Species s) {
       if (getIndex (s) < 0) els.add (s); } 

CS201J University of Virginia
Department of Computer Science
CS 201J: Engineering Software
Sponsored by the
National Science Foundation