On-the-fly garbage collector

• US 6,317,756 B1
• Filed: 10/07/1998
• Issued: 11/13/2001
• Est. Priority Date: 10/07/1998
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Petrank, Erez, Kolodner, Elliot K.
• Primary Examiner(s): VON BUHR, MARIA N
• Assistant Examiner(s): Miles, John Gladstone
• Application Number:
  US09/167,547
• Time in Patent Office: 1,133 Days
• Field of Search: 707/1-206
• US Class Current: 1/1
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 12/0269 Incremental or concurrent garbage collection, e.g. in real-time systems G06F12/0261 takes precedence
• 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 method for performing garbage collection of memory objects in a memory heap, the method includes the steps of partitioning the heap into old and new generations. There follows the step of applying an on-the-fly garbage collection to memory objects in the young generation, while running simultaneously a program thread.

Claims

1. A method for performing garbage collection of memory objects in a memory heap;

a plurality of program threads each running in successive collection cycles;

each collection cycle is constituted by a collection idle and collection active cycles; and

an on-the-fly garbage collection running in said collection active cycle;

said memory objects are associated, each, with an identifier value selected from a group of values that includes;

a first identifier value indicating that said memory object is subject to reclaiming or has not yet been subject to trace,

a second identifier value indicating that said object is referenced, constituting alive memory object, and descendant memory objects of said object have been subject to a trace for assigning to said descendant memory objects a value,

and a third value indicating that said object is referenced, constituting alive memory object, and descendant memory objects of said object have not been subject to said trace;

the method comprising the steps of;

(a) partitioning said heap or portion thereof into at least two generations; and

(b) applying substantiality on-the-fly garbage collection to memory objects in at least one from among said generations, whilst running at least one program thread said step (b) includes;

(i) upon starting said collection active cycle, the program thread assigning the third value to any memory object a reference to which is subject to a reference modification;

(ii) the program assigning a first inter-generational value, during said collection cycle, to an inter-generational value associated with a memory object that is subject to a reference modification;

(iii) the on-the-fly garbage collection performing, for any memory object associated with said second value and having an inter-generational value indicative of candidate inter-generational reference, the following steps that include;

(1) associating said third value to any memory object being descendant of said memory object, stipulated in (ii), and which descendant object being associated with said first value;

(2) in response of assigning said third value to all descendant objects of said memory object, stipulated in (ii), altering said inter-generational value.

2. The method of claim 1, wherein said inter-generational value being constituted by a dirty bit.

3. The method of claim 1, wherein said dirty bit is either set or reset for indicating a candidate inter-generational reference value.

4. The method of claim 1, wherein said inter-generational value being constituted by a dirty bit.

5. The method of claim 1, wherein said dirty bit is either set or reset for indicating a candidate inter-generational reference value.

6. The method of claim 1, wherein said first identifier value, second identifier value and third identifier value correspond to a white color, black color and gray color, respectively.

7. The method of claim 1, wherein said manipulating step further utilizing a unique identifier value for avoiding pre-mature promotion of memory objects from a young generation to an older generation from among said at least two generations.

8. The method of claim 1, wherein said manipulating step utilizing identifier toggling.

9. The method of claim 1, wherein said group of values further includes:

a fourth identifier value indicating that by the end of said collection cycle, said memory object is not subject to reclaiming and that said memory object is not associated with said second identifier value; and

wherein said step (b) further comprising,

(iii) after altering said inter-generational value, assigning said fourth value to newly created memory objects;

(iv) during said collection cycle, turning the fourth value associated with memory object to said first value.

10. The method of claim 1, wherein said group of values further includes:

a fourth value indicating that said memory object should turn to said first value; and

wherein said step (b) further comprising, (iii) after altering said inter-generational value, assigning said fourth value to newly created memory objects;

(iv) toggling between said first value and forth values such that in each collection cycle the first value plays the role that was played by the fourth value in the previous collection cycle, and the fourth value plays the role that was played by the first value in the previous collection cycle.

11. The method of claim 1, wherein said memory objects are further associated, each, with an age value indicative of the time duration that said object remains in a given generation;

said manipulating step further utilizing at least said age value as a criterion for promoting memory objects from said given generation to an older generation, from among said generations.

12. The method of claim 1, wherein said time duration is measured in number of collection cycles.

13. The method of claim 1, wherein said manipulating step utilizing identifier toggling.

15. The method of claim 1, wherein said time duration is measured in number of collection cycles.

16. The method of claim 1, wherein said manipulating step utilizing identifier toggling.

17. The method of claim 1, wherein said memory object is associated with two inter-generational values, said manipulation step further including manipulating said two inter-generational values for avoiding weak consistency.

18. The method of claim 1, wherein said memory object is associated with two inter-generational values, said manipulation step further including manipulating said two inter-generational values for avoiding weak consistency.

19. The method of claim 1, wherein said memory object is associated with two inter-generational values, said manipulation step further including manipulating said two inter-generational values for avoiding weak consistency.

20. The method of claim 1, wherein said inter-generational values and the identifier values, are stored in respective separate atomic write units.

21. The method of claim 1, wherein said inter-generational values and the identifier values, are stored in respective separate atomic write units.

22. The method of claim 1, wherein said first identifier value, second identifier value and third identifier value correspond to a first color, second color and third color, respectively.

23. The method of claim 1, wherein said fourth identifier value corresponds to a yellow color.

24. The method of claim 1, wherein said first identifier value, second identifier value and third identifier value correspond to a white color, black color and gray color, respectively.

14. A method for performing garbage collection of memory objects in a memory heap;

a plurality of program threads each running in successive collection cycles;

each collection cycle is constituted by a collection idle and collection active cycles;

an on-the-fly garbage collection running in said collection active cycle;

said memory objects are associated, each, with an identifier value selected from a group of values that includes;

a first identifier value indicating that said memory object is subject to reclaiming or that an identifier has not as yet been assigned to said memory object,

a second identifier value indicating that said object is referenced, constituting alive memory object, and descendant memory objects of said object have been subject to a trace for assigning to said descendant memory objects a value,

and a third identifier value indicating that said object is referenced, constituting alive memory object, and descendant memory objects of said object have not been subject to said trace;

said memory object is further associated with age value indicative of the time duration that said object remains in a given generation

the method comprising the steps of;

(a) partitioning said heap or portion thereof into at least two generations; and

(b) applying substantiality on-the-fly garbage collection to memory objects in at least one from among said generations, whilst running at least one program thread;

said on-the-fly garbage collection includes promoting memory objects to older generation according to at least said age value and updating said age value;

said step (b) includes;

(i) upon starting said collection active cycle, the program thread assigning the third value to any memory object a reference to which is subject to a reference modification;

(ii) the program assigning a first inter-generational value, during said collection cycle, to an inter-generational value associated with a memory object that is subject to a reference modification;

(iii) the on-the-fly garbage collection performing, during said collection active cycle, for any memory object associated with said second identifier value and having an inter-generational value indicative of candidate inter-generational reference, the following steps that include;

(1) assigning to an inter-generational value associated with said memory object a second inter-generational value;

(2) associating said third value to any memory object being descendant of said memory object, stipulated in (ii), and which descendant object being associated with said first value;

(3) in response of assigning said third value to all descendant objects of said memory object, stipulated in (ii), setting said inter-generational value to said first inter-generational value.