something completely different from what the object thought it referenced. This situation could cause all
manner of havoc when the program uses the values in that space as if they were part of something they are
not. Garbage collection solves the dangling reference problem for you because an object that's still referenced
somewhere will never be garbage-collected and so will never be considered free. Garbage collection also
solves the problem of accidentally deleting an object multiple timessomething that can also cause havoc.
Garbage is collected without your intervention, but collecting garbage still takes work. Creating and collecting
large numbers of objects can interfere with time-critical applications. You should design such systems to be
judicious in the number of objects they create and so reduce the amount of garbage to be collected.
Garbage collection is not a guarantee that memory will always be available for new objects. You could create
objects indefinitely, place them in lists, and continue doing so until there is no more space and no
unreferenced objects to reclaim. You could create a memory leak by, for example, allowing a list of objects to
refer to objects you no longer need. Garbage collection solves many, but not all, memory allocation problems.
17.2. A Simple Model
Garbage collection is easier to understand with an explicit model so this section describes a simple one, but
practical garbage collectors are far more sophisticated. Garbage collection is logically split into two phases:
separating live objects from dead objects and then reclaiming the storage of the dead ones. Live objects are
those that are reachable from running codethe objects that some action of your code can still potentially use.
Dead objects are the garbage that can be reclaimed.
One obvious model of garbage collection is reference counting: When object X references object Y, the
system increments a counter on Y, and when X drops its reference to Y, the system decrements the counter.
When the counter reaches zero, Y is no longer live and can be collected, which will decrement the counts of
any other objects to which Y refers.
Reference counting fails in the face of cycles, in which loops are created in the references. If X and Y
reference each other, neither object's counter will ever become zero, and so neither X nor Y will ever be
collected, nor will anything to which either object refers, directly or indirectly. Most garbage collectors do not
use reference counting for this and other reasons.
The simplest model of garbage collection not subject to this problem is called mark-and-sweep. The name
refers to the way the two phases of garbage collection are implemented. To find which objects are live, the
garbage collector first determines a set of roots that contains the directly reachable objects: References in local
variables on the stack, for example, are reachable because you can use those variables to manipulate the
object. Objects referred to by local variables are therefore clearly live.
Once a set of roots is determined, the collector will mark the objects referenced by those roots as reachable. It
will then examine references in each of those objects. If an object referred to by such a reference is already
marked reachable from the first step, it is ignored. Otherwise. the object is marked reachable and its references
are examined. This process continues until no more reachable objects remain unmarked. After this marking
process is complete, the collector can reclaim the dead objects (those which are not marked) by sweeping
them away.
Any change to the interconnection of objects during a run of mark-and-sweep will clearly interfere with the
collection process. A marking run can miss an object that was unreachable at the beginning of the marking
process, but which is assigned to a reachable reference in the middle. Running a basic mark-and-sweep pass
requires freezing execution of the program, at least during the marking phase.
There are other problems with mark-and-sweep. Garbage collection is a complex area of research with no
easy or universal answers. We present mark-and-sweep as a relatively simple mental model for you to use to