Electrical computers and digital processing systems: memory – Storage accessing and control – Memory configuring
Reexamination Certificate
1999-02-10
2002-06-04
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Memory configuring
C711S172000
Reexamination Certificate
active
06401182
ABSTRACT:
TECHNICAL FIELD
The present invention relates generally to memory management and more particularly to explicit memory management. Specifically, a method and apparatus are provided for memory management based upon characteristics of memory requested.
BACKGROUND OF THE INVENTION
Computer programs are typically algorithms that manipulate data to compute a result. A block of memory to store data must first be allocated before the data can be manipulated. When the data is no longer needed, the block of the memory is then deallocated or freed. Allocation and deallocation of the block of memory is commonly referred to as memory management.
Some programming languages(i.e., C, Pascal, Ada, C++, . . . ) allow a programmer to explicitly control memory management. Some of these programming languages (i.e., C, Pascal, C++) require explicit memory management by a programmer when at compile-time: the life-time of a data structure is not known; the size of a data structure is not known; or, the life-time of the program region that allocates a data structure terminates before the life-time of the data structure. These memory allocators are sometimes referred to as dynamic storage allocators because memory must be explicitly managed when information is only known at run-time.
Typically, an operating system provides a memory management service to programming languages. An application may use this service to explicitly manage memory to allocate a block of memory from an unused store of memory known as the free store or the heap. This service is typically called a heap manager.
A heap manager allocates arbitrary size blocks of memory interspersed with requests in arbitrary order to deallocate already allocated blocks of memory. Typically, each allocated block of memory does not overlap other allocated blocks of memory and a heap manager allocates or deallocates only an entire block of storage independent of the type or values of data stored in the block. In some programming languages (i.e., C, Pascal, Ada, C++) the block of memory in which data is stored may not be reallocated to compact memory while the data is in use because the heap manager cannot find and update pointers to the block of memory if it is reallocated.
Many computer architectures incur a performance penalty for accessing unaligned storage of data in memory. Stored data is unaligned if a data type is not on an appropriate boundary in memory. For example, when the alignment requirement is a word of four bytes, stored data is “aligned” when its starting address is divisible by four. The performance penalty for accessing unaligned memory may include additional instruction cycles, poor cache utilization, and/or the introduction of bubbles into the execution pipeline.
FIG. 1
illustrates an example of a block
100
of memory allocated by a heap manager for storing a data structure
102
. The data structure
102
includes two character (char) type data units
104
,
108
and one integer (int) type data unit
106
. Each char type data unit
104
,
108
requires one byte of storage and each int type data unit
106
requires four bytes (one word) of storage. The data units
104
,
106
,
108
are arranged in the data structure
102
in the order of char, int, char.
A compiler can provide a properly aligned data structure
102
by ensuring that the data structure
102
starts and ends on an alignment boundary. The alignment requirement corresponding to the data structure
102
is the largest size of any one of its data units
104
,
106
,
108
. Thus, the alignment requirement corresponding to data structure
102
is four bytes because the int type data unit
106
has a size of four bytes and is larger than the char type data units
104
,
108
.
Each data unit
104
,
106
,
108
included in the data structure
102
is aligned according to the data structure
102
alignment requirement of four bytes. Thus, the char type data unit
104
is followed by three bytes of padding
105
and other char type data unit
108
is also followed by three bytes of padding
109
. Thus, 12 bytes of memory are used to store the data units
104
,
106
,
108
which alone have a total size of only six bytes.
The heap manager allocates the block of memory
100
according to the heap manager's alignment requirement. In order to align memory access for all possible memory requests, the heap manager's alignment requirement equals the size of the largest data unit for all possible memory requests. In the example illustrated in
FIG. 1
, the heap manager's alignment requirement is eight bytes (double word).
The block
100
of memory includes a header
111
which includes a header size
110
indicating the size of the allocated memory and a header padding
112
. In this example, the header size
110
is four bytes and the header padding
112
is four bytes. The header padding
112
is necessary so the data structure
102
begins on an alignment boundary (double word). Internal fragmentation
114
of four bytes at the end of the block
100
of memory allows the block
100
to end on a double word alignment boundary.
Internal fragmentation and large headers may pollute memory with unused data which may result in poor memory utilization. For example, data cache and paging memory are finite resources. Unused data stored in a data cache or in a paging memory may force out used data which may result in higher costs when reaccessing the forced out data.
SUMMARY OF THE INVENTION
A method for improving memory utilization includes measuring an alignment requirement corresponding to each of a plurality of data structures. Storage of the plurality of data structures in a data memory is arranged based on the alignment requirements.
It is to be understood that both the foregoing general description and the following detailed description are exemplary, but are not restrictive, of the invention.
REFERENCES:
patent: 5784699 (1998-07-01), McMahon et al.
patent: 5903900 (1999-05-01), Knipped et al.
patent: 6154823 (2000-11-01), Benayon et al.
Wilson, et al., “Dynamic Storage Allocation: A Survey and Critical Review”, pp. 1-78, 1995.
Larus, et al., “EEL: Machine-Independent Executable Editing”, Association of Computing Machinery, SIGPLAN Conference on Programming Language Design and Implementation, pp. 291-300, 1995.
Ball, et al., “Branch Prediction For Free”, Computer Sciences Department, University of Wisconsin, Technical Report#1137, pp. 1-28, 1993.
Grunwald, et al., “CustoMalloc: Efficient Synthesized Memory Allocators”, Software-Practice and Experience, vol. 23(8), pp. 851-869, 1993.
Chace Christian
F. Chau & Associates LLP
Kim Matthew
LandOfFree
Method and apparatus for memory management 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 memory management, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for memory management will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2934788