Electrical computers and digital processing systems: memory – Storage accessing and control – Memory configuring
Reexamination Certificate
1999-11-29
2004-01-20
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Memory configuring
C711S159000, C711S173000, C707S793000
Reexamination Certificate
active
06681306
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of Invention
The present invention relates generally to methods and apparatus for improving the performance of software applications. More particularly, the present invention relates to methods and apparatus for reducing the overhead associated with performing memory allocation.
2. Description of the Related Art
The amount of available memory is typically limited in computing systems such as object-based computing systems. Hence, 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 as “garbage” objects or “dead” 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 are capable of changing 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.
Generally, to reduce the computational burden associated with garbage collection, a managed memory area is divided into smaller sections to enable garbage collection to be performed locally in one area at a time. One memory partitioning scheme is generational garbage collection. In generational garbage collection, 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
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. “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. 1
is a diagrammatic representation of an area of computer memory which contains objects and is suitable for generational garbage collection. A managed area of memory
102
, which is typically a heap associated with a computer system, is divided into a new generation
104
and an old generation
106
. New generation
104
contains recently created objects
110
, e.g., objects
110
a
-
110
e
, while old generation
106
contains objects
110
which were created less recently, e.g., objects
110
f
and
110
g
. When an object
110
is to be created in memory
102
, the object is created in new generation
104
. In the event that new generation
104
becomes full to the extent that a new object
110
may not be allocated in new generation
104
, a scavenging garbage collection may be performed on new generation
104
to free memory space.
In general, an object
110
may be referenced by other objects
110
. By way of example, object
110
b
has a pointer
114
a
to object
110
a
. As will be understood by one of skill in the art, object
110
b
may be considered to be live when a root points to object
110
b
transitively. That is, when object
110
b
is pointed to by a list of pointers which, in turn, is identified by a root, then object
110
b
is considered to be live.
When new generation object
110
d
is live and points to old generation object
110
f
, garbage collection performed in old generation
106
does not generally “collect” object
110
f
, since object
110
f
is referenced by a live object. However, if new generation object
110
d
is dead, a garbage collection performed in new generation
104
may result in old generation object
110
f
becoming unreachable if old generation object
110
f
is not be pointed to by any other object. If old generation object
110
f
is unreachable, then garbage collection performed in old generation
106
will result in the collection of old generation object
110
f
. When a pointer
114
b
points from new generation object
110
d
to old generation object
110
f
, old generation object
110
f
is considered to be tenured garbage, as old generation object
110
f
is not collectable using new generation garbage collection, i.e., a garbage collection performed on new generation
104
.
During a scavenging garbage collection process performed on new generation
104
when new generation
104
becomes full, as will be discussed below with respect to
FIG. 2
, live objects
110
in new generation
104
are copied from new generation
104
into old generation
106
. Newly allocated objects
110
in new generation
104
are often live and, hence, must be copied from new generation
104
into old generation
106
during a scavenging garbage collection. In general, copying operations are slow and expensive. As a result, the overall garbage collection process is expensive.
Some generational garbage collectors copy live objects from a new generation into an intermediate area before the objects are tenured to an old generation.
FIG. 1
b
is a diagrammatic representation of a memory space which is divided into a new generation, an intermediate area, and an old generation. A memory space
202
includes a new generation
204
, a “from-space” and “to-space”
205
, and an old generation
206
. Newly allocated objects
210
are allocated in new generation
204
. When new generation
204
becomes full, live objects
210
are copied out of new generation
204
and into from-space and to-space
205
. Objects
210
are allowed to remain in from-space and to-space
205
for some period of time, e.g., for a predetermined amount of time or until from-space and to-space
205
is full, to enable objects
210
in from-space and to-space
205
to die. Periodically, as for example when from-space and to-space
205
is full, a garbage collection is performed on from-space and to-space
205
. During garbage collection on from-space and to-space
205
, live objects in from-space and to-space
205
are copied into, or tenured to, old generation
206
.
With reference to
FIG. 2
, one conventional method of performing a scavenging garbage collection on a managed area of memory which is divided into a new generation and an old generation, e.g., managed area
102
of
FIG. 1
, will be described. Specifically, a process of performing a scavenging garbage collection on a new generation will be discussed. A process
252
of performing a garbage collection begins at step
256
in which a list of live objects in the new generation is obtained. A list of live objects may be obtained using a variety of different methods. For example, one method which may be used to obtain a list of live objects involves studying global objects, or roots, which reference objects within either or both a new generation and an old generation to identify objects which are currently in use.
After a list of live objects is obtained, a live object identified in the list is obtained from th
Grarup Steffen
Kessler Peter B.
Ungar David M.
Anderson Matthew D.
Beyer Weaver & Thomas LLP
Kim Matthew
Sun Microsystems Inc.
LandOfFree
Method and apparatus for increasing scavenging garbage... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for increasing scavenging garbage..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for increasing scavenging garbage... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3264517