Introduction
When processes are allocated and released over time, free memory can become scattered into many small holes. This is external fragmentation: enough free memory may exist in total, but not as one continuous block.
Compaction and the buddy system handle this problem in different ways. Compaction rearranges memory to combine holes, while the buddy system organizes memory into power-of-two blocks that can be split and merged.
The Fragmentation Problem
In contiguous memory allocation, a process often needs one continuous physical memory block. If memory contains many small holes, a large process may fail to fit even when the total free memory is enough.
For example, if free holes are 50 KB, 150 KB, and 100 KB, the total free memory is 300 KB. But a request for 250 KB fails because the largest single hole is only 150 KB.
Compaction and the buddy system both try to make memory allocation more manageable, but they do it using different ideas.
Compaction
Compaction reduces external fragmentation by moving allocated memory blocks together. When allocated blocks are placed side by side, the scattered holes combine into one larger free block.
Before compaction: P1 => Hole => P2 => Hole => P3 => Hole
After compaction: P1 => P2 => P3 => Large Free Block
The total free memory does not increase. What changes is the arrangement of free memory. Several small holes become one continuous free area.
Compaction
Compact Compaction Example
Suppose memory contains: P1 | 50 KB hole | P2 | 150 KB hole | P3 | 100 KB hole
Total free memory is: 50 KB + 150 KB + 100 KB = 300 KB
A process requesting 250 KB cannot fit before compaction because no single hole is large enough.
After compaction, memory can become: P1 | P2 | P3 | 300 KB hole
Now the 250 KB request can be satisfied because one continuous block of 300 KB exists.
Cost of Compaction
Compaction is useful, but it is not free. The operating system must move allocated blocks, update memory-management information, and ensure that processes still refer to the correct memory locations.
Important costs include:
Memory movement: Moving large blocks takes time.
Address updates: Relocation or mapping information must remain correct.
Process coordination: Processes may need to be paused or controlled during movement.
Metadata updates: The OS must update its memory tables after rearrangement.
So compaction trades runtime overhead for a larger usable contiguous free block.
Buddy System
The buddy system manages memory using block sizes that are powers of two, such as 128 KB, 256 KB, 512 KB, and 1024 KB.
A larger block can be split into two equal halves called buddies. If both buddies later become free, they can be merged back into the larger block.
This keeps memory management structured and makes splitting and merging easier.
Buddy System and Allocation
Buddy Allocation
When a request arrives, the buddy system rounds the request up to the next power of two.
For example:
Request Size | Allocated Block |
|---|---|
100 KB | 128 KB |
200 KB | 256 KB |
300 KB | 512 KB |
If a block of the required size is available, it is allocated directly. If not, the system splits a larger block repeatedly until the correct size is produced.
For a 100 KB request from a 1024 KB block:
1024 KB => 512 KB + 512 KB512 KB => 256 KB + 256 KB256 KB => 128 KB + 128 KB
One 128 KB block is allocated. The remaining blocks stay free.
Buddy Merging
When a block is freed, the system checks whether its matching buddy is also free. If both buddies are free, they can merge into a larger block.
For example:
128 KB free + matching 128 KB free => 256 KB free256 KB free + matching 256 KB free => 512 KB free512 KB free + matching 512 KB free => 1024 KB free
The key condition is that the two blocks must be matching buddies. Two adjacent free blocks of the same size do not automatically merge unless they are the correct pair created from the same larger block.
Buddy System Trade-Offs
The buddy system is fast and organized, but it can waste memory because requests are rounded up to power-of-two sizes.
Advantage | Limitation |
|---|---|
Easy splitting into equal halves | Request size may be rounded up |
Fast merging of free buddies | Internal fragmentation can occur |
Organized free lists by block size | Some space efficiency is sacrificed |
For example, a 100 KB request receives a 128 KB block. The unused 28 KB is internal fragmentation inside the allocated block.
Compaction vs Buddy System
Feature | Compaction | Buddy System |
|---|---|---|
Main goal | Combine scattered holes | Manage blocks in a structured way |
Main technique | Move allocated blocks together | Split and merge power-of-two blocks |
Handles | External fragmentation | Free-space organization and merging |
Main cost | Memory movement overhead | Internal fragmentation from rounding |
Block sizes | Not restricted to powers of two | Restricted to power-of-two sizes |
Compaction directly attacks scattered free holes. The buddy system avoids arbitrary block sizes and keeps allocation more predictable.
Summary
Compaction handles external fragmentation by moving allocated processes together so that scattered holes become one larger contiguous free block. It can make a large allocation possible, but it costs time because memory and metadata must be updated.
The buddy system manages memory using power-of-two blocks. It splits larger blocks into equal buddies during allocation and merges matching free buddies during deallocation, giving faster organization at the cost of possible internal fragmentation.
Be the first to add a comment.