What is the buddy system memory allocation algorithm?

Buddy memory allocation is a memory management Memory management refers to the process of controlling and organizing computer memory to optimize its usage and allocation. algorithm used in OS to divide memory into fixed size blocks to fulfill allocation requests. The memory is split into power-of-two-sized blocks, and each block is considered a buddy to another block of the same size.

When a request is made, the algorithm finds the smallest available block that can accommodate the request. If a larger block is available, it is split into two buddies, and the process continues until the desired size is achieved. This algorithm efficiently utilizes memory but can suffer from internal fragmentationInternal fragmentation refers to the wasted memory within a block or partition due to the allocation of memory in larger units than required.. Similarly, coalescing Coalescing refers to the process of merging adjacent blocks of free memory to create larger contiguous blocks.occurs when free memory blocks are recursively merged to create larger contiguous free space.

Allocation algorithm

Firstly we will explore the memory allocation process when the OS makes a memory request. The memory is divided into sizes that are based on powers of two.

Here are the steps involved in the allocation of memory space.

1. The available memory is divided into fixed size blocks in powers of two.

2. Each block is considered a buddy to another block of the same size.

3. When a memory request is made, the algorithm searches for the smallest available block to accommodate the requested size.

4. If a larger block is found, it is recursively split into two buddies until the desired size is achieved, and one of the buddies is allocated for the request.

Let's take an example of a system with a large free memory space of size $2^{7} = 128 \text{ bytes}$. Imagine a situation where we allocate memory in a sequence of steps: first, 32 bytes are allocated, followed by 7 bytes, then 64 bytes, and finally, 50 bytes.

Here is how the buddy memory allocation algorithm will work.

One drawback of the buddy memory system is that it can result in internal fragmentation, as memory blocks are allocated in powers of two. For example, if 7 bytes are requested, a block of at least 8 bytes is allocated, resulting in 1 byte of wasted memory.

Coalescing algorithm

Coalescing helps reduce internal fragmentation by consolidating free memory blocks into larger, contiguous regions. During coalescing, the buddy allocator merges adjacent free memory blocks to form larger blocks until the buddy block is occupied.

The following steps are involved.

1. When a memory block is deallocated or freed, the algorithm checks if its buddy (the adjacent block of the same size) is also free.

2. If the buddy is free, the algorithm merges the two blocks into a larger block by combining their memory regions.

3. The merging process in the buddy allocator occurs recursively, where larger blocks are formed by merging adjacent free blocks, and it continues until the buddy block is occupied.

To understand the functioning of memory space in coalescing, we can examine the process of deallocating the previous memory space, which was demonstrated above in the allocation algorithm. We will deallocate the memory blocks in the following order: 8-byte block, 32-byte block, and 64-byte block.

Conclusion

In conclusion, the buddy memory allocation algorithm provides efficient memory management by dividing memory into blocks of powers of two. It allows for quick allocation and deallocation of memory blocks and supports coalescing to reduce fragmentation.