Methods and apparatus for generational dynamic management of computer memory

• US 6,308,185 B1
• Filed: 02/09/1999
• Issued: 10/23/2001
• Est. Priority Date: 03/06/1998
• Status: Expired due to Fees

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Grarup, Steffen, Bak, Lars
• Primary Examiner(s): Kulik, Paul V.
• Application Number:
  US09/247,817
• Time in Patent Office: 987 Days
• Field of Search: 707/206
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0276 Generational garbage collection
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

The present invention relates to methods and apparatus for performing generational garbage collection within computer memory. According to one aspect of the present invention, a computer-implemented method for dynamically managing memory which includes a first memory section and a second memory section that is divided into a plurality of blocks each having an associated marker, includes performing a first garbage collection on the first memory section. The method also includes performing a second garbage collection on a selected one of the blocks in the second memory section. A third garbage collection is performed on the selected block in the second memory section. The third garbage collection includes determining whether the selected block includes a first object which references a second object which is not included in the selected block based at least in part on a status indicated by the marker associated with the selected block. The status includes an indication of whether the reference to the second object was stored after the second garbage collection was performed, and if the reference to the second object was stored after the second garbage collection was performed, a new root array is created using the selected marker.

Claims

1. A computer-implemented method for dynamically managing memory associated with a computer system, the memory including a first memory section and a second memory section that is divided into a plurality of blocks, the blocks in the second memory section each having an associated marker, the method comprising:

performing a first garbage collection on the first memory section;

performing a second garbage collection on a selected one of the blocks in the second memory section;

performing a third garbage collection on the selected block in the second memory section, wherein the third garbage collection includes determining whether the selected block includes a first object which references a second object which is not included in the selected block based at least in part on a status indicated by the marker associated with the selected block, wherein the status includes an indication of whether the reference to the second object was stored after the second garbage collection was performed; and

when the reference to the second object was stored after the second garbage collection was performed, creating a new root array using the selected marker.

2. A computer-implemented method as recited in claim 1 wherein when it is determined that the first object does not reference a second object which is not included in the selected block, the method further includes releasing the selected block.

3. A computer-implemented method as recited in claim 1 wherein when it is determined that the selected block includes a first object which references a second object, the step of performing the third garbage collection further includes:

determining whether the second object is in the first memory section using the selected block marker; and

when it is determined that the second object is in the first memory section, a root array associated with the selected block marker is updated to insure that the root array associated with the selected block marker includes a pointer to the second object.

4. A computer-implemented method as recited in claim 1 wherein when it is determined that the selected block includes a first object which references a second object, the step of performing the third garbage collection further includes:

determining whether the second object is in the second memory section using the selected block marker; and

when it is determined that the second object is in the second memory section, a root array associated with the selected block marker is scanned to identify references to other objects.

5. A computer-implemented method as recited in claim 4 further including following the references to other objects.

6. A computer-implemented method as recited in claim 1 wherein the plurality of blocks are arranged as a plurality of trains, the selected block being included in a first one of the plurality of trains, the step of performing the third garbage collection further including:

determining whether the second object is in a second one of the plurality of trains based at least in part on the status indicated by the marker associated with the block.

7. A computer-implemented method as recited in claim 6 wherein when it is determined that the second object is not in a second one of the plurality of trains, the method further includes releasing the second train.

8. A computer-implemented method as recited in claim 1 wherein the plurality of blocks are arranged as a plurality of cars, the plurality of cars further being arranged as a plurality of trains, the selected block being included in a first one of the plurality of cars that forms a selected one of the plurality of trains, the step of performing the third garbage collection further including:

determining whether the second object is in a second one of the plurality of cars that forms the selected train based at least in part on the status indicated by the marker associated with the block.

9. A computer-implemented method as recited in claim 8 wherein when it is determined that the second object is not in the second car of the selected train, the method further includes releasing the second car.

10. A computer-implemented method for dynamically managing memory associated with a computer system, the memory being divided into a plurality of blocks, the blocks each having an associated marker, the method comprising:

performing a first garbage collection on a selected one of the blocks;

performing a second garbage collection on the selected block, wherein the second garbage collection includes determining whether the selected block includes a first object which references a second object which is not included in the selected block based at least in part on a status indicated by the marker associated with the selected block, the status indicated by the marker including an indication of whether the reference to the second object was stored after the first garbage collection was performed; and

when the reference to the second object was stored after the first garbage collection was performed, creating a new root array using the selected block.

11. A computer-implemented method as recited in claim 10 wherein when it is determined that the first object does not reference a second object which is not included in the selected block, the method further includes releasing the selected block.

12. A computer-implemented method as recited in claim 10 wherein the plurality of blocks are arranged as a plurality of trains, the selected block being included in a first one of the plurality of trains, the step of performing the garbage collection further including:

determining whether the second object is in a second one of the plurality of trains based at least in part on the status indicated by the marker associated with the block.

13. A computer-implemented method as recited in claim 12 wherein when it is determined that the second object is not in a second one of the plurality of trains, the method further includes releasing the second train.

14. A computer-implemented method as recited in claim 10 wherein the plurality of blocks are arranged as a plurality of cars, the plurality of cars further being arranged as a plurality of trains, the selected block being included in a first one of the plurality of cars that forms a selected one of the plurality of trains, the step of performing the garbage collection further including:

determining whether the second object is in a second one of the plurality of cars that forms the selected train based at least in part on the status indicated by the marker associated with the block.

15. A computer-implemented method as recited in claim 14 wherein when it is determined that the second object is not in the second car of the selected train, the method further includes releasing the second car.

16. A computer-implemented method as recited in claim 10 further including an additional memory section, wherein when it is determined that the second object is not included in the selected block, the step of performing the garbage collection on the selected block further includes determining whether the second object is included in the additional memory section based at least in part on the status indicated by the marker associated with the selected block.

17. A computer-implemented method for allocating a selected object in computer memory, the computer memory including a first section, a second section, and an array of words associated with elements in the second section, the words being arranged to indicate whether the contents of their associated elements reference objects in the first section, the method comprising:

determining whether the first section is suitable for the selected object to be allocated;

allocating the selected object when it is determined that the first section is suitable for the object to be allocated; and

performing a garbage collection in the first section when it is determined that the first section is not suitable for the selected object to be allocated, wherein performing the garbage collection includes scanning the array of words to locate selected words that indicate that their associated elements in the second section reference particular objects in the first section, and wherein the particular objects in the first section are retained during the garbage collection.

18. A computer-implemented method as recited in claim 17 wherein when the selected markers that indicate that their associated elements in the second section reference the particular objects are located, performing the garbage collection in the first section further includes:

following associations of roots within the associated elements in the second section, wherein following the associations of the roots includes updating the roots to new locations within the computer memory and updating the selected words.

19. A computer-implemented method as recited in claim 18 wherein updating the selected words includes:

determining when a selected one of the roots is in the second section and references a selected one of the particular objects is in the first section; and

when it is determined that the selected root is in the second section and references the selected particular object in the first section, updating the selected words to indicate that the selected root is in the second section and the selected particular object is in the first section.

20. A computer-implemented method as recited in claim 17 further including:

performing a garbage collection in the second section, wherein performing the garbage collection includes following associations of roots associated with selected ones of the elements, the roots being associated with the new generation, whereby following the associations of the roots involves updating some of the words in the array of words.

21. A computer-implemented method as recited in claim 20 wherein performing the garbage collection in the second section further includes:

scanning the array of markers to locate a first word selected from the array of words which indicates that its associated element in the second section is suitable for release; and

releasing the element.

22. A computer-implemented method as recited in claim 17 wherein scanning the array of words to locate selected words that indicate that their associated elements in the second section reference particular objects in the first section includes identifying a root array which includes addresses for the particular referenced objects.

23. A computer readable medium for use in a computer system including a first memory section and a second memory section that is arranged as a plurality of elements, the computer readable medium having computer code for configuring a marker, the marker being associated with a first element selected from the plurality of elements, the marker comprising:

a first indicator arranged to identify whether the first selected element references an object contained within the first memory section.

24. A computer readable medium for use in a computer system as recited in claim 23 wherein the marker further includes a reference to the object.

25. A computer readable medium for use in a computer system as recited in claim 24 wherein the reference to the object is a pointer to an array which contains an address for the object.

26. A computer readable medium for use in a computer system as recited in claim 23, wherein the marker further includes a second indicator arranged to identify whether the first selected element references a second element selected from the plurality of elements.

27. A computer readable medium for use in a computer system as recited in claim 23 wherein the plurality of elements is organized such that a first set of the elements selected from the plurality of elements forms a first car arrangement and a second set of the elements selected from the plurality of elements forms a second car arrangement, the first selected element being included in the first car arrangement, the first car arrangement and the second car arrangement further forming a train, the marker further including:

a second indicator arranged to identify whether the first selected element references a second element selected from the plurality of elements, the second selected element being included in the second car arrangement.

28. A computer readable medium for use in a computer system as recited in claim 27, wherein the marker further includes a reference to the second selected element, wherein the reference is a pointer to an array which includes an address associated with the second selected element.

29. A computer readable medium for use in a computer system as recited in claim 23 wherein the plurality of elements is organized such that a first set of the elements selected from the plurality of elements forms a first car arrangement and a second set of the elements selected from the plurality of elements forms a second car arrangement, the first selected element being included in the first car arrangement, the first car arrangement being a part of a first train and the second car arrangement being a part of a second train, the marker further including:

a second indicator arranged to identify whether the first selected element references a second element selected from the plurality of elements, the second selected element being included in the second car arrangement.

30. A computer readable medium for use in a computer system as recited in claim 29, wherein the marker further includes a reference to the second selected element, wherein the reference is a pointer to an array which includes an address associated with the second selected element.

31. A computer system comprising:

memory including a first memory section and a second memory section that is segmented into a plurality of blocks;

an array of markers, each marker corresponding to an associated block in the second memory section, the markers being configured to indicate when their associated blocks reference objects outside of their associated block;

a set of root arrays, the root arrays being arranged to hold addresses of the objects, wherein selected markers from the array of markers are associated with the set of root arrays;

a first garbage collector for reclaiming space within the first memory section; and

a second garbage collector for reclaiming space within the second memory section based at least in part upon the status of the markers in the array of markers.

32. A computer system as recited in claim 31 wherein a first marker selected from the array of markers includes a section indicator that identifies when the associated block of the first marker references a first object in the first memory section.

33. A computer system as recited in claim 31 wherein the plurality of blocks is arranged as a plurality of cars, the plurality of cars further being arranged as a plurality of trains.

34. A computer system as recited in claim 33 wherein a first marker selected from the array of markers includes a car indicator that identifies when the associated block of the first marker references a first block of a first car selected from the plurality of cars, the block associated with the first marker being a part of a second car selected from the plurality of cars, the first car and the second car being a part of a first train selected from the plurality of trains.

35. A computer system as recited in claim 33 wherein a first marker selected from the array of markers includes a train indicator that identifies when the associated block of the first marker references a first block of a first car of a first train selected from the plurality of trains, the block associated with the first marker being a part of a second car of a second train selected from the plurality of trains.

36. A computer system as recited in claim 31 wherein the root arrays are created from selected markers from the array of markers.

37. A computer system as recited in claim 31 wherein the objects include newer objects and older objects, the newer objects being associated with the first memory section, and the older objects being associated with the second memory section.

38. A computer system comprising:

memory that is segmented into a plurality of blocks;

an array of markers, each marker corresponding to an associated block in the memory, the markers being configured to indicate when their associated blocks reference objects outside of their associated block;

a set of root arrays, the root arrays being arranged to hold addresses of the objects, wherein selected markers from the array of markers are associated with the set of root arrays; and

a garbage collector for reclaiming space within the memory based at least in part upon the status of the markers in the array of markers.

39. A computer system as recited in claim 38 wherein the plurality of blocks is arranged as a plurality of cars, the plurality of cars further being arranged as a plurality of trains.

40. A computer system as recited in claim 39 wherein a first marker selected from the array of markers includes a car indicator that identifies when the associated block of the first marker references a first block of a first car selected from the plurality of cars, the block associated with the first marker being a part of a second car selected from the plurality of cars, the first car and the second car being a part of a first train selected from the plurality of trains.

41. A computer system as recited in claim 39 wherein a first marker selected from the array of markers includes a train indicator that identifies when the associated block of the first marker references a first block of a first car of a first train selected from the plurality of trains, the block associated with the first marker being a part of a second car of a second train selected from the plurality of trains.

42. A computer program product for dynamically managing memory associated with a computer system, the computer program product comprising:

computer code that performs a first garbage collection in a first memory section of the computer;

computer code that performs a second garbage collection on a second memory section of the computer, the second memory section being divided into a plurality of blocks, wherein the second garbage collection includes determining whether a block selected from the plurality of blocks includes a first object which references a second object which is not included in the selected block based at least in part on a status indicated by the marker associated with the selected block; and

a computer readable medium that stores the computer codes.

43. A computer program product as recited in claim 42 further including:

computer code that releases the selected block when it is determined that the first object does not reference a second object which is not included in the selected block.

44. A computer program product as recited in claim 42 further including:

computer code that determines whether the second object is in the first memory section using the selected block marker when it is determined that the selected block includes a first object which references a second object; and

computer code that updates a root array associated with the selected block marker to insure that the root array includes a pointer to the second object when it is determined that the second object is in the first memory section.

45. A computer program product as recited in claim 42 further including:

computer code that determines whether the second object is in the second memory section using the selected block marker when it is determined that the selected block includes a first object which references a second object; and

computer code that scans a root array associated with the selected block marker to identify references to other objects when it is determined that the second object is in the second memory section.

46. A computer program product for causing a processor of a computer system to dynamically manage memory associated with the computer system, the computer program product comprising:

computer code that performs a first garbage collection in a first memory section of the computer;

computer code that performs a second garbage collection on a second memory section of the computer, the second memory section being divided into a plurality of blocks, wherein the second garbage collection includes determining whether a block selected from the plurality of blocks includes a first object which references a second object which is not included in the selected block based at least in part on a status indicated by the marker associated with the selected block; and

a computer data signal embodied in a carrier wave that represents the computer codes.

47. A computer program product as recited in claim 46 further including:

computer code that releases the selected block when it is determined that the first object does not reference a second object which is not included in the selected block.

48. A computer program product as recited in claim 46 further including:

computer code that determines whether the second object is in the first memory section using the selected block marker when it is determined that the selected block includes a first object which references a second object; and

computer code that updates a root array associated with the selected block marker to insure that the root array includes a pointer to the second object when it is determined that the second object is in the first memory section.

49. A computer program product as recited in claim 46 further including:

computer code that determines whether the second object is in the second memory section using the selected block marker when it is determined that the selected block includes a first object which references a second object; and

computer code that scans a root array associated with the selected block marker to identify references to other objects when it is determined that the second object is in the second memory section.