Merging trains in a collector based on the train algorithm
First Claim
Patent Images
1. A method for employing a computer system that includes memory to operate as a garbage collector, which examines the memory to find and reclaim unused memory, the method comprising:
- A) treating a generation in the memory as divided into car sections organized into a set of trains;
B) collecting unused memory in the generation in accordance with the train algorithm in increments with which respective collection sets of objects are associated, in at least some of which the garbage collector determines for at least one train whether any references located outside that train refer to objects within that train and reclaims as unused, memory in the car sections belonging to that train if there are no such references, and in at least some of which the garbage collector evacuates to respective trains containing references outside the collection set any objects in the collection set referred to thereby and reclaims as unused, memory in the remaining collection set;
C) making a determination of whether at least one set of train-merging criteria is met; and
D) if any said set of train-merging criteria is met, combining a plurality of the existing trains into a single train.
2 Assignments
0 Petitions
Accused Products
Abstract
A garbage collector that employs the train algorithm determines whether futile collections have been occurring or the number of trains has reached a maximum. When either situation occurs, it merges a plurality of existing trains into a single new train. If the collector detects futile collection, it merges the oldest train with one of the other trains. If the number of trains reaches a maximum, the collection so merges trains that the next train addition will not cause the number of trains to exceed the maximum.
-
Citations
43 Claims
-
1. A method for employing a computer system that includes memory to operate as a garbage collector, which examines the memory to find and reclaim unused memory, the method comprising:
-
A) treating a generation in the memory as divided into car sections organized into a set of trains; B) collecting unused memory in the generation in accordance with the train algorithm in increments with which respective collection sets of objects are associated, in at least some of which the garbage collector determines for at least one train whether any references located outside that train refer to objects within that train and reclaims as unused, memory in the car sections belonging to that train if there are no such references, and in at least some of which the garbage collector evacuates to respective trains containing references outside the collection set any objects in the collection set referred to thereby and reclaims as unused, memory in the remaining collection set; C) making a determination of whether at least one set of train-merging criteria is met; and D) if any said set of train-merging criteria is met, combining a plurality of the existing trains into a single train. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
-
-
15. A computer system that includes memory and comprises:
-
A) processor circuitry operable to execute processor instructions; and B) memory circuitry, to which the processor circuitry is responsive, that contains processor instructions readable by the processor circuitry to configure the computer system as a garbage collector that; i) treats a generation in the memory as divided into car sections organized into a set of trains; ii) collects the generation in accordance with the train algorithm in increments with which respective collection sets of objects are associated, in at least some of which the garbage collector determines for at least one train whether any references located outside that train refer to objects within that train and reclaims the car sections belonging to that train if there are no such references, and in at least some of which the garbage collector evacuates to respective trains containing references outside the collection set any objects in the collection set referred to thereby and reclaims the remaining collection set; iii) makes a determination of whether at least one set of train-merging criteria is met; and iv) if any said set of train-merging criteria is met, combines a plurality of the existing trains into a single train. - View Dependent Claims (16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28)
-
-
29. A storage medium containing instructions readable by a computer to configure the computer to operate as a garbage collector that
A) treats a generation in the memory as divided into car sections organized into a set of trains; -
B) collects the generation in accordance with the train algorithm in increments with which respective collection sets of objects are associated, in at least some of which the garbage collector determines for at least one train whether any references located outside that train refer to objects within that train and reclaims the car sections belonging to that train if there are no such references, and in at least some of which the garbage collector evacuates to respective trains containing references outside the collection se any objects in the collection set referred to thereby and reclaims the remaining collection set; C) makes a determination of whether at least one set of train-merging criteria is met; and D) if any said set of train-merging criteria is met, combines a plurality of the existing trains into a single train. - View Dependent Claims (30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42)
-
-
43. A garbage collector operating in the memory of a computer system to find and reclaim unused memory, the garbage collector comprising:
-
A) means for treating a generation in the memory as divided into car sections organized into a set of trains; B) means for collecting unused memory in the generation in accordance with the train algorithm in increments with which respective collection sets of objects are associated, in at least some of which the garbage collector determines for at least one train whether any references located outside that train refer to objects within that train and reclaims as unused, memory in the car sections belonging to that train if there are no such references, and in at least some of which the garbage collector evacuates to respective trains containing references outside the collection set any objects in the collection set referred to thereby and reclaims as unused, memory in the remaining collection set; C) means for making a determination of whether at least one set of train merging criteria is met; and D) means for combining a plurality of the existing trains into a single train if any said set of train-merging criteria is met.
-
Specification