Compaction and Buddy System

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.

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.

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.

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.

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:

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.

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:

1. Identify the allocation request that triggered compaction
2. Find neighboring free holes that, if merged, would satisfy the request
3. 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 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:

1. Maintain a 'compaction debt' metric indicating fragmentation severity
2. During CPU idle time or low-activity periods, move one or a few processes
3. 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:

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).

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.

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:

1. Global Stop-the-World:

   • Halt all cores except the one performing compaction
   • Safe but expensive—entire system pauses

2. Per-Region Locking:

   • Use read-write locks on memory regions
   • Compactor acquires write locks; others use read locks
   • More granular but complex

3. 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.

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:

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.

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.