US 6,185,581 B2Granted

Train-algorithm-based garbage collector employing fixed-size remembered sets

AssigneeSun Microsystems, Inc.

InventorAlexander T. Garthwaite

Life of this patent

Estimating the term…

Loading patent…

Abstract

A garbage collector collects a generation of a collected heap in accordance with the train algorithm. It employs remembered sets associated with respective car sections to keep track of references into the associated car sections. Each remembered set contains entries that identify respective regions in the generation that contain references into the associated car section. A limit is imposed on the number of entries in the remembered sets used to keep track of references to objects in certain car sections that contain only a single object each. An object in any such car section whose remembered set has more than a threshold number of entries is treated as reachable and relinked into a younger train without having the memory regions that those entries identify searched for valid references.

Claims14

Dependent claims

A method of garbage collection that includes treating a generation of a collected heap as divided into car sections that belong to trains in such a manner as to impose a collection sequence, maintaining remembered sets, associated with respective car sections, of remembered-set entries that identify regions containing inter-car references to objects contained in car sections with which those remembered sets are respectively associated, performing a remembered-set-update process by searching through the generation for references into the car sections with which the remembered sets are associated and adding to the remembered sets remembered-set entries that identify regions thereby found in car sections less forward in the collection sequence than the car sections with which the remembered sets are associated, and collecting the generation in collection cycles, in each of which a collection set of at least one car section is collected in accordance with the train algorithm and the remembered sets associated with each car section of the collection set are processed to identify objects that will survive the collection cycle, and wherein:

A) when the number of remembered-set entries in at least one, given remembered set associated with one, given car section that contains only a single, given object has reached a predetermined maximum, the remembered-set-update process includes increasing the number of remembered-set entries in the given remembered set no further;
and
B) when the given car section's turn for collection arrives and the regions identified by the given remembered set contain less than all the references to the given object found during the update process in car sections less forward than the given car section, the given car section is linked into a train independently of which regions identified by the given remembered set still contain references to the given object.

A garbage collector that treats a generation of a collected heap as divided into car sections, so links the car sections into trains as to impose a collection sequence on the car sections, maintains remembered sets, associated with respective car sections, of remembered-set entries that identify regions containing inter-car references to objects contained in the car sections with which those remembered sets are respectively associated, performs a remembered-set-update process by searching through the generation for references into the car sections with which the remembered sets are associated and adding to the remembered sets remembered-set entries that identify regions thereby found in car sections less forward in the collection sequence than the car sections with which the remembered sets are associated, and collects the generation in accordance with the collection sequence in collection cycles, in each of which the garbage collector collects a collection set of at least one car section in accordance with the train algorithm and processes the remembered sets associated with each car section of the collection set to identify objects that will survive the collection cycle, and wherein:

A) the garbage collector limits to a predetermined maximum the number of remembered-set entries in at least a given remembered set associated with a respective, given car section that contains a given object set of at least one object in such a manner as to permit the given remembered set to omit an entry that identifies a region, located in a car section farther forward than the given car section, that contains a reference to an object in the given object set;
and
B) when the collection sequence reaches the given car section, the garbage collector's processing of the given remembered set comprises:
i) making a remembered-set-omission determination of whether the remembered set may omit an entry that identifies a region, located in a car section farther forward than the given car section, that contains a reference to an object in the given object set;
and
ii) if so, linking the given car section into a train independently of which regions identified by the given remembered set contain references to the given set.

3 more elements

Dependencies are inferred from the claim text.