Java Reference
In-Depth Information
0000
0000
BUDDIES
BUDDIES
0100
1000
1000
BUDDIES
1100
(A)
(B)
Figure12.14
Example of the buddy system. (a) Blocks of size 8. (b) Blocks of
size 4.
The reason why this method is called the buddy system is because of the way
that merging takes place. The buddy for any block of size 2
k
is another block
of the same size, and with the same address (i.e., the byte position in memory,
read as a binary value) except that the kth bit is reversed. For example, the block
of size 8 with beginning address 0000 in Figure 12.14(a) has buddy with address
1000. Likewise, in Figure 12.14(b), the block of size 4 with address 0000 has
buddy 0100. If free blocks are sorted by address value, the buddy can be found by
searching the correct block-size list. Merging simply requires that the address for
the combined buddies be moved to the freelist for the next larger block size.
Other Memory Allocation Methods
In addition to sequential-fit and buddy methods, there are many ad hoc approaches
to memory management. If the application is sufficiently complex, it might be
desirable to break available memory into several memory zones, each with a differ-
ent memory management scheme. For example, some zones might have a simple
memory access pattern of first-in, first-out. This zone can therefore be managed ef-
ficiently by using a simple stack. Another zone might allocate only records of fixed
size, and so can be managed with a simple freelist as described in Section 4.1.2.
Other zones might need one of the general-purpose memory allocation methods
discussed in this section. The advantage of zones is that some portions of memory
can be managed more efficiently. The disadvantage is that one zone might fill up
while other zones have excess free memory if the zone sizes are chosen poorly.
Another approach to memory management is to impose a standard size on all
memory requests. We have seen an example of this concept already in disk file
management, where all files are allocated in multiples of the cluster size. This
approach leads to internal fragmentation, but managing files composed of clusters
