Scalable-remembered-set garbage collection

Details Scalable-remembered-set garbage collection Scalable-remembered-set garbage collection

1999-08-19

2002-08-13

Breene, John (Department: 2177)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000

Reexamination Certificate

active

06434577

ABSTRACT:

CROSS-REFERENCE TO RELATED APPLICATIONS
This application is related to commonly assigned U.S. Patent applications of Alexander T. Garthwaite for Popular-Object Handling in a Train-Algorithm-Based Garbage Collector, for a Train-Algorithm-Based Garbage Collector Employing Fixed-Size Remembered Sets, and for a Train-Algorithm-Based Garbage Collector Employing Reduced Oversized-Object Threshold, and it is also related to commonly assigned U.S. Patent applications of Garthwaite et al. for Reduced-Cost Remembered-Set Processing in a Train-Algorithm-Based Garbage Collector and for a Train-Algorithm-Based Garbage Collector Employing Farthest-Forward-Car Indicator, all of which are filed concurrently herewith and are hereby incorporated in their entirety by reference.
BACKGROUND OF THE INVENTION
The present invention is directed to memory management. It particularly concerns what has come to be known as “garbage collection.”
In the field of computer systems, considerable effort has been expended on the task of allocating memory to data objects. For the purposes of this discussion, the term object refers to a data structure represented in a computer system's memory. Other terms sometimes used for the same concept are record and structure. An object may be identified by a reference, a relatively small amount of information that can be used to access the object. A reference can be represented as a “pointer” or a “machine address,” which may require, for instance, only sixteen, thirty-two, or sixty-four bits of information, although there are other ways to represent a reference.
In some systems, which are usually known as “object oriented,” objects may have associated methods, which are routines that can be invoked by reference to the object. They also may belong to a class, which is an organizational entity that may contain method code or other information shared by all objects belonging to that class. In the discussion that follows, though, the term object will not be limited to such structures; it will additionally include structures with which methods and classes are not associated.
The invention to be described below is applicable to systems that allocate memory to objects dynamically. Not all systems employ dynamic allocation. In some computer languages, source programs can be so written that all objects to which the program's variables refer are bound to storage locations at compile time. This storage-allocation approach, sometimes referred to as “static allocation,” is the policy traditionally used by the Fortran programming language, for example.
Even for compilers that are thought of as allocating objects only statically, of course, there is often a certain level of abstraction to this binding of objects to storage locations. Consider the typical computer system
10
depicted in
FIG. 1
, for example. Data, and instructions for operating on them, that a microprocessor
11
uses may reside in on-board cache memory or be received from further cache memory
12
, possibly through the mediation of a cache controller
13
. That controller
13
can in turn receive such data from system read/write memory (“RAM”)
14
through a RAM controller
15
or from various peripheral devices through a system bus
16
. The memory space made available to an application program may be “virtual” in the sense that it may actually be considerably larger than RAM
14
provides. So the RAM contents will be swapped to and from a system disk
17
.
Additionally, the actual physical operations performed to access some of the most-recently visited parts of the process's address space often will actually be performed in the cache
12
or in a cache on board microprocessor
11
rather than on the RAM
14
, with which those caches swap data and instructions just as RAM
14
and system disk
17
do with each other.
A further level of abstraction results from the fact that an application will often be ran as one of many processes operating concurrently with the support of an underlying operating system. As part of that system's memory management, the application's memory space may be moved among different actual physical locations many times in order to allow different processes to employ shared physical memory devices. That is, the location specified in the application's machine code may actually result in different physical locations at different times because the operating system adds different offsets to the machine-language-specified location.
Despite these expedients, the use of static memory allocation in writing certain long-lived applications makes it difficult to restrict storage requirements to the available memory space. Abiding by space limitations is easier when the platform provides for dynamic memory allocation, i.e., when memory space to be allocated to a given object is determined only at run time.
Dynamic allocation has a number of advantages, among which is that the run-time system is able to adapt allocation to run-time conditions. For example, the programmer can specify that space should be allocated for a given object only in response to a particular run-time condition. The C-language library function malloc( ) is often used for this purpose. Conversely, the programmer can specify conditions under which memory previously allocated to a given object can be reclaimed for reuse. The C-language library function free( ) results in such memory reclamation.
Because dynamic allocation provides for memory reuse, it facilitates generation of large or long-lived applications, which over the course of their lifetimes may employ objects whose total memory requirements would greatly exceed the available memory resources if they were bound to memory locations statically.
Particularly for long-lived applications, though, allocation and reclamation of dynamic memory must be performed carefully. If the application fails to reclaim unused memory—or, worse, loses track of the address of a dynamically allocated segment of memory—its memory requirements will grow over time to exceed the system's available memory. This kind of error is known as a “memory leak.”
Another kind of error occurs when an application reclaims memory for reuse even though it still maintains a reference to that memory. If the reclaimed memory is reallocated for a different purpose, the application may inadvertently manipulate the same memory in multiple inconsistent ways. This kind of error is known as a “dangling reference,” because an application should not retain a reference to a memory location once that location is reclaimed. Explicit dynamic-memory management by using interfaces like malloc( )/free( ) often leads to these problems.
A way of reducing the likelihood of such leaks and related errors is to provide memory-space reclamation in a more-automatic manner. Techniques used by systems that reclaim memory space automatically are commonly referred to as “garbage collection.” Garbage collectors operate by reclaiming space that they no longer consider “reachable.” Statically allocated objects represented by a program's global variables are normally considered reachable throughout a program's life. Such objects are not ordinarily stored in the garbage collector's managed memory space, but they may contain references to dynamically allocated objects that are, and such objects are considered reachable. Clearly, an object referred to in the processor's call stack is reachable, as is an object referred to by register contents. And an object referred to by any reachable object is also reachable.
The use of garbage collectors is advantageous because, whereas a programmer working on a particular sequence of code can perform his task creditably in most respects with only local knowledge of the application at any given time, memory allocation and reclamation require a global knowledge of the program. Specifically, a programmer dealing with a given sequence of code does tend to know whether some portion of memory is still in use for that sequence of code, but it is considerably more difficult

Affiliated with

Also associated with

Rating

Scalable-remembered-set garbage collection does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Scalable-remembered-set garbage collection, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scalable-remembered-set garbage collection will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2953589