Java Reference
In-Depth Information
Small block: External fragmentation
Unused space in allocated block: Internal fragmentation
Figure12.10
An illustration of internal and external fragmentation. The small
white block labeled ”External fragmentation” is too small to satisfy typical mem-
ory requests. The small grey block labeled ”Internal fragmentation” was allocated
as part of the grey block to its left, but it does not actually store information.
block is found, then the memory manager must resort to a failure policy such as
discussed in Section 12.3.2.
If there is a request for m words, and no block exists of exactly size m, then
a larger block must be used instead. One possibility in this case is that the entire
block is given away to the memory allocation request. This might be desirable
when the size of the block is only slightly larger than the request. This is because
saving a tiny block that is too small to be useful for a future memory request might
not be worthwhile. Alternatively, for a free block of size k, with k > m, up to
k m space may be retained by the memory manager to form a new free block,
while the rest is used to service the request.
Memory managers can suffer from two types of fragmentation, which refers to
unused space that is too small to be useful. External fragmentation occurs when
a series of memory requests and releases results in small free blocks. Internal
fragmentation occurs when more than m words are allocated to a request for m
words, wasting free storage. This is equivalent to the internal fragmentation that
occurs when files are allocated in multiples of the cluster size. The difference
between internal and external fragmentation is illustrated by Figure 12.10.
Some memory management schemes sacrifice space to internal fragmentation
to make memory management easier (and perhaps reduce external fragmentation).
For example, external fragmentation does not happen in file management systems
that allocate file space in clusters. Another example of sacrificing space to inter-
nal fragmentation so as to simplify memory management is the buddy method
described later in this section.
The process of searching the memory pool for a block large enough to service
the request, possibly reserving the remaining space as a free block, is referred to as
a sequential fit method.
Sequential Fit Methods
Sequential-fit methods attempt to find a “good” block to service a storage request.
The three sequential-fit methods described here assume that the free blocks are
organized into a doubly linked list, as illustrated by Figure 12.11.
