Handling futile collections in the train algorithm through selective extension of the collection set

摘要

In incremental garbage collectors based on the Train algorithm a futile condition may exist where the collector never finishes collecting an old train. The present invention provides an expanded collection set of a younger car with an object referenced from another train. That reference will be found by scanning the remembered sets of other car. If no such younger car is found, then a younger car with an external reference may be added to the collection set. One of these other cars is added to the collection set and, if there are no other changes, the collection will reduce the volume in the train being collected and therefore break the futile situation.