Cars, Trains, and a Railway Station

The train algorithm divides the mature object space into fixed-sized blocks of memory, each of which is collected individually during a separate invocation of the algorithm. The name, "train algorithm," comes from the way the algorithm organizes the blocks. Each block belongs to one set. The blocks within a set are ordered, and the sets themselves are ordered. To help explain the algorithm in their original paper, Hudson and Moss called blocks "cars" and sets "trains." In this metaphor, the mature object space plays the role of a railway station. Blocks within the same set are ordered, just like cars within the same train are ordered. The sets are ordered within the mature object space much like trains might line up on track 1, track 2, track 3, and so on, at a railway station. This organization is shown graphically in Figure 9-2.

Figure 9-2. Heap organization for the train algorithm.

Trains (sets of blocks) are assigned numbers in the order in which they are created. At the railway station, therefore, the first train to arrive pulls into track 1 and becomes train 1. The next train to arrive pulls into track 2 and becomes train 2. The next train to arrive pulls into track 3 and becomes train 3, and so on. Given this numbering scheme, a smaller train number will always indicate an older train. Within a train, cars (blocks) are added only to the end of the train. The first car added to a train is car 1. The next car added to that same train is car 2. Within a single train, therefore, a smaller car number indicates an older car. This numbering scheme yields an overall order for blocks in the mature object space.

Figure 9-2 shows three trains, numbered 1, 2, and 3. Train 1 has four cars, labeled 1.1 through 1.4. Train 2 has three cars, labeled 2.1 through 2.3. And train 3 has five cars, labeled 3.1 though 3.5. This manner of labeling cars, in which labels are composed of the train number, a dot, and the car number, indicates the overall order of the blocks contained in the mature object space. Car 1.1 precedes car 1.2, which precedes car 1.3, and so on. The last car in train 1 also precedes the first car in train 2, so car 1.4 precedes car 2.1. Likewise, car 2.3 precedes car 3.1. Each time the train algorithm is invoked, it will garbage collect one and only one block: the lowest numbered block. Thus, the first time the train algorithm is invoked on the heap shown in Figure 9-2, it will collect block 1.1. The next time is invoked, it will collect block 1.2. After it collects the last block of train 1, the algorithm will at its next invocation collect the first block of train 2.

Objects arrive in the mature object space when they get old enough to be promoted from the sub-heap of a younger generation. Whenever objects are promoted into the mature object space from younger generations, they are either added to any existing train except the lowest-numbered train, or one or more new trains are created to hold them. Thus you can think of new objects arriving at the railway station in one of two ways. Either they roll up in cars that are shunted onto the end of any existing train except the lowest numbered train, or they pull into the railway station on a brand new train.