Better placement of objects promoted into a generation managed by the train algorithm

• US 20040172507A1
• Filed: 02/27/2003
• Published: 09/02/2004
• Est. Priority Date: 02/27/2003
• 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,096,329 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/99953 Recoverability
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

A garbage collector for more efficient placement of newly promoted objects into a generation managed by the train algorithm. A promotion train is established near the oldest train and the objects are placed therein. If some objects are referenced from existing trains in the generation those objects are placed into those trains, and if any such objects are referenced from several existing trains, the objects are placed at the end of the youngest referencing train. The promotion train may be a new train that is placed or a existing train selected near the oldest train. The distance based on the amount of memory compared to the size of a collection set. In the case of multiple collector threads, multiple cars in a promotion train or multiple promotion trains may be formed. In this case each car or each may be associated with a particular collector thread. The distance from the oldest train for the multiple promotion trains is determined from a measure or estimation of the survival of the promoted objects. The estimation may be heuristically derived from the object class or object prolificness or some other known metric.

Claims

1. A method for placing objects newly promoted into a generation managed by the train algorithm, the method comprising the steps of:

establishing at least one promotion train for newly promoted objects, wherein the promotion train is between the oldest train and the youngest train, and

placing the newly promoted objects into the promotion train,

2. The method of claim 1 further comprising the step of, if there were a prior existing promotion train, then establishing the most recent promotion train to be no older than a prior existing promotion train.

3. The method of claim 1 further comprising the steps of:

determining a distance from the oldest train, and

placing the promotion train at that distance from the oldest train.

4. The method of claim 3 further comprising the step of determining the distance of the promotion train from the oldest train as a function of the memory size of a collection set.

5. The method of claim 1 further comprising the steps of:

determining if any newly promoted objects are referenced from trains in the generation, and

if any found, placing those objects into the referencing trains.

6. The method of claim 5, wherein if any newly promoted objects are referenced from more than one train in the generation, then

finding the youngest referencing train, and

placing the objects therein.

7. The method of claim 1, wherein when there are multiple collector threads promoting objects into a generation in parallel, the method further comprising the steps of:

establishing local allocation buffers within car sections, wherein each local allocation buffer is exclusive to a particular collector thread.

8. The method of claim 7 wherein the step of establishing the local allocation buffers includes establishing the local allocation buffers in cars sections in the at least one promotion train.

9. The method of claim 7 further comprising the steps of:

establishing for each collector thread a data structure for each local allocation buffer, wherein the data structure maintains at least the location and the free space within the local allocation buffer.

10. A computer system for placing objects newly promoted into a generation managed by the train algorithm, the system comprising:

a promotion train for newly promoted objects, wherein the promotion train is between the oldest train and the youngest train, and

means for placing the newly promoted objects into the promotion train.

11. The system of claim 10 wherein, if there were a prior existing promotion train, then the most recently established promotion train is no older than a prior existing promotion train.

12. The system of claim 10 further comprising:

means for determining a distance from the oldest train, wherein the promotion train is placed at that distance from the oldest train.

13. The system of claim 12 further comprising means for determining the distance of the promotion train from the oldest train as a function of the memory size of a collection set.

14. The system of claim 10 further comprising:

means for determining if any newly promoted objects are referenced from trains in the generation, and

if any found, means for placing those objects into the referencing trains.

15. The system of claim 14, wherein if any newly promoted objects are referenced from more than one train in the generation, then further comprising:

means for finding the youngest referencing train, and

means for placing the objects therein.

16. The system of claim 10, wherein when there are multiple collector threads promoting objects into a generation in parallel, the method further comprising:

local allocation buffers established within car sections, wherein each local allocation buffer is exclusive to a particular collector thread.

17. The system of claim 16 further wherein the local allocation buffers are established in cars sections in the at least one promotion train.

18. The system of claim 16 further comprising:

a data structure maintained by each collector thread buffer, wherein the data structure maintains at least the location of and the free space within each respective local allocation buffer.

19. 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 promotion train for newly promoted objects, wherein the promotion train is between the oldest train and the youngest train, and

placing the newly promoted objects into the promotion train.

20. The computer readable media of claim 19, comprising further computer readable media containing instructions for execution in a processor for the practice of the method of, if there were a prior existing promotion train, then establishing the most recent promotion train to be no older than a prior existing promotion train.

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

determining a distance from the oldest train, and

placing the promotion train at that distance from the oldest train.

22. The computer readable media of claim 19, comprising further computer readable media containing instructions for execution in a processor for the practice of the method comprising the step of determining the distance of the promotion train from the oldest train as a function of the memory size of a collection set.

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

determining if any newly promoted objects are referenced from trains in the generation, and

if any found, placing those objects into the referencing trains.

24. The computer readable media of claim 23, comprising further computer readable media containing instructions for execution in a processor, if any newly promoted objects are referenced from more than one train in the generation, for the practice of the method comprising the steps of

finding the youngest referencing train, and

placing the objects therein.

25. The computer readable media of claim 19, comprising further computer readable media containing instructions for execution in a processor, if any newly promoted objects are referenced from more than one train in the generation, for the practice of the method comprising the steps of

establishing local allocation buffers within car sections, wherein each local allocation buffer is exclusive to a particular collector thread.

26. The computer readable media of claim 25, comprising further computer readable media containing instructions for execution in a processor, if any newly promoted objects are referenced from more than one train in the generation, wherein the step of establishing the local allocation buffers includes establishing the local allocation buffers in cars sections in the at least one promotion train.

27. The computer readable media of claim 25, comprising further computer readable media containing instructions for execution in a processor, if any newly promoted objects are referenced from more than one train in the generation, for the practice of the method further comprising the steps of:

establishing for each collector thread a data structure for each local allocation buffer, wherein the data structure maintains at least the location and the free space within the local allocation buffer.

28. 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 promotion train for newly promoted objects,

placing the promotion train between the oldest train and the youngest train, and

placing the newly promoted objects into the promotion train.

29. The electromagnetic signals of claim 28 further comprising signals for the practice of the step of, if there were a prior existing promotion train, then establishing the most recent promotion train to be no older than a prior existing promotion train.

30. The electromagnetic signals of claim 28 further comprising signals for the practice of the steps of:

determining a distance from the oldest train, and

placing the promotion train at that distance from the oldest train.

31. The electromagnetic signals of claim 30 further comprising signals for the practice of the step of determining the distance of the promotion train from the oldest train as a function of the memory size of a collection set.

32. The electromagnetic signals of claim 28 further comprising signals for the practice of the steps of:

determining if any newly promoted objects are referenced from trains in the generation, and

if any found, placing those objects into the referencing trains.

33. The electromagnetic signals of claim 28 further, if any newly promoted objects are referenced from more than one train in the generation, comprising signals for the practice of the steps of:

finding the youngest referencing train, and

placing the objects therein.

35. The electromagnetic signals of claim 28 further, if any newly promoted objects are referenced from more than one train in the generation, comprising signals for the practice of the steps of:

establishing local allocation buffers within car sections, wherein each local allocation buffer is exclusive to a particular collector thread.

36. The electromagnetic signals of claim 35 further, if any newly promoted objects are referenced from more than one train in the generation, wherein the step of establishing the local allocation buffers includes establishing the local allocation buffers in cars sections in the at least one promotion train.

37. The electromagnetic signals of claim 35 further, if any newly promoted objects are referenced from more than one train in the generation, comprising signals for the practice of the steps of:

establishing for each collector thread a data structure for each local allocation buffer, wherein the data structure maintains at least the location and the free space within the local allocation buffer