Advancing cars in trains managed by a collector based on the train algorithm

• US 7,085,790 B2
• Filed: 12/06/2002
• Issued: 08/01/2006
• Est. Priority Date: 12/06/2002
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Garthwaite, Alexander T.
• Primary Examiner(s): Robinson, Greta
• Assistant Examiner(s): Veillard, Jacques
• Application Number:
  US10/313,476
• Publication Number:
  US 20040111444A1
• Time in Patent Office: 1,334 Days
• Field of Search: 707/1, 707/100, 707/103.R, 707/200, 707/203, 707/206, 707/205, 711/6, 711/133, 711/136, 711/160, 711170-173
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0276 Generational garbage collection
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99957 Garbage collection

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.

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) when a given car section satisfies a set of at least one advancement criterion, advances the given car section in the collection order; and

vii) collects the car sections in increments in which the garbage collector uses the remembered sets to identify reachable objects and reclaims memory occupied by objects not identified as reachable; and

C) employing the computer system to execute the garbage collector.

2. A method as defined in claim 1 wherein:

D) the car sections are organized into trains on which the collection order is imposed;

E) the collector collects the cars in accordance with the train algorithm; and

F) car sections that are not in the oldest train are sometimes advanced in the collection order.

3. A method as defined in claim 1 wherein:

D) the garbage collector maintains for each car section metadata associated therewith that give that car section'"'"'s nominal position in the collection order; and

E) the advancing of the given car section does not include updating the metadata associated therewith to change the car section'"'"'s nominal position in the collection order.

4. A method as defined in claim 3 wherein:

F) the remembered sets associated with car sections that have not been advanced in the collection order contain entries only for references located in younger cars; and

G) the remembered set associated with a car section that has been advanced ahead of other car sections additionally includes entries for any references in those other car sections that refer to objects in the advanced car.

5. A method as defined in claim 4 wherein, for at least one car section that has been advanced in the collection order:

H) the remembered set associated therewith is stored in a plurality of remembered-set structures; and

I) each of that advanced car section'"'"'s remembered-set entries for references located in car sections older than that advanced car section is stored in a remembered-set structure separate from the remembered-set structure in which any entry is stored for a reference located in a car section older than that advanced car section.

6. A method as defined in claim 1 wherein:

D) the garbage collector maintains for each car section metadata associated therewith that give that car section'"'"'s nominal position in the collection order; and

E) the advancing of the given car section includes updating the metadata associated therewith to change the car section'"'"'s nominal position in the collection order.

7. A method as defined in claim 1 wherein one advancement criterion in the set of at least one advancement criterion is that the size of the remembered set associated with the given car exceed a remembered-set size limit.

8. A method as defined in claim 1 wherein one advancement criterion in the set of at least one advancement criterion is that the number of entries in the remembered set associated with the given car exceed an entry limit.

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) when a given car section satisfies a set of at least one advancement criterion, advances the given car section in the collection order; and

vii) collects the car sections in increments in which the garbage collector uses the remembered sets to identify reachable objects and reclaims memory occupied by objects not identified as reachable.

10. A computer system as defined in claim 9 wherein:

C) the car sections are organized into trains on which the collection order is imposed;

D) the collector collects the cars in accordance with the train algorithm; and

E) car sections that are not in the oldest train are sometimes advanced in the collection order.

11. A computer system as defined in claim 9 wherein:

C) the garbage collector maintains for each car section metadata associated therewith that give that car section'"'"'s nominal position in the collection order; and

D) the advancing of the given car section does not include updating the metadata associated therewith to change the car section'"'"'s nominal position in the collection order.

12. A computer system as defined in claim 11 wherein:

E) the remembered sets associated with car sections that have not been advanced in the collection order contain entries only for references located in younger cars; and

F) the remembered set associated with a car section that has been advanced ahead of other car sections additionally includes entries for any references in those other car sections that refer to objects in the advanced car.

13. A computer system as defined in claim 12 wherein, for at least one car section that has been advanced in the collection order:

G) the remembered set associated therewith is stored in a plurality of remembered-set structures; and

H) each of that advanced car section'"'"'s remembered-set entries for references located in car sections older than that advanced car section is stored in a remembered-set structure separate from the remembered-set structure in which any entry is stored for a reference located in a car section older than that advanced car section.

14. A computer system as defined in claim 9 wherein:

D) the garbage collector maintains for each car section metadata associated therewith that give that car section'"'"'s nominal position in the collection order; and

E) the advancing of the given car section includes updating the metadata associated therewith to change the car section'"'"'s nominal position in the collection order.

15. A computer system as defined in claim 9 wherein one advancement criterion in the set of at least one advancement criterion is that the size of the remembered set associated with the given car exceed a remembered-set size limit.

16. A computer system as defined in claim 9 wherein one advancement criterion in the set of at least one advancement criterion is that the number of entries in the remembered set associated with the given car exceed an entry limit.

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) when a given car section satisfies a set of at least one advancement criterion, advances the given car section in the collection order; and

G) collects the car sections in increments in which the garbage collector uses the remembered sets to identify reachable objects and reclaims memory occupied by objects not identified as reachable.

18. A storage medium as defined in claim 17 wherein:

H) the car sections are organized into trains on which the collection order is imposed;

I) the collector collects the cars in accordance with the train algorithm; and

J) car sections that are not in the oldest train are sometimes advanced in the collection order.

19. A storage medium as defined in claim 17 wherein:

H) the garbage collector maintains for each car section metadata associated therewith that give that car section'"'"'s nominal position in the collection order; and

I) the advancing of the given car section does not include updating the metadata associated therewith to change the car section'"'"'s nominal position in the collection order.

20. A storage medium as defined in claim 19 wherein:

J) the remembered sets associated with car sections that have not been advanced in the collection order contain entries only for references located in younger cars; and

K) the remembered set associated with a car section that has been advanced ahead of other car sections additionally includes entries for any references in those other car sections that refer to objects in the advanced car.

21. A storage medium as defined in claim 20 wherein, for at least one car section that has been advanced in the collection order:

L) the remembered set associated therewith is stored in a plurality of remembered-set structures; and

M) each of that advanced car section'"'"'s remembered-set entries for references located in car sections older than that advanced car section is stored in a remembered-set structure separate from the remembered-set structure in which any entry is stored for a reference located in a car section older than that advanced car section.

22. A storage medium as defined in claim 17 wherein:

H) the garbage collector maintains for each car section metadata associated therewith that give that car section'"'"'s nominal position in the collection order; and

I) the advancing of the given car section includes updating the metadata associated therewith to change the car section'"'"'s nominal position in the collection order.

23. A storage medium as defined in claim 17 wherein one advancement criterion in the set of at least one advancement criterion is that the size of the remembered set associated with the given car exceed a remembered-set size limit.

24. A storage medium as defined in claim 17 wherein one advancement criterion in the set of at least one advancement criterion is that the number of entries in the remembered set associated with the given car exceed an entry limit.

25. A garbage collector operating in a memory of a computer system and 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 operable when a given car section satisfies a set of at least one advancement criterion for advancing the given car section in the collection order; and

G) means for collecting the car sections in increments in which the garbage collector uses the remembered sets to identify reachable objects and reclaims memory occupied by objects not identified as reachable.