Reducing the memory footprint of a session duration semispace

Details Reducing the memory footprint of a session duration semispace Reducing the memory footprint of a session duration semispace

1998-10-13

2001-08-21

Black, Thomas (Department: 2171)

Data processing: database and file management or data structures

Database design

Data structure types

Reexamination Certificate

active

06279012

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to the garbage collection of objects.
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 and re-use memory that has been dynamically allocated to 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 “dead”. Garbage collection refers to the process of automatically reclaiming memory that is currently allocated to dead objects.
Garbage collection may be performed in cycles referred to as garbage collection cycles. During a garbage collection cycle, a set of operations are performed to identify the dead and live objects within a memory area at a particular point in time, and to reclaim memory allocated to the identified dead objects. Typically, during a garbage collection cycle, the objects that reside in the memory that is undergoing garbage collection may not be accessed by user processes (processes that are not involved in the garbage collection operation).
A garbage collection cycle is commenced when a garbage collection event is detected. Garbage collection events include, for example, an “insufficient memory” response during an attempt to allocate memory for a new object. A garbage collection event may simply be the lapse of a threshold period of time, thus causing garbage collection to be performed on a periodic basis.
One conventional method of garbage collection is known as the “tracing” approach. According to the tracing approach, a “trace” is performed during each garbage collection cycle. A trace is an operation performed to identify objects that are not dead (i.e. “live” objects). During a trace, live objects are identified by following direct and indirect references that exist in one or more areas of memory. An area of memory that contains references which directly or indirectly refer to live objects is referred to as a “root set”. A base set is a set of root sets that are traced by a garbage collector to find all the live objects 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 is considered dead, and memory allocated to the object may be reclaimed. For example, assume that a call stack S is the only root set in the base set for a garbage collector that manages memory A. Assume also that object A, object B, and object C reside in memory A. 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 therefore 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.
One common approach used in conjunction with the tracing approach is the copying approach. Under the conventional “copying” approach, an area of memory is divided into semispaces. A semispace is an area of memory used to store objects which are garbage collected using the copying approach. 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.
During a garbage collection cycle, live objects identified through a trace are copied into the to-space. An object is copied into the to-space beginning at the memory location that immediately follows the memory area into which the previously copied object was copied. Because most objects in the from-space are dead (due to the short life span of the objects), the total memory allocated to the objects copied to the to-space from the from-space is typically much smaller than the amount that was allocated to all objects in the from-space. The difference represents reclaimed memory.
Because the moved objects now reside at new storage locations, all references 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 unoccupied portion of the current from-space (the semispace to which live objects have just been copied).
One advantage of the copying approach is that live objects are compacted into one end of the to-space, thereby reducing fragmentation. Another advantage is that the objects most likely to have longer life spans, i.e. the set of objects that are alive at the end of a garbage collection cycle, are clustered into fewer pages of memory. This results in greater data locality.
A disadvantage of the copying approach is that memory utilization is inefficient. Because the memory area managed by the garbage collector is divided into two semispaces, only one of which is used to store live objects, the greatest memory utilization that may be achieved is 50%. This inefficiency becomes more problematic for memory areas that are concurrently shared by a relatively greater number of processes.
FIG. 1
, for example, shows a database system
101
, which is used to illustrate problems associated with the conventional copying approach on computer systems with memory areas that are concurrently shared by a relatively large number of processes. Referring to
FIG. 1
, database system
101
receives calls from one or more clients
160
. A call is a request to perform a task. A call may be, for example, a query in the form of an SQL statement, or a method invocation of a Java™ object or class residing on database system
101
.
Before client
161
issues any calls to database server
101
, a database session must be created for client
161
. A database session is the establishment of a particular connection between a client and a database system through which a series a calls may be made. While the client remains connected in the database session, the client and the database session are referred to as being active.
When client
161
calls database server
101
, one of server processes
110
is assigned to execute the call. At any given moment of time, a server process is assigned to execute the call of no more than one client. However, after a server process completes its execution of a call from one client, the server process may be assigned to respond to the call of another client. Thus, over a period of time, a server process may be assigned to execute the calls of multiple clients.
The number of calls requiring execution by a server process is typically less than the current number of active clients. Thus, database system
101
is typically configured to run less server processes than the maximum number of clients who may be active.
Database system
101
includes various memory areas used to store data used by server processes
110
. These include call shared memory area
120
, call global area
130
, and session space
140
. A shared memory area, such as shared memory area
120
, is used to store data that may be shared concurrently by more than one process. For example, shared memory area may be used store the code for routines (e.g. byte code of Java classes) executed by multiple server processes
110
.
A call global area, such as call global area
13

Affiliated with

Also associated with

Rating

Reducing the memory footprint of a session duration semispace does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Reducing the memory footprint of a session duration semispace, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reducing the memory footprint of a session duration semispace will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2517674