US 7,548,940 B2Granted

Generational real-time garbage collection

AssigneeInternational Business Machines Corporation

InventorsDavid F. Bacon, Perry Chang, David Grove, Martin T. Vechev

Life of this patent

Estimating the term…

Loading patent…

Abstract

Disclosed are a partial heap garbage collector, and a partial heap garbage collection method, that during collection checks the time remaining (or equivalently the time taken so far, or the work done so far) to complete the partial heap collection. In a preferred embodiment, the partial heap collection is guaranteed to complete within a fixed time interval. For example, this guarantee may be obtained by applying a worst-case execution time (WCET) and sizing a nursery so that complete evacuation of the nursery can always be achieved on time. As an alternative, a technique, referred to as syncopation, may be used to allow generational collection to be used despite variance in program behavior over the short time scales in which a nursery can be collected. Syncopation may be accomplished via allocation control or via collection control.

Claims15

Dependent claims

A partial heap garbage collector for managing a memory heap having a nursery portion and a non-nursery portion, the partial heap garbage collector comprising a processor unit including a computer readable processing code, wherein the computer readable processing code, when executing in the processor unit, configures the processor unit for:

collecting data objects in the nursery portion in a defined collection period, said collection period including a plurality of intervals, each of said intervals including a mutator portion and a garbage collector portion;
using time-based scheduling to guarantee that in each of the time intervals, a minimum amount of time is provided for the mutator portion by:
checking, during said collection period, a parameter representing the amount of time or work remaining to complete a defined partial heap collection;
based on the value of said parameter, moving collection work from one of said intervals to another of said intervals to finish a defined partial heap collection within said defined collection period;
and
changing the capacity of the nursery portion from one nursery collection to the next nursery collection to ensure that said next nursery collection is completed in the defined collection period;
for each of a plurality of arrays of data objects, providing an arrayoid and one or more arraylets, the arrayoid including one or more pointers to said one or more arraylets, each of the arraylets being a continuous section of memory areas, and the arraylet size Σ is determined by the memory page size π and a given fragmentation ratio p, where Σ=ρπ;
allocating the arraylets to the non-nursery portion of the memory, including the step of reducing an allocation limit for said nursery portion when one of said arraylets is allocated to said non- nursery portion of the memory using mixed forms of arraylets to bound the fragmentation by ρ;
and
moving the arrayoids to the non-nursery portion of the memory while keeping said pointers in the arrayoids unchanged, to reduce the cost of evacuating the arrays of data objects from the nursery portion of the memory;
wherein said defined partial heap collection is guaranteed to complete within a fixed time interval, and said guarantee to complete the partial heap collection within the fixed time interval is obtained by applying a worst-case execution time (WCET) and sizing the nursery portion whereby complete evacuation of the nursery portion can always be achieved on time.

8 more elements

A partial heap garbage collection method for managing a memory heap having a nursery portion and a non-nursery portion, the nursery portion having a variable capacity, said method comprising the steps of:

collecting data objects in the nursery portion in a defined collection period, said collection period including a plurality of intervals, each of said intervals including a mutator portion and a garbage collector portion;
using time-based scheduling to guarantee that in each of the time intervals, a minimum amount of time is provided for the mutator portion by:
checking, during said collection period, a parameter representing the amount of time or work remaining to complete a defined partial heap collection;
based on the value of said parameter, moving collection work from one of said intervals to another of said intervals to finish a defined partial heap collection within said defined collection period;
and
changing the capacity of the nursery portion from one nursery collection to the next nursery collection to ensure that said next nursery collection is completed in the defined collection period;
for each of a plurality of arrays of data objects, providing an arrayoid and one or more arraylets, the arrayoid including one or more pointers to said one or more arraylets, each of the arraylets being a continuous section of memory areas, and the arraylet size Σ is determined by the memory page size π and a given fragmentation ratio p, where Σ=ρπ;
allocating the arraylets to the non-nursery portion of the memory, including the step of reducing an allocation limit for said nursery portion when one of said arraylets is allocated to said non-nursery portion of the memory using mixed forms of arraylets to bound the fragmentation by ρ;
and
moving the arrayoids to the non-nursery portion of the memory while keeping said pointers in the arrayoids unchanged, to reduce the cost of evacuating the arrays of data objects from the nursery portion of the memory;
wherein said defined partial heap collection is guaranteed to complete within a fixed time interval, and said guarantee to complete the partial heap collection within the fixed time interval is obtained by applying a worst-case execution time (WCET) and sizing the nursery portion whereby complete evacuation of the nursery portion can always be achieved on time.

8 more elements

A method of memory management comprising the steps of:

providing a memory heap having a nursery portion and a non-nursery portion, the nursery portion having a variable capacity;
collecting data objects in the nursery portion in a defined collection period having a plurality of intervals, each of said intervals including a mutator portion and a garbage collector portion;
using time-based scheduling to guarantee that in each of the time intervals, a minimum amount of time is provided for the mutator potion by:
changing the capacity of the nursery portion from one nursery collection to the next nursery collection to ensure that said next nursery collection is completed in the defined collection period;
for each of a plurality of arrays of data objects, providing an arrayoid and one or more arraylets, the arrayoid including one or more pointers to said one or more arraylets, and each of the arraylets being a contiguous section of memory areas, and the arraylet size is determined by the memory page size π and a given fragmentation ratio ρ, where Σ=ρπ;
allocating the arraylets to the non-nursery portion of the memory, including the step of reducing an allocation limit for said nursery portion when one of said arraylets is allocated to said non- nursery portion of the memory;
allocating the arrayoids into said nursery portion;
evacuating the arrayoids from the nursery portion of the memory by moving the arrayoids into the non-nursery portion of the memory without changing any of the pointers of the arrayoids to reduce the cost of evacuating the arrayoids from the nursery portion of the memory heap;
and
using mixed forms of arraylets to bound the fragmentation by ρ;
whereby allocating the arraylets to said non-nursery portion increases the effective size of said nursery portion without increasing either the physical size of said nursery portion or the cost of nursery collection.

8 more elements

A system for computer memory management, for use with arrays of data objects, each of said arrays including an arrayoid and one or more arraylets, the arrayoid of the array including one or more pointers to the one or more arraylets of the array, and each of the arraylets being a contiguous section of memory areas, the system comprising:

a memory heap having a nursery portion and a non-nursery portion, the nursery portion having a variable capacity;
an allocator for allocating the arraylets to the non-nursery portion of the memory, and for allocating the arrayoids into said nursery portion, by reducing an allocation limit for said nursery portion when one of said arraylets is allocated to said non-nursery portion of the memory,
wherein the arraylet size Σ is determined by the memory page size π and a given fragmentation ratio ρ, where Σ=ρπ;
a collector for using time-based scheduling to evacuate the arrayoids from the nursery portion of the memory by moving the arrayoids into the non-nursery portion of the memory without changing any of the pointers of the arrayoids to reduce the cost of evacuating the arrayoids from the nursery portion of the memory heap;
and by changing the capacity of the nursery portion from one nursery collection to the next nursery collection to ensure that said next nursery collection is completed in the defined collection period;
using mixed forms of arraylets to bound the fragmentation by ρ;
wherein the allocator reduces an allocation limit for said nursery portion when one of said arraylets is allocated to said non-nursery portion of the memory, and whereby allocating the arraylets to said non-nursery portion increases the effective size of said nursery portion without increasing either the physical size of said nursery portion or the cost of nursery collection.

4 more elements

A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for a partial heap garbage collection for managing a memory heap having a nursery portion and a non-nursery portion, the nursery portion having a variable capacity, said method steps comprising:

collecting data objects in the nursery portion in a defined collection period, said collection period including a plurality of intervals, each of said intervals including a mutator portion and a garbage collector portion;
using time-based scheduling to guarantee that in each of the time intervals, a minimum amount of time is provided for the mutator portion by:
checking, during said collection period, a parameter representing the amount of time or work remaining to complete a defined partial heap collection;
based on the value of said parameter, moving collection work from one of said intervals to another of said intervals to finish a defined partial heap collection within said defined collection period;
and
changing the capacity of the nursery portion from one nursery collection to the next nursery collection to ensure that said next nursery collection is completed in the defined collection period;
for each of a plurality of arrays of data objects, providing an arrayoid and one or more arraylets, the arrayoid including one or more pointers to said one or more arraylets, each of the arraylets being a continuous section of memory areas, and the arraylet size Σ is determined by the memory page size π and a given fragmentation ratio p, where Σ=ρπ;
allocating the arraylets to the non-nursery portion of the memory, including the step of reducing an allocation limit for said nursery portion when one of said arraylets is allocated to said non-nursery portion of the memory using mixed forms of arraylets to bound the fragmentation by ρ;
and
moving the arrayoids to the non-nursery portion of the memory while keeping said pointers in the arrayoids unchanged, to reduce the cost of evacuating the arrays of data objects from the nursery portion of the memory;
wherein said defined partial heap collection is guaranteed to complete within a fixed time interval, and said guarantee to complete the partial heap collection within the fixed time interval is obtained by applying a worst-case execution time (WCET) and sizing the nursery portion whereby complete evacuation of the nursery portion can always be achieved on time.

8 more elements

Dependencies are inferred from the claim text.