Advancing cars in trains managed by a collector based on the train algorithm
First Claim
1. For performing garbage collection, a method comprising:
- A) providing a computer system that includes memory;
B) configuring the computer system to act as a garbage collector that;
i) treats at least a portion of a garbage-collected heap in the computer system'"'"'s memory as divided into car sections;
ii) searches the car sections for references;
iii) maintains for each car section a remembered set associated therewith that contains entries representing locations where references have thereby been detected that refer to objects located in that car section;
iv) imposes upon the car sections a collection order from older to younger;
v) determines whether a given car section satisfies a set of at least one advancement criterion;
vi) if it does, advances the given car section in the collection order; and
vii) collects the car sections in increments in which it uses the remembered sets to identify potentially reachable objects and reclaims memory occupied by objects not identified as potentially reachable; and
C) employing the computer system to execute the garbage collector.
2 Assignments
0 Petitions
Accused Products
Abstract
In a garbage collector that employs the train algorithm, the collector identifies cars that are located far back in the collection order but already have large remembered sets, and it advances their collection. One way of doing so includes advancing a car'"'"'s nominal position in the collection order, placing it nominally ahead of erstwhile “older” cars as well as actually. Another way does not include changing the advanced car'"'"'s nominal position. The advancement operation is simpler with the latter approach, but normal updating is simpler with the former. Although both approaches tend to increase the number of entries in the remembered set of the car thus advanced, they actually reduce the overall memory cost of remembered-set maintenance.
-
Citations
33 Claims
-
1. For performing garbage collection, a method comprising:
-
A) providing a computer system that includes memory;
B) configuring the computer system to act as a garbage collector that;
i) treats at least a portion of a garbage-collected heap in the computer system'"'"'s memory as divided into car sections;
ii) searches the car sections for references;
iii) maintains for each car section a remembered set associated therewith that contains entries representing locations where references have thereby been detected that refer to objects located in that car section;
iv) imposes upon the car sections a collection order from older to younger;
v) determines whether a given car section satisfies a set of at least one advancement criterion;
vi) if it does, advances the given car section in the collection order; and
vii) collects the car sections in increments in which it uses the remembered sets to identify potentially reachable objects and reclaims memory occupied by objects not identified as potentially reachable; and
C) employing the computer system to execute the garbage collector. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. A computer system comprising:
-
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 at least a portion of a garbage-collected heap in the computer system'"'"'s memory as divided into car sections;
ii) searches the car sections for references;
iii) maintains for each car section a remembered set associated therewith that contains entries representing locations where references have thereby been detected that refer to objects located in that car section;
iv) imposes upon the car sections a collection order from older to younger;
v) determines whether a given car section satisfies a set of at least one advancement criterion;
vi) if it does, advances the given car section in the collection order; and
vii) collects the car sections in increments in which it uses the remembered sets to identify potentially reachable objects and reclaims memory occupied by objects not identified as potentially reachable. - View Dependent Claims (10, 11, 12, 13, 14, 15, 16)
-
-
17. A storage medium containing instructions readable by a computer to configure the computer to operate as a garbage collector that:
-
A) treats at least a portion of a garbage-collected heap in the computer system'"'"'s memory as divided into car sections;
B) searches the car sections for references;
C) maintains for each car section a remembered set associated therewith that contains entries representing locations where references have thereby been detected that refer to objects located in that car section;
D) imposes upon the car sections a collection order from older to younger;
E) determines whether a given car section satisfies a set of at least one advancement criterion;
F) if it does, advances the given car section in the collection order; and
G) collects the car sections in increments in which it uses the remembered sets to identify potentially reachable objects and reclaims memory occupied by objects not identified as potentially reachable. - View Dependent Claims (18, 19, 20, 21, 22, 23, 24)
-
-
25. An electromagnetic signal representing sequences of instructions that, when executed by a computer system that includes memory, cause it to operate as a garbage collector that:
-
A) treats at least a portion of a garbage-collected heap in the computer system'"'"'s memory as divided into car sections;
B) searches the car sections for references;
C) maintains for each car section a remembered set associated therewith that contains entries representing locations where references have thereby been detected that refer to objects located in that car section;
D) imposes upon the car sections a collection order from older to younger;
E) determines whether a given car section satisfies a set of at least one advancement criterion;
F) if it does, advances the given car section in the collection order; and
G) collects the car sections in increments in which it uses the remembered sets to identify potentially reachable objects and reclaims memory occupied by objects not identified as potentially reachable. - View Dependent Claims (26, 27, 28, 29, 30, 31, 32)
-
-
33. A garbage collector comprising:
-
A) means for treating at least a portion of a garbage-collected heap in a computer system'"'"'s memory as divided into car sections;
B) means for searching the car sections for references;
C) means for maintaining for each car section a remembered set associated therewith that contains entries representing locations where references have thereby been detected that refer to objects located in that car section;
D) means for imposing upon the car sections a collection order from older to younger;
E) means for determining whether a given car section satisfies a set of at least one advancement criterion;
F) means for, if it does, advancing the given car section in the collection order; and
G) means for collecting the car sections in increments in which it uses the remembered sets to identify potentially reachable objects and reclaims memory occupied by objects not identified as potentially reachable.
-
Specification