Java Reference
In-Depth Information
tend to be of similar size, with rare large and small requests, first or worst fit might
work well. Unfortunately, there are always request patterns that one of the three
sequential fit methods will service, but which the other two will not be able to
service. For example, if the series of requests 600, 650, 900, 500, 100 is made to
a freelist containing blocks 500, 700, 650, 900 (in that order), the requests can all
be serviced by first fit, but not by best fit. Alternatively, the series of requests 600,
500, 700, 900 can be serviced by best fit but not by first fit on this same freelist.
Buddy Methods
Sequential-fit methods rely on a linked list of free blocks, which must be searched
for a suitable block at each memory request. Thus, the time to find a suitable free
block would be (n) in the worst case for a freelist containing n blocks. Merging
adjacent free blocks is somewhat complicated. Finally, we must either use addi-
tional space for the linked list, or use space within the memory pool to support the
memory manager operations. In the second option, both free and reserved blocks
require tag and size fields. Fields in free blocks do not cost any space (because they
are stored in memory that is not otherwise being used), but fields in reserved blocks
create additional overhead.
The buddy system solves most of these problems. Searching for a block of
the proper size is efficient, merging adjacent free blocks is simple, and no tag or
other information fields need be stored within reserved blocks. The buddy system
assumes that memory is of size 2
N
for some integer N. Both free and reserved
blocks will always be of size 2
k
for k N. At any given time, there might be both
free and reserved blocks of various sizes. The buddy system keeps a separate list
for free blocks of each size. There can be at most N such lists, because there can
only be N distinct block sizes.
When a request comes in for m words, we first determine the smallest value of
k such that 2
k
m. A block of size 2
k
is selected from the free list for that block
size if one exists. The buddy system does not worry about internal fragmentation:
The entire block of size 2
k
is allocated.
If no block of size 2
k
exists, the next larger block is located. This block is split
in half (repeatedly if necessary) until the desired block of size 2
k
is created. Any
other blocks generated as a by-product of this splitting process are placed on the
appropriate freelists.
The disadvantage of the buddy system is that it allows internal fragmentation.
For example, a request for 257 words will require a block of size 512. The primary
advantages of the buddy system are (1) there is less external fragmentation; (2)
search for a block of the right size is cheaper than, say, best fit because we need
only find the first available block on the block list for blocks of size 2
k
; and (3)
merging adjacent free blocks is easy.
