Using class properties to segregate objects in a generation managed by the train algorithm

• US 7,620,943 B1
• Filed: 06/30/2004
• Issued: 11/17/2009
• Est. Priority Date: 06/30/2004
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Garthwaite, Alexander T.
• Primary Examiner(s): Zhen; Wei Y
• Assistant Examiner(s): Rampuria; Satish
• Application Number:
  US10/881,101
• Time in Patent Office: 1,966 Days
• Field of Search: 717140-161, 707/206
• US Class Current: 717/140
• CPC Class Codes: G06F 12/0276 Generational garbage collection

Abstract

A garbage collector that employs the train algorithm divides object classes into a number of class groups, which are considered to have different ranks. The class group having the lowest rank, for example, may include only classes whose instances contain no references. The group of the next-higher rank may consist of classes whose instances include references only to objects that are instances of final classes whose instances include no references. The highest-rank group may include all other classes. Car sections are associated with the class groups and contain only instances of classes belonging to the class groups with which they are associated. Within each train, each car associated with a class group of a higher-rank is placed earlier in the collection order than is a car associated with a lower-rank class group.

Claims

1. A computer system comprising:

a processor;

a memory operatively connected to the processor; and

a garbage collector stored in memory and configured to;

identify a plurality of objects marked as garbage in a memory heap of the computer system;

identify a first object of a first object class, a second object of a second object class, and a third object of a third object class from the plurality of objects, wherein the first object comprises a first reference to the second object, wherein the second object comprises a second reference to the third object, and wherein the third object comprises a lack of references to the plurality of objects;

assign the first object class to a first class group based on the first reference, the second object class to a second class group based on the second reference, and the third object class to a third class group based on the lack of references;

reserve a first car section of a garbage collection train (GCT) solely for instances of members of the first class group, a second car section of the GCT solely for instances of members of the second class group, and a third car section of the GCT solely for instances of members of the third class group;

insert the first object into the first car section, insert the second object in the second car section, and insert the third object into the third car section; and

reclaim a portion of the memory heap for reuse by collecting the first car section.

2. The computer system as defined in claim 1 wherein:

the garbage collector assigns respective collection-order positions in a nominal collection order from oldest to youngest to the car sections and treats the class groups as having respective ranks within a rank order; and

the collection-order position that the garbage collector assigns within the GCT to each car section associated with a class group of a given rank is ahead of any car section in the GCT that is associated with a class group of a lower rank.

3. The computer system as defined in claim 2 wherein no instance of any class belonging to a class group of a given rank includes a reference to an object that is an instance of a class belonging to a class group of a higher rank.

4. The computer system as defined in claim 2 wherein the third class group consists of classes whose instances contain no references.

5. The computer system as defined in claim 4 wherein the second class group consists of classes whose instances contain references of which all refer only to objects that contain no references.

6. The computer system as defined in claim 5 wherein no instance of any class belonging to a class group of a given rank includes a reference to an object that is an instance of a class belonging to a class group of a higher rank.

7. The computer system as defined in claim 6 wherein the first class group consists of all classes that do not belong to the second class group or the third class group.

8. The computer system as defined in claim 2 wherein:

the garbage collector treats certain objects, denominated proxy objects, as proxies for data structures stored outside a generation; and

the garbage collector associates some car sections with proxy objects,

wherein the collection-order position that the garbage collector assigns within the GCT to each car section associated with a class group is ahead of the collection-order position that the garbage collector assigns within the GCT to any car section that is associated with proxy objects.

9. The computer system as defined in claim 8 wherein, if the GCT includes a car section associated with proxy objects, at least one such car section includes a proxy object not referred to by references in the generation.

10. The computer system as defined in claim 1 wherein the third class group consists of classes whose instances contain no references.

11. The computer system as defined in claim 10 wherein the second class group consists of classes whose instances contain references of which all refer only to objects that contain no references.

12. The computer system as defined in claim 11 wherein the first class group consists of all classes that do not belong to the second class group or the third class group.

13. A machine readable medium storing instructions to perform garbage collection, the instructions comprising functionality to:

identify a plurality of objects marked as garbage in a memory heap in a computer system;

identify a first object of a first object class, a second object of a second object class, and a third object of a third object class from the plurality of objects, wherein the first object comprises a first reference to the second object, wherein the second object comprises a second reference to the third object, and wherein the third object comprises a lack of references to the plurality of objects;

assign the first object class to a first class group based on the first reference, the second object class to a second class group based on the second reference, and the third object class to a third class group based on the lack of references;

reserve a first car section of a garbage collection train (GCT) solely for instances of members of the first class group, a second car section of the GCT solely for instances of members of the second class group, and a third car section of the GCT solely for instances of members of the third class group;

insert the first object into the first car section, insert the second object in the second car section, and insert the third object into the third car section; and

reclaim a portion of the memory heap for reuse by collecting the first car section.

14. The machine readable medium as defined in claim 13, the instructions further comprising functionality to:

assign respective collection-order positions in a nominal collection order from oldest to youngest to the car sections and treat the class groups as having respective ranks within a rank order,

wherein the collection-order position assigned within the GCT to each car section associated with a class group of a given rank is ahead of any car section in the GCT that is associated with a class group of a lower rank.

15. The machine readable medium as defined in claim 14 wherein no instance of any class belonging to a class group of a given rank includes a reference to an object that is an instance of a class belonging to a class group of a higher rank.

16. The machine readable medium as defined in claim 14 wherein the third class group consists of classes whose instances contain no references.

17. The machine readable medium as defined in claim 16 wherein the second class group consists of classes whose instances contain references of which all refer only to objects that contain no references.

18. The machine readable medium as defined in claim 17 wherein no instance of any class belonging to a class group of a given rank includes a reference to an object that is an instance of a class belonging to a class group of a higher rank.

19. The machine readable medium as defined in claim 18 wherein the first class group consists of all classes that do not belong to the second class group or the third class group.

20. The machine readable medium as defined in claim 14, the instructions further comprising functionality to:

treat certain objects, denominated proxy objects, as proxies for data structures stored outside a generation; and

associate some car sections with proxy objects,

wherein the collection-order position assigned within the GCT to each car section associated with a class group is ahead of the collection-order position assigned within the GCT to any car section that is associated with proxy objects.

21. The machine readable medium as defined in claim 20 wherein the GCT includes a car section associated with proxy objects, and at least one such car section includes a proxy object not referred to by references in the generation.

22. The machine readable medium as defined in claim 13 wherein the third class group consists of classes whose instances contain no references.

23. The machine readable medium as defined in claim 22 wherein the second class group consists of classes whose instances contain references of which all refer only to objects that contain no references.

24. The machine readable medium as defined in claim 23 wherein the first class group consists of all classes that do not belong to the second class group or the third class group.

25. A method of garbage collection comprising:

identifying a plurality of objects marked as garbage in a memory heap of a computer system;

identifying a first object of a first object class, a second object of a second object class, and a third object of a third object class from the plurality of objects, wherein the first object comprises a first reference to the second object, wherein the second object comprises a second reference to the third object, and wherein the third object comprises a lack of references to the plurality of objects;

assigning the first object class to a first class group based on the first reference, the second object class to a second class group based on the second reference, and the third object class to a third class group based on the lack of references;

reserving a first car section of a garbage collection train (GCT) solely for instances of members of the first class group, a second car section of the GCT solely for instances of members of the second class group, and a third car section of the GCT solely for instances of members of the third class group;

inserting the first object into the first car section, inserting the second object in the second car section, and inserting the third object into the third car section; and

reclaiming a portion of the memory heap for reuse by collecting the first car section.

26. The method as defined in claim 25 further comprising:

assigning respective collection-order positions in a nominal collection order from oldest to youngest to the car sections and treating the class groups as having respective ranks within a rank order,

wherein the collection-order assigned within the GCT to each car section associated with a class group of a given rank is ahead of any car section in the GCT that is associated with a class group of a lower rank.

27. The method as defined in claim 26 wherein no instance of any class belonging to a class group of a given rank includes a reference to an object that is an instance of a class belonging to a class group of a higher rank.

28. The method as defined in claim 26 wherein the third class group consists of classes whose instances contain no references.

29. The method as defined in claim 28 wherein the second class group consists of classes whose instances contain references of which all refer only to objects that contain no references.

30. The method as defined in claim 29 wherein no instance of any class belonging to a class group of a given rank includes a reference to an object that is an instance of a class belonging to a class group of a higher rank.

31. The method as defined in claim 30 wherein the first class group consists of all classes that do not belong to the second class group or the third class group.

32. The method as defined in claim 26 further comprising:

treating certain objects, denominated proxy objects, as proxies for data structures stored outside a generation; and

associating some car sections with proxy objects,

wherein the collection-order position assigned within the GCT to each car section associated with a class group is ahead of the collection-order position that the garbage collector assigns within the GCT to any car section that is associated with proxy objects.

33. The method as defined in claim 32 wherein, if the GCT includes a car section associated with proxy objects, at least one such car section includes a proxy object not referred to by references in the generation.

34. The method as defined in claim 25 wherein the third class group consists of classes whose instances contain no references.

35. The method as defined in claim 34 wherein the second class group consists of classes whose instances contain references of which all refer only to objects that contain no references.

36. The method as defined in claim 35 wherein the first class group consists of all classes that do not belong to the third class group first or the second class group.