Allocation Strategies - Learning Module

Loading content...

0/227

Dynamic Adjustment

Adaptation: The Final Layer

Static allocation strategies—whether equal, proportional, priority-based, or combinations thereof—share a fundamental limitation: they assume memory needs are known in advance. In reality, memory requirements change continuously.

A database query might spike memory usage temporarily. A compiler might need more memory during certain compilation phases. A web server's memory footprint fluctuates with request load. Dynamic adjustment addresses this reality by continuously monitoring process behavior and adapting allocations in response.

Dynamic adjustment transforms static policies into living systems that respond to actual conditions rather than predicted ones.

What You Will Learn

By the end of this page, you will understand: monitoring techniques for detecting allocation mismatches, adjustment algorithms that respond to runtime behavior, feedback control systems for stable adaptation, and real-world implementations in Linux and Windows. You'll be able to design and analyze dynamically-adjusting allocation systems.

Why Static Allocation Fails

Static allocation assumes predictable memory behavior. Real workloads violate this assumption constantly:

Phase Behavior: Programs go through distinct phases with different memory requirements. An initialization phase might need 50MB, processing phase 500MB, and cleanup 20MB.

Load Variation: Server applications scale memory with request load. Peak hours require more memory than idle periods.

Data Dependency: Memory needs depend on input data. Processing a small file vs. a large file yields dramatically different requirements.

Temporal Patterns: Database caches grow over time. Garbage collectors temporarily double memory usage. Long-running processes accumulate state.

Static vs. Dynamic Allocation Behavior
Scenario	Static Allocation	Dynamic Adjustment
Process enters memory-intensive phase	Thrashes within fixed allocation	Detects need, increases allocation
Process becomes memory-idle	Holds unused frames	Reclaims frames for other processes
New process joins system	Fixed redistribution	Gradual adaptation based on actual usage
Memory pressure increases	Fixed proportions maintained	Reduces allocations for low-activity processes

Monitoring Techniques

Dynamic adjustment requires continuous monitoring to detect when allocations should change. Key metrics include:

Page Fault Rate (PFR): The primary indicator of allocation inadequacy. High PFR suggests allocation is below working set.

Working Set Size (WSS): Estimated pages actively in use. Approximated via reference bit sampling.

Memory Pressure Indicators:

System-wide free page count
Swap activity rate
Average page fault latency

Process Activity:

CPU utilization (memory-bound vs. compute-bound)
I/O wait time
Active threads

monitoring.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
typedef struct {
    int pid;
    
    // Page fault metrics
    unsigned long page_faults;        // Total faults
    unsigned long major_faults;       // Disk I/O required
    unsigned long minor_faults;       // In-memory resolution
    double fault_rate;                // Faults per second
    
    // Working set estimation
    size_t resident_set;              // Current RSS
    size_t working_set_estimate;      // Estimated WSS
    size_t allocated_frames;          // Current allocation
    
    // Activity indicators
    double cpu_percent;               // CPU utilization
    double io_wait_percent;           // I/O wait time
    
    // Derived metrics
    double allocation_ratio;          // allocated / WSS
    bool is_thrashing;                // High fault rate indicator
} ProcessMonitor;
 
// Update monitoring data for a process
void update_monitor(ProcessMonitor* mon) {
    static unsigned long last_faults[MAX_PROCESSES];
    static time_t last_time[MAX_PROCESSES];
    
    // Calculate fault rate
    time_t now = time(NULL);
    unsigned long current_faults = get_process_faults(mon->pid);
    
    if (last_time[mon->pid] > 0) {
        double elapsed = difftime(now, last_time[mon->pid]);
        if (elapsed > 0) {
            mon->fault_rate = (current_faults - last_faults[mon->pid]) / elapsed;
        }
    }
    
    last_faults[mon->pid] = current_faults;
    last_time[mon->pid] = now;
    
    // Update working set estimate via reference bit sampling
    mon->working_set_estimate = estimate_working_set(mon->pid);
    mon->allocation_ratio = (double)mon->allocated_frames / 
                            mon->working_set_estimate;
    
    // Thrashing detection: high fault rate + low allocation ratio
    mon->is_thrashing = (mon->fault_rate > THRASH_THRESHOLD) &&
                        (mon->allocation_ratio < 1.0);
}
 
// Estimate working set using reference bit sampling
size_t estimate_working_set(int pid) {
    size_t referenced_pages = 0;
    PageTableEntry* pte = get_page_table(pid);
    size_t page_count = get_page_count(pid);
    
    for (size_t i = 0; i < page_count; i++) {
        if (pte[i].valid && pte[i].referenced) {
            referenced_pages++;
            pte[i].referenced = 0;  // Clear for next interval
        }
    }
    
    return referenced_pages;
}

Page Fault Frequency (PFF) Algorithm

The Page Fault Frequency (PFF) algorithm is the classic approach to dynamic adjustment. It uses page fault rate as the control signal for allocation changes.

Principle: Maintain page fault rate within an acceptable range by adjusting allocation.

If fault rate > upper threshold → process needs more frames
If fault rate < lower threshold → process may have excess frames
If fault rate within range → allocation is appropriate

Upper Threshold: Indicates insufficient allocation. Process is page faulting too frequently and cannot make efficient progress.

Lower Threshold: Indicates potential over-allocation. Process has more frames than it actively uses.

Converting Mermaid diagram...

pff_controller.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
from dataclasses import dataclass
from typing import List
import time
 
@dataclass
class PFFProcess:
    pid: int
    name: str
    allocated_frames: int
    min_frames: int
    max_frames: int
    
    # Monitoring state
    page_faults: int = 0
    last_faults: int = 0
    fault_rate: float = 0.0
 
class PFFController:
    """Page Fault Frequency dynamic adjustment controller."""
    
    def __init__(self, upper_threshold: float, lower_threshold: float):
        self.upper = upper_threshold  # Faults/sec above which to add frames
        self.lower = lower_threshold  # Faults/sec below which to reclaim
        self.processes: List[PFFProcess] = []
        self.free_pool: int = 0
        self.interval: float = 1.0    # Seconds between adjustments
    
    def update_fault_rates(self):
        """Calculate current fault rates for all processes."""
        for p in self.processes:
            current = get_page_fault_count(p.pid)
            p.fault_rate = (current - p.last_faults) / self.interval
            p.last_faults = current
    
    def adjust_allocations(self):
        """Perform PFF-based allocation adjustment."""
        
        # Processes needing more frames
        starving = [p for p in self.processes 
                   if p.fault_rate > self.upper and 
                      p.allocated_frames < p.max_frames]
        
        # Processes with excess frames
        excess = [p for p in self.processes
                 if p.fault_rate < self.lower and
                    p.allocated_frames > p.min_frames]
        
        # First: reclaim from excess processes
        for p in excess:
            reclaimable = min(
                p.allocated_frames - p.min_frames,
                int(p.allocated_frames * 0.1)  # Max 10% per interval
            )
            p.allocated_frames -= reclaimable
            self.free_pool += reclaimable
        
        # Second: allocate to starving processes
        if starving and self.free_pool > 0:
            per_process = max(1, self.free_pool // len(starving))
            for p in starving:
                grant = min(per_process, p.max_frames - p.allocated_frames)
                if grant > 0 and self.free_pool >= grant:
                    p.allocated_frames += grant
                    self.free_pool -= grant
    
    def run_control_loop(self):
        """Main PFF control loop."""
        while True:
            time.sleep(self.interval)
            self.update_fault_rates()
            self.adjust_allocations()
            self.log_status()

PFF Limitations

PFF has known limitations:

• Reactive, not predictive: Only responds after problems occur • Threshold selection: Wrong thresholds cause oscillation or sluggish response • Phase change lag: Takes time to detect and respond to sudden changes • No global optimization: Each process adjusted independently

Working Set-Based Adjustment

An alternative to PFF is direct working set tracking. Rather than reacting to fault rates, track which pages are actually in use and adjust allocation to match.

Working Set Model:

The working set W(t, Δ) at time t with window Δ is the set of pages referenced in the interval [t-Δ, t].

Adjustment Policy:

Target allocation = |W(t, Δ)| + buffer
If allocated < target → grant more frames
If allocated > target → reclaim excess

Advantages over PFF:

Proactive: adjusts to working set, not fault rate
More stable: working set changes more smoothly than fault rate
Better global view: can sum working sets across processes

wss_adjustment.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#define WSS_WINDOW_INTERVALS 10  // Working set window
#define WSS_BUFFER_PERCENT 20     // Extra allocation buffer
 
typedef struct {
    int pid;
    size_t allocated;
    size_t wss_estimate;
    size_t target_allocation;
    
    // Reference bit history for WSS estimation
    unsigned char* ref_bits[WSS_WINDOW_INTERVALS];
    int current_interval;
} WSSProcess;
 
// Update working set estimate using sliding window
void update_wss(WSSProcess* proc) {
    size_t page_count = get_virtual_page_count(proc->pid);
    
    // Capture current reference bits
    capture_reference_bits(proc->pid, 
        proc->ref_bits[proc->current_interval], page_count);
    
    // Advance interval
    proc->current_interval = 
        (proc->current_interval + 1) % WSS_WINDOW_INTERVALS;
    
    // Estimate WSS: pages referenced in any interval
    proc->wss_estimate = 0;
    for (size_t page = 0; page < page_count; page++) {
        bool referenced = false;
        for (int i = 0; i < WSS_WINDOW_INTERVALS; i++) {
            if (proc->ref_bits[i][page]) {
                referenced = true;
                break;
            }
        }
        if (referenced) proc->wss_estimate++;
    }
    
    // Calculate target with buffer
    proc->target_allocation = proc->wss_estimate + 
        (proc->wss_estimate * WSS_BUFFER_PERCENT / 100);
}
 
// Adjust allocation toward target
void adjust_to_wss(WSSProcess* proc, size_t* free_pool) {
    if (proc->allocated < proc->target_allocation) {
        // Need more frames
        size_t need = proc->target_allocation - proc->allocated;
        size_t grant = (need < *free_pool) ? need : *free_pool;
        proc->allocated += grant;
        *free_pool -= grant;
        
    } else if (proc->allocated > proc->target_allocation) {
        // Have excess frames
        size_t excess = proc->allocated - proc->target_allocation;
        size_t reclaim = excess / 2;  // Gradual reclamation
        proc->allocated -= reclaim;
        *free_pool += reclaim;
    }
}

Feedback Control Systems

Both PFF and WSS-based adjustment are forms of feedback control—systems that measure output, compare to a target, and adjust inputs to minimize error. Understanding control theory principles leads to more stable, responsive allocation systems.

Control System Components:

Set Point: Desired behavior (target fault rate or allocation ratio)
Sensor: Monitoring subsystem (fault counters, reference bits)
Error Signal: Difference between measured and desired
Controller: Algorithm that determines adjustment
Actuator: Frame allocation/deallocation mechanism
Plant: The process receiving frames

PID Control for Memory Allocation:

A PID (Proportional-Integral-Derivative) controller provides sophisticated control:

Proportional: Adjustment proportional to current error

Large error → large adjustment
Risk: may not reach target exactly (steady-state error)

Integral: Adjustment based on accumulated error

Eliminates steady-state error
Risk: can cause overshoot

Derivative: Adjustment based on error rate of change

Dampens oscillation
Risk: sensitive to noise

pid_memory_controller.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class PIDMemoryController:
    """PID controller for dynamic frame allocation."""
    
    def __init__(self, kp: float, ki: float, kd: float, 
                 target_fault_rate: float):
        self.kp = kp  # Proportional gain
        self.ki = ki  # Integral gain
        self.kd = kd  # Derivative gain
        self.target = target_fault_rate
        
        # State
        self.integral = 0.0
        self.last_error = 0.0
        
    def compute_adjustment(self, current_fault_rate: float, 
                          dt: float) -> int:
        """
        Compute frame adjustment based on fault rate error.
        
        Returns: Number of frames to add (positive) or 
                 remove (negative)
        """
        # Error: difference from target fault rate
        error = self.target - current_fault_rate
        # Note: negative error means too many faults (need more frames)
        
        # Proportional term
        p_term = self.kp * error
        
        # Integral term (with anti-windup)
        self.integral += error * dt
        self.integral = max(-100, min(100, self.integral))
        i_term = self.ki * self.integral
        
        # Derivative term
        derivative = (error - self.last_error) / dt if dt > 0 else 0
        d_term = self.kd * derivative
        self.last_error = error
        
        # Combined output
        output = p_term + i_term + d_term
        
        # Convert to frame count (negative output = add frames)
        return int(-output * 10)  # Scale factor
    
    def reset(self):
        """Reset controller state."""
        self.integral = 0.0
        self.last_error = 0.0

Tuning Control Parameters

Control parameter tuning is critical:

• Too aggressive (high gains): Oscillation, instability • Too conservative (low gains): Slow response, thrashing persists • Balanced: Quick response without overshoot

Start with proportional-only control, add integral to eliminate steady-state error, then add derivative if oscillation occurs.

Real-World Implementations

Linux: kswapd and Direct Reclaim

Linux uses multiple mechanisms for dynamic adjustment:

kswapd: Background daemon that reclaims pages when free memory drops below watermarks
Direct Reclaim: Synchronous reclamation when allocation fails
Memory cgroups: memory.low and memory.high provide gradual pressure response
PSI (Pressure Stall Information): Exposes memory pressure metrics to userspace

Windows: Working Set Manager

Windows actively manages per-process working sets:

Each process has minimum and maximum working set bounds
Working Set Manager periodically trims processes exceeding their maximum
Under pressure, aggressively trims to maintain system responsiveness
Balance Set Manager coordinates across all processes

linux_pressure_monitoring.sh
Bash
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#!/bin/bash
# Linux Pressure Stall Information (PSI) monitoring
 
# Read memory pressure metrics
echo "Memory Pressure Metrics:"
cat /proc/pressure/memory
 
# Output format:
# some avg10=0.00 avg60=0.00 avg300=0.00 total=0
# full avg10=0.00 avg60=0.00 avg300=0.00 total=0
 
# "some": Time at least one task stalled on memory
# "full": Time all tasks stalled on memory
# avg10/60/300: 10-second, 60-second, 5-minute averages
 
# Use PSI for dynamic adjustment trigger
THRESHOLD=25.0  # 25% stalled time
 
CURRENT=$(cat /proc/pressure/memory | grep "^some" |           awk '{print $2}' | cut -d= -f2)
 
if (( $(echo "$CURRENT > $THRESHOLD" | bc -l) )); then
    echo "Memory pressure detected: ${CURRENT}%"
    echo "Triggering allocation adjustment..."
fi

Dynamic Adjustment Mechanisms by OS
OS	Mechanism	Trigger	Response
Linux	kswapd	Free pages < low watermark	Background page reclaim
Linux	Direct reclaim	Allocation failure	Synchronous reclaim
Linux	OOM killer	No reclaimable memory	Process termination
Windows	Working Set Trim	Periodic or pressure	Per-process page-out
Windows	Memory Manager	Continuous	Dynamic balance adjustment

Challenges and Best Practices

Common Challenges

•Oscillation: Aggressive adjustment causes allocation to swing repeatedly between too-high and too-low
•Delayed Response: Conservative adjustment lets thrashing persist too long before correcting
•Global Coordination: Individual process adjustments may conflict system-wide
•Measurement Overhead: Continuous monitoring consumes CPU and memory resources
•Phase Transition: Sudden workload changes cause temporary performance degradation

Best Practices

•Use hysteresis: Different thresholds for increasing vs. decreasing allocation prevents oscillation
•Gradual adjustment: Change allocation incrementally rather than in large jumps
•Combined signals: Use multiple metrics (fault rate + WSS + pressure) for robust decisions
•Rate limiting: Limit how frequently allocations can change
•Global awareness: Consider system-wide state when adjusting individual processes
•Fallback modes: Have simple static behavior for when dynamic adjustment fails

Summary and Key Takeaways

Core Concepts Mastered

•Static allocation limitations: Memory needs change continuously; static policies cannot adapt
•Monitoring techniques: Page fault rate, working set estimation, and pressure indicators provide adjustment signals
•PFF Algorithm: Adjusts allocation based on page fault rate thresholds—reactive but simple
•Working Set Adjustment: Directly tracks active pages for proactive allocation matching
•Feedback Control: PID controllers provide stable, responsive adjustment with proper tuning
•Real implementations: Linux kswapd/PSI and Windows Working Set Manager implement dynamic adjustment
•Best practices: Hysteresis, gradual changes, multiple signals, and global awareness prevent instability

Module Complete

You have now mastered the complete spectrum of frame allocation strategies:

Equal Allocation — Simple fairness baseline
Proportional Allocation — Size-aware distribution
Priority-Based Allocation — Importance-aware allocation
Combination Approaches — Hybrid policies for production systems
Dynamic Adjustment — Runtime adaptation to changing conditions

These strategies form the foundation of memory management in all modern operating systems. Understanding them enables you to analyze, design, and optimize memory allocation policies for any computing environment.

Module Complete

You now possess comprehensive knowledge of frame allocation strategies—from simple equal allocation to sophisticated dynamic adjustment. You can analyze real-world allocation policies, design appropriate strategies for specific workloads, and understand how modern operating systems manage memory across competing processes.