Mark and Sweep Garbage Collector
- use free list, as in malloc+free, but do free automatically
- mark all reachable objects
- insert all unreachable objects into free list
How to determine reachable objects?
- start from the set of roots (e.g. live local and global variables)
- follow all reference variables in allocated objects
- compiler generates information that indicates which fields and variables are of reference type
- mark reachable objects using depth-first search
What are roots?
- global reference variables
- reference variables on stack
- inserting into a functional tree twice
- not using middle tree
- performing mark and sweep