×

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

  • US 6,185,581 B1
  • Filed: 08/19/1999
  • Issued: 02/06/2001
  • Est. Priority Date: 08/19/1999
  • Status: Active Grant
First Claim
Patent Images

1. 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.

View all claims
  • 2 Assignments
Timeline View
Assignment View
    ×
    ×