Compaction and Buddy System

Memory compaction eliminates external fragmentation, but this benefit comes at a substantial cost. Every byte moved during compaction represents CPU cycles spent, memory bandwidth consumed, and cache lines invalidated. Every process suspended for relocation represents application latency that users experience.

Understanding compaction cost is not merely an academic exercise—it's essential knowledge for system designers who must weigh the benefits of consolidated memory against the real performance penalties incurred. This page provides a rigorous analysis of compaction costs, enabling you to make informed trade-offs in memory management design.

The fundamental cost of compaction is time—the duration during which memory operations consume system resources and affected processes cannot execute. Let's build a precise model of compaction time.

The Basic Model:

For a single memory region of size S bytes being moved:

T_move = S / bandwidth_effective

Where bandwidth_effective is the actual memory copy throughput, which depends on:

• Memory bus speed
• Cache behavior
• Memory access patterns
• CPU overhead for managing the copy

Realistic Memory Bandwidth:

Modern systems have theoretical memory bandwidths measured in GB/s, but effective copy throughput is significantly lower:

Why Effective Rate is Lower:

1. Read-Modify-Write Cycles: Memory copy involves reading from source AND writing to destination—double the bus traffic

2. Cache Pollution: Large copies may evict useful data from CPU caches, causing secondary slowdowns afterward

3. Memory Controller Overhead: Arbitration, refreshing, and command processing consume bandwidth

4. Non-Sequential Access: If source/destination aren't well-aligned, access patterns become suboptimal

The Complete Time Formula:

For compacting N processes with sizes S₁, S₂, ..., Sₙ:

T_total = T_suspend + T_plan + T_copy + T_update + T_resume

Where:
  T_suspend = Σ(suspension_overhead_per_process) ≈ N × t_suspend
  T_plan    = O(N log N) for optimal planning, O(N) for greedy
  T_copy    = Σ(Sᵢ) / bandwidth_effective  [the dominant term]
  T_update  = O(N) for PCB updates + O(structures) for kernel updates
  T_resume  = Σ(resumption_overhead_per_process) ≈ N × t_resume

Concrete Examples:

Example 1: Small System

• Total memory to move: 100 MB
• Effective copy rate: 5 GB/s
• Number of processes: 10

T_copy = 100 MB / 5 GB/s = 100 MB / 5000 MB/s = 20 ms
T_other ≈ 10 × 0.1 ms (suspend) + 10 × 0.1 ms (resume) = 2 ms
T_total ≈ 22 ms

Example 2: Large Server

• Total memory to move: 10 GB
• Effective copy rate: 30 GB/s
• Number of processes: 500

T_copy = 10 GB / 30 GB/s = 333 ms
T_other ≈ 500 × 0.1 ms + 500 × 0.1 ms = 100 ms
T_total ≈ 433 ms (nearly half a second!)

Example 3: Real-Time Embedded

• Total memory to move: 10 MB
• Effective copy rate: 3 GB/s
• Number of processes: 20

T_copy = 10 MB / 3 GB/s = 3.3 ms
T_other ≈ 20 × 0.05 ms + 20 × 0.05 ms = 2 ms
T_total ≈ 5.3 ms

For a real-time system with deadlines, even 5ms can be problematic.

Beyond raw time, compaction consumes specific system resources. Understanding these costs enables better resource planning and trade-off analysis.

CPU Cycles:

The memcpy or memmove operation is CPU-intensive even when memory-bound:

• Loop Overhead: Increment counters, check conditions
• Address Calculation: Compute source and destination addresses
• Instruction Execution: Load/store instructions for each word
• Prefetching Logic: CPU attempts to predict and prefetch upcoming data

Modern CPUs can copy ~4-8 bytes per cycle:

For a 3 GHz CPU copying 1 GB:
  Cycles needed ≈ 1 GB / 8 bytes × some_constant
                ≈ 125 million cycles × 2 (read+write)
                ≈ 250 million cycles minimum
  Time = 250M / 3GHz ≈ 83 ms (compute-bound estimate)

Actual is memory-bound, so ~50 ms at 20 GB/s

Memory Bandwidth Consumption:

Compaction is a memory bandwidth hog. During compaction:

1. Source Data Read: Every byte of process memory is read
2. Destination Data Write: Every byte is written to the new location
3. Bus Saturation: Memory bus may become the bottleneck

Impact on Other Operations:

During compaction, other memory-intensive operations slow dramatically:

• Other processes' cache misses take longer to service
• I/O DMA operations may stall
• Graphics operations may stutter

Memory Bandwidth Math:

Compaction bandwidth = 2 × bytes_moved / time
                      (factor of 2 for read + write)

If moving 1 GB in 50 ms:
  Bandwidth used = 2 × 1 GB / 0.05 s = 40 GB/s

On a system with 50 GB/s total bandwidth:
  80% of bandwidth consumed by compaction!

Cache Impact:

Compaction devastates CPU caches:

L1 Cache (typically 32-64 KB per core):

• Entirely replaced by compaction data within microseconds
• Hot data from running processes evicted
• Cache warm-up required after compaction

L2 Cache (typically 256 KB - 1 MB per core):

• Also flushed during large compactions
• Shared victim cache behaviors may be affected

L3 Cache (typically 8-32 MB shared):

• For compactions < L3 size, some data may survive
• For larger compactions, L3 is also polluted

Post-Compaction Cache Warming Penalty:

After compaction, resumed processes face cold caches:

Post-compaction penalty per process:
  = (working_set_size / cache_line_size) × cache_miss_penalty

For a process with 1 MB working set, 64-byte cache lines, 100ns miss penalty:
  = (1 MB / 64 B) × 100 ns = 16,384 × 100 ns = 1.64 ms

This penalty is per process and adds to the visible latency users experience.

The direct costs of compaction—time and bandwidth—are measurable. Indirect costs are more subtle but equally impactful on system behavior.

Cost 1: Process Suspension Latency

Processes suspended for compaction cannot do useful work. This creates visible latency:

User-Facing Impact:

• Interactive applications freeze momentarily
• Real-time systems miss deadlines
• Network services drop connections on timeout

Background Process Impact:

• Batch jobs take longer overall
• Periodic tasks may miss their windows
• Watchdog timers may trigger false alarms

Cost 2: Priority Inversion

When compaction is triggered by a low-priority process's allocation failure, high-priority processes may be suspended to compact memory—classic priority inversion.

Scenario:

1. Low-priority batch job allocates memory
2. Allocation fails due to fragmentation
3. Compaction begins, suspending all processes
4. High-priority real-time task is frozen
5. High-priority task misses deadline

Mitigation Strategies:

• Exclude critical processes from compaction
• Use priority inheritance: compaction inherits priority of highest-blocked process
• Defer compaction for low-priority triggers until no high-priority processes are active

Cost 3: TLB and Virtual Memory Effects

In systems using paging on top of contiguous allocation, or in hybrid schemes, compaction may invalidate Translation Lookaside Buffer (TLB) entries:

TLB Shootdown Cost:

TLB shootdown (inter-processor interrupt) cost:
  = IPI_latency + TLB_flush_time + synchronization
  ≈ 1-10 microseconds per shootdown

For compaction affecting multiple processes on multiple cores:
  Total TLB cost = num_cores × num_affected_entries × per_entry_cost
                 = 8 cores × 100 entries × 2 μs = 1.6 ms

Post-Shootdown Penalty: After TLB invalidation, every memory access incurs TLB miss penalties until the TLB is repopulated:

TLB miss penalty: 10-100 cycles
Memory accesses to re-warm TLB: ~1000 per process
Total TLB rewarming: 1000 × 50 cycles / 3 GHz = 17 μs per process

Cost 4: I/O Pipeline Disruption

I/O operations in progress may be affected even if their memory is pinned:

DMA Channel Effects:

• DMA controllers may be delayed waiting for memory bus
• Completion callbacks are delayed as their process is suspended
• I/O scheduling may become suboptimal

Disk I/O Impact:

During compaction:
  - Read requests complete but callbacks wait
  - Write requests may have data in volatile state
  - Disk queue servicing is delayed

Post-compaction:
  - Burst of I/O completions
  - Potential I/O scheduler confusion
  - Temporary throughput spike then normalization

Network I/O Impact:

• TCP connections may timeout if compaction exceeds TCP timeout
• Packets may be dropped if network buffers aren't being drained
• Retransmissions increase network load after compaction

The decision to compact should be based on a quantitative comparison of costs versus benefits. Let's build a framework for this analysis.

Benefit of Compaction:

The primary benefit is enabling allocations that would otherwise fail:

Benefit = Value_of_allocations_enabled + Avoidance_of_OOM_consequences

Where:
  Value_of_allocations_enabled:
    = Sum of (allocation_size × value_per_byte × duration_needed)
    
  Avoidance_of_OOM_consequences:
    = Probability(OOM_without_compaction) × Cost_of_OOM
    = P(OOM) × (process_termination_cost + data_loss_cost + user_experience_cost)

Cost of Compaction:

Cost = Direct_cost + Indirect_cost + Opportunity_cost

Where:
  Direct_cost:
    = CPU_cycles × cost_per_cycle + Memory_bandwidth × cost_per_byte
    
  Indirect_cost:
    = Process_suspension_time × impact_per_unit_time
    + Cache_warming_cost + TLB_shootdown_cost + I/O_disruption_cost
    
  Opportunity_cost:
    = Work_not_done_during_compaction

Decision Framework:

if (Expected_Benefit > Expected_Cost) {
    perform_compaction();
} else {
    defer_compaction() or use_alternative();
}

Practical Heuristics:

Since exact benefit/cost calculations are often impractical in real-time, systems use heuristics:

Heuristic 1: Proportional Response

Compaction aggressiveness ∝ (Fragmentation_severity / Current_system_load)

High fragmentation + Low load → Compact now
High fragmentation + High load → Compact partially or defer
Low fragmentation + Any load → Don't compact

Heuristic 2: Request-Driven Bounds

max_acceptable_cost = k × request_size

Where k is a tunable constant (e.g., 0.1 = compact only if moving ≤ 10% of request size)

Only compact if:
  Total_bytes_to_move < max_acceptable_cost

Given compaction's substantial costs, systems employ various strategies to minimize the impact while still achieving fragmentation reduction.

Strategy 1: Move Minimum Necessary

Instead of complete compaction, move only the minimum bytes needed to satisfy the pending request:

Algorithm: Minimal Movement Compaction
1. Identify pending request size R
2. Find the two largest adjacent holes H1 and H2 separated by process P
3. If |H1| + |H2| + overhead > R:
   - Move process P to merge H1 and H2
   - Merged hole size: |H1| + |P| + |H2| - |P| = |H1| + |H2|
4. Repeat until request can be satisfied

This approach may move only a fraction of total memory compared to full compaction.

Strategy 2: Reduce Compaction Frequency

Prevent fragmentation from occurring in the first place:

Better Allocation Strategies:

• Use allocation strategies that minimize fragmentation (best-fit for long-lived allocations)
• Implement memory pools for common allocation sizes
• Group allocations by expected lifetime

Memory Hints:

// Application provides hints about allocation lifetime
void* os_alloc(size_t size, AllocationHint hint) {
    switch (hint) {
        case HINT_SHORT_LIVED:
            return allocate_from_short_pool(size);
        case HINT_LONG_LIVED:
            return allocate_from_stable_region(size);
        case HINT_HUGE:
            return allocate_contiguous_region(size);
    }
}

By segregating allocations by lifetime, short-lived allocation churn doesn't fragment regions used by long-lived allocations.

Strategy 3: Use Hardware Acceleration

Some systems leverage hardware to accelerate memory copies:

DMA Engine for Memory-to-Memory Copy:

Modern chipsets include DMA engines capable of:
- Memory-to-memory copy without CPU involvement
- Scatter-gather operations
- Copy with transformation (encryption, compression)

CPU can initiate copy and continue other work:
  initiate_dma_copy(source, dest, size, callback);
  // CPU does other work while DMA engine copies
  // Callback invoked on completion

Benefits:

• CPU cycles freed for other work during copy
• Potentially higher throughput than CPU copy
• Better cache behavior (CPU caches not polluted)

Limitations:

• Programming complexity
• DMA setup overhead makes it inefficient for small copies
• Not all systems have capable DMA engines

Strategy 4: Amortize Cost Over Time

Continuous Background Compaction:

Algorithm: Background Compaction Daemon

while (system_running) {
    wait_for_idle_period(threshold_ms);
    
    if (fragmentation_metric() > LOW_THRESHOLD) {
        // Find one small, easily movable process
        Process* p = find_smallest_movable_process();
        
        if (p != NULL) {
            // Move incrementally
            suspend_briefly(p);
            relocate_small_chunk(p);
            resume(p);
            
            // Allow other work before next iteration
            yield_for_ms(BACKOFF_TIME);
        }
    }
    
    sleep_until_fragmentation_check();
}

Advantages:

• No single large pause
• Compaction happens during otherwise wasted cycles
• System remains responsive

Disadvantages:

• Fragmentation is never fully eliminated
• Complex state management
• May interfere with energy-saving modes

Memory compaction is a powerful tool for eliminating external fragmentation, but it comes with substantial costs that must be carefully weighed against benefits. Understanding these costs enables informed decision-making about when and how to apply compaction.

What's Next:

Having examined the costs of compaction, we now turn to an alternative approach: the Buddy System Algorithm. Rather than consolidating fragmented memory after the fact, the buddy system uses a clever allocation scheme that makes merging free regions trivial—trading some internal fragmentation for dramatically simpler and faster free-space management.