Java Reference
In-Depth Information
Figure12.11 A doubly linked list of free blocks as seen by the memory manager.
Shaded areas represent allocated memory. Unshaded areas are part of the freelist.
There are two basic approaches to implementing the freelist. The simpler ap-
proach is to store the freelist separately from the memory pool. In other words,
a simple linked-list implementation such as described in Chapter 4 can be used,
where each node of the linked list contains a pointer to a single free block in the
memory pool. This is fine if there is space available for the linked list itself, sepa-
rate from the memory pool.
The second approach to storing the freelist is more complicated but saves space.
Because the free space is free, it can be used by the memory manager to help it do
its job. That is, the memory manager can temporarily “borrow” space within the
free blocks to maintain its doubly linked list. To do so, each unallocated block must
be large enough to hold these pointers. In addition, it is usually worthwhile to let
the memory manager add a few bytes of space to each reserved block for its own
purposes. In other words, a request for m bytes of space might result in slightly
more than m bytes being allocated by the memory manager, with the extra bytes
used by the memory manager itself rather than the requester. We will assume that
all memory blocks are organized as shown in Figure 12.12, with space for tags and
linked list pointers. Here, free and reserved blocks are distinguished by a tag bit
at both the beginning and the end of the block, for reasons that will be explained.
In addition, both free and reserved blocks have a size indicator immediately after
the tag bit at the beginning of the block to indicate how large the block is. Free
blocks have a second size indicator immediately preceding the tag bit at the end of
the block. Finally, free blocks have left and right pointers to their neighbors in the
free block list.
The information fields associated with each block permit the memory manager
to allocate and deallocate blocks as needed. When a request comes in for m words
of storage, the memory manager searches the linked list of free blocks until it finds
a “suitable” block for allocation. How it determines which block is suitable will
be discussed below. If the block contains exactly m words (plus space for the tag
and size fields), then it is removed from the freelist. If the block (of size k) is large
enough, then the remaining km words are reserved as a block on the freelist, in
the current location.
When a block F is freed, it must be merged into the freelist. If we do not
care about merging adjacent free blocks, then this is a simple insertion into the
doubly linked list of free blocks. However, we would like to merge adjacent blocks,
Search WWH ::




Custom Search