The experiment includes designing and implementing a dynamic memory allocator for allocating and releasing memory blocks of different sizes for users' programs at runtime, and testing it to verify its correctness and performance. This experiment implements the Buddy memory allocator.

As shown in the figure below, the principle of the Buddy memory allocator is to treat a whole block of available memory as a whole. When memory needs to be allocated, it's repeatedly split in half until a block of the appropriate size is obtained.

The two sub-blocks obtained by dividing the same block are called "Buddies". When memory is released, in addition to releasing the block that needs to be released, it is also necessary to check whether its "Buddy" is free. If so, it can be merged upwards. The Buddy memory allocator is suitable for responding to larger memory requests, and because of the Buddy's merging mechanism, external memory fragmentation can be minimized as much as possible.

This experiment does not use a linked list structure to manage memory blocks, but instead uses a bitmap to manage them all, maintaining a binary tree structure composed of a series of bitmaps. For the allocated memory size $n$ (in units of the smallest memory block size), there are a total of $l = log2 n + 1$ Buddy memory block sizes, the maximum block size is the smallest power of 2 greater than n; the minimum block size is defined as a constant LEAF_SIZE = 16 bytes. When they are treated as a tree structure, there are n nodes at the bottom root node, each of which is 16 bytes, and there is one node at the top level, which is 16n bytes in size. Take a 4-level buddy system as an example, as shown in the figure below:

As shown in the figure below, for a block, if it is not a block of l = 0, the two sub-blocks obtained by dividing it, which are mutually buddy, are defined as its left sub-block and right sub-block, respectively; if it is not a top-level block, the block that is generated by division is defined as its parent block. At the same time, for each layer of blocks, from left to right (in the direction of increasing address), the index is marked as 0. For each layer of blocks, two arrays are maintained: aaaa and spppp, the length of the array is the number of blocks.

• allocated indicates whether the corresponding block has been allocated as a whole;
• split indicates whether any part of the corresponding block has been divided and allocated;

Since each element of the above two arrays only needs one bit to represent the state, a bitmap is used to reduce the overhead of managing memory data structures. For example, in a char array, each element consists of 8 bits, so a char array of k elements can manage 8k blocks.