Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-06-30
2002-07-16
Black, Thomas (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
Reexamination Certificate
active
06421689
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to management of memory in a computer, and in particular, to garbage collection.
BACKGROUND OF THE INVENTION
Many computer systems provide for dynamic allocation of data objects. The performance of these systems relies on the ability to reclaim memory and re-use memory for dynamically allocated objects after the objects are no longer being used by an executing program. In practice, an object is considered unused when no reference on a computer system refers to the object. When no reference refers to an object, the object is referred to as being dead. Garbage collection includes the process of automatically reclaiming memory allocated to dead objects.
One conventional method of garbage collection is the “tracing” approach. A trace is the identification of objects which may be referenced, directly or indirectly, through a reference in a root set. A root set is one or more areas of memory that contain references which refer to, directly or indirectly, objects that are considered to be “live” for the purposes of garbage collection. A base set is a set of root sets that are traced by a garbage collector to find all the live objects in issue in the area of memory being managed by the garbage collector. Any object not identified through a trace of the root sets in the base set are considered dead, and memory allocated to the object may be reclaimed. For example, object A, object B, and object C reside in memory A. Call stack S is a root set. A reference from call stack S refers to object A, and a reference within object A refers to object B. Object A is thus directly referenced by the reference in call stack S and, object B is indirectly referenced by the reference in call stack S. A trace through the call stack identifies object A and object B, but not object C. Object C is therefore dead, and memory allocated to object C may be reclaimed.
The tracing approach poses several problems for computer systems that use large amounts of memory to store objects. Because execution of processes running on the computer system (e.g. real-time applications) are paused during garbage collection, and a trace accesses all the active objects, long delays in the execution of the processes may occur. Furthermore, accessing all the objects on a computer system violates the presumption of locality of reference that underlies virtual memory operating systems, and may result in excessive memory page thrashing.
These problems have prompted the development of the generational approach to garbage collection. Under the generational approach, two or more areas of memory are used to store objects according to age. The generational approach takes advantage of the empirical observation that newly created (“young”) objects tend to “die” quickly (i.e. become unused). Newly created objects under a threshold size (small objects tend to have small life times) are stored in an area of memory referred to as a “nursery”.
Under the generational approach, as the object in a nursery ages (e.g. remains alive after a threshold number of garbage collection cycles), the objects are moved from the nursery into another area of memory for storing older objects. Because the nursery contains the newer objects, the memory that is most often reclaimed and reallocated is clustered (i.e. in the nursery). Furthermore, garbage collection is performed more often on objects in the nursery. Thus, under the generational approach, locality of reference is improved.
One common approach to collecting memory from a nursery is the copying approach. Under the “copying” approach, an area of memory (i.e. the nursery) is divided into semispaces. One semispace is designated as the “to-space”, and one is designated as the “from-space”. Live objects are stored in the from-space, and newly created objects are allocated memory from the from-space.
When there is insufficient memory to allocate for a new object, garbage collection is performed. Objects identified as live through a trace are copied into the to-space. Because most objects in a nursery are dead due to the short life span of the objects, after copying the live objects the total memory allocated to objects in the to-space is much smaller than that was allocated in the from-space. The difference represents reclaimed memory.
In addition to copying objects, a reference referring to any object that was copied must be reset to refer to the new location of the copied object. Finally, the to-space is established as the current from-space, and the former from-space becomes the current to-space. New objects are allocated memory from the reclaimed portion of the newly established from-space.
Some computer languages lack runtime typing of data. It is not always possible to identify at runtime the references used by programs written in such languages. Garbage collectors used to manage the objects used by such programs are hampered by the difficulty in distinguishing object references from other types of data structures (e.g. integers, characters). A memory area that may contain one or more references (e.g. pointers) that may not be distinguishable from other types of data structures stored in the memory area is referred to as an ambiguous root set. A “C” call stack is an example of an ambiguous root set (i.e. a four byte entity stored in the call stack might represent a reference or a procedure parameter of the type integer).
The term “ambiguous reference” refers to a portion of memory (e.g. the number of bytes in a pointer) which may or may not be a reference, but if evaluated as a reference refers to an area of memory occupied by an object. An object referred to by an ambiguous reference is considered to be live and may not be moved to another memory location for the following reason. After moving such an object, the ambiguous reference could not be modified because the ambiguous reference might in fact not be a reference, but instead, may be, for example, an integer. On the other hand, moving the object without modifying the ambiguous reference would break a reference to the object, if indeed the ambiguous reference was in fact a reference.
A hybrid of the copying approach that accounts for the problem of ambiguous references has been proposed by Bartlett. Structures shown in
FIG. 1
are used to illustrate the Bartlett approach.
FIG. 1
depicts from-space
102
and ambiguous root set
104
. From-space
102
contains live object
132
, and dead objects
134
,
142
, and
152
. Garbage collection of objects in from-space
102
and its corresponding to-space (not shown) is performed by a garbage collector. Objects in from-space
102
and its corresponding to-space are sufficiently described to garbage collector
170
such that garbage collector
170
may discern boundaries between objects and the data structures contained within objects, as well as the data type of the data structures (i.e. integer, pointer).
Under the Bartlett approach, both the to-space (not shown) and from-space
102
are logically divided into pages, like page
130
. Furthermore, an object cannot span a page. Thus, typically there is some memory left unallocated between the last object in a page and the end of the page.
Furthermore, during garbage collection, if any ambiguous reference in ambiguous root set
104
refers to memory that falls within a page, the whole page is “pinned”. When a page is pinned, the objects contained in the page are left in the to-space and cannot be garbage collected. In addition, any other objects referred to (directly or indirectly) by objects in the pinned page become ineligible for garbage collection.
For example, ambiguous root set
104
contains an ambiguous reference
106
, which refers to object
132
in page
130
. Thus page
130
is pinned. Furthermore, object
134
, which is in page
130
, cannot be moved or garbage collected. Object
134
refers to object
142
. Although object
142
can be moved, it cannot be garbage collected. Likewise, object
152
, which is referred to by object
142
(and thus indirectly by object
134
), can be moved but
Benson Peter
Sexton Harlan
Bingham Marcel K.
Black Thomas
Hickman Palermo & Truong & Becker LLP
Le Uyen
Oracle Corporation
LandOfFree
Moderately conservative, mostly copying 2 space 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 Moderately conservative, mostly copying 2 space garbage..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Moderately conservative, mostly copying 2 space garbage... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2897662