Do you think IIT Guwahati certified course can help you in your career?
Introduction
A Buddy System is a memory management and allocation algorithm that divides memory into the power of two and tries to satisfy a memory request as suitable as possible. It uses memory in halves to try to give the best fit.
Assume the size of memory is 2m and the size of the process is P.
If 2m-1 < P <= 2m, we will allocate the memory to the process. Otherwise, we will divide the memory blocks into equal halves and check for the condition as mentioned earlier. If it does not satisfy the requirement, we will recursively repeat this step until it fulfills the condition.
What is Buddy System?
The Buddy System is a method used in computer operating systems to manage memory effectively. It works by dividing memory into fixed-size blocks. When a process needs memory, the system locates the smallest available block that fits the requested memory size. This helps in efficient memory allocation and management, optimizing system performance. To continue fulfilling the request, one of the two companions will further divide into smaller pieces. Buddy technology divides blocks of different sizes when they are allocated and then coalesces them when they are released to effectively partition a large block into smaller blocks of different sizes as needed.
Example
Assume we have a buddy system with a physical address space of 256 KB, and we want to find the partition size for the 36 KB process.
Here, 36 Kb is greater than 32 KB but less than 64 KB. Therefore a 64KB partition is suitable for storing the process.
Why buddy system?
There is a limit on the number of active processes in static partitioning. Space usage is also inefficient if there is a big difference between partition size and process size.
Dynamic partitioning is more complex to maintain because the size of the partition changes when the partition is allocated to a new process.
Buddy system falls somewhere between static and dynamic partitioning. It supports limited but efficient splitting and combining of memory blocks.
Types of Buddy System
Researchers propose several buddy systems that can reduce execution time and increase memory utilization.
Binary Buddy System
In this buddy system, the memory block of 2m is divided into two equal parts of 2m-1. It satisfies the following recurrence relation. Now let us see an example to understand the binary buddy system.
Consider a scenario where the kernel wants 50 kb of memory and the memory segment is initially 512 kb in size. At first, the section is split into two buddies. Assume that A1 and A2 are 256 kb each in size. Two 128 kb buddies, designated B1 and B2, are created from one of these buddies. But, 64 kb is the next highest power of 50 kb. Thus either B1 or B2 is then divided into two 64 kb friends (C1 and C2), and one of these buddies is then used to fulfil the 50 kb request. Only the split block's special buddy block can be combined with it to recreate the larger block from which it was split.
Fibonacci Buddy System
A Fibonacci buddy system uses block sizes 16, 32, 48, 80, 128, 208 bytes, such that each block size is the sum of the two preceding blocks. While splitting a block from one free list, the two parts get added to the two preceding free lists. It can be reduced by making the permitted block sizes closer together. Now let us see an example to understand the Fibonacci buddy system.
Suppose there is a memory size of 377 kb. Then 377 kb will be divided into 144 kb and 233 kb, respectively. After that, 144 will be further divided into (55 + 89), and 233 will be further divided into (89 + 144). According to the memory requirement, this division will go on.
Weighted Buddy System
In a weighted buddy system, the memory block of size 2k+2 is split into 3.2k and 2k sized blocks. Further 3.2k sized block is split into two 2k+1 and 2k sized blocks. Now let us see an example to understand the weighted buddy system.
We are already aware that the memory block of size 2k+2 is split into 3.2k and 2k-sized blocks. Suppose there is a memory size of 64 kb. Then, according to the formula, it will divide into 48 and 16 kb, respectively. Again proceeding with the formula, 48 kb will be divided into 32 and 16 kb. And 16 kb will be divided into 12 and 4 kb, respectively. Like this, the memory partitioning will be done and the memory requested will be granted.
Tertiary Buddy System
The tertiary buddy system allows blocks of sizes 2k, 0 ≤ k ≤ m and 3.2k, 0 ≤ k ≤ m-3. This scheme allows blocks of sizes 4096, 2048, 1536, 1024, 768, 512,384, 256, and so on. In a tertiary buddy system, there are twice as many block sizes as are available in the binary buddy system. There is a decrease in the amount of internal fragmentation by allowing more block sizes.
Now let us see an example to understand the tertiary buddy system.
We are aware that it allows blocks of size 2k and 3.2k. So, if there is a memory size of 64 kb, it will be divided into 32 kb, 24 kb, and 8 kb, respectively. 32 kb will be further divided into 16, 12, and 4 kb, according to the partitioning size. This partitioning will go on further.
Buddy System Memory Allocation Technique
The buddy system memory allocation technique uses an algorithm that splits memory to best accommodate memory requests. For the optimal fit, this system involves dividing memory in half. Implementing the Buddy memory allocation is not that difficult. The buddy system comes in a variety of forms. The simplest and most prevalent types are those in which each block is broken into two smaller blocks. In this system, each memory block has an order, which is a number ranging from 0 to a predetermined upper limit.
Example of Buddy System Memory Allocation
Let us see an example of buddy system memory allocation technique. Think about a buddy system-equipped system with a 256 KB physical address space. Determine the partition size for a 50 KB process.
Think a bit about it. How will you proceed with this problem? We hope that you have got the right one. Let us discuss the solution now.
Buddy system allocation has the following advantages, such as:
The buddy memory system has less external fragmentation than other simpler techniques.
The buddy memory allocation system is achieved using a binary tree for representing used or unused split memory blocks.
It Allocates a memory block of the correct size.
The buddy system is speedy for the allocation or deallocation of memory.
The cost to allocate and deallocate a block of memory is low compared to that of best-fit or first-fit algorithms in comparison to other simpler techniques,
Merging adjacent free blocks is easy.
The main advantage of the buddy system is coalescing. It is defined as how fastly adjacent buddies can be combined to form more significant segments. This is known as coalescing.
Disadvantages of Buddy System
It has the following disadvantages:
It requires all allocation blocks to be powers of two.
It allows internal fragmentation. For example, a request of 515KB of size 1024KB. In consequence, such an approach gives a waste of 509KB.
Splitting and merging adjacent blocks is a recurrent operation, thus very unpredictable and inefficient.
It requires extra time to fragment and coalesce blocks.
The two smaller portions of the block are therefore the same size, making them buddies. Two different buddies work together as a single unit to watch out for and support one another. To continue fulfilling the request, one will further divide it into smaller pieces.
2. What is Buddy System used for?
The buddy memory allocation system is achieved using a binary tree for representing used or unused split memory blocks. The buddy system is fast to allocate or deallocate memory. The cost of allocating and deallocating a block of memory is low compared to best-fit or first-fit algorithms in buddy systems.
3. What are the advantages of Buddy System in OS?
The advantages of the buddy system are it has less external fragmentation than other simpler techniques and is achieved using a binary tree for representing used or unused split memory blocks. It Allocates a memory block of the correct size.
4. What is Buddy memory technique?
The buddy system memory allocation technique uses an algorithm that splits memory to best accommodate memory requests. For the optimal fit, this system involves dividing memory in half. Implementing the Buddy memory allocation is not that difficult.
Conclusion
A Buddy system is a memory allocation method in which the size of memory blocks is in the power of two. It is fast and memory-efficient compared to other allocation techniques like first-fit or best fit. There are four buddy systems based on execution time and memory utilization.
Visit here to learn more about different topics related to database and management systems. Ninjas don't stop here. Check out theTop 100 SQL Problems to master frequently asked questions in big companies and land your dream job. Also, try Coding Ninjas Studio to practice a wide range of DSA questions asked in many interviews.
569+ registered 
