Better placement of objects reachable from outside a generation managed by the train algorithm

• US 20040111573A1
• Filed: 12/06/2002
• Published: 06/10/2004
• 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.
• Granted Patent: US 7,072,905 B2
• Time in Patent Office: Days
• US Class Current: 711/159
• CPC Class Codes: G06F 12/0276 Generational garbage collection
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A garbage collector for more efficient placement of objects referenced from external references. The expected life times of these objects is measured by trial and error, by the class or type, by how often the object has been evacuated or the external reference processed, by the stability and longevity of the root source, or by the prolificness of the class or type of object. The measured value is held in the header of each object in an AGE field available for this purpose. These objects may be evacuated into existing trains or into new trains, or into a combination of existing and new trains. When new trains are created the trains are distributed among the existing trains according to a distribution contour that may be linear, normal, gamma or any other contour that might be found useful. Also, when new trains are created the youngest train must be a new train. When objects are evacuated into existing trains the objects are placed in trains according the survivability of the objects with the longer-lived objects placed proportionally in the younger trains. The objects are evacuated into the new trains from oldest to youngest Is trains according to the value in the AGE field. The higher the value the younger the train. A threshold on the AGE value may be established such that when the threshold is reached, the objects are evacuated into the youngest new train.

Claims

1. A method for placing objects reachable from outside a generation managed by the train algorithm, the method comprising the steps of:

establishing a measure associated with lifetime of the objects,

incrementing and tracking the value of the measure, and

evacuating the objects into younger trains, wherein the higher values of the measure directs the evacuation to younger trains.

2. The method of claim 1 for placing objects reachable from outside a generation managed by the train algorithm, the method further comprising the steps of:

creating new trains, and

distributing the new trains among existing trains.

3. The method of claim 2 wherein the evacuating of objects is into the new trains.

4. The method of claim 2 wherein the step of distributing comprising the steps of:

placing a new train as the youngest train, and

placing another new train at least after the oldest existing train with cars not in a collection set.

5. The method of claim 2 further comprising establishing a contour for the distributing of the new trains among existing trains.

6. The method of claim 5 wherein the contour is selected from the group consisting of even, linear, logarithmic, normal, gamma, and binomial distributions.

7. The method of claim 1 further comprising the steps of establishing a contour for the distribution of the objects among existing trains.

8. The method of claim 7 wherein the contour is selected from the group consisting of even, linear, logarithmic, normal, gamma, and binomial distributions.

9. The method of claim 1 further comprising:

establishing a threshold or maximum for the value of the measure,

reaching the threshold for objects, and

evacuating the corresponding objects to the youngest train.

10. The method as defined claim 1 wherein the measure is selected from the group consisting of:

object class or type;

inversely on the relative prolificness of the object type;

the stability and longevity of the root source;

the number of times external references to the object are processed; and

the number of times the object is evacuated.

11. The method of claim 10 further comprising the step of determining a value for incrementing the measure, wherein the value depends on the selected measure.

12. A computer system for placing objects reachable from outside a generation managed by the train algorithm, the computer system comprising:

a measure associated with lifetime of the objects,

means for incrementing and tracking the value of a measure, and

means for evacuating the objects into younger trains, wherein the higher values of the measure directs the evacuation to the younger trains.

13. The computer system of claim 12 for placing objects reachable from outside a generation managed by the train algorithm, the computer system further comprising:

means for creating new trains, and

means for distributing the new trains among the existing trains.

14. The computer system of claim 13 wherein the means for evacuating evacuates the objects into the new trains.

15. The computer system of claim 13 wherein the means for distributing further comprises:

means for placing a new train as the youngest train, and

means for placing another new train at least after the oldest train with cars not in a collection set.

16. The computer system of claim 13 further comprising means for establishing a contour for the distributing of the new trains among the existing trains.

17. The computer system of claim 16 wherein the contour is selected from the group

consisting of linear, logarithmic, normal, gamma, and binomial.

18. The computer system of claim 12 further comprising:

means for establishing a

contour for the distribution of the objects among the existing trains.

19. The computer system of claim 18 wherein the contour is selected from the group

consisting of linear, logarithmic, normal, gamma, and binomial distributions.

20. The computer system of claim 12 further comprising:

means for establishing a threshold or maximum for the value of the measure,

means for determining objects with a value of the measure reaching the threshold, and

means for evacuating the corresponding objects to the youngest train.

21. The computer system of claim 12 wherein the measure is selected from the group consisting of:

object class or type;

inversely on the relative prolificness of the object type;

the stability and longevity of the root source;

the number of times external references to the object are processed; and

the number of times the object is evacuated.

22. The method of claim 21 further comprising means for determining a value for incrementing the measure, wherein the value depends on the selected measure.

23. A computer readable media, comprising:

the computer readable media containing instructions for execution in a processor for the practice of the method of;

establishing a measure associated with lifetime of the objects,

incrementing and tracking the value of the measure, and

evacuating the objects into younger trains, wherein the higher values of the measure directs the evacuation to the younger trains.

24. The computer readable media of claim 23, comprising further computer readable media containing instructions for execution in a processor for the practice of the method steps of:

creating new trains, and

distributing the new trains among the existing trains.

25. The computer readable media of claim 24 wherein the evacuating of objects is into the new trains.

26. The computer readable media of claim 24, comprising further computer readable media containing instructions for execution in a processor for the practice of the steps of:

placing a new train as the youngest train, and

placing another new train at least after the oldest train with cars not in a collection set.

27. The computer readable media of claim 24, comprising further computer readable media containing instructions for execution in a processor for the practice of the method step of:

establishing a contour for the distributing of the new trains among the existing trains.

28. The computer readable media of claim 27, wherein the contour is selected from the group consisting of even, linear, logarithmic, normal, gamma, and binomial.

29. The computer readable media of claim 23, comprising further computer readable media containing instructions for execution in a processor for the practice of the step of establishing a contour for the distribution of the objects among existing trains.

30. The computer readable media of claim 29, wherein the contour is selected from the group consisting of even, linear, logarithmic, normal, gamma, and binomial.

31. The computer readable media of claim 23, comprising further computer readable media containing instructions for execution in a processor for the practice of the steps of:

establishing a threshold or maximum for the value of the measure, reaching the threshold for objects, and

evacuating the corresponding objects to the youngest train.

32. The computer readable media of claim 23, wherein the measure is selected from the group consisting of:

object class or type;

inversely on the relative prolificness of the object type;

the stability and longevity of the root source;

the number of times external references to the object are processed; and

the number of times the object is evacuated.

33. The computer readable media of claim 32, comprising further computer readable media containing instructions for execution in a processor for the practice of the step of determining a value for the incrementing of the measure, wherein the value depends on the selected measure.

34. Electromagnetic signals propagating on a computer network comprising:

the electromagnetic signals for execution on a processor for the practice of the a method of;

establishing a measure associated with lifetime of the objects,

incrementing and tracking the value of the measure, and

evacuating the objects into younger trains, wherein the higher values of the measure directs the evacuation to the younger trains.

35. The electromagnetic signals of claim 34 further comprising signals for the practice of the steps of:

creating new trains, and

distributing the new trains among the existing trains.

36. The electromagnetic signals of claim 34 wherein the evacuating of objects is into the new trains.

37. The electromagnetic signals of claim 35 further comprising signals for the practice of the steps of:

placing a new train as the youngest train, and

placing another new train at least after the oldest train with cars not in a collection set.

38. The electromagnetic signals of claim 35 further comprising signals for the practice of the steps of:

establishing a contour for the distributing of the new trains among the existing trains.

39. The electromagnetic signals of claim 38 wherein the contour is selected from the group consisting of linear, logarithmic, normal, gamma, and binomial distributions.

40. The electromagnetic signals of claim 34 further comprising signals for the practice of the step of establishing a contour for the distribution of the objects among existing trains.

41. The electromagnetic signals of claim 40 wherein the contour is selected from the group consisting of linear, logarithmic, normal, gamma, and binomial distributions.

42. The electromagnetic signals of claim 34 further comprising signals for the practice of the steps of:

establishing a threshold for the value of the measure,

reaching the threshold for objects, and

evacuating the corresponding objects to the youngest train.

43. The electromagnetic signals of claim 34 wherein the measure is selected from the group consisting of:

object class or type;

inversely on the relative prolificness of the object type;

the stability and longevity of the root source;

the number of times external references to the object are processed; and

the number of times the object is evacuated.

44. The electromagnetic signals of claim 43 further comprising signals for the practice of the step of determining a value for incrementing the measure, wherein the value depends on the selected measure.