Collection-tick mechanism for a collector based on the train algorithm

• US 20040111449A1
• Filed: 12/06/2002
• Published: 06/10/2004
• Est. Priority Date: 12/06/2002
• 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,069,280 B2
• Time in Patent Office: Days
• US Class Current: 707/206
• CPC Class Codes: G06F 12/0276 Generational garbage collection
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

A garbage collector employs the train algorithm to collect a generation in a dynamically allocated heap. When direct allocation of an object into the generation results in the need to allocate a new car section, the collector makes a determination of whether a new collection increment or interval needs to be initiated. It makes this determination by comparing the amount of new allocation in that generation with a threshold value. During each collection increment, it updates the threshold value by determining how much can occur during the next collection increment without exceeding an allowable pause time. It then projects from that value how much memory-space reclamation is likely to occur. From that likely amount of reclamation, it arrives at a limit on the permitted amount of allocation.

Claims

1. For employing a computer system, which includes memory of which at least some is used as a heap for dynamic allocation, to perform as a garbage collector that collects an incrementally collected generation of the heap in collection increments in which the generation is treated as divided into allocation regions, a method comprising repeatedly:

A) allocating objects in the generation between increments of collection of the generation;

B) responding to some allocations of objects in the generation by making a determination of whether the amount of allocation has met a predetermined trigger criterion, the allocation of a given object in the generation causing an evaluation of whether the amount of allocation has met the trigger criterion only when that object is allocated in a new allocation region; and

C) initiating a collection increment when the amount of allocation is thereby found to meet the trigger criterion.

2. A method as defined in claim 1 wherein:

A) the method further includes;

i) projecting a projected amount of reclamation by computing it from the size of a collection set projected to be collected in an upcoming collection increment; and

ii) determining a maximum allocation amount by computing it from the projected amount of reclamation; and

B) the determination of whether the amount of allocation has met a predetermined trigger criterion includes computing an allocation amount from the amount of allocation that has occurred since the most-recent collection increment and comparing the allocation amount thus computed with the maximum allocation amount.

3. A method as defined in claim 2 wherein the projected amount of reclamation is computed by computing the size of the collection set projected to be collected in an upcoming collection increment from an allowed pause time.

4. A method as defined in claim 1 wherein:

A) the collector treats the generation as divided into car sections organized into trains and collects it in accordance with the train algorithm; and

B) the allocation regions are the car sections.

12. A computer system as defined in claim 1 wherein the projected amount of reclamation is computed by computing the size of the collection set projected to be collected in an upcoming collection increment from an allowed pause time.

5. For employing a computer system, which includes memory of which at least some is used as a heap for dynamic allocation, to perform garbage collection on an incrementally collected generation of the heap in collection increments in which respective collection sets are collected, a method comprising:

A) projecting a projected amount of reclamation by computing it from the size of a collection set projected to be collected in an upcoming collection increment;

B) determining a maximum allocation amount by computing it from the projected amount of reclamation;

C) repeatedly making a determination, by computing an allocation amount from the amount of allocation that has occurred since the most-recent collection increment and comparing the allocation amount thus computed with the maximum allocation amount, of whether to trigger a collection increment; and

D) triggering a collection increment in response to an affirmative result of such a determination.

6. A method as defined in claim 5 wherein the projected amount of reclamation is computed by computing the size of the collection set projected to be collected in an upcoming collection increment from an allowed pause time.

7. A computer system comprising:

A) processor circuitry operable to execute processor instructions; and

B) memory circuitry, to which the processor circuitry is responsive, that contains processor instructions readable by the processor circuitry to configure it to;

i) treat at least a portion of the memory as a heap, in which dynamic allocation occurs,

ii) act as a garbage collector that collects an incrementally collected generation of the heap in collection increments in which the generation is treated as divided into allocation regions; and

iii) repeatedly;

a) allocate objects in the generation between increments of collection of the generation;

b) respond to some allocations of objects in the generation by making a determination of whether the amount of allocation has met the trigger criterion, the allocation of a given object in the generation causing an evaluation of whether the amount of allocation has met the trigger criterion only when that object is allocated in a new car section; and

C) initiate a collection increment when the amount of allocation is thereby found to meet the trigger criterion.

8. A computer system as defined in claim 7 wherein:

A) the instructions further configure the processor circuitry to;

i) project a projected amount of reclamation by computing it from the size of a collection set projected to be collected in an upcoming collection increment; and

ii) determine a maximum allocation amount by computing it from the projected amount of reclamation; and

B) the determination of whether the amount of allocation has met a predetermined trigger criterion includes computing an allocation amount from the amount of allocation that has occurred since the most-recent collection increment and comparing the allocation amount thus computed with the maximum allocation amount.

9. A computer system as defined in claim 8 wherein the projected amount of reclamation is computed by computing the size of the collection set projected to be collected in an upcoming collection increment from an allowed pause time.

10. A computer system as defined in claim 7 wherein:

A) the collector treats the generation as divided into car sections organized into trains and collects it in accordance with the train algorithm; and

B) the allocation regions are the car sections.

11. A computer system comprising:

A) a processor circuitry operable to execute processor instructions; and

B) memory circuitry, to which the processor circuitry is responsive, that contains processor instructions readable by the processor circuitry to configure it to;

i) treat at least some of the memory as a heap, in which dynamic allocation occurs;

ii) perform garbage collection on an incrementally collected generation of the heap in collection increments in which respective collection sets are collected;

iii) project a projected amount of reclamation by computing it from the size of a collection set projected to be collected in an upcoming collection increment;

iv) determine a maximum allocation amount by computing it from the projected amount of reclamation;

v) repeatedly make a determination, by computing an allocation amount from the amount of allocation that has occurred since the most-recent collection increment and comparing the allocation amount thus computed with the maximum allocation amount, of whether to trigger a collection increment; and

vi) trigger a collection increment in response to an affirmative result of such a determination.

13. A storage medium containing instructions readable by processor circuitry in a computer system including memory to configure the processor circuitry to:

A) treat at least a portion of the memory as a heap, in which dynamic allocation occurs,

B) act as a garbage collector that collects an incrementally collected generation of the heap in collection increments in which the generation is treated as divided into allocation regions; and

C) repeatedly;

i) allocate objects in the generation between increments of collection of the generation;

ii) respond to some allocations of objects in the generation by making a determination of whether the amount of allocation has met the trigger criterion, the allocation of a given object in the generation causing an evaluation of whether the amount of allocation has met the trigger criterion only when that object is allocated in a new car section; and

iii) initiate a collection increment when the amount of allocation is thereby found to meet the trigger criterion.

14. A storage medium as defined in claim 13 wherein:

A) the instructions further configure the processor circuitry to;

i) project a projected amount of reclamation by computing it from the size of a collection set projected to be collected in an upcoming collection increment; and

ii) determine a maximum allocation amount by computing it from the projected amount of reclamation; and

B) the determination of whether the amount of allocation has met a predetermined trigger criterion includes computing an allocation amount from the amount of allocation that has occurred since the most-recent collection increment and comparing the allocation amount thus computed with the maximum allocation amount.

15. A storage medium as defined in claim 14 wherein the projected amount of reclamation is computed by computing the size of the collection set projected to be collected in an upcoming collection increment from an allowed pause time.

16. A storage medium as defined in claim 13 wherein:

A) the collector treats the generation as divided into car sections organized into trains and collects it in accordance with the train algorithm; and

B) the allocation regions are the car sections.

17. A storage medium containing instructions readable by processor circuitry in a computer system that also includes memory to configure the processor circuitry to:

A) treat at least some of the memory as a heap, in which dynamic allocation occurs;

B) perform garbage collection on an incrementally collected generation of the heap in collection increments in which respective collection sets are collected;

C) project a projected amount of reclamation by computing it from the size of a collection set projected to be collected in an upcoming collection increment;

D) determine a maximum allocation amount by computing it from the projected amount of reclamation;

E) repeatedly make a determination, by computing an allocation amount from the amount of allocation that has occurred since the most-recent collection increment and comparing the allocation amount thus computed with the maximum allocation amount, of whether to trigger a collection increment; and

F) trigger a collection increment in response to an affirmative result of such a determination.

18. A storage medium as defined in claim 17 wherein the projected amount of reclamation is computed by computing the size of the collection set projected to be collected in an upcoming collection increment from an allowed pause time.

19. An electromagnetic signal representing sequences of instructions that, when executed by processor circuitry in a computer system that includes memory to configure the processor circuitry to:

A) treat at least a portion of the memory as a heap, in which dynamic allocation occurs,

B) act as a garbage collector that collects an incrementally collected generation of the heap in collection increments in which the generation is treated as divided into allocation regions; and

C) repeatedly;

i) allocate objects in the generation between increments of collection of the generation;

ii) respond to some allocations of objects in the generation by making a determination of whether the amount of allocation has met the trigger criterion, the allocation of a given object in the generation causing an evaluation of whether the amount of allocation has met the trigger criterion only when that object is allocated in a new car section; and

iii) initiate a collection increment when the amount of allocation is thereby found to meet the trigger criterion.

iv)

20. A electromagnetic signal as defined in claim 19 wherein:

A) the instructions further configure the processor circuitry to;

i) project a projected amount of reclamation by computing it from the size of a collection set projected to be collected in an upcoming collection increment; and

ii) determine a maximum allocation amount by computing it from the projected amount of reclamation; and

B) the determination of whether the amount of allocation has met a predetermined trigger criterion includes computing an allocation amount from the amount of allocation that has occurred since the most-recent collection increment and comparing the allocation amount thus computed with the maximum allocation amount.

21. A electromagnetic signal as defined in claim 20 wherein the projected amount of reclamation is computed by computing the size of the collection set projected to be collected in an upcoming collection increment from an allowed pause time.

22. A electromagnetic signal as defined in claim 19 wherein:

A) the collector treats the generation as divided into car sections organized into trains and collects it in accordance with the train algorithm; and

B) the allocation regions are the car sections.

23. An electromagnetic signal representing sequences of instructions that, when executed by processor circuitry in a computer system that includes memory to configure the processor circuitry to:

A) treat at least some of the memory as a heap, in which dynamic allocation occurs;

B) perform garbage collection on an incrementally collected generation of the heap in collection increments in which respective collection sets are collected;

C) project a projected amount of reclamation by computing it from the size of a collection set projected to be collected in an upcoming collection increment;

D) determine a maximum allocation amount by computing it from the projected amount of reclamation;

E) repeatedly make a determination, by computing an allocation amount from the amount of allocation that has occurred since the most-recent collection increment and comparing the allocation amount thus computed with the maximum allocation amount, of whether to trigger a collection increment; and

F) trigger a collection increment in response to an affirmative result of such a determination.

24. A electromagnetic signal as defined in claim 23 wherein the projected amount of reclamation is computed by computing the size of the collection set projected to be collected in an upcoming collection increment from an allowed pause time.