Operating SystemsWorking Set and Page Fault Frequency

Working Set Model and Page Fault Frequency

LevelAdvanced

Duration90 mins

TopicWorking Set and Page Fault Frequency

3 / 5

Page Fault Frequency (PFF)

A Simpler Path to Dynamic Allocation

The working set model, while theoretically elegant, demands precise tracking of which pages each process has accessed within a sliding window. This tracking is expensive and complex. But what if we could achieve the same goal—preventing thrashing while maximizing utilization—without tracking working sets at all?

The Page Fault Frequency (PFF) approach offers exactly this. Instead of trying to determine what a process needs, PFF observes how the process is performing. The key insight is beautifully simple:

If a process is page faulting too frequently, it needs more frames. If it's page faulting rarely, it can afford to give up some frames.

This behavioral approach sidesteps the complexity of working set tracking while achieving comparable or better results. The process itself, through its fault behavior, tells us whether it has enough memory.

What You Will Learn

By the end of this page, you will understand: (1) The fundamental insight behind PFF, (2) How to measure and interpret page fault frequency, (3) Upper and lower thresholds for allocation control, (4) The PFF algorithm in detail, (5) Advantages of PFF over working set tracking, and (6) When PFF fails and how to handle edge cases.

The Core Insight Behind PFF

Consider two processes, each with an unknown working set:

Process A: 50 page faults per second Process B: 2 page faults per second

What can we infer?

Process A is suffering. It frequently needs pages that aren't in memory. Its current frame allocation is inadequate for its actual memory needs.
Process B is comfortable. It rarely encounters missing pages. Its allocation meets or exceeds its working set.

This inference doesn't require knowing the working set size, the window parameter, or which specific pages each process needs. The fault rate itself encodes the information we need for allocation decisions.

The Fundamental Relationship:

Page fault rate is inversely related to frame allocation (given a constant access pattern):

Frames vs. WSS	Fault Rate	Process State
Frames << WSS	Very High	Thrashing
Frames < WSS	High	Struggling
Frames ≈ WSS	Moderate-Low	Operating point
Frames > WSS	Very Low	Excess capacity
Frames >> WSS	Near Zero	Memory waste

The Self-Regulating System

PFF creates a feedback loop: high faults → more frames → lower faults → stable. Low faults → fewer frames → possibly more faults → stable. The system naturally seeks an equilibrium where each process has approximately its working set.

Why This Works:

The PFF approach works because of locality of reference:

With insufficient frames: The process's working set doesn't fit. Each access to a working set page not currently resident causes a fault. Since access rates to working set pages are high (by definition of working set), fault rates are high.
With sufficient frames: The working set fits in allocated frames. Faults only occur when:
- The process transitions to a new phase (cold start)
- The process accesses pages outside current locality (rare) Both are infrequent, so fault rates are low.
With excess frames: Additional frames beyond the working set don't reduce fault rate further—you can't have negative faults. The fault rate asymptotically approaches the irreducible rate determined by phase transitions and outlier accesses.

The Operating Point:

The goal is to operate near the "knee" of the fault rate curve—where adding frames would significantly reduce faults if we're above the knee, but removing frames barely increases faults if we're below it. PFF approximates this optimal point through threshold-based control.

Measuring Page Fault Frequency

Accurately measuring page fault frequency requires careful definition and implementation.

Definition:

Page Fault Frequency (PFF) = Number of page faults / Time period

Or equivalently:

Inter-Fault Time (IFT) = Time between consecutive page faults

PFF = 1 / average(IFT)

Measurement Approaches:

PFF Measurement Strategies
Approach	Mechanism	Pros	Cons
Windowed Counter	Count faults in fixed time window	Simple, direct	Window size selection
Exponential Average	Weighted average of recent rates	Smooth, adaptive	More complex, lag
Inter-Fault Time	Measure time between each fault	Immediate signal	Noisy, needs filtering
Token Bucket	Fault decrements tokens; time adds them	Rate limiting metaphor	Parameter tuning

Windowed Counter Approach:

The simplest approach maintains a counter that's reset periodically:

On each timer tick (every T seconds):
   current_pff = fault_count / T
   fault_count = 0  // Reset for next window

Advantages:

Very simple to implement
Direct, interpretable value
Natural fit with existing timer interrupts

Disadvantages:

Quantization: faults near window boundaries may be counted in wrong window
Needs window size selection (similar to working set window problem)
No memory of past behavior

Exponential Moving Average:

A more sophisticated approach uses exponential smoothing:

On each page fault:
   current_time = now()
   interval = current_time - last_fault_time
   instantaneous_rate = 1 / interval
   smoothed_pff = α × instantaneous_rate + (1-α) × smoothed_pff
   last_fault_time = current_time

Here α (0 < α < 1) controls responsiveness:

High α (e.g., 0.8): responsive to recent behavior
Low α (e.g., 0.2): stable, slow-changing estimate

Advantages:

Smooth estimate, less noise
Infinite memory (weighted) of past behavior
Updates on each fault (event-driven, not timer-driven)

Disadvantages:

More complex
α parameter requires tuning
If faults stop completely, estimate doesn't decay to zero

pff_measurement.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
// PFF measurement implementation using exponential moving average
 
typedef struct {
    double smoothed_pff;        // Smoothed page fault frequency (faults/sec)
    uint64_t last_fault_time;   // Timestamp of most recent fault (microseconds)
    uint64_t fault_count;       // Total faults (for statistics)
    double alpha;               // Smoothing factor (0 to 1)
} ProcessPFF;
 
#define ALPHA_DEFAULT 0.25      // Balance between responsiveness and stability
 
void init_pff_tracking(ProcessPFF* pff) {
    pff->smoothed_pff = 0.0;
    pff->last_fault_time = 0;
    pff->fault_count = 0;
    pff->alpha = ALPHA_DEFAULT;
}
 
// Called by page fault handler
void record_page_fault(ProcessPFF* pff) {
    uint64_t current_time = get_microseconds();  // Current time in μs
    pff->fault_count++;
    
    if (pff->last_fault_time == 0) {
        // First fault - initialize
        pff->last_fault_time = current_time;
        return;
    }
    
    // Calculate inter-fault interval in seconds
    double interval_sec = (current_time - pff->last_fault_time) / 1000000.0;
    
    if (interval_sec > 0) {
        // Instantaneous fault rate = 1 / interval
        double instantaneous_rate = 1.0 / interval_sec;
        
        // Exponential moving average
        pff->smoothed_pff = pff->alpha * instantaneous_rate + 
                            (1.0 - pff->alpha) * pff->smoothed_pff;
    }
    
    pff->last_fault_time = current_time;
}
 
// Handle time passing without faults (decay estimate)
void pff_decay(ProcessPFF* pff, uint64_t current_time) {
    if (pff->last_fault_time == 0) return;
    
    double time_since_fault = (current_time - pff->last_fault_time) / 1000000.0;
    
    // If long time without faults, decay the estimate
    // Decay as if a hypothetical fault just occurred at low rate
    if (time_since_fault > 1.0) {  // More than 1 second
        double hypothetical_rate = 1.0 / time_since_fault;
        pff->smoothed_pff = pff->alpha * hypothetical_rate + 
                            (1.0 - pff->alpha) * pff->smoothed_pff;
    }
}

Virtual Time vs. Real Time

Like the working set model, PFF measurement can use virtual time (counting only while process is running) or real time. Virtual time is more accurate—a blocked process isn't faulting because it's waiting for I/O, not because it has sufficient frames. Most implementations pause PFF tracking when a process isn't scheduled.

The Dual Threshold Model

PFF-based allocation uses two thresholds to control frame allocation: an upper threshold for increasing allocation and a lower threshold for decreasing it.

The Basic Idea:

If PFF > upper_threshold:
    Process is faulting too much → Give it more frames
Else if PFF < lower_threshold:
    Process is faulting rarely → Take some frames away
Else:
    Process is in acceptable range → No change

Why Two Thresholds?

A single threshold would cause oscillation:

PFF slightly above threshold → add frame
PFF drops slightly below threshold → remove frame
PFF rises slightly above threshold → add frame
Continuous oscillation, wasted overhead

Two thresholds create a hysteresis band—a range where no action is taken. This provides stability:

PFF above upper → add frame
PFF drops into band → no action (stable)
PFF would need to drop below lower to trigger frame removal
The band prevents oscillation from noise

Single Threshold (Oscillation)

•One threshold at PFF = T
•PFF > T → add frame
•PFF < T → remove frame
•Small fluctuations cross threshold
•Continuous add/remove oscillation
•High overhead, unstable allocation

Dual Threshold (Stable)

•Lower threshold L, upper threshold U
•PFF > U → add frame
•PFF < L → remove frame
•L < PFF < U → no change
•Dead band absorbs fluctuations
•Stable allocation, low overhead

Choosing Threshold Values:

Threshold selection depends on several factors:

Factor	Upper Threshold	Lower Threshold
Typical value	10-50 faults/sec	1-5 faults/sec
System goal	Prevent thrashing	Reclaim excess memory
Crossing means	Process is suffering	Process has slack
Response	Immediately add 1+ frames	Gradually remove frames
Urgency	High (pain is real)	Low (no immediate harm)

Practical Considerations:

Upper threshold must be meaningful: Too high means processes thrash before getting help. Too low means frames are given too liberally.
Lower threshold should be conservative: A process with low PFF might be in a quiet phase—removing frames could cause problems when activity resumes.
The gap matters: A wide gap (e.g., 5-50 faults/sec) provides more stability but slower response. A narrow gap (e.g., 8-15 faults/sec) responds quickly but may oscillate.

Adaptive Thresholds

Advanced implementations adjust thresholds dynamically based on system load. When memory pressure is high, both thresholds might be raised (tolerating higher fault rates to accommodate more processes). When memory is abundant, thresholds can be lowered (giving processes more frames for better performance).

The PFF Algorithm in Detail

Let's examine the complete PFF algorithm for dynamic frame allocation, including edge cases and practical considerations.

pff_algorithm.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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
// Complete PFF-based dynamic frame allocation
 
typedef struct {
    // PFF tracking
    double current_pff;         // Current page fault frequency
    uint64_t last_check_time;   // Last allocation decision time
    
    // Allocation state
    int allocated_frames;       // Current frame count
    int min_frames;            // Minimum frames (architectural)
    int max_frames;            // Maximum frames (policy)
    
    // Thresholds (faults per second)
    double upper_threshold;     // Add frames above this
    double lower_threshold;     // Remove frames below this
    
    // Stability tracking
    int periods_above_upper;    // Consecutive periods above upper
    int periods_below_lower;    // Consecutive periods below lower
} ProcessAllocation;
 
// System-wide state
int total_free_frames;
Process* swap_candidates[MAX_PROCS];
int swap_candidate_count;
 
// Called periodically (e.g., every 100ms)
void pff_allocation_decision(Process* proc) {
    ProcessAllocation* alloc = &proc->allocation;
    
    // Update PFF measurement (see previous section)
    update_pff_measurement(proc);
    
    // Case 1: PFF exceeds upper threshold (process is suffering)
    if (alloc->current_pff > alloc->upper_threshold) {
        alloc->periods_above_upper++;
        alloc->periods_below_lower = 0;  // Reset other counter
        
        // Only act after sustained high PFF (avoid reacting to spikes)
        if (alloc->periods_above_upper >= 2) {
            handle_high_pff(proc);
        }
    }
    // Case 2: PFF below lower threshold (process has slack)
    else if (alloc->current_pff < alloc->lower_threshold) {
        alloc->periods_below_lower++;
        alloc->periods_above_upper = 0;
        
        // Only remove after sustained low PFF (be conservative)
        if (alloc->periods_below_lower >= 3) {
            handle_low_pff(proc);
        }
    }
    // Case 3: PFF in acceptable range
    else {
        // Reset both counters - process is stable
        alloc->periods_above_upper = 0;
        alloc->periods_below_lower = 0;
    }
}
 
void handle_high_pff(Process* proc) {
    ProcessAllocation* alloc = &proc->allocation;
    
    // Check if we can allocate more frames
    if (total_free_frames > 0 && 
        alloc->allocated_frames < alloc->max_frames) {
        
        // Give the process more frames
        int frames_to_add = min(
            calculate_frames_to_add(alloc->current_pff, alloc->upper_threshold),
            total_free_frames,
            alloc->max_frames - alloc->allocated_frames
        );
        
        alloc->allocated_frames += frames_to_add;
        total_free_frames -= frames_to_add;
        alloc->periods_above_upper = 0;  // Reset counter after action
        
        log_event("Process %d: Added %d frames (PFF=%.1f > %.1f)", 
                  proc->pid, frames_to_add, 
                  alloc->current_pff, alloc->upper_threshold);
    }
    else if (total_free_frames == 0) {
        // No free frames - need to swap out a process
        // Add to swap candidate list for global decision
        swap_candidates[swap_candidate_count++] = proc;
    }
}
 
void handle_low_pff(Process* proc) {
    ProcessAllocation* alloc = &proc->allocation;
    
    // Don't go below minimum
    if (alloc->allocated_frames > alloc->min_frames) {
        // Remove one frame (be conservative)
        alloc->allocated_frames--;
        total_free_frames++;
        alloc->periods_below_lower = 0;
        
        log_event("Process %d: Removed 1 frame (PFF=%.1f < %.1f)", 
                  proc->pid, 
                  alloc->current_pff, alloc->lower_threshold);
    }
}
 
// Calculate how many frames to add based on severity
int calculate_frames_to_add(double current_pff, double threshold) {
    double ratio = current_pff / threshold;
    
    if (ratio > 5.0) return 4;  // Severely under-allocated
    if (ratio > 3.0) return 2;  // Significantly under-allocated
    return 1;                    // Moderately under-allocated
}

Key Algorithm Features:

1. Hysteresis Through Counting: The algorithm requires multiple consecutive periods above/below thresholds before acting. This prevents reaction to temporary spikes or dips:

2+ periods above upper → add frames
3+ periods below lower → remove frames (more conservative)

2. Asymmetric Response: The algorithm is more aggressive about adding frames (2 periods) than removing them (3 periods). This reflects the asymmetry in consequences:

Under-allocation → immediate performance impact (page faults)
Over-allocation → only opportunity cost (memory that could go elsewhere)

3. Proportional Response: When adding frames, the number added depends on severity. A process faulting 5× threshold gets more frames than one barely exceeding threshold.

4. Bounds Enforcement: Every process has minimum and maximum frame limits:

Minimum: Architectural minimum (e.g., enough for one instruction's memory references)
Maximum: Policy maximum (fair share, resource limits, etc.)

5. Global Coordination: When no free frames exist, the algorithm collects swap candidates for a global decision—some process must be suspended to free frames.

The Global Decision Problem

When total demand exceeds supply (all processes have high PFF but no free frames), someone must be suspended. This decision requires global coordination—you can't solve it locally per-process. The next section on thrashing prevention addresses this.

PFF vs. Working Set: A Comparison

Let's systematically compare PFF and working set approaches to understand their relative strengths.

Working Set vs. Page Fault Frequency
Dimension	Working Set	Page Fault Frequency
What it measures	Pages referenced in window Δ	Rate of page faults
Fundamental question	What does process need?	Is process suffering?
Tracking cost	Scan all pages periodically	Increment counter on fault
Key parameter	Window size Δ	Upper/lower thresholds
Parameter sensitivity	Critical - wrong Δ breaks model	Moderate - thresholds affect responsiveness
Information required	Reference bit per page	Fault event + timestamp
Proactive/Reactive	Proactive (allocate before faults)	Reactive (respond to faults)
Phase transitions	Slow response (window lag)	Immediate signal (fault rate spikes)
Over-allocation detection	Requires tracking unused pages	Natural (low fault rate → remove frames)
Implementation complexity	High (page table scanning)	Low (counter per process)

When Working Set is Better:

Proactive Allocation: Working set can allocate frames before faults occur, if the OS monitors page loading patterns or has hints about upcoming phases.
Soft Real-Time: When even a few page faults are unacceptable, working set-based pre-allocation can ensure pages are present before they're needed.
Page Placement: Working set information tells you which pages are important—useful for NUMA placement or memory tiering decisions.
Debugging/Analysis: Knowing the actual working set aids in understanding program behavior and optimizing memory usage.

When PFF is Better:

Simplicity: Far less implementation complexity. Just count faults.
Large Address Spaces: Scanning millions of pages is expensive. PFF scales regardless of address space size.
Varied Workloads: No Δ parameter to tune per-workload. PFF naturally adapts.
Self-Correcting: If the initial allocation is wrong, PFF will correct it. Working set requires correct Δ from the start.
Cloud/Multi-Tenant: When running diverse unknown workloads, PFF's behavioral approach requires no per-workload tuning.

The Practical Reality

Most modern systems use PFF-like mechanisms (or even simpler approaches based on overall memory pressure) rather than pure working set tracking. The implementation simplicity of PFF, combined with adequate results, makes it the practical choice. Linux's memory management, for example, doesn't track per-process working sets—it monitors memory pressure globally and reclaims pages based on recency.

Edge Cases and Challenges

PFF, while simpler than working set tracking, has its own edge cases and challenges that require careful handling.

PFF Edge Cases

•Cold Start Problem — A new process or one returning from suspension will fault heavily as it loads its working set. These are legitimate faults, not signs of under-allocation. Solution: Don't adjust allocation during the first N faults or T seconds after start/resume.
•Phase Transition Spikes — When a process enters a new phase, it faults on new pages. This temporary spike shouldn't trigger permanent allocation increase. Solution: Require sustained high PFF (multiple periods) before adding frames.
•I/O-Bound Process Starvation — A process that's blocked on I/O has artificially low PFF (no faults because it's not running). If frames are taken during I/O, it will fault heavily when I/O completes. Solution: Track virtual time; don't remove frames based on time process was blocked.
•Memory-Intensive Burst — A process might briefly access a large dataset then return to small working set. Adding frames for the burst wastes memory afterward. Solution: More aggressive lower threshold enforcement; quickly reclaim after burst.
•Threshold Gaming — A malicious or poorly-designed process could artificially inflate PFF to consume memory. Solution: Absolute cap on frames per process; priority-based allocation.

Handling the Cold Start:

The cold start problem deserves special attention. When a process starts or resumes:

Without special handling:

Process starts with few frames
Every memory access causes a fault (working set not loaded)
PFF skyrockets
Algorithm rapidly allocates many frames
Working set eventually loads, PFF drops
Frames get reclaimed
...but we've thrashed during startup

With cold start handling:

Process marked as "cold starting"
Initial allocation based on estimate (e.g., historical average for this executable)
PFF tracking suspended for warm-up period
After warm-up, PFF measured from new baseline
Allocation adjusts based on steady-state behavior, not startup transients

cold_start_handling.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
// Cold start handling for PFF
 
typedef struct {
    ProcessAllocation alloc;
    
    // Cold start tracking
    bool in_cold_start;
    int faults_during_cold_start;
    uint64_t cold_start_end_time;
} ProcessPFFState;
 
#define COLD_START_FAULTS 100     // Allow 100 faults in cold start
#define COLD_START_DURATION_MS 500 // Or 500ms, whichever first
 
void on_process_start(Process* proc) {
    ProcessPFFState* state = &proc->pff_state;
    
    // Enter cold start mode
    state->in_cold_start = true;
    state->faults_during_cold_start = 0;
    state->cold_start_end_time = get_time_ms() + COLD_START_DURATION_MS;
    
    // Initial allocation based on historical behavior or heuristic
    state->alloc.allocated_frames = get_initial_allocation_estimate(proc);
}
 
void on_page_fault(Process* proc) {
    ProcessPFFState* state = &proc->pff_state;
    
    if (state->in_cold_start) {
        state->faults_during_cold_start++;
        
        // Check if cold start should end
        if (state->faults_during_cold_start >= COLD_START_FAULTS ||
            get_time_ms() >= state->cold_start_end_time) {
            
            state->in_cold_start = false;
            // Now begin normal PFF tracking
            init_pff_tracking(&state->alloc.pff);
        }
        return;  // Don't record fault for PFF during cold start
    }
    
    // Normal PFF recording
    record_page_fault(&state->alloc.pff);
}

Historical Information

Modern systems often maintain historical profiles of executables—how much memory they typically need, their steady-state working set size, etc. This information bootstraps new instances with good initial allocations, reducing cold start problems. This is particularly valuable in containerized environments where the same workload runs repeatedly.

Advanced PFF Techniques

Beyond the basic dual-threshold model, several advanced techniques can improve PFF effectiveness.

Advanced PFF Enhancements

•Predictive PFF — Use machine learning to predict upcoming phase transitions based on instruction patterns, system calls, or time-of-day. Pre-allocate frames before the fault rate rises.
•Hierarchical PFF — Different thresholds for different process classes (interactive vs. batch, high-priority vs. low-priority). Critical processes get more frames before their PFF rises.
•Rate-of-Change Tracking — Monitor not just PFF but dPFF/dt (how quickly fault rate is changing). A rapidly rising PFF signals imminent thrashing before the threshold is crossed.
•Collaborative PFF — In cluster environments, consider memory pressure across machines. A lightly-loaded machine's PFF thresholds can be lower; a heavily-loaded machine's thresholds should be higher.
•Application-Aware PFF — Let applications hint about upcoming memory needs. A database about to scan a large table can request temporary allocation before the faults occur.

Rate-of-Change Enhancement:

The derivative of PFF (how fast it's changing) provides early warning:

PFF	dPFF/dt	Interpretation
Low	Stable	All is well
Low	Rising	Trouble brewing — act now before PFF gets high
High	Stable	Under-allocated but stable — add frames
High	Rising	Cascading failure — urgent action needed
High	Falling	Recovery in progress — hold current allocation
Medium	Oscillating	Unstable equilibrium — widen threshold gap

By acting on rising dPFF/dt even when PFF is still acceptable, the system can prevent PFF from ever reaching problematic levels.

Multi-Threshold Extension:

Instead of just two thresholds, use three or more:

PFF > critical_upper:    Urgent — add many frames, consider swapping others
PFF > upper:             High — add frame
upper > PFF > lower:     Normal — no action
PFF < lower:             Low — remove frame
PFF < critical_lower:    Very low — aggressively reclaim frames

This allows graduated responses—a moderately high PFF gets one frame while a severely high PFF gets aggressive intervention.

Integration with Page Replacement

PFF can inform page replacement policy. When PFF is high, use a more conservative replacement algorithm (don't evict working set pages). When PFF is low, replacement can be more aggressive (the process has slack). This creates cooperation between allocation and replacement for better overall behavior.

Summary: Page Fault Frequency

We've explored Page Fault Frequency in comprehensive depth—from its simple core insight to advanced techniques. Let's consolidate the key learnings:

Key Takeaways

•The Core Insight — Page fault rate directly indicates whether a process has adequate frames. High PFF means under-allocation; low PFF means sufficient (or excess) allocation.
•Dual Threshold Model — Upper threshold triggers frame addition; lower threshold triggers removal. The gap between them provides stability (hysteresis).
•Measurement Techniques — Windowed counting or exponential moving average. Virtual time is more accurate than wall-clock time.
•Hysteresis Counters — Require sustained above/below threshold before acting. Prevents reaction to temporary spikes.
•vs. Working Set — PFF is simpler (counts faults vs. scanning pages) but reactive (responds to faults vs. preventing them).
•Edge Cases — Cold start, phase transitions, I/O blocking all require special handling to avoid incorrect allocation decisions.

What's Next:

In the next page, we'll explore Dynamic Allocation in practice—how operating systems combine PFF, working set, and other signals to make holistic allocation decisions across all processes, balancing individual needs with system-wide goals.

Page Complete

You now understand the Page Fault Frequency approach to dynamic frame allocation—a simpler alternative to working set tracking that achieves comparable results through behavioral observation. This understanding is essential for grasping how modern operating systems manage memory across competing processes.

3 / 5

Loading learning content...

Operating SystemsWorking Set and Page Fault Frequency

Working Set Model and Page Fault Frequency

LevelAdvanced

Duration90 mins

TopicWorking Set and Page Fault Frequency

3 / 5

Page Fault Frequency (PFF)

A Simpler Path to Dynamic Allocation

If a process is page faulting too frequently, it needs more frames. If it's page faulting rarely, it can afford to give up some frames.

What You Will Learn

The Core Insight Behind PFF

Consider two processes, each with an unknown working set:

Process A: 50 page faults per second Process B: 2 page faults per second

What can we infer?

Process A is suffering. It frequently needs pages that aren't in memory. Its current frame allocation is inadequate for its actual memory needs.
Process B is comfortable. It rarely encounters missing pages. Its allocation meets or exceeds its working set.

The Fundamental Relationship:

Page fault rate is inversely related to frame allocation (given a constant access pattern):

Frames vs. WSS	Fault Rate	Process State
Frames << WSS	Very High	Thrashing
Frames < WSS	High	Struggling
Frames ≈ WSS	Moderate-Low	Operating point
Frames > WSS	Very Low	Excess capacity
Frames >> WSS	Near Zero	Memory waste

The Self-Regulating System

Why This Works:

The PFF approach works because of locality of reference:

With insufficient frames: The process's working set doesn't fit. Each access to a working set page not currently resident causes a fault. Since access rates to working set pages are high (by definition of working set), fault rates are high.
With sufficient frames: The working set fits in allocated frames. Faults only occur when:
- The process transitions to a new phase (cold start)
- The process accesses pages outside current locality (rare) Both are infrequent, so fault rates are low.
With excess frames: Additional frames beyond the working set don't reduce fault rate further—you can't have negative faults. The fault rate asymptotically approaches the irreducible rate determined by phase transitions and outlier accesses.

The Operating Point:

Measuring Page Fault Frequency

Accurately measuring page fault frequency requires careful definition and implementation.

Definition:

Page Fault Frequency (PFF) = Number of page faults / Time period

Or equivalently:

Inter-Fault Time (IFT) = Time between consecutive page faults

PFF = 1 / average(IFT)

Measurement Approaches:

PFF Measurement Strategies
Approach	Mechanism	Pros	Cons
Windowed Counter	Count faults in fixed time window	Simple, direct	Window size selection
Exponential Average	Weighted average of recent rates	Smooth, adaptive	More complex, lag
Inter-Fault Time	Measure time between each fault	Immediate signal	Noisy, needs filtering
Token Bucket	Fault decrements tokens; time adds them	Rate limiting metaphor	Parameter tuning

Windowed Counter Approach:

The simplest approach maintains a counter that's reset periodically:

On each timer tick (every T seconds):
   current_pff = fault_count / T
   fault_count = 0  // Reset for next window

Advantages:

Very simple to implement
Direct, interpretable value
Natural fit with existing timer interrupts

Disadvantages:

Quantization: faults near window boundaries may be counted in wrong window
Needs window size selection (similar to working set window problem)
No memory of past behavior

Exponential Moving Average:

A more sophisticated approach uses exponential smoothing:

On each page fault:
   current_time = now()
   interval = current_time - last_fault_time
   instantaneous_rate = 1 / interval
   smoothed_pff = α × instantaneous_rate + (1-α) × smoothed_pff
   last_fault_time = current_time

Here α (0 < α < 1) controls responsiveness:

High α (e.g., 0.8): responsive to recent behavior
Low α (e.g., 0.2): stable, slow-changing estimate

Advantages:

Smooth estimate, less noise
Infinite memory (weighted) of past behavior
Updates on each fault (event-driven, not timer-driven)

Disadvantages:

More complex
α parameter requires tuning
If faults stop completely, estimate doesn't decay to zero

pff_measurement.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
// PFF measurement implementation using exponential moving average
 
typedef struct {
    double smoothed_pff;        // Smoothed page fault frequency (faults/sec)
    uint64_t last_fault_time;   // Timestamp of most recent fault (microseconds)
    uint64_t fault_count;       // Total faults (for statistics)
    double alpha;               // Smoothing factor (0 to 1)
} ProcessPFF;
 
#define ALPHA_DEFAULT 0.25      // Balance between responsiveness and stability
 
void init_pff_tracking(ProcessPFF* pff) {
    pff->smoothed_pff = 0.0;
    pff->last_fault_time = 0;
    pff->fault_count = 0;
    pff->alpha = ALPHA_DEFAULT;
}
 
// Called by page fault handler
void record_page_fault(ProcessPFF* pff) {
    uint64_t current_time = get_microseconds();  // Current time in μs
    pff->fault_count++;
    
    if (pff->last_fault_time == 0) {
        // First fault - initialize
        pff->last_fault_time = current_time;
        return;
    }
    
    // Calculate inter-fault interval in seconds
    double interval_sec = (current_time - pff->last_fault_time) / 1000000.0;
    
    if (interval_sec > 0) {
        // Instantaneous fault rate = 1 / interval
        double instantaneous_rate = 1.0 / interval_sec;
        
        // Exponential moving average
        pff->smoothed_pff = pff->alpha * instantaneous_rate + 
                            (1.0 - pff->alpha) * pff->smoothed_pff;
    }
    
    pff->last_fault_time = current_time;
}
 
// Handle time passing without faults (decay estimate)
void pff_decay(ProcessPFF* pff, uint64_t current_time) {
    if (pff->last_fault_time == 0) return;
    
    double time_since_fault = (current_time - pff->last_fault_time) / 1000000.0;
    
    // If long time without faults, decay the estimate
    // Decay as if a hypothetical fault just occurred at low rate
    if (time_since_fault > 1.0) {  // More than 1 second
        double hypothetical_rate = 1.0 / time_since_fault;
        pff->smoothed_pff = pff->alpha * hypothetical_rate + 
                            (1.0 - pff->alpha) * pff->smoothed_pff;
    }
}

Virtual Time vs. Real Time

The Dual Threshold Model

PFF-based allocation uses two thresholds to control frame allocation: an upper threshold for increasing allocation and a lower threshold for decreasing it.

The Basic Idea:

If PFF > upper_threshold:
    Process is faulting too much → Give it more frames
Else if PFF < lower_threshold:
    Process is faulting rarely → Take some frames away
Else:
    Process is in acceptable range → No change

Why Two Thresholds?

A single threshold would cause oscillation:

PFF slightly above threshold → add frame
PFF drops slightly below threshold → remove frame
PFF rises slightly above threshold → add frame
Continuous oscillation, wasted overhead

Two thresholds create a hysteresis band—a range where no action is taken. This provides stability:

PFF above upper → add frame
PFF drops into band → no action (stable)
PFF would need to drop below lower to trigger frame removal
The band prevents oscillation from noise

Single Threshold (Oscillation)

•One threshold at PFF = T
•PFF > T → add frame
•PFF < T → remove frame
•Small fluctuations cross threshold
•Continuous add/remove oscillation
•High overhead, unstable allocation

Dual Threshold (Stable)

•Lower threshold L, upper threshold U
•PFF > U → add frame
•PFF < L → remove frame
•L < PFF < U → no change
•Dead band absorbs fluctuations
•Stable allocation, low overhead

Choosing Threshold Values:

Threshold selection depends on several factors:

Factor	Upper Threshold	Lower Threshold
Typical value	10-50 faults/sec	1-5 faults/sec
System goal	Prevent thrashing	Reclaim excess memory
Crossing means	Process is suffering	Process has slack
Response	Immediately add 1+ frames	Gradually remove frames
Urgency	High (pain is real)	Low (no immediate harm)

Practical Considerations:

Upper threshold must be meaningful: Too high means processes thrash before getting help. Too low means frames are given too liberally.
Lower threshold should be conservative: A process with low PFF might be in a quiet phase—removing frames could cause problems when activity resumes.
The gap matters: A wide gap (e.g., 5-50 faults/sec) provides more stability but slower response. A narrow gap (e.g., 8-15 faults/sec) responds quickly but may oscillate.

Adaptive Thresholds

The PFF Algorithm in Detail

Let's examine the complete PFF algorithm for dynamic frame allocation, including edge cases and practical considerations.

pff_algorithm.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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
// Complete PFF-based dynamic frame allocation
 
typedef struct {
    // PFF tracking
    double current_pff;         // Current page fault frequency
    uint64_t last_check_time;   // Last allocation decision time
    
    // Allocation state
    int allocated_frames;       // Current frame count
    int min_frames;            // Minimum frames (architectural)
    int max_frames;            // Maximum frames (policy)
    
    // Thresholds (faults per second)
    double upper_threshold;     // Add frames above this
    double lower_threshold;     // Remove frames below this
    
    // Stability tracking
    int periods_above_upper;    // Consecutive periods above upper
    int periods_below_lower;    // Consecutive periods below lower
} ProcessAllocation;
 
// System-wide state
int total_free_frames;
Process* swap_candidates[MAX_PROCS];
int swap_candidate_count;
 
// Called periodically (e.g., every 100ms)
void pff_allocation_decision(Process* proc) {
    ProcessAllocation* alloc = &proc->allocation;
    
    // Update PFF measurement (see previous section)
    update_pff_measurement(proc);
    
    // Case 1: PFF exceeds upper threshold (process is suffering)
    if (alloc->current_pff > alloc->upper_threshold) {
        alloc->periods_above_upper++;
        alloc->periods_below_lower = 0;  // Reset other counter
        
        // Only act after sustained high PFF (avoid reacting to spikes)
        if (alloc->periods_above_upper >= 2) {
            handle_high_pff(proc);
        }
    }
    // Case 2: PFF below lower threshold (process has slack)
    else if (alloc->current_pff < alloc->lower_threshold) {
        alloc->periods_below_lower++;
        alloc->periods_above_upper = 0;
        
        // Only remove after sustained low PFF (be conservative)
        if (alloc->periods_below_lower >= 3) {
            handle_low_pff(proc);
        }
    }
    // Case 3: PFF in acceptable range
    else {
        // Reset both counters - process is stable
        alloc->periods_above_upper = 0;
        alloc->periods_below_lower = 0;
    }
}
 
void handle_high_pff(Process* proc) {
    ProcessAllocation* alloc = &proc->allocation;
    
    // Check if we can allocate more frames
    if (total_free_frames > 0 && 
        alloc->allocated_frames < alloc->max_frames) {
        
        // Give the process more frames
        int frames_to_add = min(
            calculate_frames_to_add(alloc->current_pff, alloc->upper_threshold),
            total_free_frames,
            alloc->max_frames - alloc->allocated_frames
        );
        
        alloc->allocated_frames += frames_to_add;
        total_free_frames -= frames_to_add;
        alloc->periods_above_upper = 0;  // Reset counter after action
        
        log_event("Process %d: Added %d frames (PFF=%.1f > %.1f)", 
                  proc->pid, frames_to_add, 
                  alloc->current_pff, alloc->upper_threshold);
    }
    else if (total_free_frames == 0) {
        // No free frames - need to swap out a process
        // Add to swap candidate list for global decision
        swap_candidates[swap_candidate_count++] = proc;
    }
}
 
void handle_low_pff(Process* proc) {
    ProcessAllocation* alloc = &proc->allocation;
    
    // Don't go below minimum
    if (alloc->allocated_frames > alloc->min_frames) {
        // Remove one frame (be conservative)
        alloc->allocated_frames--;
        total_free_frames++;
        alloc->periods_below_lower = 0;
        
        log_event("Process %d: Removed 1 frame (PFF=%.1f < %.1f)", 
                  proc->pid, 
                  alloc->current_pff, alloc->lower_threshold);
    }
}
 
// Calculate how many frames to add based on severity
int calculate_frames_to_add(double current_pff, double threshold) {
    double ratio = current_pff / threshold;
    
    if (ratio > 5.0) return 4;  // Severely under-allocated
    if (ratio > 3.0) return 2;  // Significantly under-allocated
    return 1;                    // Moderately under-allocated
}

Key Algorithm Features:

1. Hysteresis Through Counting: The algorithm requires multiple consecutive periods above/below thresholds before acting. This prevents reaction to temporary spikes or dips:

2+ periods above upper → add frames
3+ periods below lower → remove frames (more conservative)

2. Asymmetric Response: The algorithm is more aggressive about adding frames (2 periods) than removing them (3 periods). This reflects the asymmetry in consequences:

Under-allocation → immediate performance impact (page faults)
Over-allocation → only opportunity cost (memory that could go elsewhere)

3. Proportional Response: When adding frames, the number added depends on severity. A process faulting 5× threshold gets more frames than one barely exceeding threshold.

4. Bounds Enforcement: Every process has minimum and maximum frame limits:

Minimum: Architectural minimum (e.g., enough for one instruction's memory references)
Maximum: Policy maximum (fair share, resource limits, etc.)

5. Global Coordination: When no free frames exist, the algorithm collects swap candidates for a global decision—some process must be suspended to free frames.

The Global Decision Problem

PFF vs. Working Set: A Comparison

Let's systematically compare PFF and working set approaches to understand their relative strengths.

Working Set vs. Page Fault Frequency
Dimension	Working Set	Page Fault Frequency
What it measures	Pages referenced in window Δ	Rate of page faults
Fundamental question	What does process need?	Is process suffering?
Tracking cost	Scan all pages periodically	Increment counter on fault
Key parameter	Window size Δ	Upper/lower thresholds
Parameter sensitivity	Critical - wrong Δ breaks model	Moderate - thresholds affect responsiveness
Information required	Reference bit per page	Fault event + timestamp
Proactive/Reactive	Proactive (allocate before faults)	Reactive (respond to faults)
Phase transitions	Slow response (window lag)	Immediate signal (fault rate spikes)
Over-allocation detection	Requires tracking unused pages	Natural (low fault rate → remove frames)
Implementation complexity	High (page table scanning)	Low (counter per process)

When Working Set is Better:

Proactive Allocation: Working set can allocate frames before faults occur, if the OS monitors page loading patterns or has hints about upcoming phases.
Soft Real-Time: When even a few page faults are unacceptable, working set-based pre-allocation can ensure pages are present before they're needed.
Page Placement: Working set information tells you which pages are important—useful for NUMA placement or memory tiering decisions.
Debugging/Analysis: Knowing the actual working set aids in understanding program behavior and optimizing memory usage.

When PFF is Better:

Simplicity: Far less implementation complexity. Just count faults.
Large Address Spaces: Scanning millions of pages is expensive. PFF scales regardless of address space size.
Varied Workloads: No Δ parameter to tune per-workload. PFF naturally adapts.
Self-Correcting: If the initial allocation is wrong, PFF will correct it. Working set requires correct Δ from the start.
Cloud/Multi-Tenant: When running diverse unknown workloads, PFF's behavioral approach requires no per-workload tuning.

The Practical Reality

Edge Cases and Challenges

PFF, while simpler than working set tracking, has its own edge cases and challenges that require careful handling.

PFF Edge Cases

•Cold Start Problem — A new process or one returning from suspension will fault heavily as it loads its working set. These are legitimate faults, not signs of under-allocation. Solution: Don't adjust allocation during the first N faults or T seconds after start/resume.
•Phase Transition Spikes — When a process enters a new phase, it faults on new pages. This temporary spike shouldn't trigger permanent allocation increase. Solution: Require sustained high PFF (multiple periods) before adding frames.
•I/O-Bound Process Starvation — A process that's blocked on I/O has artificially low PFF (no faults because it's not running). If frames are taken during I/O, it will fault heavily when I/O completes. Solution: Track virtual time; don't remove frames based on time process was blocked.
•Memory-Intensive Burst — A process might briefly access a large dataset then return to small working set. Adding frames for the burst wastes memory afterward. Solution: More aggressive lower threshold enforcement; quickly reclaim after burst.
•Threshold Gaming — A malicious or poorly-designed process could artificially inflate PFF to consume memory. Solution: Absolute cap on frames per process; priority-based allocation.

Handling the Cold Start:

The cold start problem deserves special attention. When a process starts or resumes:

Without special handling:

Process starts with few frames
Every memory access causes a fault (working set not loaded)
PFF skyrockets
Algorithm rapidly allocates many frames
Working set eventually loads, PFF drops
Frames get reclaimed
...but we've thrashed during startup

With cold start handling:

Process marked as "cold starting"
Initial allocation based on estimate (e.g., historical average for this executable)
PFF tracking suspended for warm-up period
After warm-up, PFF measured from new baseline
Allocation adjusts based on steady-state behavior, not startup transients

cold_start_handling.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
// Cold start handling for PFF
 
typedef struct {
    ProcessAllocation alloc;
    
    // Cold start tracking
    bool in_cold_start;
    int faults_during_cold_start;
    uint64_t cold_start_end_time;
} ProcessPFFState;
 
#define COLD_START_FAULTS 100     // Allow 100 faults in cold start
#define COLD_START_DURATION_MS 500 // Or 500ms, whichever first
 
void on_process_start(Process* proc) {
    ProcessPFFState* state = &proc->pff_state;
    
    // Enter cold start mode
    state->in_cold_start = true;
    state->faults_during_cold_start = 0;
    state->cold_start_end_time = get_time_ms() + COLD_START_DURATION_MS;
    
    // Initial allocation based on historical behavior or heuristic
    state->alloc.allocated_frames = get_initial_allocation_estimate(proc);
}
 
void on_page_fault(Process* proc) {
    ProcessPFFState* state = &proc->pff_state;
    
    if (state->in_cold_start) {
        state->faults_during_cold_start++;
        
        // Check if cold start should end
        if (state->faults_during_cold_start >= COLD_START_FAULTS ||
            get_time_ms() >= state->cold_start_end_time) {
            
            state->in_cold_start = false;
            // Now begin normal PFF tracking
            init_pff_tracking(&state->alloc.pff);
        }
        return;  // Don't record fault for PFF during cold start
    }
    
    // Normal PFF recording
    record_page_fault(&state->alloc.pff);
}

Historical Information

Advanced PFF Techniques

Beyond the basic dual-threshold model, several advanced techniques can improve PFF effectiveness.

Advanced PFF Enhancements

•Predictive PFF — Use machine learning to predict upcoming phase transitions based on instruction patterns, system calls, or time-of-day. Pre-allocate frames before the fault rate rises.
•Hierarchical PFF — Different thresholds for different process classes (interactive vs. batch, high-priority vs. low-priority). Critical processes get more frames before their PFF rises.
•Rate-of-Change Tracking — Monitor not just PFF but dPFF/dt (how quickly fault rate is changing). A rapidly rising PFF signals imminent thrashing before the threshold is crossed.
•Collaborative PFF — In cluster environments, consider memory pressure across machines. A lightly-loaded machine's PFF thresholds can be lower; a heavily-loaded machine's thresholds should be higher.
•Application-Aware PFF — Let applications hint about upcoming memory needs. A database about to scan a large table can request temporary allocation before the faults occur.

Rate-of-Change Enhancement:

The derivative of PFF (how fast it's changing) provides early warning:

PFF	dPFF/dt	Interpretation
Low	Stable	All is well
Low	Rising	Trouble brewing — act now before PFF gets high
High	Stable	Under-allocated but stable — add frames
High	Rising	Cascading failure — urgent action needed
High	Falling	Recovery in progress — hold current allocation
Medium	Oscillating	Unstable equilibrium — widen threshold gap

By acting on rising dPFF/dt even when PFF is still acceptable, the system can prevent PFF from ever reaching problematic levels.

Multi-Threshold Extension:

Instead of just two thresholds, use three or more:

PFF > critical_upper:    Urgent — add many frames, consider swapping others
PFF > upper:             High — add frame
upper > PFF > lower:     Normal — no action
PFF < lower:             Low — remove frame
PFF < critical_lower:    Very low — aggressively reclaim frames

This allows graduated responses—a moderately high PFF gets one frame while a severely high PFF gets aggressive intervention.

Integration with Page Replacement

Summary: Page Fault Frequency

We've explored Page Fault Frequency in comprehensive depth—from its simple core insight to advanced techniques. Let's consolidate the key learnings:

Key Takeaways

•The Core Insight — Page fault rate directly indicates whether a process has adequate frames. High PFF means under-allocation; low PFF means sufficient (or excess) allocation.
•Dual Threshold Model — Upper threshold triggers frame addition; lower threshold triggers removal. The gap between them provides stability (hysteresis).
•Measurement Techniques — Windowed counting or exponential moving average. Virtual time is more accurate than wall-clock time.
•Hysteresis Counters — Require sustained above/below threshold before acting. Prevents reaction to temporary spikes.
•vs. Working Set — PFF is simpler (counts faults vs. scanning pages) but reactive (responds to faults vs. preventing them).
•Edge Cases — Cold start, phase transitions, I/O blocking all require special handling to avoid incorrect allocation decisions.

What's Next:

Page Complete

3 / 5