US 7,624,137 B2Granted

Method and apparatus for scheduling and performing garbage collection in a real-time system with guaranteed space bounds

AssigneeInternational Business Machines Corporation

InventorsDavid Francis Bacon, Perry Cheng, Vadakkedathu Thomas Rajan

Life of this patent

Estimating the term…

Loading patent…

Abstract

A garbage collection system that needs to meet real-time requirements with guaranteed space bounds uses a mostly non-copying hybrid collector that performs defragmentation with limited copying of objects. The garbage collection and the real-time application are interleaved on a time-based schedule. An interval for the interleaving is selected based upon a garbage collector processing rate, a garbage generation rate and a memory allocation rate of the real-time application. An amount of memory for the real-time application and the garbage collection process is selected based upon the maximum excess memory requirement of the garbage collection process and the maximum memory requirement for the application. Defragmentation is only performed when an amount of available memory falls below a predetermined level.

Claims21

Dependent claims

A method of performing a mark and sweep garbage collection process for a real-time application such that it has determinable space bounds, the method comprising:

using a memory for:
allocating memory space for the application, wherein allocated memory is defined to include directly allocated memory and indirectly allocated memory due to mutation;
segmenting the memory space into a number of pages of a predetermined size;
and
dividing the pages into blocks of a predetermined size;
using a mutator for performing an iterative mutation process by:
assuring that only non-null, unmarked objects are placed into a write buffer;
identifying objects to be allocated;
allocating the objects into the pages and blocks;
marking objects no longer used as dead objects;
and
sorting the pages of memory according to a number of dead objects per page;
wherein each iterative mutation process consumes memory a size of one object pointer;
using a trace-based hybrid collector for:
removing the dead objects;
and
defragmenting the memory space using defragmentation with limited copying of objects;
using a processor for selecting an interval for an interleaving based upon a processing rate of the hybrid garbage collector;
wherein the garbage collection process is bounded by a time for collection and an overhead memory space requirement;
and
using a timer for interleaving the garbage collection and the real-time application on a time-based schedule.

18 more elements

A computer-readable medium comprising

a program product for implementing a mark and sweep garbage collection process for a real-time application such that the real-time application can meet real-time requirements, the medium comprising instructions for:
using a memory for:
allocating memory space for the real-time application;
segmenting the memory space into a number of pages;
and
dividing the pages into blocks;
using a mutator for performing an iterative mutation process by:
identifying objects to be allocated;
allocating the objects into the pages and blocks;
marking objects as no longer used as dead objects;
sorting the pages of memory according to a number of dead objects per page;
wherein each mutation process consumes memory a size of one object pointer;
using a trace-based hybrid collector for:
removing the dead objects;
and
defragmenting the memory space using defragmentation with limited copying of objects;
using a processor for selecting an interval for an interleaving based upon a processing rate of the hybrid garbage collector;
wherein the garbage collection process is bounded by a time for collection and an overhead memory space requirement;
and
using a timer for interleaving the real-time application and the garbage collection process on a time-based schedule.

17 more elements

A computer apparatus for performing a real-time application comprising:

a processor for executing instructions;
a memory for storing:
application software for performing the real-time application;
and
a trace-based hybrid collector used to perform defragmentation with limited copying of objects, wherein mark and sweep garbage collection software comprises instructions for:
segmenting a memory space into a number of pages of a predetermined size;
dividing the pages into blocks of a predetermined size;
identifying objects to be allocated;
allocating the objects into the pages and blocks;
marking objects as no longer used as dead objects;
removing the dead objects;
defragmenting the memory space;
wherein the identifying, allocating, marking, and removing instructions are performed iteratively as part of an iterative mutation process and wherein each iteration consumes memory a size of one object pointer;
selecting an interval for an interleaving based upon a processing rate of the hybrid garbage collector;
wherein the garbage collection process is bounded by a time for collection and an overhead memory space requirement;
and
using a timer for interleaving the real-time application and the garbage collection process on a time-based schedule.

14 more elements

Dependencies are inferred from the claim text.