Java Reference
In-Depth Information
We now consider how a “suitable” free block is selected to service a memory
request. To illustrate the process, assume that we have a memory pool with 200
units of storage. After some series of allocation requests and releases, we have
reached a point where there are four free blocks on the freelist of sizes 25, 35, 32,
and 45 (in that order). Assume that a request is made for 30 units of storage. For
our examples, we ignore the overhead imposed for the tag, link, and size fields
discussed above.
The simplest method for selecting a block would be to move down the free
block list until a block of size at least 30 is found. Any remaining space in this
block is left on the freelist. If we begin at the beginning of the list and work down
to the first free block at least as large as 30, we select the block of size 35. 30 units
of storage will be allocated, leaving a free block with 5 units of space. Because this
approach selects the first block with enough space, it is called first fit. A simple
variation that will improve performance is, instead of always beginning at the head
of the freelist, remember the last position reached in the previous search and start
from there. When the end of the freelist is reached, search begins again at the
head of the freelist. This modification reduces the number of unnecessary searches
through small blocks that were passed over by previous requests.
There is a potential disadvantage to first fit: It might “waste” larger blocks
by breaking them up, and so they will not be available for large requests later.
A strategy that avoids using large blocks unnecessarily is called best fit. Best fit
looks at the entire list and picks the smallest block that is at least as large as the
request (i.e., the “best” or closest fit to the request). Continuing with the preceding
example, the best fit for a request of 30 units is the block of size 32, leaving a
remainder of size 2. Best fit has the disadvantage that it requires that the entire list
be searched. Another problem is that the remaining portion of the best-fit block is
likely to be small, and thus useless for future requests. In other words, best fit tends
to maximize problems of external fragmentation while it minimizes the chance of
not being able to service an occasional large request.
A strategy contrary to best fit might make sense because it tends to minimize the
effects of external fragmentation. This is called worst fit, which always allocates
the largest block on the list hoping that the remainder of the block will be useful
for servicing a future request. In our example, the worst fit is the block of size
45, leaving a remainder of size 15. If there are a few unusually large requests,
this approach will have less chance of servicing them. If requests generally tend
to be of the same size, then this might be an effective strategy. Like best fit, worst
fit requires searching the entire freelist at each memory request to find the largest
block. Alternatively, the freelist can be ordered from largest to smallest free block,
possibly by using a priority queue implementation.
Which strategy is best? It depends on the expected types of memory requests.
If the requests are of widely ranging size, best fit might work well. If the requests
