Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Reexamination Certificate
1999-06-28
2001-09-04
Thai, Tuan V. (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
C711S100000, C711S170000, C711S171000
Reexamination Certificate
active
06286088
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to personal computer and peripheral systems and, more particularly, to a method and apparatus for relocating memory by dynamically allocating data buffers in a manner that optimizes the memory allocations based upon space or speed, particularly when allocating complex data types.
BACKGROUND OF THE INVENTION
Personal computers, peripheral devices and data processing systems rely on memory when implementing operating systems and application programs. Techniques for managing memory are known in the art. For example, the delivery of print jobs to a printer involves the processing of a printer definition language (PDL). However, memory fragmentation is a problem encountered when processing a printer definition language (PDL). Memory fragmentation occurs when there is not enough contiguous memory.
For example, on some Hewlett-Packard LaserJet products, memory fragmentation has negatively affected throughput, and has resulted in memory outs. A memory out occurs when a block of requested memory is not available. Several firmware approaches are available which can alleviate this problem. First, data structures can be used which reside in fragmented memory. Secondly, fragmentation can be avoided by grouping like-sized or like-used allocations together. Thirdly, fragmentation can be reduced by relocating allocated memory objects to coalesce free space.
Several Hewlett-Packard LaserJet products have applied the first two approaches. For example, according to one implementation, the dissected compressed strip is provided as a data type that can reside in fragmented memory. According to another implementation, the personality scraps and array memory clients group like-sized allocations. According to a third implementation, various font memory clients group like-used allocations. Unfortunately the application of these techniques did not sufficiently alleviate the negative consequences of memory fragmentation for some products.
SUMMARY OF THE INVENTION
A technique is provided for reducing memory fragmentation by relocating allocated memory objects in order to coalesce free space. Pursuant to this technique, a method and an apparatus are provided for moving dynamically allocated buffers using a memory manager with data structures that embed self-referencing pointers in data buffers.
According to one aspect of the invention, a memory management system usable with a client is provided. The system includes memory which defines a memory space including at least one memory buffer, and the memory buffer is defined by a set of attributes including base address and size. The memory includes a fixed-simple memory allocation, having a link, and one of a relocatable simple memory allocation coupled with the link, a head of a complex memory allocation comprising multiple simple memory allocations, or a null simple memory allocation. A memory manager is coupled with the memory and is configured to manage specific instances of memory allocation usable by a client. A memory management interface is coupled with the memory manager and is configurable to enable a client to specify a request for a relocatable memory object. Processing circuitry is coupled with the memory and the memory management interface and is operative to detect a low memory condition. The memory manager is operative to relocate the memory object from one physical location in memory to another physical location in memory to generate a sufficiently large contiguous free memory block for the client so as to overcome the low memory condition.
According to another aspect of the invention, a method for relocating memory is provided. The method provides a memory; allocates a memory object, either relocatable or non-relocatable; requests an allocation of memory; assigns a fit for the memory object, then allocates a fit for the memory object; and determines if the allocation from free memory can be satisfied. If the allocation from free memory can be satisfied, then moving memory objects to different places in memory to get a sufficiently big free block of memory.
One advantage is provided in that already existing printer definition language code that is very large can be used make space available without having to rewrite the code to accommodate double indirection techniques.
REFERENCES:
patent: 5491785 (1996-02-01), Robson et al.
patent: 5524186 (1996-06-01), Campbell
patent: 5550954 (1996-08-01), Campbell et al.
patent: 5586300 (1996-12-01), Wilcox et al.
patent: 5706469 (1998-01-01), Kobayashi
patent: 5749092 (1998-05-01), Heeb et al.
patent: 5809228 (1998-09-01), Langendorf et al.
patent: 5809317 (1998-09-01), Kogan et al.
patent: 5809561 (1998-09-01), Sheffield et al.
patent: 5812803 (1998-09-01), Pawlowski et al.
patent: 5819079 (1998-10-01), Glew et al.
patent: 5835958 (1998-11-01), Long et al.
patent: 5845297 (1998-12-01), Grimsrud et al.
patent: 5857213 (1999-01-01), Benhase et al.
patent: 5873105 (1999-02-01), Tremblay et al.
patent: 5920876 (1999-07-01), Ungar et al.
patent: 5920896 (1999-07-01), Grimstrud et al.
patent: 5970240 (1999-10-01), Chen et al.
Structured Computer organization, Third Edition (Andrew S. Tanenbaum; 1990; pp. 338-343).
Blair Timothy P.
Campbell Russell
Lanning David L.
Hewlett--Packard Company
Thai Tuan V.
LandOfFree
Memory management system and method for relocating 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 Memory management system and method for relocating memory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Memory management system and method for relocating memory will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2515908