13.3.2 The Buddy System

Another organization, called the buddy system, provides faster request and return time responses than two-way circular lists. The buddy system requires the heap to be of length 2m for some integer m, occupying addresses 0 to 2m - 1. Over time, the heap is split into nodes of varying lengths. These lengths are constrained to be powers of 2, and nodes are kept on separate lists, each list containing nodes of a specific length. An array a of length m contains the heads of these lists, so a[k] points to the first node on the list corresponding to length 2k. Initially, a[m] points to the first address of the heap; all other array entries are null, since all other lists are empty.

To satisfy a request for a node of length n, k is set to ?/FONT>lg n?I>. If a[k] is not null, a node is deleted from its list to satisfy the request. Otherwise, the next nonnull list is found. Its nodes will be of length 2r, where r > k. A node is deleted from that list and split into two nodes, each of length 2r-1. That node created by the split with the greater address is placed on the appropriate list, while the other is used to satisfy the request if r - 1 = k. Otherwise it is split and processed in the same way. Eventually a node of length k will be generated to satisfy the request.

During this iterated splitting process, each time a node is split, it is split into two special nodes called buddies. Buddies bear a unique relation to each other. Only buddies are allowed to coalesce. Although this can result in unused nodes being contiguous but not coalescing because they are not buddies, it is a rare occurrence. This restriction allows very fast coalescing of buddies, as will be shown.

When a node is to be returned to the list of available space (a misnomer now), its buddy is first checked to see if it is not in use and, if it is not, the buddies are coalesced. This node is, in turn, coalesced with its buddy when possible, and so on, until no further coalescing is possible. This coalescing process is the reverse of the splitting process that created the buddies in the first place.

At this point you must be wondering how a node's buddy is found. The scheme ensures that it may be done quickly because a node of size 2k with starting address

has as its buddy a node of size 2k with starting address

In general, given the address of a node of size 2k to be returned, its (k + 1)th bit (addresses are expressed in binary notation) is changed from 1 to 0 or 0 to 1, and the result is the address of its buddy. A tag field is used to indicate whether or not a node is in use.

Example 13.6

How does the buddy system respond when m is 6 and a sequence of requests is made for nodes of size 8, 16, 4, and 6? n

(a) After a Sequence of Requests Is Made for Nodes of Size 8, 16, 4, 6

(b) After the Node of Length 16 Is Returned

Figure 13.3 Sequence of Memory Configurations for Example 13.6

The sequence of memory configurations is as shown in Figure 13.3(a). lf the node of length 16 is now returned, the configuration becomes as shown in Figure13.3(b)

A[4] is now the head of a list with two nodes, each of length 16. The released node of length 16 starting at address 16 (10000 in binary) has the node of length 16 starting at address 0 (00000 in binary) as its buddy. Since it is not free, it cannot coalesce with it. Neither can it coalesce with the node of length 4 starting at address 12, since that node is not its buddy.

The distribution of nodes can be mirrored by a binary tree. This tree is a kind of derivation tree for nodes currently in existence and expands and contracts as nodes are split and coalesced. The tree shown in Figure 13.4 reflects the configuration for Example 13.6 before the node of length 16 is returned.

Buddies appear as successors of the same parent. Thus [12, 15] and [16, 31], although contiguous in memory, are not buddies and therefore may not be coalesced.

With the buddy system, lists are never actually traversed to find storage to allocate, although time is spent finding the proper list from which to take the storage. The result is quick response to requests and returns. However, in contrast to two-way lists, this scheme produces significant internal fragmentation. Internal fragmentation occurs when allocated nodes are larger than requested, resulting in wasted storage residing within a node. This is one of the drawbacks of the buddy system. Studies have been done on similar schemes that allow a greater variety of node sizes to appear. They also tend to be fast and to reduce storage loss due to internal fragmentation.

Figure 13.4 Binary Tree Reflecting the Memory Configuration for Example 13.6 Just before Return of Node of Length 16