The Train Algorithm

One of the potential disadvantages of garbage collection compared to the explicit freeing of objects is that garbage collection gives programmers less control over the scheduling of CPU time devoted to reclaiming memory. It is in general impossible to predict exactly when (or even if) a garbage collector will be invoked and how long it will take to run. Because garbage collectors usually stop the entire program while seeking and collecting garbage objects, they can cause arbitrarily long pauses at arbitrary times during the execution of the program. Such garbage collection pauses can sometimes be long enough to be noticed by users. Garbage collection pauses can also prevent programs from responding to events quickly enough to satisfy the requirements of real-time systems. If a garbage collection algorithm is capable of generating pauses lengthy enough to be either noticeable to the user or make the program unsuitable for real-time environments, the algorithm is said to be disruptive. To minimize the potential disadvantages of garbage collection compared to the explicit freeing of objects, a common design goal for garbage collection algorithms is to minimize or, if possible, eliminate their disruptive nature.

One approach to achieving (or at least attempting to achieve) non-disruptive garbage collection is to use algorithms that collect incrementally. An incremental garbage collector is one that, rather than attempting to find and discard all unreachable objects at each invocation, just attempts to find and discard a portion of the unreachable objects. Because only a portion of the heap is garbage collected at each invocation, each invocation should in theory run in less time. A garbage collector that can perform incremental collections, each of which is guaranteed (or at least very likely) to require less than a certain maximum amount of time, can help make a Java virtual machine suitable for real-time environments. A garbage collector that does its work in time-bounded increments is also desirable in user environments, because such a collector can eliminate garbage collection pauses that are noticeable to the user.

A common incremental collector is a generational collector, which during most invocations collects only part of the heap. As mentioned earlier in this chapter, a generational collector divides the heap into two or more generations, each of which is awarded its own sub-heap. Taking advantage of the empirical observation that most objects have very short lifetimes, a generational collector collects the sub-heaps of younger generations more often than those of older generations. Because every sub-heap except that of the most mature generation (the mature object space) can be given a maximum size, a generational collector can in general ensure that incremental collections of all but the most mature generation will complete within a certain maximum amount of time. The reason the mature object space cannot be given a maximum size is that any objects that don't fit in the sub-heaps of the younger generations must by definition go into the mature object space. Such objects have no other place to go.

The train algorithm, which was first proposed by Richard Hudson and Eliot Moss and is currently used by Sun's Hotspot virtual machine, specifies an organization for the mature object space of a generational collector. The purpose of the train algorithm is to provide time-bounded incremental collections of the mature object space.