Easily coalesced, sub-allocating, hierarchical, multi-bit...

Details Easily coalesced, sub-allocating, hierarchical, multi-bit... Easily coalesced, sub-allocating, hierarchical, multi-bit...

2000-11-28

2003-10-28

Kim, Hong (Department: 2186)

Electrical computers and digital processing systems: memory

Storage accessing and control

Control technique

C711S170000, C711S172000, C710S056000, C707S793000

Reexamination Certificate

active

06640290

ABSTRACT:

TECHNICAL FIELD
This invention relates to memory managers for managing physical data memory. More particularly, this invention relates to memory managers that utilize bitmaps to manage the data memory.
BACKGROUND
Most computer programs require dynamic memory allocation because the exact memory requirements needed during execution cannot typically be predicted prior to execution. Normally, a program specifies an initial amount of memory that is needed before execution starts. During execution, the program invariably requires more memory, depending on the input data it has to process or a number of other possible factors.
Ideally, the program would accurately predict how much memory it would use during execution. However, static prediction techniques are inefficient because they must conservatively estimate the worst-case maximum amount of memory that will ever be needed under all executions of the program.
As a result, software systems allow programs to specify their memory needs dynamically, and to enlarge or reduce the amount of in-use memory as needed. A “memory manager” is a software module that is in charge of handling memory allocations and deallocations for one or more application programs. Typically, the memory manager is incorporated into the computer operating system because main memory is a resource that is divided among a number of programs running on top of the operating system.
When an application program needs additional memory, it sends a request to the memory manager. In response, the memory manager allocates a memory block of a certain size for use by the program. The program can ask for the actual size of the allocated memory block, request a reallocation of the block to a larger or smaller size, and request other statistical or bookkeeping information from the memory manager. When the program finishes with the block, the memory manager deallocates the block to free that block for other uses. The primary goal of the memory manager is to efficiently perform these management tasks (i.e., allocation, reallocation, deallocation, and bookkeeping) while minimizing wasted space without undue time overhead.
There are many different types of memory managers. Perhaps the best known conventional memory manager is one that utilizes free lists. Free-list memory managers are widely used for managing addressable core memory, such as RAM (Random Access Memory). Another well-known type of memory manager is one that utilizes a bitmap to manage memory space. The bitmap memory manager is primarily used for special situations in which block size is fixed, such as managing disk memory. Bitmap memory managers have not been traditionally used to manage core memory. These two types of memory manager are discussed separately below.
Conventional Free-List Memory Manager
A free-list memory manager maintains a set of free lists that identify different size blocks of free memory space within a memory heap. In this context, the term “heap” means a pool of memory available for the allocation and deallocation of arbitrary-sized blocks of memory in arbitrary order.
FIG. 1
shows a conventional free-list memory manager
20
that manages a memory heap 22. The memory manager
20
maintains a free list
24
that identifies different sizes of free memory blocks in the memory heap
22
. In this example, the free list
24
tracks blocks in various sizes that increase at a rate of a power of two, such as 16-byte, 32-byte, 64-byte, . . . , 1 page, and more than 1 page.
The free list
24
maintains entry pointers into the memory heap
22
. Here, the free list
24
has an entry pointer
26
for a free 16-byte block A in the memory heap
22
. The free block A maintains a pointer
28
to another free 16-byte block B within the heap
22
. In this manner, one entry pointer
26
in the free list
24
eventually leads to all free 16-byte blocks in the heap
22
. The free list
24
also maintains similar pointers for larger size blocks.
When asked to allocate a block of a given size, the memory manager
20
scans the free list
24
for a suitable candidate block. The memory manager
20
follows the entry pointer into heap
22
and allocates one block to the requesting program. Subsequently, when the program is finished with the block, the memory manager
20
deallocates the block and places it back on the free list
24
by adding the appropriate pointers.
One problem encountered by conventional free-list memory managers is “fragmentation”. Block deallocations tend to create a disjoint array of free and in-use blocks within the heap. Over time, the fragmentation becomes more severe. As a result, there are fewer large blocks of memory available for allocation. Entries on the free list
24
tend to migrate toward smaller size blocks, as larger size blocks become extinct.
To combat excessive fragmentation, memory managers typically perform a process known as “coalescing”, which attempts to combine smaller free blocks into larger free blocks for more efficient allocation. There are many techniques for coalescing, and this concept is well-understood in the art.
FIG. 2
shows one exemplary coalescing process that utilizes block headers. In
FIG. 2
, each block
30
in the heap has a header
32
and a data portion
34
. The header
32
contains information on the size of the block and whether the block is free or in-use.
During coalescing, the memory manager examines the header of a first free block (e.g.,
30
(
1
)) and traverses forward in the heap by the size amount of the first block to the next block (e.g.,
30
(
2
)). The memory manager then looks at the header of the next block
30
(
2
) to determine whether that block is free. If free, the memory manager combines the two blocks and forms a single header for the bigger unified block
30
(
1
+
2
). The memory manager then continues to the next block in the heap, and so on. Unfortunately, this coalescing process is both time-consuming and unidirectional.
To improve speed and enable bi-directional processing, each block header might further be equipped with information indicating whether the preceding block is free.
FIG. 3
shows a portion of a heap having free blocks
40
. Each block
40
has a header
42
with size and use information for the local block, as well as use information for the preceding block, and a data portion
44
. The use information for the preceding block is updated when the state of the preceding block is changed. In addition, each free block
40
has a trailer
46
positioned at the end of the data portion
44
to specify its block size, indicating that the free block can hold a data portion that is at the very least as large as the block size.
During coalescing, the memory manager examines the header of a free block (e.g.,
40
(
2
)) to determine whether it is free and whether the preceding block is free. If both are free, the memory manager moves backward to the trailer
46
of the preceding block (e.g.,
40
(
1
)) to learn the size of the preceding block. The memory manager combines the two free blocks and forms a new header to create a unified block
40
(
1
+
2
). With the block structure of
FIG. 3
, the memory manager can also traverse forward in the heap according to the process described with reference to FIG.
2
.
One drawback of this coalescing technique is that the block structure comes at a cost of inefficient space overhead. The headers consume memory space that could otherwise be used for data.
Another drawback concerns alignment. For 64 bit integers, for example, the data portion of the memory block structure must align on 8 byte boundaries; otherwise the processor might generate an unaligned trap. Some processors might accept the unaligned data, but with a considerable performance cost. As a result, the end of the header needs to align at 64 bits. As the amount of header information grows (i.e., by adding information on preceding or succeeding blocks), the header itself must grow at 8 byte increments. As a result, there may be more space reserved for the header than is actually needed, just for alignment purposes.

Affiliated with

Also associated with

Rating

Easily coalesced, sub-allocating, hierarchical, multi-bit... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Easily coalesced, sub-allocating, hierarchical, multi-bit..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Easily coalesced, sub-allocating, hierarchical, multi-bit... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3119526