Electrical computers and digital processing systems: memory – Storage accessing and control – Memory configuring
Reexamination Certificate
1999-09-30
2003-01-07
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Memory configuring
C710S200000
Reexamination Certificate
active
06505283
ABSTRACT:
FIELD OF INVENTION
The present invention relates to the dynamic allocation of memory within a computer system and, in particular, to a method of lowering fragmentation overheads.
DESCRIPTION OF PRIOR ART
Modern computer systems rely heavily on dynamic memory allocation to provide memory space where data may be stored during processing. The program makes requests to a dynamic memory allocator for varying sized blocks of memory, which are later returned for reuse to the memory allocator when they are no longer required. A dynamic memory allocator typically manages a list of free blocks from which it can satisfy new requests on behalf of the system, and to which blocks which have been released can be returned.
A dynamic memory allocator can form a central part of a computer system, with its allocation services being used extensively by numerous system components. Moreover, allocation of memory must take place efficiently in order to provide the required overall system performance.
To operate efficiently, a memory allocator must meet two requirements: it must manage the overall pool of available memory efficiently, and must respond to allocation and release requests in a timely manner. These two requirements can be contradictory, and conventional dynamic memory allocators attempt to compromise by implementing allocation strategies that lie somewhere on the spectrum between being very fast and being very memory-efficient.
The memory efficiency of a dynamic memory allocator is the degree to which the overall pool of available memory is used effectively. Inefficient memory allocation strategies lead to excessive memory requirements, either increasing overall system cost to provide for inflated memory requirements, or causing system failure when required memory is not available. The degree of memory efficiency of an allocator operating in a particular system is determined by the amount of memory which is unusable because it is broken into fragments which are too small to satisfy requests made by the system.
Fragmentation can occur internally within the allocator as a result of allocation policy, or externally as a result of the combination of the system's allocation profile and the allocator's allocation policy. Both forms of fragmentation represent wastage which degrades the system's overall memory efficiency.
In order to satisfy memory allocation requests in a timely manner, conventional dynamic memory allocators typically maintain a number of separate free lists from which memory blocks are allocated. Each list contains blocks of a fixed size, or within a particular size range, so that an allocation can be satisfied without the need to search the entire free list for a block of the requested size. If the free list corresponding to the requested size is empty, a block from one of the larger sized lists may need to be broken down in order to satisfy the request, contributing to fragmentation and reducing memory efficiency.
Fixed-size free lists are commonly used, where the size of blocks on a given free list may be rounded up to a particular power of two, the next number in a Fibbonacci sequence, or some other easily computable sequence. The amount of memory returned by an allocation request for a block of a particular size will typically include this internal fragmentation due to rounding, which remains unusable by the rest of the system.
External fragmentation occurs as a result of the interaction between allocator policy and system allocation request profile. Blocks are frequently returned to the allocator by the system in an unpredictable order, leaving allocated blocks interspersed between free blocks in memory. A large allocation request may not be satisfiable, because no large contiguous block of free memory is available, notwithstanding the fact that the total amount of memory available would otherwise by sufficient to satisfy the request.
Allocator policy can further contribute to external fragmentation, depending on how often the small blocks which have been returned to the allocator are merged back into large blocks on. a larger sized free list. This merging process typically involves computationally expensive sorting of all the current free lists, which in turn has an impact on allocation speed. As a result, conventional allocators typically defer merging until absolutely necessary, or perform regular merges after a certain number of block allocations or releases, in an attempt to mitigate the undesirable external fragmentation effects caused by storing many small blocks separately on multiple free lists.
Conventional allocators trade off a degree of memory efficiency for speed in a variety of ways, which can lead to poor memory efficiency due to fragmentation.
Dynamic memory allocators also vary according to where they store the free list information used internally by the allocator. In-place allocators store this information in the free blocks themselves, and are commonly used in general purpose single- or multi-processor systems where the processor has a fast data path to the memory being allocated. Out-of-place allocators store the information about the free list in a separate area of memory to that being controlled by the allocator, and may be used to allocate memory on behalf of a co-processor and/or when processor access to the memory being allocated incurs a significant performance penalty.
SUMMARY OF THE INVENTION
In a first aspect, the present invention provides a method of dynamically allocating blocks of memory in a computer system, the method including the steps of:
generating a first memory allocation list in which free memory blocks are recorded on the basis of size;
generating a second memory allocation list in which free memory blocks are recorded on the basis of memory block address;
when a memory block is requested by the computer system, searching the first list to determine a suitably sized memory block, allocating the requested memory block from the suitably sized memory block in response to the request, and updating the first and second lists to take the allocation into account; and
when a memory block is freed by the computer system:
determining whether a free memory block exists adjacent the freed memory block by searching the second list;
in the event that one or more free memory blocks exist adjacent the freed memory block, merging the freed memory block and free memory blocks together to form a unitary free memory block; and
updating the first and second lists to take the freed memory block and any free memory block merges therewith into account.
Preferably, the first and second lists are linked list data structures. More preferably, the first and second lists are merged. In a particularly preferred form, the first and second lists take the form of a merged skip-list.
In a second aspect, the present invention provides an apparatus for dynamically allocating blocks of memory in a computer system, the method including the steps of:
allocation list generating means for generating a first memory allocation list in which free memory blocks are recorded on the basis of size and generating a second memory allocation list in which free memory blocks are recorded on the basis of memory block address;
searching means for searching the first list to determine a suitably sized memory block when a memory block is requested by the computer system and, for searching the second list to determine whether a free memory block exists adjacent a freed memory block when the memory block is freed by the computer system;
allocating means for allocating the requested memory block from the suitably sized memory block in response to the request, and updating the first and second lists to take the allocation into account; and
merging means for merging the freed memory block and free memory blocks together to form a unitary free memory block in the event that one or more free memory blocks exist adjacent the freed memory block; and
updating means for updating the first and second lists to take the freed memory block and any free memory block merges therewit
Chae Christian P.
Fitzpatrick ,Cella, Harper & Scinto
Kim Matthew
LandOfFree
Efficient memory allocator utilizing a dual free-list structure does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Efficient memory allocator utilizing a dual free-list structure, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient memory allocator utilizing a dual free-list structure will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3026331