On-the-fly garbage collector

• US 6,490,599 B2
• Filed: 12/11/2000
• Issued: 12/03/2002
• 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.
• Application Number:
  US09/733,085
• Publication Number:
  US 20010000821A1
• Time in Patent Office: 722 Days
• Field of Search: 707/206, 711/147-173
• 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, whilst running simultaneously a program thread.

Claims

1. A method for performing garbage collection of memory objects in a memory heap, the method comprising the steps of:

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

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

2. The method of claim 1, wherein said memory objects are associated with inter-generational values and identifier values and wherein said step (b) further includes manipulating inter-generational values and identifier values associated with said memory objects, whilst avoiding races.

3. The method of claim 2, wherein said step of manipulating includes synchronizing between said inter-generational values and identifier values associated with said memory objects.

4. The method of claim 2, wherein said inter-generational values and the identifier values, stipulated in said step (b), are stored in respective separate atomic write units.

14. A computer system having a memory that includes data representative of memory objects in a memory heap;

the memory heap or portion thereof is partitioned into at least two generations;

the memory objects in at least one of said generations sustain after applying the garbage collection step according to claim 1.

5. A computer system that includes memory for performing garbage collection of memory objects in a memory heap, the heap or portion thereof is partitioned into at least two generations;

the system comprising;

at least one program thread running in said computer system;

a garbage collector for applying substantially on-the-fly garbage collection to memory objects in at least one from among said generations, whilst running at least one of said program threads.

6. The system of claim 5, wherein said memory objects are associated with inter-generational values and identifier values and wherein said at least one program thread and garbage collector are capable of manipulating inter-generational values and identifier values associated with said memory objects whilst avoiding races.

7. The system of claim 5, wherein said inter-generational values and the identifier values are stored in respective separate atomic write units.

8. The system of claim 6, wherein said manipulating further includes utilizing a unique color identifier value for avoiding premature promotion of memory objects from a young generation to an older generation from among said at least two generations.

9. The system of claim 6, wherein said manipulating utilizes identifier toggling.

10. The system of claim 6, 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 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.

11. The system of claim 10, wherein said time duration is measured in number of collection cycles.

12. The system of claim 6, wherein said memory object is associated with two inter-generational values, said manipulation further including said two inter-generational values for avoiding weak consistency.

13. The system of claim 6, wherein said first identifier value, second identifier value and third identifier value correspond to a first color, second color and third color, respectively.