Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2002-03-22
2004-01-13
Jung, David (Department: 2134)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
06678697
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to computer system and more particularly to managing memory for a runtime execution environment.
BACKGROUND OF THE INVENTION
In a dynamic run-time environment for a language such as JAVA™, memory management for objects is very important. In specific, a dynamic run-time environment has to handle the allocation and deallocation of memory for objects. An object is an entity that encapsulates data and, in some environments such as JAVA, operations associated with the object.
When an object is created, a certain amount of memory must be allocated for the object. When the object is no longer needed, the memory for the object needs to be deallocated so that it can be reused for other purposes. Memory deallocation can be manual, as in the C programming languages, or handled automatically by a “garbage collector.” There are various types of garbage collectors. For example, a generational garbage collector distinguishes objects based on their lifetime because a recently-allocated object is usually a short-lived object. In one implementation of a generational garbage collector, objects are stored in one of at least two memory areas, referred to as “oldspace” and “newspace.” When an object is first created, memory for the object is allocated out the newspace. After the object has lasted for a period time, such as four scavenges of newspace, it is “tenured” and migrated into the oldspace.
Use of different memory areas for objects, where the different areas are distinguished by the lifetime of the objects contained therein, allows the generational garbage collector to employ different allocation and garbage collection strategies for the memory areas. For example, since newspace tends to hold many objects that are frequently allocated and abandoned, memory allocation within newspace is preferably implemented by a cheap technique such as “frontier consing” (incrementing a pointer to the beginning of free storage) and garbage collection by a copying garbage collector. On the other hand, since oldspace tends to hold fewer and longer-lived objects, it may be preferable to perform memory allocation a buddy or best fit allocation technique, and deallocation by a mark-sweep garbage collector.
The performance of a generational garbage collector is greatly affected by the efficiency of calculating a “root set” for all the objects in newspace. A root set for newspace is a set of objects such that the transitive closure of the set contains all the live objects in newspace. In specific, it is important to determine all the oldspace objects that reference objects in newspace. One method of simplifying the root set calculation is to maintain a “remember table,” which is a data structure used by the garbage collector to record which objects in newspace are referenced by an object in oldspace. The remember table is updated when an assignment operation might places a reference to a newspace object in an oldspace object. The check that occurs to determine whether an assignment operation places a reference to a newspace object in an oldspace object is referred to as a “write barrier”. It is desirable to detect such assignments in an efficient manner.
One approach to detecting the assignment of a reference to a newspace object in an oldspace object is to reserve a respective, contiguous range of memory locations for newspace and oldspace, and to examine the location of the objects with respect to the reserved ranges. For example, if newspace objects are always allocated in the contiguous range 012,000,000-012,777,777 (octal) and oldspace objects are always allocated in the contiguous range 023,450,000-023,517,730, then an occurrence of storing of a newspace reference into an oldspace object can be identified simply by comparing the location of the objects within the reserved ranges. Thus, a reference to one object at location 012,345,670 is determined to be in newspace because the location 012,345,670 falls within the range 012,000,000-012,777,777.
Many run-time environments, however, are implemented in an environment that does not allow for large contiguous memory areas to be allocated. In such environments, memory can only be obtained as a plurality of usually segments. As a result, determining which memory area the object is located in cannot merely be determined by examining the location of the object.
One approach to determining to which memory area an object belongs involves traversing an ancillary data structure that lists which segments are allocated to which memory area. However, this approach incurs many expensive pointer dereferences for the ancillary data structure. Another approach involves storing a header at the beginning of every object that describes the space within which the object is located. Accessing the information stored in the object header, however, requires dereferencing a memory pointer to the object, which is expensive due to holes in the instruction pipeline, cache misses, or even a page fault if the page upon which the object header is located has been swapped out by the virtual memory system.
Therefore, a need exists for a run-time environment to manage storage properties for objects, such as properties that indicate within which memory area an object is allocated. There also exists a need for efficiently determining a storage property for an object, preferably without having to dereference a memory pointer. Furthermore, there is a need for an efficient way to detect an assignment of a reference to a newspace object within an oldspace object.
SUMMARY OF THE INVENTION
These and other needs are addressed by encoding storage properties about an object within some of the least significant bits, called a “tag,” of a reference to the object, such as a machine pointer. Therefore, the storage properties can be efficiently determined simply by extracting and examining the specified bits of the tag without having to dereference the machine pointer. The storage properties of an object that can be encoded in the tag of a reference to the object generally indicate how and when the object is stored in memory managed by a run-time environment. For example, the tag can encode information about the lifetime, format, and/or contiguity of an object; thus, the tag can indicate whether the object is allocated in newspace or in oldspace.
Accordingly, one aspect of the invention relates to a computer-implemented method and computer-readable medium bearing instructions for managing information about a storage property for an object. The object is stored in a memory, for example at an N-bit aligned address, and a reference to the object is created by storing, in an base address portion of the reference, a location of the object within the memory. The methodology includes storing, in a tag portion of the reference, the information about the storage property for the object. The tag portion of the reference includes one or more bits of the reference that are less significant than bits for the address portion. In one embodiment, information about the storage property for the object is retrieved by accessing the tag portion of the reference to the object.
Another aspect of the invention pertains to a computer-implemented method and computer-readable medium bearing instructions for managing memory for a plurality of objects. The methodology includes allocating the objects in a first memory area and migrating some of the objects from the first memory area to a second memory area based on their lifetimes. Either the first memory area or the second memory area or both include a plurality of noncontiguous segments. A data structure of information about which second objects in the second memory area reference first objects in the first memory area is maintained by determining whether a first object is allocated in the first memory area and a second object is allocated in the second memory area based on a first reference to a first object and a second reference to a second object, without dereferencing a memory pointer. In one embodiment, determining the first ob
Benson Peter
Sexton Harlan
Unietis David
Ditthavong & Carlson P.C.
Jung David
Oracle Corp.
LandOfFree
Memory management within a run-time environment does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Memory management within a run-time environment, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Memory management within a run-time environment will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3218952