Compaction and Buddy System
Memory Compaction
Read aloud is unavailable in this browser.
The Fragmentation Dilemma
External fragmentation represents one of the most insidious problems in memory management. As processes are allocated and deallocated over time, the memory landscape becomes increasingly fragmented—like a parking lot where small spaces are scattered between parked cars, making it impossible to park a large truck even though the total free space exceeds the truck's size.
Memory compaction is the operating system's solution to this problem: a systematic process of relocating allocated memory regions to consolidate free space into contiguous blocks. While conceptually straightforward, compaction involves significant engineering complexity, performance trade-offs, and design decisions that separate theoretical solutions from practical implementations.
By the end of this page, you will understand memory compaction algorithms in depth, including when and how to relocate processes, the role of relocation registers, different compaction strategies, and the fundamental tension between memory efficiency and system performance that shapes all compaction decisions.
Understanding External Fragmentation
Before examining compaction solutions, we must deeply understand the external fragmentation problem. External fragmentation represents a state space problem: the total amount of free memory may be sufficient for a request, but no single contiguous region can satisfy it.
The Formal Definition:
External fragmentation exists when the sum of all free memory holes exceeds a memory request size, yet no individual hole is large enough to satisfy the request:
Let F = {f₁, f₂, ..., fₙ} be the set of free memory holes
Let request_size = R
External fragmentation exists when:
Σfᵢ ≥ R, but ∀fᵢ ∈ F: fᵢ < R
This mathematical definition captures the essence of the problem: memory exists, but it's unusable in its current configuration.
A system with 100MB of free memory scattered across 50 small holes cannot satisfy a request for 10MB if the largest hole is only 8MB. The memory 'exists' but is simultaneously 'unavailable'. This paradox drives the need for compaction.
The Evolution of Fragmentation:
External fragmentation develops progressively through a predictable lifecycle:
Phase 1: Initial State The system begins with one large contiguous free region. Memory allocation is simple—requests are satisfied from this monolithic block.
Phase 2: Allocation Phase Processes are allocated sequentially or according to the chosen allocation strategy (first fit, best fit, etc.). Memory becomes partitioned into allocated and free regions.
Phase 3: Deallocation Begins Processes terminate in a different order than they were allocated. This creates 'holes'—non-contiguous free regions between still-active processes.
Phase 4: Fragmentation Cascade New allocations may partially fill some holes but rarely fill them exactly. This creates more, smaller holes. The fragmentation problem compounds with each allocation/deallocation cycle.
Phase 5: Critical Fragmentation Eventually, the system reaches a state where legitimate allocation requests fail despite adequate total free memory. At this point, compaction or alternative strategies become mandatory.
| Time | Event | Memory State | Largest Hole | Total Free |
|---|---|---|---|---|
| T₀ | Initial state | [100MB free] | 100MB | 100MB |
| T₁ | Alloc A (30MB) | [A:30MB][70MB free] | 70MB | 70MB |
| T₂ | Alloc B (25MB) | [A:30MB][B:25MB][45MB free] | 45MB | 45MB |
| T₃ | Alloc C (20MB) | [A:30MB][B:25MB][C:20MB][25MB free] | 25MB | 25MB |
| T₄ | Free B | [A:30MB][25MB hole][C:20MB][25MB free] | 25MB | 50MB |
| T₅ | Alloc D (30MB) → FAILS | Cannot satisfy: need 30MB, max hole = 25MB | 25MB | 50MB |
Quantifying Fragmentation:
Operating systems use several metrics to measure fragmentation severity:
Fragmentation Ratio:
Fragmentation_Ratio = 1 - (Largest_Hole / Total_Free_Memory)
A ratio of 0 means no fragmentation (one contiguous block); approaching 1 indicates severe fragmentation.
Unusable Memory Percentage:
Unusable_Memory = (Total_Free - Max_Satisfiable_Request) / Total_Memory × 100%
Hole Count: The number of separate free regions. Higher counts typically correlate with worse fragmentation, though hole sizes matter more than count.
Average Hole Size:
Avg_Hole_Size = Total_Free_Memory / Number_of_Holes
Smaller average hole sizes indicate more severe fragmentation.
Compaction Fundamentals
Memory compaction is the process of relocating allocated memory regions to consolidate scattered free space into one or more large contiguous blocks. This seemingly simple concept involves substantial complexity in implementation.
The Core Compaction Invariant:
A valid compaction must maintain the following invariant:
∀ process P: behavior(P) before compaction ≡ behavior(P) after compaction
The compaction process must be completely transparent to running processes. No process should detect that it has been relocated—all memory references must continue to work correctly.
Requirements for Compaction:
Compaction is only possible when certain architectural prerequisites are met:
- •Execution-time Binding — Processes must use execution-time address binding (not compile-time or load-time binding). This allows the relocation of processes after they've started executing.
- •Relocation Registers — The hardware must support relocation registers (base registers) that can be updated without modifying process code. All process addresses are computed as: physical_address = base_register + logical_address.
- •MMU Support — A Memory Management Unit must translate logical addresses to physical addresses transparently, allowing the OS to change the mapping without process awareness.
- •Process State Preservation — The system must be able to suspend processes, relocate their memory, update mapping registers, and resume execution without corrupting process state.
Early systems with compile-time or load-time binding could NOT perform compaction. If a program was compiled to run at address 0x1000, it had to remain at address 0x1000 forever. The transition to execution-time binding, enabled by relocation hardware, made compaction possible and revolutionized memory management.
The Compaction Process:
Compaction follows a systematic sequence of operations:
Step 1: Suspend Activity All affected processes must be suspended. Memory being copied cannot be simultaneously modified by executing processes—this would cause data races and corruption.
Step 2: Calculate Target Locations The OS determines where each process will be relocated. This involves deciding:
- Which processes to move
- Where to move them
- In what order to perform the moves
Step 3: Copy Memory Content Physical memory content is copied from source to destination locations. This is the performance-critical phase—large memory regions require significant time to copy.
Step 4: Update Relocation Registers Process Control Blocks are updated with new base addresses. The relocation register values are modified to reflect new physical locations.
Step 5: Update Internal References Any OS data structures that reference physical memory locations (I/O buffers, page tables in paged systems, etc.) must be updated.
Step 6: Resume Processes Processes resume execution. From their perspective, nothing has changed—they continue using the same logical addresses, which now map to different physical locations.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455
// Simplified compaction algorithm pseudocodetypedef struct { int pid; void* base_address; // Current physical address size_t size; // Process memory size size_t new_base; // Target address after compaction} ProcessMemoryInfo; void perform_compaction(ProcessMemoryInfo* processes, int count) { // Step 1: Suspend all processes for (int i = 0; i < count; i++) { suspend_process(processes[i].pid); } // Step 2: Calculate target positions (simple end-to-end packing) size_t current_position = MEMORY_START; for (int i = 0; i < count; i++) { processes[i].new_base = current_position; current_position += processes[i].size; } // Step 3: Perform relocation (careful ordering to avoid overwrites) // Sort by destination to determine safe copy order sort_by_destination(processes, count); for (int i = 0; i < count; i++) { if (processes[i].base_address != processes[i].new_base) { // Use memmove for overlapping regions, memcpy otherwise if (regions_overlap(processes[i].base_address, processes[i].new_base, processes[i].size)) { memmove((void*)processes[i].new_base, processes[i].base_address, processes[i].size); } else { memcpy((void*)processes[i].new_base, processes[i].base_address, processes[i].size); } } } // Step 4: Update relocation registers in PCBs for (int i = 0; i < count; i++) { update_pcb_base_register(processes[i].pid, processes[i].new_base); } // Step 5: Update free memory list update_free_list(); // Step 6: Resume all processes for (int i = 0; i < count; i++) { resume_process(processes[i].pid); }}Compaction Strategies
Not all compaction approaches are equal. The choice of compaction strategy significantly impacts system performance and behavior. Different strategies offer different trade-offs between simplicity, speed, and effectiveness.
Strategy 1: Complete Compaction (One-End Packing)
The simplest strategy moves all processes to one end of memory, creating a single large free region at the other end.
Advantages:
- Maximum contiguous free space created
- Simple conceptually and algorithmically
- Eliminates all external fragmentation completely
Disadvantages:
- Potentially moves all processes (maximum data movement)
- Longest pause time
- All processes must be suspended simultaneously
Strategy 2: Partial Compaction (Selective Movement)
Instead of relocating all processes, this strategy identifies the minimum number of processes that must move to satisfy pending allocation requests.
Approach:
- Identify the allocation request that triggered compaction
- Find neighboring free holes that, if merged, would satisfy the request
- Move only the processes between those holes
Advantages:
- Less data movement than complete compaction
- Shorter pause times
- Fewer processes disrupted
Disadvantages:
- May leave residual fragmentation
- More complex to implement
- May require repeated partial compactions
Strategy 3: Optimal Compaction
This strategy seeks to minimize total data movement while achieving the compaction goal. It's formulated as an optimization problem:
Minimize: Σ(bytes_moved for each process)
Subject to: After compaction, largest_free_block ≥ pending_request
The Optimal Compaction Problem is NP-Hard:
Finding the truly optimal solution—minimum total bytes moved—is computationally intractable for large numbers of processes. This is reducible to a variant of the bin-packing problem.
Practical Approaches:
- Greedy heuristics that approximate optimal solutions
- Move smallest processes first (less data, more flexibility)
- Move processes closest to destination first (minimize per-move cost)
- Prefer moving processes that haven't been moved recently (fairness)
| Strategy | Data Movement | Pause Time | Fragmentation After | Complexity |
|---|---|---|---|---|
| Complete | Maximum | Longest | Zero | Low |
| Partial | Moderate | Medium | Possible residual | Medium |
| Optimal | Minimum | Shortest | Controlled | High |
| Incremental | Distributed | Many short | Gradual reduction | High |
Strategy 4: Incremental Compaction
Rather than compacting all at once, incremental compaction performs small moves during idle periods or as part of regular system maintenance.
Approach:
- Maintain a 'compaction debt' metric indicating fragmentation severity
- During CPU idle time or low-activity periods, move one or a few processes
- Gradually reduce fragmentation without large pause times
Advantages:
- No single large pause disrupts the system
- Can be tuned to system load patterns
- Continuous maintenance prevents crisis-level fragmentation
Disadvantages:
- Fragmentation never fully eliminated (always catching up)
- Complex state management across increments
- May interfere with process locality if not carefully designed
When to Use Each Strategy:
- •Complete Compaction — Use during low-activity periods (maintenance windows, boot time) or when fragmentation is severe and affecting system stability.
- •Partial Compaction — Use in response to specific failed allocations when complete compaction is too expensive.
- •Optimal Compaction — Use when pause time is critical and the number of processes is small enough for planning algorithms.
- •Incremental Compaction — Use for continuous maintenance in systems that cannot tolerate long pauses but can accept gradual improvement.
Implementation Challenges
Implementing memory compaction in a real operating system reveals numerous challenges that textbook descriptions often overlook. Each presents engineering trade-offs that system designers must navigate carefully.
Challenge 1: Overlapping Regions
When relocating a process to a position that overlaps with its current position, care must be taken to avoid corrupting memory during the copy. Consider process P currently at address 1000-2000 being moved to address 1500-2500:
Current: [----P----][free]
1000 2000 2500
Target: [----P----]
1500 2500
If we copy forward: Content at 1500-2000 is overwritten before it's copied!
Solution: Use memmove semantics—copy backward when destination overlaps and is higher than source. Alternatively, copy to a temporary buffer first (at the cost of extra memory and two copy operations).
When source and destination overlap, the copy direction determines correctness. If dest > source, copy from end to start. If dest < source, copy from start to end. Getting this wrong causes silent data corruption—one of the most dangerous bugs in systems programming.
Challenge 2: I/O in Progress
Devices performing DMA (Direct Memory Access) read from or write to specific physical memory addresses. If we compact memory while DMA is in progress, the device will access the wrong locations.
Scenarios:
- Disk reading data into a buffer that gets relocated
- Network card writing received packets to relocated memory
- GPU reading texture data from a moved buffer
Solutions:
- Pin Memory: Mark pages involved in active I/O as non-relocatable until I/O completes
- I/O Completion Waiting: Wait for all I/O to complete before compaction
- I/O Redirection: Update device DMA registers (if hardware supports it)
Best Practice: Maintain an 'I/O lock count' per memory region. Regions with non-zero lock counts cannot be moved until all locks are released.
12345678910111213141516171819202122232425262728293031323334
// I/O memory pinning for safe compactiontypedef struct MemoryRegion { void* base; size_t size; atomic_int io_lock_count; // Number of active I/O operations bool compaction_pending; // Compactor wants to move this} MemoryRegion; // Called before starting DMA operationbool pin_for_io(MemoryRegion* region) { // Increment lock count atomically int expected = atomic_load(®ion->io_lock_count); while (expected >= 0) { if (atomic_compare_exchange_weak(®ion->io_lock_count, &expected, expected + 1)) { return true; // Successfully pinned } } return false; // Region is being compacted, cannot pin} // Called when DMA operation completesvoid unpin_from_io(MemoryRegion* region) { int old = atomic_fetch_sub(®ion->io_lock_count, 1); if (old == 1 && region->compaction_pending) { // This was the last I/O hold; wake up compactor wake_compactor(); }} // Compactor checks if region can be movedbool can_relocate(MemoryRegion* region) { return atomic_load(®ion->io_lock_count) == 0;}Challenge 3: Process State Consistency
When a process is suspended for compaction, its state must be captured completely. This includes:
- Registers: All CPU registers are saved in the PCB
- Stack State: The entire execution stack must be relocated correctly
- Heap Pointers: Internal pointers within the process's memory remain valid (they're logical addresses)
- Open File Descriptors: These reference kernel structures, not affected by relocation
- Signal Handlers: These use logical addresses, remain valid after relocation
The Critical Invariant: After compaction, when the process resumes:
logical_address + NEW_base_register = correct_physical_location
Since only the base register changes, and all process references are logical addresses, correctness is maintained automatically.
Challenge 4: Multi-Core Synchronization
On multi-core systems, compaction requires careful coordination:
Problem: Different cores may be accessing memory being compacted. Even with processes suspended, kernel threads, interrupt handlers, and other cores may reference affected memory.
Solution Approaches:
-
Global Stop-the-World:
- Halt all cores except the one performing compaction
- Safe but expensive—entire system pauses
-
Per-Region Locking:
- Use read-write locks on memory regions
- Compactor acquires write locks; others use read locks
- More granular but complex
-
RCU-style (Read-Copy-Update):
- Copy to new location first
- Update references atomically
- Wait for all readers of old location to finish
- Reclaim old location
Modern Systems: Typically use a combination—regions are locked during copy, with minimal global synchronization for reference updates.
Most modern systems have moved away from pure compaction for contiguous allocation in favor of paging, which eliminates external fragmentation by design. However, compaction concepts remain relevant in specialized contexts: real-time systems with contiguous memory requirements, embedded systems without MMU support, and memory allocators within user-space applications (like malloc implementations and garbage collectors).
Determining When to Compact
Compaction is expensive. Performing it too frequently wastes CPU cycles; performing it too rarely leads to severe fragmentation and failed allocations. The decision of when to compact is a critical policy choice.
Trigger Strategies:
1. On-Demand Compaction
Compact only when an allocation request fails due to fragmentation.
if (allocation_fails(request)) {
if (total_free_memory >= request_size) {
// External fragmentation detected
perform_compaction();
retry_allocation(request);
} else {
// Genuine memory shortage
return OUT_OF_MEMORY;
}
}
Advantages:
- Compaction only happens when truly needed
- No wasted work during normal operation
Disadvantages:
- Allocation latency spike when compaction occurs
- May cause priority inversion if high-priority process triggers compaction
2. Threshold-Based Compaction
Compact when fragmentation metrics exceed thresholds.
Possible Thresholds:
- Fragmentation ratio > 0.5 (largest hole < 50% of total free)
- Number of holes > N
- Average hole size < minimum useful size
- Allocation failure rate > acceptable level
Implementation:
void periodic_fragmentation_check() {
FragmentationMetrics m = calculate_fragmentation();
if (m.ratio > FRAGMENTATION_THRESHOLD ||
m.largest_hole < MIN_USEFUL_HOLE_SIZE ||
m.failure_rate > MAX_ACCEPTABLE_FAILURES) {
schedule_compaction();
}
}
Advantages:
- Proactive—prevents allocation failures
- Can schedule compaction during low-activity periods
Disadvantages:
- Threshold tuning is workload-dependent
- May compact unnecessarily if workload changes
3. Periodic Compaction
Compact at fixed intervals regardless of fragmentation state.
Advantages:
- Simple to implement
- Predictable maintenance windows
Disadvantages:
- May compact when not needed (wasted work)
- Fixed intervals may not match workload patterns
- May miss urgent needs between intervals
4. Opportunistic Compaction
Compact during natural low-activity periods.
Triggers:
- CPU idle time exceeds threshold
- System in maintenance mode
- Low memory pressure detected
- User-initiated defragmentation request
Hybrid Approach (Recommended):
Combine multiple strategies for robust handling:
1234567891011121314151617181920212223242526272829303132333435363738
// Hybrid compaction policytypedef struct CompactionPolicy { float fragmentation_threshold; // Trigger if exceeded int max_holes; // Trigger if exceeded size_t min_largest_hole; // Trigger if below int idle_seconds_for_background; // Background compact after idle bool emergency_on_failure; // Immediate compact on alloc fail} CompactionPolicy; CompactionDecision evaluate_compaction_need(CompactionPolicy* policy) { FragmentationMetrics m = calculate_fragmentation(); SystemLoad load = get_system_load(); // Emergency: allocation failed due to fragmentation if (allocation_just_failed() && policy->emergency_on_failure) { return COMPACT_IMMEDIATELY; } // Threshold breach: schedule ASAP but not during peak load if (m.ratio > policy->fragmentation_threshold || m.hole_count > policy->max_holes || m.largest_hole < policy->min_largest_hole) { if (load.cpu_utilization < 0.3) { return COMPACT_NOW; } else { return COMPACT_WHEN_IDLE; } } // Opportunistic: compact during extended idle if (load.idle_seconds > policy->idle_seconds_for_background) { if (m.ratio > 0.2) { // Only if some fragmentation exists return COMPACT_BACKGROUND; } } return COMPACT_NOT_NEEDED;}In production systems, never perform compaction during peak hours unless absolutely necessary. Schedule maintenance for off-peak periods. Monitor fragmentation trends over time—if they're worsening, investigate the underlying allocation patterns rather than just compacting more frequently. Often, changing the allocation strategy or adjusting workload distribution is more effective than aggressive compaction.
Summary: Memory Compaction
Memory compaction represents the operating system's mechanism for reclaiming fragmented memory space. While conceptually straightforward—move allocated regions together to consolidate free space—the implementation involves significant engineering complexity.
- •External fragmentation occurs when total free memory exceeds a request but no single contiguous block can satisfy it—a paradox where memory exists but is unusable.
- •Compaction prerequisites include execution-time binding, relocation registers, and MMU support—without these, processes cannot be moved after loading.
- •Compaction strategies vary from complete (move everything) to optimal (minimize movement)—each trades simplicity for performance.
- •Implementation challenges include overlapping regions, I/O pinning, process state consistency, and multi-core synchronization—all require careful engineering.
- •Compaction triggers can be on-demand, threshold-based, periodic, or opportunistic—hybrid approaches provide the best balance.
- •Modern systems largely avoid compaction through paging, but compaction concepts remain essential for specialized systems and user-space allocators.
What's Next:
While compaction addresses fragmentation after it occurs, the next page examines the cost of compaction—the performance implications, pause times, and system overhead that make compaction a powerful but expensive tool. Understanding these costs is essential for making informed memory management decisions.
You now understand memory compaction at a deep level—from the mathematics of fragmentation through implementation challenges to policy decisions. This foundation prepares you to evaluate the true cost of compaction and make informed trade-offs in system design.
KEEP LEARNING
Keep learning for free.
Read the complete lesson, save your notes and pick up where you left off with a free account. No card needed.