Electrical computers and digital processing systems: memory – Storage accessing and control – Shared memory area
Reexamination Certificate
1998-06-30
2001-03-27
Bragdon, Reginald G. (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Shared memory area
C711S170000, C711S173000
Reexamination Certificate
active
06209066
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of Invention
The present invention relates generally to memory allocation in computer systems. More particularly, the present invention relates to efficient, low-overhead memory allocation in multi-threaded, object-based computer systems.
2. Description of the Related Art
As the use of virtual machines in computer technology increases, improving the overall efficiency of a virtual machine is becoming more important. The amount of memory associated with a computer system that includes a virtual machine 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, while other programming languages require explicit manual deallocation of previously allocated memory, which deallocation may be complicated and prone to error. Languages that 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 that 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 that are in use are generally referred to as “live” objects, whereas objects that 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, and an automatic storage-reclamation system is often referred to as a garbage collector. Computer programs written in languages such as the Java™ programming language (developed by Sun Microsystems, Inc.) and the Smalltalk programming language use garbage collection to automatically manage memory.
The use of a compacting garbage collector generally allows objects to be allocated relatively quickly. That is, one advantage of using a compacting garbage collector is fast allocation of objects. Objects may be allocated in a contiguous memory area, e.g., an allocation area, such that the allocation of the objects may be performed by incrementing an allocation pointer by the desired amount of storage. When the end of the allocation area has been reached, a garbage collection may be performed.
One garbage collection method is a generational garbage collection method. A generational garbage collection method is a method 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
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.
In a system that uses generational garbage collection, a special memory area is designated for the allocation of new objects. Such a memory area is generally considered to be a “nursery,” as new objects are allocated within the memory area. As will be appreciated by those skilled in the art, the memory area is often referred to as “Eden.”
FIG. 1
a
is a diagrammatic representation of a single thread and a memory allocation area that is dedicated to the single thread. Such a memory allocation area is suitable for implementation within a single-threaded system that uses generational garbage collection. As shown, a memory allocation area
102
, which may be known as Eden, is indexed by an allocation pointer
104
. In general, Eden
102
is a block of memory in which new objects may be created. When a thread
106
, which is associated with Eden
102
, attempts to allocate a new object, allocation pointer
104
is typically incremented by the size of the new object, and a check is made to determine if allocation pointer
104
has reached the end of Eden
102
. When it is determined that the end of Eden
102
has been reached, a generational garbage collection may be performed to effectively empty Eden
102
, thereby allowing new objects to be created by thread
106
within Eden
102
.
While the allocation of memory and, hence, new objects, as described with respect to
FIG. 1
a
is effective in a single-threaded system, such an allocation of memory and objects generally may not be used in a multi-threaded system with multiple central processing units (CPUs). By way of example, when two threads concurrently attempt to request space in a single Eden, concurrency problems may arise. As such, in a multi-threaded system, when Eden is a shared resource, access to Eden must generally be synchronized in order to prevent more than one thread from allocating in Eden at any given time. Synchronizing access to Eden may involve associating an allocation lock with Eden that is obtained by a thread when the thread wishes to create a new object, and released by the thread after the new object has been created.
FIG. 1
b
is a diagrammatic representation of two threads and a memory allocation area shared by the two threads within an overall multi-threaded system. An Eden
112
has an associated allocation pointer
114
which is arranged to indicate the beginning of an unused portion
115
of Eden
112
. When threads
116
and
118
, which share Eden
112
, wish to allocate a new object in Eden
112
, they must generally obtain the allocation lock (not shown) associated with Eden
112
. Specifically, if thread
116
wishes to access unused portion
115
, thread
116
must obtain the allocation lock on Eden
112
. Once thread
116
obtains the allocation lock, and it is determined that the end of Eden
112
has not been reached, allocation pointer
114
may be incremented, and a new object may be allocated by thread
116
. If the end of Eden
112
has been reached, i.e., when unused portion
115
is null, a garbage collection may be performed to effectively empty Eden
112
, thereby allowing new objects to be created by threads
116
and
118
.
When access to Eden is synchronized, the allocation of new objects within Eden is typically slowed considerably due to the overhead associated with the acquisition of and the releasing of the allocation lock associated with Eden. Each time a thread wishes to create a new object in Eden, the thread must acquire exclusive rights to Eden, as for example by acquiring an allocation lock. In general, even so-called “fast” locking primitives which are directly implemented by hardware, e.g., a compare-and-swap primitive, may be relatively slow when compared to the base costs associated with allocation. For instance, on a multiprocessor system, a locking primitive may incur a remote cache miss, as will be appreciated by those skilled in the art. In such a system, adding synchronization features often significantly increases the cost of allocation, e.g., by a factor of two or three. Hence, adding synchronization during allocation greatly affects the performance of the overall system.
In order to improve performance associated with accessing Eden in a multi-threaded system by avoiding synchronization, each thread in the multi-threaded system may be assigned its own Eden. That is, when each thread has its own Eden, concurrency problems that may arise when more than one thread attempts to access a shared Eden may be avoided.
FIG. 2
a
is a diagrammatic representation of two threads with their own associated Edens, or memory allocation areas. Within a multi-threaded system
200
, a first Eden
202
, which is referenced by an allocation pointer
204
, is associated w
Grarup Steffen
Holzle Urs
Beyer Weaver & Thomas LLP
Bragdon Reginald G.
Sun Microsystems Inc.
Vital Pierre H.
LandOfFree
Method and apparatus for memory allocation in a... 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 memory allocation in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for memory allocation in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2448289