Merging trains in a collector based on the train algorithm

• US 7,188,129 B2
• Filed: 11/15/2002
• Issued: 03/06/2007
• Est. Priority Date: 11/15/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): Vo; Tim
• Assistant Examiner(s): MORRISON, JAY A
• Application Number:
  US10/295,280
• Publication Number:
  US 20040098553A1
• Time in Patent Office: 1,572 Days
• Field of Search: 707/104.1, 707/200, 707/103.R, 707/202, 707/205, 707/206, 711/159, 711/165, 711/171, 711/173, 711/140, 711/148
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0276 Generational garbage collection
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99957 Garbage collection

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.

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.

2. A method as defined in claim 1 wherein:

E) the garbage collector adds a train from time to time to the set of trains;

F) one said set of train-merging criteria includes the criterion that the number of said trains in the set thereof be equal to a predetermined maximum number of trains;

G) the determination of whether that set of train-merging criteria is met is made when a train is to be added to a plurality thereof and

H) when that set of criteria is met, the combining of the plurality of existing trains occurs before the train is added, whereby the number of trains is prevented from exceeding the maximum number of trains.

3. A method as defined in claim 1 wherein the collector imposes a front-to-rear order on trains in the set of trains and trains farthest to the rear in the set of trains are the plurality of trains combined into the single train.

4. A method as defined in claim 1 wherein the garbage collector compares the number of cars in at least one group of existing trains with a predetermined limit value and adopts a group whose number of cars has thus been compared as the plurality of existing trains to be combined only if the number of cars in that group does not exceed the limit value.

5. A method as defined in claim 1 wherein the garbage collector imposes a front-to-rear order on trains in the set of trains and one said set of train-merging criteria includes the criterion that the number of car sections belonging to a train farthest forward in the set of trains has failed to be reduced by a predetermined car-reduction minimum within a maximum number of collection increments.

6. A method as defined in claim 5 wherein the car-reduction minimum is one car section.

7. A method as defined in claim 5 wherein the maximum number of collection increments is a function of the number of car sections that belong to the farthest-forward train.

8. A method as defined in claim 5 wherein the farthest forward of the trains in the train set is included in the plurality of trains combined into the single train.

9. A method as defined in claim 1 wherein the garbage collector imposes a front-to-rear order on trains in the set of trains and one said set of train-merging criteria includes the criterion that the volume of objects located in car sections belonging to a train farthest forward in the set of trains has failed to be reduced by a predetermined volume-reduction minimum within a maximum number of collection increments.

10. A method as defined in claim 9 wherein the train farthest forward in the set of trains is included in the plurality of trains combined into the single train.

11. A method as defined in claim 9 wherein the maximum number of collection increments is a function of the number of car sections that belong to the farthest-forward train.

12. A method as defined in claim 1 wherein the garbage collector imposes a front-to-rear order on trains in the set of trains and one said set of train-merging criteria includes the criterion that the number of objects evacuated to car sections belonging to trains other than a train farthest forward in the set of trains has failed to reach a predetermined evacuation minimum within a maximum number of collection increments.

13. A method as defined in claim 12 wherein the train farthest forward in the set of trains is included in the plurality of trains combined into the single train.

14. A method as defined in claim 1 wherein the garbage collector imposes a front-to-rear order on trains in the set of trains and a farthest forward train in the set of trains is included in the plurality of trains combined into the single train.

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.

16. A computer system as defined in claim 15 wherein:

C) the garbage collector adds a train from time to time to the set of trains;

D) one said set of train-merging criteria includes the criterion that the number of said trains in the set thereof be equal to a predetermined maximum umber of trains;

E) the determination of whether that set of train-merging criteria is met is made when a train is to be added to a plurality thereof and

F) when that set of criteria is met, the combining of the plurality of existing trains occurs before the train is added, whereby the number of trains is prevented from exceeding the maximum number of trains.

17. A computer system as defined in claim 15 wherein the collector imposes a front to-rear order on trains in the set of trains and trains farthest to the rear in the set of trains are the plurality of trains combined into the single train.

18. A computer system as defined in claim 15 wherein the garbage collector compares the number of cars in at least one group of existing trains with a predetermined limit value and adopts a group whose number of cars has thus been compared as the plurality of existing trains to be combined only if the number of cars in that group does not exceed the limit value.

19. A computer system as defined in claim 15 wherein the garbage collector imposes a front-to-rear order on trains in the set of trains and one said set of train-merging criteria includes the criterion that the number of car sections belonging to a train farthest forward in the set of trains has failed to be reduced by a predetermined car-reduction minimum within a maximum number of collection increments.

20. A computer system as defined in claim 19 wherein the car-reduction minimum is one car section.

21. A computer system as defined in claim 19 wherein the maximum number of collection increments is a function of the number of car sections that belong to the farthest-forward train.

22. A computer system as defined in claim 19 wherein the farthest forward of the trains in the train set is included in the plurality of trains combined into the single train.

23. A computer system as defined in claim 15 wherein the garbage collector imposes a front-to-rear order on trains in the set of trains and one said set of train-merging criteria includes the criterion that the volume of objects located in car sections belonging to a train farthest forward in the set of trains has failed to be reduced by a predetermined volume-reduction minimum within a maximum number of collection increments.

24. A computer system as defined in claim 23 wherein the train farthest forward in the set of trains is included in the plurality of trains combined into the single train.

25. A computer system as defined in claim 23 wherein the maximum number of collection increments is a function of the number of car sections that belong to the farthest-forward train.

26. A computer system as defined in claim 15 wherein the garbage collector imposes a front-to-rear order on trains in the set of trains and one said set of train-merging criteria includes the criterion that the number of objects evacuated to car sections belonging to trains other than a train farthest forward in the set of trains has failed to reach a predetermined evacuation minimum within a maximum number of collection increments.

27. A computer system as defined in claim 26 wherein the train farthest forward in the set of trains is included in the plurality of trains combined into the single train.

28. A computer system as defined in claim 15 wherein the garbage collector imposes a front-to-rear order on trains in the set of trains and a farthest forward train in the set of trains is included in the plurality of trains combined into the single train.

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.

30. A storage medium as defined in claim 29 wherein:

E) the garbage collector adds a train from time to time to the set of trains;

F) one said set of train-merging criteria includes the criterion that the number of said trains in the set thereof be equal to a predetermined maximum number of trains;

G) the determination of whether that set of train-merging criteria is met is made when a train is to be added to a plurality thereof; and

H) when that set of criteria is met, the combining of the plurality of existing trains occurs before the train is added, whereby the number of trains is prevented from exceeding the maximum number of trains.

31. A storage medium as defined in claim 29 wherein the collector imposes a front-to-rear order on trains in the set of trains and trains farthest to the rear in the set of trains are the plurality of trains combined into the single train.

32. A storage medium as defined in claim 29 wherein the garbage collector compares the number of cars in at least one group of existing trains with a predetermined limit value and adopts a group whose number of cars has thus been compared as the plurality of existing trains to be combined only if the number of cars in that group does not exceed the limit value.

33. A storage medium as defined in claim 29 wherein the garbage collector imposes a front-to-rear order on trains in the set of trains and one said set of train-merging criteria includes the criterion that the number of car sections belonging to a train farthest forward in the set of trains has failed to be reduced by a predetermined car-reduction minimum within a maximum number of collection increments.

34. A storage medium as defined in claim 33 wherein the car-reduction minimum is one car section.

35. A storage medium as defined in claim 33 wherein the maximum number of collection increments is a function of the number of car sections that belong to the farthest-forward train.

36. A storage medium as defined in claim 33 wherein the farthest forward of the trains in the train set is included in the plurality of trains combined into the single train.

37. A storage medium as defined in claim 29 wherein the garbage collector imposes a front-to-rear order on trains in the set of trains and one said set of train-merging criteria includes the criterion that the volume of objects located in car sections belonging to a train farthest forward in the set of trains has failed to be reduced by a predetermined volume-reduction minimum within a maximum number of collection increments.

38. A storage medium as defined in claim 37 wherein the train farthest forward in the set of trains is included in the plurality of trains combined into the single train.

39. A storage medium as defined in claim 37 wherein the maximum number of collection increments is a function of the number of car sections that belong to the farthest forward train.

40. A storage medium as defined in claim 29 wherein the garbage collector imposes a front-to-rear order on trains in the set of trains and one said set of train-merging criteria includes the criterion that the number of objects evacuated to car sections belonging to trains other than a train farthest forward in the set of trains has failed to reach a predetermined evacuation minimum within a maximum number of collection increments.

41. A storage medium as defined in claim 40 wherein the train farthest forward in the set of trains is included in the plurality of trains combined into the single train.

42. A storage medium as defined in claim 29 wherein the garbage collector imposes a front-to-rear order on trains in the set of trains and a farthest forward train in the set of trains is included in the plurality of trains combined into the single train.

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.