Buddy System | Operating System - Computer Science Engineering (CSE) PDF Download

Introduction

Static partitioning techniques are constrained by a predetermined number of active processes, often leading to suboptimal space utilization. In contrast, the buddy system represents a dynamic memory allocation and management approach utilizing increments based on powers of two. Assuming a memory size of 2U, when a size S is required, the buddy system efficiently divides memory into fixed-size blocks. When a process requests memory, it identifies the smallest available block capable of accommodating the requested size.

What is the Buddy System?

The Buddy System is a memory allocation technique employed by computer operating systems to efficiently manage memory. It achieves this by dividing memory into fixed-size blocks. When a process requests memory, the system locates the smallest available block that can accommodate the requested memory size.

This method of memory control is widely used in operating systems where memory allocation and deallocation occur frequently, especially in multitasking environments or systems with varying memory requirements. Memory is divided into blocks of fixed lengths, typically in powers of two (e.g., 1KB, 2KB, 4KB). When a memory allocation request is made, the system searches for a block of the appropriate size. If an exact match is found, it allocates that block to the requesting process. However, if no precise match exists, the system allocates a larger block and recursively splits it into smaller blocks until a block of the correct size is obtained.

Algorithm of Buddy System Memory Allocation Technique

The Buddy System allocates and manages memory efficiently through a structured approach:

• Memory is initially divided into fixed-size blocks, each sized in powers of 2 (e.g., 2, 4, 8, 16, 32, 64, 128, etc.).
• Each block is labeled with its size and a unique identifier.
• Initially, all memory blocks are free and organized in a binary tree structure. Nodes represent blocks, with leaves being the smallest available blocks.
• When a process requests memory, the system locates the smallest block that can satisfy the request. If the found block is larger than needed, it is split into two equal-sized "buddy" blocks.
• One buddy block is allocated to the process and recorded in the memory allocation table, while the other buddy block returns to the free memory pool and reconnects with the binary tree.
• Upon memory release by a process, the system marks the block as free and checks for its buddy block. If both blocks are free, they merge into a larger block and reintegrate into the binary tree.

The Buddy System offers benefits such as efficient memory utilization, reduced fragmentation, and rapid allocation and deallocation of memory blocks. However, it may suffer from internal fragmentation when allocated blocks are larger than necessary, leading to potential memory wastage. Despite these drawbacks, the Buddy System remains a valuable memory allocation technique in operating systems, especially beneficial for embedded systems with limited memory resources.

Types of Buddy Systems 

The Buddy System in memory management typically refers to a specific method used for allocating and deallocating memory blocks. However, within this framework, variations or adaptations may exist depending on specific requirements or optimizations needed for different systems. Here are several types of Buddy Systems:

1. Fibonacci Buddy System: In a Fibonacci buddy system, block sizes follow a Fibonacci sequence (e.g., 16, 32, 48, 80 bytes), where each block size is the sum of the two preceding sizes. This approach minimizes fragmentation by clustering allowable block sizes closely together. For example, with a memory size of 377 KB, it would be partitioned into sizes like 144 KB and 233 KB, subdivided further based on memory demands.
2. Binary Buddy System: This system maintains free lists of blocks of each size, allowing efficient discovery of blocks matching requested sizes. Initially, memory is split into halves recursively (e.g., 512 KB into two 256 KB partitions), further subdivided as needed to fulfill memory requests based on powers of 2.
3. Weighted Buddy System: In this variant, each memory block carries a weight relative to its size. When allocating memory, the system considers both the size of the requested memory and the weight of available blocks to find the best match efficiently.
4. Tertiary Buddy System: Unlike traditional buddy systems that divide memory into fixed-size blocks, the tertiary buddy system introduces a third level of memory structure, offering greater flexibility in memory allocation.

Features of Buddy System 

The Buddy System offers several key features:

• Scalability: It scales effectively with increasing memory demands by dynamically adjusting block sizes based on allocation patterns.
• Efficient Splitting and Merging: Ensures optimal utilization of memory by splitting allocated blocks into smaller buddies and merging adjacent free blocks when possible.
• Reduced Fragmentation: Minimizes memory fragmentation through efficient block management, merging adjacent free blocks to prevent unusable gaps.
• Allocation Efficiency: Provides fast allocation and deallocation of memory blocks due to its structured approach.
• Power of Two Block Sizes: Simplifies memory management by dividing memory into sizes that are powers of two, facilitating straightforward splitting and merging processes.

Advantages of Buddy System The Buddy System offers several advantages:

• Easy implementation and management of memory allocation.
• Efficient allocation of memory blocks of appropriate size, reducing waste.
• Effective prevention of memory fragmentation, maintaining system performance.
• Suitable for dynamic memory allocation needs in systems like embedded systems and operating systems.

Disadvantages of Buddy System Despite its advantages, the Buddy System has limitations:

• Requires all allocation units to be powers of two, leading to potential internal fragmentation.
• Designed for fixed-sized memory allocations, which may not be optimal for variable-sized allocations.
• General-purpose approach may not suit all specialized applications requiring specific memory allocation strategies for optimal performance.

Example: Consider a system having buddy system with physical address space 128 KB.Calculate the size of partition for 18 KB process.
Sol:

So, size of partition for 18 KB process = 32 KB. It divides by 2, till possible to get minimum block to fit 18 KB.