Electrical computers and digital processing systems: memory – Storage accessing and control – Memory configuring
Reexamination Certificate
1999-06-25
2002-08-06
Hudspeth, David (Department: 2651)
Electrical computers and digital processing systems: memory
Storage accessing and control
Memory configuring
C711S158000
Reexamination Certificate
active
06430665
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to systems and methods for allocating memory and, more particularly, to systems and methods for allocating memory by using a heuristic analysis.
2. Description of the Related Art
Most data processing systems have a fixed amount of memory for running computer programs. Although a larger amount of memory would increase the speed and flexibility of the system, it would also increase the size and cost of the system as well. This tradeoff is especially true for embedded data processing systems, such as computerized fax machines and telephone answering machines, since they typically have a limited amount of memory to minimize size and cost.
Unfortunately, smaller memories tend to become severely fragmented during program execution. Memory becomes fragmented when it contains a random assortment of free memory blocks located between allocated memory blocks. This usually occurs after data has been repeatedly allocated and deallocated (i.e., freed) to the memory.
FIG. 1
illustrates an example of a fragmented memory array
100
containing blocks of free memory
110
and blocks of allocated memory
120
. As shown in
FIG. 1
, the amount of free memory is broken up into various sizes of free memory blocks
110
.
Fragmentation causes several problems. First, fragmentation makes the memory less efficient by breaking up the free memory into blocks of various sizes. Thus, a memory system must search for an adequately sized block of free memory before it can store data of a certain size. This increases processing time, typically by an amount proportional to the number of free blocks. Second, fragmentation often causes a loss of overall effective memory since some of the free blocks will be too small to be of any use.
One way to reduce fragmentation is by having a memory system that allocates data in an optimum manner based on the particularly memory requirements of the overall data processing system. This approach is nearly impossible, however, since there is no reliable way to predict the exact memory requirements for each program using the memory. Other approaches use a free list to efficiently allocate data to the memory. As known in the art, the free list is a file created by the memory system that comprises a linked-list of pointers to each block of free memory in the memory array. The pointers are typically ordered by the memory addresses of the corresponding free memory blocks. Thus, the first pointer of the free list points to the first free memory block in the array, while the second pointer points to the second free memory block, and so on. For purposes of illustration,
FIG. 1
shows a representation of such a free list
130
for memory array
100
.
Conventional methods that allocate memory by using a free list include the “first-fit” and the “best-fit” approaches. Under the first-fit approach, the memory system traverses the free list until it encounters a pointer to a block large enough to store the data. The memory system usually uses a linear search to traverse the free-list. Accordingly, the longer the free list (i.e., the greater the number of free memory blocks), the longer will be the average time to locate the first block of sufficient size. Although this approach is relatively fast, it is not very efficient. In particular, the first-fit approach simply allocates the data to the first free memory block capable of storing the data, rather than to the free memory block that most closely matches the data size.
The best-fit approach, on the other hand, is more efficient but requires more processing time. Under the best-fit approach, the memory system searches for a free block whose size most closely matches the size of the data to be stored. To increase the search speed, the system first sorts the free list according to the size of the free blocks.
Because a smaller amount of free memory typically remains after each allocation, the system must re-sort the free list after each allocation. In particular, the block of free memory that best-fits the data to be allocated is normally somewhat larger than the stored data. Thus, the system must re-sort the free list to reorder the remaining amount of free memory. Similarly, the system must re-sort after each deallocation. This constant re-sorting after each allocation or deallocation requires a substantial amount of processing time, making this approach undesirable.
Therefore, it is desirable to have a memory system that can allocate memory without causing fragmentation. Furthermore, it is desirable to have a memory system that can reduce fragmentation efficiently and without taking a large amount of processing time.
SUMMARY OF THE INVENTION
Systems and methods consistent with the present invention reduce fragmentation of a memory array by efficiently allocating memory to the memory array, and without requiring a large amount of processing time.
In accordance with the purposes of the invention as embodied and broadly described herein, a memory management system and method consistent with the present invention provides a list of pointers to blocks of free memory of a memory array. The system then determines whether to sort the list based on deallocation activity of the memory array. Finally, the system sorts the list, based on the sort determination, according to the memory size of the blocks of free memory indicated by the list.
Both the foregoing general description and the following detailed description are exemplary and are intended to provide further explanation of the invention as claimed.
REFERENCES:
patent: 5561786 (1996-10-01), Morse
patent: 5577243 (1996-11-01), Sherwood et al.
patent: 5675790 (1997-10-01), Walls
patent: 5742793 (1998-04-01), Sturges et al.
patent: 5930827 (1999-07-01), Sturges
patent: 5950231 (1999-09-01), Nichol
Allison David
Jacoby Raphael
Poger Elliot
Finnegan Henderson Farabow Garrett & Dunner LLP
Hudspeth David
Sun Microsystems Inc.
Tzeng Fred F.
LandOfFree
System and method for heuristically allocating 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 System and method for heuristically allocating memory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for heuristically allocating memory will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2894759