Up to this point the sizes of blocks have been either fixed or completely arbitrary. Another

technique used in some storage methods is to restrict the sizes of blocks to some fixed set

of sizes. All the blocks of each size can be linked together with the intent of speeding up the

search for a block of suitable size. For a request of a block of size n, the number m, the sm-

allest of the fixed sizes equal to or larger than n, is determined and a block of size m is all-

ocated . If no block of size m is available, then a larger block is split into two sub blocks

(known as buddies), each also of fixed size, and this process is repeated until a block of size

m is produced.

Besides the improvement in search time, there is another advantage in using in using

this technique. The collapsing of two smaller blocks into one larger block is relatively easy

since only two buddies formed by splitting a larger block may be combined to form this lar-

ger block once again. Because the sizes are fixed relative to one another, the address of the

buddy of a block is relatively easily determined.

There are, however, some potential disadvantages associated with this technique. Inter-

nal fragmentation will be increased generally because of the allocation of blocks which may

be somewhat larger than the requested size. As well, there can be an increased amount of ex-

ternal fragmentation due to the fact that two blocks may be contiguous and yet not merged,

because they are not buddies. Generally, though, this technique of storage management has

proven to be quite efficient.

The usual approach in implementing this method of storage management is to specify

the fixed sizes, F0, Fl, …., F max, for blocks according to some pattern such as the recurrence

relation.

Fn =Fn-1 +Fn-k k<=n<=MAX

F0 = a, Fl=b, …., Fk-1=c

where a ,b,….,c are minimum block sizes that are used , and k=1 or 2 or 3 or….etc. For

example, if k is one and F0 is 1, then the block sizes, which are 1,2,4,8,16, …, are the successive

powers of 2 and the method is called the buddy system. If k=2 with F0=F1=1, then the sizes are

just the successive members of the Fibonacci sequence 1,1,2,3,5,8,13,…In all likelihood, though,

though, the F0,F1,etc.., terms are not defined to be such small values. Blocks of size 1are not much

use, especially if they must carry control information so that the allocation and release mechanisms

will work.

The feature that makes this system work is that the merges must correspond exactly to the splits.

By this we mean that the only two blocks that can be merged are the precise two that were formed by

splitting. Furthermore, before each block can be reformed, each of its sub blocks must be reformed

from their sub blocks. Consequently, the storage-block pattern formed by the sequence of splits has the

form of a binary tree. The problem with which we are faced is the recording of the position of a parti-

cular block within this tree structure.

One particular solution consists of a coding for each block by which we can reconstruct splitting

sequence that produced that block. Looking at the recurrence relation Fn = Fn-1+ Fn-k, if we specify

that the Fn-1 term corresponds to the block that forms the left branch of a split and the Fn-k term is

the right branch, then all we must record for each block is the size of the block, the number of splits

it took to form the block, and whether it is a left block or right block. Since one left block and one

right block are formed in each split, we need only record the count of left blocks. In fact, this allows

us to code the left or right factor together with the split count in one coded field. The left block has the

relative split count, while the right block has a code of 0. The formulas to use are the following:

Initially: CODE_max= 0 where F_max is the entire segment considered to be a right block

Splitting: CODE_left= CODE_parent +1

CODE_right=0

Merging: CODE_parent= CODE_left +1

1

As an example, consider a storage block of 144 cells and the recurrence relation

F_n=F_n-1+F_n-2 2≤n≤6

F₀=8, F₁=13

The entire tree of possible splits is given in the figure where the vertex value is the block size and the

superscript is the code value as computed by the above formulas. Consider the tree cross section that is

the set of potential blocks of size 13. A block of size 13 with code of 0 is the right block formed by

splitting a block of size 34. The left or right nature of this size 34 block is determined by the left buddy

for the block of size 13. If its left buddy has a code of 1, then the size 34 block is the right block for

some larger block of size 89, while if the left buddy has a code greater than 1, then the block of size 34

is a left block of some still larger block. A block of size 13 with a code value greater than 0 is the left

block of a split block of size 31. The numeric value of the code for a left block of size 13 is the

number of splits of some higher right block that had to be made to get this left block of size 13. Or, in

other words, the value of the code for a left block is the number of merges that this left block must

under go to become the first 13 locations of some larger block which is finally a right block.

FREE(P) is 0 or greater than 0, depending on whether block P is free, SIZE(P) contains the value I for

block P of size F_i, SUC(P) and PRED(P) for a free block P are the forward and backward pointers to

other free blocks of size F_i in a doubly linked list of all the free blocks of size F_i. The list head with

address AVAIL[i] for this list if given in the figure. CODE(P) for block P is the code giving the left or

right handedness of block P and the relative split count if P is a left block. In addition to the array of

list heads AVAIL[0:MAX], we also have the array F[0:MAX], which records the block sizes F_i,

0<=i<=MAX, as determined by the recurrence relation. It is assumed that F₀ has a value large enough

to allot the storage of the control fields.

The following are the 2 sub algorithms that take care of the insertion and deletion of blocks into and

from the above linked lists.

Procedure: INSERT(P,I) given the arrays and block structures as previously described, parameters I

and P, this procedure inserts P into the list headed by AVAIL[I].

1.FREE(P)←0

SIZE(P) ←1

SUC(P) ←SUC(AVAIL[I])

SUC(AVAIL[I]) ←P

PRED(P) ←AVAIL[I]

PRED(SUC(P)) ←P

2.[finished]

Return

Procedure: DELETE(P). Given the arrays and block structures as previously described and parameter

P, this algorithm deletes block P from the list in which it appears.

1. SUC(PRED(P)) ←SUC(P)

PRED(SUC(P)) ←PRED(P)

2.[Finished]

Return

A general algorithm for allocating storage using the buddy system is as follows:

1. Check that the requested amount of storage is not larger than amount available.

2. Determine the smallest size block larger than the requested amount of storage.

3. Search list head blocks for smallest free block greater than or equal to the

requested size.

4. If such a block does not exist then return.

5. Remove the free block from its linked list.

6. Repeat step 7 until the correct size is reached.

7. Split the block into buddies and place inappropriate buddy on its linked list.

8. Return address of block.

The following algorithm services the request for storage blocks.

The algorithm presumes that the value of K has been fixed so as to determine which

recurrence relation is being used.

Function: ALLOCATE_BUDDY(N). Given the arrays and block structures as

previously described, this algorithm receives a request for a block of size N and

returns the pointer P set to the address of block of size F_i , which is the smallest

size larger than or equal to N. It is assumed that the value of K has been fixed so

as to determine which recurrence relation is being used. Local variables include I

and J (integers) and Q(pointer).

1. [Determine size code]

If N>F[MAX]

then Return(NULL)

else I←0

Repeat while N>F[I]

I←I+1

2. [Find first available block]

J←I

Repeat while SUC(AVAIL[J])=AVAIL[J]

J←J+1

If J>MAX

then Return(NULL)

P←SUC(AVAIL[J])

Call DELETE(P)

3. [Split as required until correct size is reached]

Repeat while J>I and J≥K

Q←P+F[J-1]

CODE(P) ←CODE(P)+1

CODE(Q) ←0

If I>J-K

then Call INSERT(Q,J-K)

J←SIZE(P) ←J-1

else Call INSERT(P,J-1)

J←SIZE(Q) ←J-K

P←Q

4. [Allocate block P of size F_i]

FREE(P) ←1

Return(P)

In the First step of the function, a check is made to ensure the requested amount of storage is not larger

that the amount available. If such a condition occurs, a NULL value is returned and appropriate action

is assumed to be taken in the calling program. Otherwise, the first step of the algorithm determines the

smallest size of block that is larger than the requested amount of storage. The second step searches the

list head blocks for the smallest free block equal to or larger than the required size. If such a block is

found, it is removed from the doubly linked list. The third step controls the splitting operation on this

block. The if statement in step 3 causes the left buddy of each split block to be placed on the

appropriate linked list until one of the left buddies satisfies the request size. the inappropriate

buddy(either left or right) is placed on the correct linked list, while the other buddy is marked

allocated and its address returned.

Consider the following situation. A request for a block of storage of size 30(N =30) has been received.

The storage allocation system in use us the Fibonacci buddy system described previously(K=2 and

MAX=6). Initially, the entire block of size 144 is free, as shown in Fig. The SUC and PRED fields

have been dropped to simplify the diagram. Since the block of size 144 is the smallest block larger

than size 30, it is selected, Figure shows the first split of this block. The smallest right buddy is again

split as shown in the figure. The new right buddy is still larger than the requested size, so the larger

left buddy is marked free, and the CODE is set to zero indicating a right buddy and placed on the

appropriate linked list. the left buddy in Figure is the most efficient size for the request. This block is

marked occupied and its address is returned to the calling program. Figure shows the segment of

memory after the splitting is complete. The occupied bock is indicated by shading.

The following general algorithm controls the return of storage, merging with appropriate buddies

whenever possible. The algorithm assumes K has been set to indicate the recurrence relation being

used.

1. Repeat step 2 until all possible merges have been made.

2. If the code of the freed block is greater than zero

then determine the address of its right buddy

if the right buddy is occupied or the wrong size

then insert the free block on the appropriate list and return

else remove the right the buddy from its linked list and combine buddies

else determine the address of its left buddy

if the left buddy is occupied or the wrong size

then insert the free block on the appropriate list and return

else remove the left buddy from its linked list and combine buddies

3. Insert maximal block on appropriate linked list

A detailed algorithm for this function is now presented.

Procedure: FREE_BUDDY(P). Given a block beginning at address P, this algorithm inserts it(or merges of it with appropriate buddies) onto the proper free list. It is assumed that the value of K has been fixed so as to determine which recurrence relation is being used. Q is local variable.

1. [Perform all possible merger]

Repeat step 2 while SIZE(P)<MAX

2. [Merges blocks]

If CODE(P)>0

then Q←P+F[SIZE{P}]

(P is a left block, Q is address of right block)

If FREE(Q)>0 or SIZE(Q)≠SIZE(P)-K+1

then (right block id occupied or wrong size)

Call INSERT(P,SIZE(P))

Return

else (combine buddies)

CODE(P) ←CODE(P) -1

SIZE(P) ←SIZE(P)+1

Call DELETE(Q)

else (P is a right block, Q is address of left block)

Q←P-F[SIZE(P)+K-1]

If FREE(Q)>0 or SIZE(Q) ≠ SIZE(P) +K-1

then (left block is occupied or wrong size)

Call INSERT(P,SIZE(P))

Return

else (combine buddies)

CODE(Q) ←CODE(Q)-1

SIZE(Q) ←SIZE(Q)+1

Call DELETE(Q)

P←Q

3. [We get here if only if P is maximal block]

Call INSERT(P,MAX)

Return

The first step of the algorithm controls the merging process. The second step performs the actual

merging of blocks. If the CODE of freed block is greater than 0, P is a left block; otherwise it is a

right block. In both these cases, if the neighboring block to the retuned block is free and a buddy, the

two blocks are combined and the looping continues. If the neighboring block is not a buddy or is in

use, the function places the final block on the appropriate linked list and terminates.

Suppose that the previously allocated block of storage in Figure is now released. The initial situation is

given in the Figure. The PRED and SUC fields have once more been let out to simplify the diagram.

Since the CODE of the released block is greater than 0, it is recognized as a left block. Its right buddy

is examined and found to be free, allowing the two blocks to be merged. CODE field of the new block

is determined and its SIZE field incremented. The situation after this process is shown in the Figure.

The CODE field of this new block is 0, indicating a right block. The left buddy of this block is free,

and the two blocks are combined following the same procedure as described above. Since P is now the

maximal block, it is inserted on the appropriate linked list and the function terminates. The final result

is shown in the figure.

It should be noted that when K=1(when the strategy is in effect the buddy system), then the addresses

of buddies differ from each other by amounts that are integral powers of two. Since all addresses are

in binary representation in a computer, the address calculating given earlier could be replaced by a

method that makes use of this fact, possibly speeding up these algorithms.

With regard to the performance of the algorithms, Knuth’s simulation showed that the buddy

performed quite well, comparable to his boundary-tag method, and in fact, buddy system has proven

itself in practice. Statistical analysis has been performed on the Fibonacci system, and the results

appear to show it to be superior to the buddy system(quite possibly because of the wider range of

block sizes available for a given segment of storage). The advantage of the Fibonacci system which

makes it appear even more useful is that the average amount of wasted storage is less than for the

buddy system. This is because there are at least as many Fibonacci numbers less than a given number

than there are integral powers of two. In fact, for n>4, there are always more Fibonacci numbers less

than or equal to n than there are powers of two, while n≤4, there are at least as any Fibonacci numbers.

Hence the Fibonacci system has more sizes available and is more likely to achieve a better fit of

allocated amount to requested amount. In summary, then, both of these methods appear to be suitable

for use as part of a storage management system.