Lists and Arrays Revisited - Data Structures and Algorithm Analysis - page 414

Figure12.9 Dynamic storage allocation model. Memory is made up of a series
of variable-size blocks, some allocated and some free. In this example, shaded
areas represent memory currently allocated and unshaded areas represent unused
memory available for future allocation.

handle itself), thus method get does not include a length parameter but instead
returns the length of the message actually stored. Method release allows the
client to tell the memory manager to release the space that stores a given message.
When all inserts and releases follow a simple pattern, such as last requested,
first released (stack order), or first requested, first released (queue order), memory
management is fairly easy. We are concerned here with the general case where
blocks of any size might be requested and released in any order. This is known
as dynamic storage allocation. One example of dynamic storage allocation is
managing free store for a compiler's runtime environment, such as the system-
level new operation in Java. Another example is managing main memory in a
multitasking operating system. Here, a program might require a certain amount
of space, and the memory manager must keep track of which programs are using
which parts of the main memory. Yet another example is the file manager for a
disk drive. When a disk file is created, expanded, or deleted, the file manager must
allocate or deallocate disk space.
A block of memory or disk space managed in this way is sometimes referred to
as a heap. The term “heap” is being used here in a different way than the heap data
structure discussed in Section 5.5. Here “heap” refers to the memory controlled by
a dynamic memory management scheme.
In the rest of this section, we first study techniques for dynamic memory man-
agement. We then tackle the issue of what to do when no single block of memory
in the memory pool is large enough to honor a given request.

12.3.1 Dynamic Storage Allocation

For the purpose of dynamic storage allocation, we view memory as a single array
which, after a series of memory requests and releases tends to become broken into
a series of variable-size blocks, where some of the blocks are free and some are
reserved or already allocated to store messages. The memory manager typically
uses a linked list to keep track of the free blocks, called the freelist, which is used
for servicing future memory requests. Figure 12.9 illustrates the situation that can
arise after a series of memory allocations and deallocations.
When a memory request is received by the memory manager, some block on
the freelist must be found that is large enough to service the request. If no such