Buddy Memory Allocation - in Practice

In Practice

The following is an example of what happens when a program makes requests for memory. Let's say in this system, the smallest possible block is 64 kilobytes in size, and the upper limit for the order is 4, which results in a largest possible allocatable block, 24 times 64K = 1024K in size. The following shows a possible state of the system after various memory requests.

This allocation could have occurred in the following manner

1. The initial situation.
2. Program A requests memory 34K, order 0.
   1. No order 0 blocks are available, so an order 4 block is split, creating two order 3 blocks.
   2. Still no order 0 blocks available, so the first order 3 block is split, creating two order 2 blocks.
   3. Still no order 0 blocks available, so the first order 2 block is split, creating two order 1 blocks.
   4. Still no order 0 blocks available, so the first order 1 block is split, creating two order 0 blocks.
   5. Now an order 0 block is available, so it is allocated to A.
3. Program B requests memory 66K, order 1. An order 1 block is available, so it is allocated to B.
4. Program C requests memory 35K, order 0. An order 0 block is available, so it is allocated to C.
5. Program D requests memory 67K, order 1.
   1. No order 1 blocks are available, so an order 2 block is split, creating two order 1 blocks.
   2. Now an order 1 block is available, so it is allocated to D.
6. Program B releases its memory, freeing one order 1 block.
7. Program D releases its memory.
   1. One order 1 block is freed.
   2. Since the buddy block of the newly freed block is also free, the two are merged into one order 2 block.
8. Program A releases its memory, freeing one order 0 block.
9. Program C releases its memory.
   1. One order 0 block is freed.
   2. Since the buddy block of the newly freed block is also free, the two are merged into one order 1 block.
   3. Since the buddy block of the newly formed order 1 block is also free, the two are merged into one order 2 block.
   4. Since the buddy block of the newly formed order 2 block is also free, the two are merged into one order 3 block.
   5. Since the buddy block of the newly formed order 3 block is also free, the two are merged into one order 4 block.

As you can see, what happens when a memory request is made is as follows:

• If memory is to be allocated

1. Look for a memory slot of a suitable size (the minimal 2k block that is larger or equal to that of the requested memory)
   1. If it is found, it is allocated to the program
   2. If not, it tries to make a suitable memory slot. The system does so by trying the following:
      1. Split a free memory slot larger than the requested memory size into half
      2. If the lower limit is reached, then allocate that amount of memory
      3. Go back to step 1 (look for a memory slot of a suitable size)
      4. Repeat this process until a suitable memory slot is found

• If memory is to be freed

1. Free the block of memory
2. Look at the neighboring block - is it free too?
3. If it is, combine the two, and go back to step 2 and repeat this process until either the upper limit is reached (all memory is freed), or until a non-free neighbour block is encountered