Placement of allocation trains in the train algorithm

• US 7,035,884 B2
• Filed: 11/05/2002
• Issued: 04/25/2006
• Est. Priority Date: 11/05/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): Rodriguez, Paul L.
• Assistant Examiner(s): OSBORNE, LUKE R
• Application Number:
  US10/288,008
• Publication Number:
  US 20040088277A1
• Time in Patent Office: 1,267 Days
• Field of Search: 707/206, 707/205, 707/103.R, 707/103.X, 707/103.Y, 707/102, 707/103.Z, 718/104, 718/1, 711/159
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0276 Generational garbage collection
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

A garbage collector collects a dynamically allocated heap by employing the train algorithm, in which “car” sections of a heap generation are organized in groups, or “trains.” When a car section comes up for collection, objects that it contains are evacuated if they are referred to by references located in cars not currently being collected. The cars to which they are evacuated belong to the trains that contain the references. The trains form a sequence in which their constituent cars are to be collected, and objects that are directly allocated in the generation are placed into trains that precede some existing train in the collection sequence.

Claims

1. A method for employing a computer system that includes memory to collect garbage in accordance with the train algorithm in at least a generation of a dynamically allocated heap in the memory, the method comprising:

A) treating a generation of a collected heap in the memory as divided into car sections that belong to trains linked in a front-to-rear order;

B) collecting the generation in collection increments, in each of which a collection set of at least one car section is collected in accordance with the train algorithm such that cars in trains, which are in front of other trains in the front-to-rear order, are collected before cars in the other trains; and

C) linking cars in to a train that is linked ahead of at least one other train each of at least some cars into which objects are directly allocated;

D) objects directly allocated before a predetermined time threshold in an interval between collection increments, are allocated in a set of at least one early-object car, and those directly allocated after the predetermined time threshold in the interval are allocated in a set of at least one different, late-object car; and

E) the trains into which the at least one early-object car and at least one late-object care are linked are not the same.

2. A method as defined in claim 1 wherein:

F) each early-object car is placed in a train that contains a car belonging to the next collection set; and

G) each late-object car is placed in a train that contains no cars belonging to the next collection set.

3. A method as defined in claim 1 wherein:

F) objects directly allocated before the time threshold since the last collection increment are allocated in the set of at least one early-object car;

G) objects directly allocated after the time threshold since the last collection increment are allocated in the set of at least one late-object car; and

H) the method includes increasing the time threshold if the fraction of objects reclaimed from early-object cars is greater than a threshold-increase value and decreasing the time threshold if the fraction of objects reclaimed from early-object cars is less than a threshold-decrease value.

4. A method as defined in claim 3 wherein the threshold-increase value is different from the threshold-decrease value.

5. A method as defined in claim 1 wherein the directly allocated objects are allocated in trains that contain no objects other than directly allocated objects.

6. A method as defined in claim 1 wherein:

D) the cars that are linked in trains are linked in a front-to-rear order within their respective trains such that trains in front of other trains in the front-to-rear order are collected before those other trains; and

E) the order in which the at least some cars into which objects are directly allocated are linked into a train is the reverse of the order in which those cars were allocated.

7. 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 a generation of a dynamically allocated heap as divided into car sections that belong to trains linked in a front-to-rear order;

ii) collects the generation in collection increments, in each of which a collection set of at least one car section is collected in accordance with the train algorithm such that cars in trains which are in front of other trains in the front-to-rear order, are collected before cars in the other trains;

iii) links into a train that is linked ahead of at least one other train each of at least some cars into which objects are directly allocated;

C) objects directly allocated before a predetermined time threshold in an interval between collection increments are allocated in a set of at least one early-object car, and those directly allocated after the predetermined threshold in the interval are allocated in a set of at least one different, late-object car; and

D) the trains into which the at least one early-object car and at least one late-object car are linked are not the same.

8. A computer system as defined in claim 7 wherein:

E) each early-object car is placed in a train that contains a car belonging to the next collection set; and

F) each late-object car is placed in a train that contains no cars belonging to the next collection set.

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

E) objects directly allocated before the time threshold since the last collection cycle are allocated in the set of at least one early-object car;

F) objects directly allocated after the time threshold since the last collection cycle are allocated in the set of at least one late-object car; and

G) the garbage collector increases the time threshold if the fraction of objects reclaimed from early-object cars is greater than a threshold-increase value and decreasing the time threshold if the fraction of objects reclaimed from early-object cars is less than a threshold-decrease value.

10. A computer system as defined in claim 9 wherein the threshold-increase value is different from the threshold-decrease value.

11. A computer system as defined in claim 7 wherein the directly allocated objects are allocated in trains that contain no objects other than directly allocated objects.

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

C) the cars that are linked in trains are linked in a front-to-rear order within their respective trains such that trains that are in front of other trains in the front-to-rear order are collected before those other trains; and

D) the order in which the at least some cars into which objects are directly allocated are linked into a train is the reverse of the order in which those cars were allocated.

13. A storage medium containing instructions readable by a computer including memory to configure the computer to operate as a garbage collector that:

A) treats a generation of a dynamically allocated heap as divided into car sections that belong to trains linked in a front-to-rear order;

B) collects the generation in collection increments, in each of which a collection set of at least one car section is collected in accordance with the train algorithm such that cars in trains which are in front of other trains in the front-to-rear order, are collected before cars in the other trains;

C) links into a train that is linked ahead of at least one other train each of at least some cars into which objects are directly allocated;

C) objects directly allocated before a predetermined time threshold in an interval between collection increments are allocated in a set of at least one early-object car, and those directly allocated after the predetermined threshold in the interval are allocated in a set of at least one different, late-object car; and

D) the trains into which the at least one early-object car and at least one late-object car are linked are not the same.

14. A storage medium as defined in claim 13 wherein:

F) each early-object car is placed in a train that contains a car belonging to the next collection set; and

G) each late-object car is placed in a train that contains no cars belonging to the next collection set.

15. A storage medium as defined in claim 13 wherein:

F) objects directly allocated before the time threshold since the last collection cycle are allocated in the set of at least one early-object car;

G) objects directly allocated after the time threshold since the last collection cycle are allocated in the set of at least one late-object car; and

H) the garbage collector increases the time threshold if the fraction of objects reclaimed from early-object cars is greater than a threshold-increase value and decreasing the time threshold if the fraction of objects reclaimed from early-object cars is less than a threshold-decrease value.

16. A storage medium as defined in claim 15 wherein the threshold-increase value is different from the threshold-decrease value.

17. A storage medium as defined in claim 13 wherein the directly allocated objects are allocated in trains that contain no objects other than directly allocated objects.

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

D) the cars that are linked in trains are linked in a front-to-rear order within their respective trains such that cars, which are in front of other cars in the front-to-rear order, are collected before the other cars; and

E) the order in which the at least some cars into which objects are directly allocated are linked into a train is the reverse of the order in which those cars were allocated.

19. A computer program product comprising a tangible computer usable medium having computer readable program code thereon representing sequences of instructions that, when executed by a computer system including memory, cause it to operate as a garbage collector that:

A) treats a generation of a dynamically allocated heap as divided into car sections that belong to trains linked in a front-to-rear order;

B) collects the generation in collection increments, in each of which a collection set of at least one car section is collected in accordance with the train algorithm such that cars in trains which are in front of other trains in the front-to-rear order, are collected before cars in the other trains;

C) links into a train that is linked ahead of at least one other train each of at least some cars into which objects are directly allocated;

C) objects directly allocated before a predetermined time threshold in an interval between collection increments are allocated in a set of at least one early-object car, and those directly allocated after the predetermined threshold in the interval are allocated in a set of at least one different, late-object car; and

D) the trains into which the at least one early-object car and at least one late-object car are linked are not the same.

20. A computer program product as defined in claim 19 wherein:

F) each early-object car is placed in a train that contains a car belonging to the next collection set; and

G) each late-object car is placed in a train that contains no cars belonging to the next collection set.

21. A computer program product as defined in claim 19 wherein:

F) objects directly allocated before the time threshold since the last collection cycle are allocated in the set of at least one early-object car;

G) objects directly allocated after the time threshold since the last collection cycle are allocated in the set of at least one late-object car; and

H) the garbage collector increases the time threshold if the fraction of objects reclaimed from early-object cars is greater than a threshold-increase value and decreasing the time threshold if the fraction of objects reclaimed from early-object cars is less than a threshold-decrease value.

22. A computer program product as defined in claim 21 wherein the threshold-increase value is different from the threshold-decrease value.

23. A computer program product as defined in claim 19 wherein the directly allocated objects are allocated in trains that contain no objects other than directly allocated objects.

24. A computer program product as defined in claim 19 wherein:

D) the cars that are linked in trains are linked in a front-to-rear order within their respective trains such that trains that are in front of other trains in the front-to-rear order are collected before those other trains; and

E) the order in which the at least some cars into which objects are directly allocated are linked into a train is the reverse of the order in which those cars were allocated.

25. A garbage collector program operation in the memory of a computer and comprising:

A) means for treating a generation of a collected heap in a computer system'"'"'s memory as divided in car section that belong to trains linked in front-to-rear order;

B) collecting the generation in collection increments, in each of which a collection set of at least one car section is collected in accordance with the train algorithm such that cars in trains, which are in front of other trains in the front-to-rear order are collected before cars in the other trains;

C) linking into a train that is linked ahead of at least one other train each of at least some cars into which objects are directly allocated;

D) objects directly allocated before a predetermined time threshold in an interval between collection increments are allocated in a set of at least one early-object car, and those directly allocated after the predetermined threshold in the interval are allocated in a set of at least one different, late-object car; and

E) the trains into which the at least one early-object car and at least one late-object car are linked are not the same.