Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-02-09
2001-10-23
Kulik, Paul V. (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
Reexamination Certificate
active
06308185
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of Invention
The invention relates generally to the management of dynamically allocated memory in a computer system. More particularly, the invention relates to tracking references between separate sections of memory associated with a computer system such that automatic storage-reclamation may be performed locally.
2. Description of the Relevant Art
The amount of memory associated with a computer system is typically limited. As such, memory must generally be conserved and recycled. Many computer programming languages enable software developers to dynamically allocate memory within a computer system. Some programming languages require explicit manual deallocation of previously allocated memory, which may be complicated and prone to error. Languages which require explicit manual memory management include the C and C++ programming languages. Other programming languages utilize automatic storage-reclamation to reclaim memory that is no longer necessary to ensure the proper operation of computer programs which allocate memory from the reclamation system. Such automatic storage-reclamation systems reclaim memory without explicit instructions or calls from computer programs which were previously utilizing the memory.
In object-oriented or object-based systems, the typical unit of memory allocation is commonly referred to as an object or a memory object, as will be appreciated by those skilled in the art. Objects which are in use are generally referred to as “live” objects, whereas objects which are no longer needed to correctly execute computer programs are typically referred to a “garbage” objects. The act of reclaiming garbage objects is commonly referred to as garbage collection, while an automatic storage-reclamation system is often referred to as a garbage collector. Computer programs which use automatic storage-reclamation systems are known as mutators due to the fact that such computer programs can change live memory objects during execution. Computer programs written in languages such as the Java™ programming language (developed by Sun Microsystems, Inc. of Palo Alto, Calif.) and the Smalltalk programming language use garbage collection to automatically manage memory.
Objects typically contain references to other objects. As such, an area of computer memory which is managed by a garbage collector will generally contain a set of objects which reference one another.
FIG. 1
is a diagrammatic representation of an area of computer memory which contains objects. A managed area of memory
10
, which is typically a heap associated with a computer system, includes objects
20
. In general, an object
20
may be referenced by other objects
20
. By way of example, object
20
a
has a pointer
24
a
to object
20
b
. Object
20
c
also has a pointer
24
b
to object
20
b
.As such, object
20
b
is referenced by both objects
20
a
and
20
c.
A number of external references into memory
10
. As shown, a fixed root
30
which is external to memory
10
includes pointers
34
to objects, e.g., objects
20
a
and
20
c
,located in memory
10
. All objects, as for example objects
20
a-d
, which may be reachable by following references from fixed root
30
are considered to be live objects. Alternatively, object
20
e
, which is not reachable by following references from fixed root
30
, is characterized as a garbage object.
Garbage collectors are typically implemented to identify garbage objects such as object
20
e
.In general, garbage collectors may operate using a number of different algorithms. Conventional garbage collection algorithms include reference counting collectors, mark sweep collectors, and copying collectors, as described in
Garbage Collection: Algorithms for Automatic Dynamic Memory Management
by Richard Jones and Rafael Lins (John Wiley & Sons Ltd., 1996), which is incorporated herein by reference in its entirety. As will be appreciated by those skilled in the art, during garbage collection, when objects
20
are moved, references to objects
20
must be adjusted accordingly.
It is often beneficial to separate a managed memory area into smaller sections to enable garbage collection to be preformed locally in one area at a time. One memory partitioning scheme is generational garbage collection, in which objects are separated based upon their lifetimes as measured from the time the objects were created. Generational garbage collection is described in more detail in above-referenced
Garbage Collection: Algorithms for Automatic Dynamic Memory Management
by Richard Jones and Rafael Lins (John Wiley & Sons Ltd., 1996). “Younger” objects have been observed as being more likely to become garbage than “older” objects. As such, generational garbage collection may be used to increase the overall efficiency of memory reclamation.
FIG. 2
is a diagrammatic representation of an interface between a root and memory which is partitioned into a new generation and an old generation. A memory
110
, which is typically a heap that is associated with a computer system, includes a new generation
110
a
and an old generation
110
b
. A fixed root
114
, or a global object which references objects within either or both new generation
110
a
and old generation
110
b
, includes pointers
116
to objects
120
in new generation
110
a
, as shown. Root
114
may be located on a stack, as will be appreciated by those skilled in the art.
Some objects
120
within new generation
110
a
, as for example object
120
a
, may also be considered as roots, since object
120
a
is assumed to be live and includes a pointer
122
to another object
120
d
. When new generation object
126
is live and to old generation object
128
, garbage collection performed in old generation
110
b
does not generally “collect” object
128
. However, if new generation object
126
is dead, a garbage collection performed in new generation
110
a
will result in old generation object
128
becoming unreachable, since old generation object
128
will not be pointed to by any other object. If old generation object
128
is unreachable, then garbage collection performed in old generation
110
b
will result in the collection of old generation object
128
. It should be appreciated that pointer
130
, which points between new generation object
126
and old generation object
128
is considered to be an inter-generational pointer, since pointer
130
spans both new generation
110
a
and old generation
110
b
. When pointer
130
points from new generation object
126
to old generation object
128
, old generation object
128
is considered to be tenured garbage, as old generation object
128
is not collectable using new generation garbage collection.
Another memory partitioning scheme involves separating memory into smaller areas in order to reduce the amount of time required for a single garbage collection to be performed. Pauses caused by garbage collection often tend to disrupt an associated mutator and are, therefore, undesirable. In some systems, the garbage collector may be able to provide a guaranteed small maximum pause duration. Such garbage collectors associated are known as real-time garbage collectors. In other systems, the garbage collector may attempt to keep pause times small, but may fail to do so in some situations. Garbage collectors which attempt to keep pause times small are known as non-disruptive or incremental garbage collectors.
In order to operate on an individual memory area, a garbage collector must have knowledge of all references into that area. References into an area are referred to as roots for that area. It should be appreciated that roots may include both external references, e.g., fixed roots, and references from other areas of computer memory. Accordingly, garbage collectors generally provide mechanisms for finding and tracking roots, or references.
One method of locating references into a memory area involves scanning through all objects in memory. For most systems, scanning through all objects in memory is prohibitively time-consuming
Bak Lars
Grarup Steffen
Beyer Weaver & Thomas LLP
Kulik Paul V.
Sun Microsystems Inc.
LandOfFree
Methods and apparatus for generational dynamic management of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for generational dynamic management of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for generational dynamic management of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2568999