Electrical computers and digital processing systems: memory – Storage accessing and control – Memory configuring
Reexamination Certificate
1998-05-08
2001-06-19
Ellis, Kevin L. (Department: 2185)
Electrical computers and digital processing systems: memory
Storage accessing and control
Memory configuring
Reexamination Certificate
active
06249852
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates to memory management systems and more particularly to a system for managing memory pages for accessing fixed size data objects.
2. Prior Art
Many applications today are very heap intensive with respect to working set size and performance. In object-oriented programs written in C
++
, objects are created and deleted from the heap with the life of an object often being very short.
A solution to increase the performance of these kind of applications is to use a very efficient heap allocator that can perform allocate and release operations in constant time and also minimize the “page hits” required, i.e. objects are allocated from minimal set of pages.
Known attempts to improve the performance of applications which manipulate large numbers of small data objects have included chaining released objects of a specific size in a linked list and reusing these objects for future allocations. While this approach results in faster performance than another known method which coalesces released objects, the chaining method for released objects can however result in unnecessary page hits during allocations. Another disadvantage is that the chaining of released objects will tend to increase the heap size since free objects cannot be recycled for other sizes. Furthermore, each object size is rounded to a factor suitable by the main heap allocator which may have heap working set size implications.
Therefore, there remains a need in the art to improve the speed of a heap allocator while at the same time reducing the working set size in a manner that is page sensitive. The method is preferably suitable for systems which utilize multiple user controlled heaps.
SUMMARY OF THE INVENTION
The present invention provides a page-based allocator and de-allocator for fixed size data objects.
According to a first aspect of the present invention, internal information, i.e. size, associated with a data object is stored external to the object as opposed to inside the object. The page-based allocator according to the present invention features a memory page structure in which objects of a specific size are obtained from a common set of pages that are shared with other objects of the same size. According to the invention, each page includes a reserved area for storing internal information relevant to the objects within the given page including object size and a user heap handle. The user heap handle indicates from which heap the page was obtained in a multiple heap system. During a release of an object, the page is determined by performing an arithmetic operation on the object address and the size and heap for the object is obtained by examining the reserved area of that page.
Since many pages of storage may be required to satisfy allocation requests within an application, the method according to the present invention also features a mechanism for chaining all the pages that are dedicated to a specific object size in a linked list. The chaining mechanism facilitates the insertion and deletion of a page in real time.
To reduce the working set size, i.e. the number of pages in the heap, the page allocator according to the present invention features a recycle mechanism for recycling pages in which all the objects have been returned.
In a first aspect, the present invention provides an allocator/de-allocator suitable for fixed size data objects, the allocator comprising: (a) a plurality of page lists, each of the page lists being intended for a specified object size range and comprising one or more pages for objects within the specified size range; (b) a range list array having means for storing pointers for each of the page lists, wherein the pointers include a cache pointer for pointing to the page being most recently accessed.
In a second aspect, the present invention provides a method for allocating a fixed size object in response to an allocation request specifying a size for the fixed size object, the method comprising the steps of: (a) rounding the specified size for the object; (b) determining a page list corresponding to the rounded object size; (c) allocating the object on the first available page in the page list; (d) if a page is not available in the selected page list, adding a page to the page list.
In another aspect, the present invention provides a method for freeing a fixed size object from a page list having one or more pages for the object size of interest, the method comprising the steps: (a) computing the page in the page list where the object resides from the address of the object; (b) releasing the object from the page determined in step (a); and (c) moving the page to a recycled page list if all the objects have been returned.
REFERENCES:
patent: 5561785 (1996-10-01), Blandy et al.
Benayon Jay William
Ewart Graham W.
August Casey P.
Ellis Kevin L.
International Business Machines - Corporation
Scully Scott Murphy & Presser
LandOfFree
Method for heap management of fixed sized objects using pages 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 for heap management of fixed sized objects using pages, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for heap management of fixed sized objects using pages will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2514718