Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-07-23
2002-02-19
Peikari, B. James (Department: 2186)
Data processing: database and file management or data structures
Database design
Data structure types
C711S170000, C711S173000, C707S793000
Reexamination Certificate
active
06349312
ABSTRACT:
BACKGROUND
This invention relates generally to computer systems and more particularly to a method and apparatus for achieving deterministic memory allocation response in a computer system.
In many modem computer systems, memory needed for execution of program components, such as objects, is allocated at run time rather than at compile time. In such systems, whenever an object is created or instantiated during execution, memory is dynamically allocated from a memory heap to accommodate the object. This memory may be used to hold data associated with the object, or to perform operations required by the object. When the memory is no longer needed (for example, when the object becomes obsolete), the memory is released back to the heap to be used for other objects. Different methodologies is exist for releasing memory back to a memory heap. A common methodology is known as garbage collection (GC).
With GC, the release of memory back to a memory heap is system controlled. That is, the user (i.e. the application developer) controls when an object is instantiated, and hence, when memory is allocated, but it is the underlying system that controls when memory is de-allocated and released back to the heap. Typically, a GC operation is triggered when the amount of free memory space in the heap drops below a certain threshold. This determination is typically made at the time of allocating memory for a new object instance. Thus, a memory allocation operation may (but does not always) trigger a GC operation. When triggered, the GC mechanism typically performs a trace to determine which object instances can be reached by the current program. All of the memory spaces associated with such object instances are marked as active and are preserved. All of the other memory spaces (presumably associated with objects that are no longer reachable by the current program, and hence are obsolete) are recaptured and released back to the heap. In this manner, the GC mechanism collects the “garbage” memory spaces and returns them to the heap.
As noted above, a memory allocation operation may trigger a GC operation. Because of this possibility, the time needed to perform a memory allocation may vary greatly from allocation to allocation. To illustrate, suppose that when a first memory allocation request is processed, the free space available in the heap is above a certain GC threshold; thus, no GC operation is needed. As a result, this first allocation is performed in an X amount of time. Suppose, however, that when a subsequent memory allocation request is processed, the free space available in the heap has dropped below the threshold. In that case, a GC operation will have to be performed before the subsequent memory allocation can be carried out. Thus, the time needed to perform the subsequent memory allocation will be X+GCT, where GCT is the time required to perform the GC operation. Because GCT is substantial relative to X, the time difference between the two memory allocation operations is very significant.
While the triggering of a GC operation is a major factor in causing memory allocation times to vary, it is not the only factor. Other factors such as memory fragmentation can also contribute to the variance. If the memory in a heap is contiguous, it takes less time to allocate memory than if the heap were highly fragmented. Thus, the degree of fragmentation of the heap can affect allocation times. These and other factors can cause memory allocation times to vary from allocation to allocation.
In some implementations, it is important for memory allocation operations to be deterministic, that is, to take substantially the same amount of time each time the operation is performed, or to at least have the allocation times be predictable. For example, in a real-time implementation, it is imperative for memory allocations to be deterministic. Because of the potential for great variations in memory allocation times, the typical allocation-garbage collection mechanism cannot be used in such implementations. Consequently, an improved mechanism is needed.
SUMMARY OF THE INVENTION
The present invention provides a mechanism for enabling memory allocation operations to be deterministic. The present invention is based, at least partially, upon the observation that determinism may be achieved by first pre-allocating a contiguous memory space, and then using that memory space to perform the actual memory allocation operations. Because the memory allocation operations are performed using memory space that has already been allocated, it is ensured that the allocation operations will not trigger a GC operation. Also, because the pre-allocated memory space is contiguous, there will be no fragmentation concerns. Thus, the present invention eliminates the two major causes of non-constant allocation times. By doing so, the present invention makes it possible to achieve determinism in a dynamic memory allocation system.
REFERENCES:
patent: 5689707 (1997-11-01), Donnelly
patent: 5790852 (1998-08-01), Salm
patent: 6130759 (2000-10-01), Blair
patent: 0 473 802 (1992-03-01), None
Fresko Nedim
Long Dean R. E.
Hickman Palermo & Truong & Becker LLP
Peikari B. James
Truong Bobby K.
LandOfFree
Method and apparatus for performing pre-allocation of memory... 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 performing pre-allocation of memory..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for performing pre-allocation of memory... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2973894