Page 132 - DCAP403_Operating System

Unit 7: Memory Management

Buddy System Notes

Memory management, especially memory allocation to processes, is a fundamental issue in

operating systems. A fixed partitioning scheme limits the number of active processes and may

use space inefficiently if there is a poor match between available partition sizes and process
sizes. A dynamic partitioning scheme is more complex to maintain and includes the overhead of
compaction. An interesting compromise is the buddy system.
In a buddy system, the entire memory space available for allocation is initially treated as a single
block whose size is a power of 2. When the first request is made, if its size is greater than half

of the initial block then the entire block is allocated. Otherwise, the block is split in two equal
companion buddies. If the size of the request is greater than half of one of the buddies, then
allocate one to it. Otherwise, one of the buddies is split in half again. This method continues until
the smallest block greater than or equal to the size of the request is found and allocated to it.
In this method, when a process terminates the buddy block that was allocated to it is freed.
Whenever possible, an unnallocated buddy is merged with a companion buddy in order to form
a larger free block. Two blocks are said to be companion buddies if they resulted from the split
of the same direct parent block.
The following Figure 7.5 illustrates the buddy system at work, considering a 1024k (1-megabyte)
initial block and the process requests as shown at the left of the table.
Figure 7.5: Diagram of Buddy System
0 128k 256k 512k 1024k
start 1024k
A=70K A 128 256 512
B=35K A B 64 256 512
C=80K A B 64 C 128 512

A ends 128 B 64 C 128 512
D=60K 128 B D C 128 512
B ends 128 64 D C 128 512
D ends 256 C 128 512
C ends 512 512
end 1024k

Notice that, whenever there is a request that corresponds to a block of sizes, your program should
select the block of that size that was most recently declared free. Furthermore, when a block is
split in two, the left-one (lower addresses) should be selected before the right-one.

You can assume that the list of requests is such that all requests can always be served. In other
words, you can make the following assumptions: no process will request more than the available

memory; processes are uniquely identified while active; and no request for process termination
is issued before its corresponding request for memory allocation.
It is preferable when dealing with large amounts of memory to use physically contiguous pages
in memory both for cache related and memory access latency reasons. Unfortunately, due to
external fragmentation problems with the buddy allocator, this is not always possible.

LOVELY PROFESSIONAL UNIVERSITY 125