In addition, in comparison to other simpler techniques such as dynamic allocation, the buddy memory system has little internal fragmentation, and has little overhead trying to do compaction of memory.
After deciding on the upper limit (let's call the upper limit u), the programmer has to decide on the lower limit, i.e. the smallest memory block that can be allocated. This lower limit is necessary so that the overhead of storing used and free memory locations is minimised. If this lower limit did not exist, and many programs request small blocks of memory like 1K or 2K, the system would waste a lot of space trying to remember which blocks are allocated and unallocated. Typically this number would be a moderate number (like 2, so that memory is allocated in 22 = 4K blocks), large enough to keep wastage low, but small enough to avoid overhead. Let's call this lower limit l).
Now we have got our limits right, let us see what happens when a program requests for memory. Let's say in this system, l = 6, which results in blocks 26 = 64K in size, and u = 10, which results in a largest possible allocatable block, 210 = 1024K in size. The following shows a possible state of the system after various memory requests.
Disadvantages
Because of the way the buddy memory allocation technique works, there may be a moderate amount of external fragmentation - memory wasted because the memory requested is a little larger than a small block, but a lot smaller than a large block. (For instance, a program that requests 65K of memory would be allocated 128K, which results in a waste of 63K of memory).How it works
The buddy memory allocation technique allocates memory in powers of 2, i.e 2x, where x is an integer. Thus, the programmer has to decide on, or to write code to obtain the upper limit of x. For instance, if the system had 2000K of physical memory, the upper limit on x would be 10, since 210 would be the best fit, since it is lesser than 2000K. Sadly, this results in a waste of about 976K of memory. (There are ways of countering this, of course : the programmer could choose to just divide the memory into halves, ignoring the power of 2 rule. That would result in the optimal usage of memory).
64K | 64K | 64K | 64K | 64K | 64K | 64K | 64K | 64K | 64K | 64K | 64K | 64K | 64K | 64K | 64K |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1024K | |||||||||||||||
A-64K | 64K | 128K | 256K | 512K | |||||||||||
A-64K | 64K | B-128K | 256K | 512K | |||||||||||
A-64K | C-64K | B-128K | 256K | 512K | |||||||||||
A-64K | C-64K | B-128K | D-128K | 128K | 512K | ||||||||||
A-64K | 64K | B-128K | D-128K | 128K | 512K | ||||||||||
128K | B-128K | D-128K | 128K | 512K | |||||||||||
256K | D-128K | 128K | 512K | ||||||||||||
1024K |
This allocation could have occured in the following manner
Typically the buddy memory allocation system is implemented with the use of a binary tree to represented used or unused split memory blocks.