2.7.4 Buddy Systems of Memory Allocation

The objective of this assignment is to compare the performance of the exponential and the Fibonacci buddy systems of memory allocation. For more details on buddy systems, refer to the book: Donald E Knuth. Fundamental Algorithms, Volume 1 of The Art of Computer Programming, Addison-Wesley, 1968, Second Edition, 1973. Consider an exponential buddy system with the following allowable block sizes: 8, 16, 32, 64, 128, 512, 1024, 2048, and 4096. Let the allowable block sizes for the Fibonacci system be 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2594, and 4191. Your tasks are the following.

1.

Generate a random sequence of allocations and liberations. Start with an empty memory and carry out a sequence of allocations first, so that the memory becomes adequately committed. Now generate a sequence of allocations and liberations interleaved randomly. You may try with 100 or 200 or even 1000 such allocations and liberations. While generating the memory sizes requested for allocations, you may use a reasonable distribution. For example, one typical scenario is:

Range of block size	Probability
8-100:	0.1
100-500:	0.5
500-1000:	0.2
1000-2000:	0.1
2000-4191:	0.1

2.

Simulate the memory allocations and liberations for the above random sequences. At various intermediate points, print out the detailed state of the memory, indicating the allocated portions, available portions, and the i-lists. Use recursive algorithms for allocations and liberations. It would be excellent if you implement very general allocation and liberation algorithms, that will work for any arbitrary order buddy system.

3.

Compute the following performance measures for each random sequence:

• Average fragmentation.
• Total number of splits.
• Total number of merges.
• Average size of all linked lists used in maintaining the available block information.
• Number of blocks that cannot be combined with buddies.
• Number of contiguous blocks that are not buddies.

4.

Repeat the experiments for several random sequences and print out the average performance measures. You may like to repeat the experimentation on different distributions of request sizes.