Working Set Model and Page Fault Frequency

In 1968, Peter Denning introduced a concept that would fundamentally transform how operating systems manage memory: the working set model. Before this breakthrough, memory management was largely reactive—systems would respond to page faults as they occurred, often leading to catastrophic performance degradation known as thrashing.

The working set model provided something revolutionary: a predictive framework for understanding which pages a process truly needs at any given moment. Rather than treating all pages equally or making arbitrary eviction decisions, the working set approach recognizes a fundamental truth about program behavior—locality of reference.

This page explores the working set model in exhaustive detail, from its theoretical foundations to its mathematical formalization, establishing the groundwork for understanding modern memory management policies.

To appreciate the significance of the working set model, we must first understand the severe challenges that plagued early multiprogramming systems.

The Early Virtual Memory Dilemma:

When virtual memory systems were first developed in the 1960s, designers faced a fundamental question: How many frames should each process receive? The answers seemed deceptively simple:

1. Give each process an equal share — If you have 100 frames and 10 processes, each gets 10 frames
2. Let processes compete freely — Use global replacement and let page fault rates determine allocation
3. Allocate based on process size — Larger processes get more frames

Each of these approaches harbored critical flaws that would manifest catastrophically under load.

The Thrashing Catastrophe:

The most devastating failure mode was thrashing—a condition where the system spends more time handling page faults than executing useful work. Consider this progression:

1. System has 1000 frames, 10 processes, each using ~150 pages actively
2. Total active pages: 1500, but only 1000 frames available
3. Every process constantly page faults, stealing frames from others
4. Stolen frames cause more page faults in victim processes
5. CPU utilization drops to near zero while disk I/O saturates
6. System becomes completely unresponsive

The terrifying aspect of thrashing is its positive feedback loop—once it starts, it accelerates. More page faults lead to more context switches, which leads to more diverse page references, which leads to more page faults.

What Was Missing:

The fundamental gap in early approaches was predictive understanding of process memory behavior. Systems needed to answer:

• Which pages does each process actually need right now?
• How do memory requirements change over time?
• What is the minimum allocation that prevents excessive page faults?
• How can we detect when a process doesn't have enough frames?

Peter Denning's working set model provided elegant answers to all these questions by formalizing the observation that programs exhibit locality of reference.

The working set model rests on a profound empirical observation about program behavior: programs do not reference their entire address space uniformly. Instead, at any given time, they focus their memory accesses on a small subset of their pages. This phenomenon is called the principle of locality, and it manifests in three distinct forms.

Why Locality Exists:

Locality is not accidental—it emerges from fundamental properties of program structure:

Program Structure:

• Most execution time is spent in loops (temporal locality of instructions)
• Functions are called repeatedly (temporal locality of code pages)
• Local variables are accessed throughout function execution (temporal locality of stack)
• Data structures are processed systematically (spatial locality of heap)

Algorithm Behavior:

• Sorting algorithms repeatedly compare and swap adjacent elements
• Search algorithms focus on progressively smaller regions
• Graph algorithms explore neighborhoods before moving on
• Matrix operations process elements in predictable patterns

Memory Layout:

• Compilers group related code together
• Data structures store related data contiguously
• Stack frames contain related local variables
• Object-oriented systems cluster object data

Locality and Program Phases:

Programs don't maintain constant locality—they move through phases, each with its own working set of pages:

During each phase, the program's memory requirements may differ dramatically. The working set model captures this phase behavior by defining the working set relative to recent history, automatically adapting as the program transitions between phases.

With the principle of locality established, we can now formalize the working set concept. Denning's definition is elegant and precise:

Definition: The working set of a process at virtual time t with window size Δ, denoted W(t, Δ), is the set of pages referenced during the time interval from t - Δ to t.

Let's unpack each component of this definition carefully.

Mathematical Formalization:

Let r₁, r₂, r₃, ... be the sequence of page references made by a process, where rᵢ is the page referenced at virtual time i.

Then the working set is defined as:

W(t, Δ) = { rᵢ | t - Δ < i ≤ t }

And the working set size is:

|W(t, Δ)| = number of distinct pages in W(t, Δ)

Properties of Working Sets:

Working sets exhibit several important mathematical properties:

1. Monotonicity with Δ: If Δ₁ ≤ Δ₂, then W(t, Δ₁) ⊆ W(t, Δ₂)

A larger window always includes at least the pages in a smaller window. This means:

• |W(t, Δ₁)| ≤ |W(t, Δ₂)|
• Working set size is non-decreasing in Δ

2. Bounds on Working Set Size: 1 ≤ |W(t, Δ)| ≤ min(Δ, N)

Where N is the total number of pages in the process's address space. The working set always contains at least one page (the most recently referenced) and at most Δ pages (if every reference in the window is to a different page) or N pages (if the entire address space is covered).

3. Inclusion Property: If page P ∈ W(t, Δ), then either:

• P was just referenced (at time t), or
• P was referenced within the last Δ references and hasn't been 'pushed out' by Δ new distinct pages

4. Temporal Coherence: For most programs, W(t, Δ) ≈ W(t+1, Δ) — the working set changes slowly over time. Dramatic changes occur only at phase transitions.

To build intuition for how working sets behave, let's trace through a detailed example. Consider a program with the following page reference string:

Reference String: 1, 2, 3, 2, 1, 4, 1, 2, 5, 1, 2, 3, 4, 5

We'll compute the working set at each time step with Δ = 4 (a window of 4 references).

Observations from the Trace:

1. Working Set Stability: Notice how the working set remains relatively stable. From t=4 to t=5, despite different references, the working set stays {1, 2, 3}. This stability is what makes working sets useful—they change slowly, tracking genuine phase transitions rather than individual references.

2. Page Entry and Exit: Page 3 exits the working set at t=7 (its last reference at t=5 falls outside the window) but re-enters at t=12 when referenced again. The working set naturally captures which pages are 'currently important.'

3. Size Fluctuation: The working set size fluctuates between 3 and 4 pages. If we allocate exactly |W(t, Δ)| frames to this process at each moment, we'd need between 3 and 4 frames—far less than the 5 distinct pages eventually used.

4. Effect of Window Size: With a larger Δ (say, 6 instead of 4), working sets would be larger and change more slowly. With a smaller Δ (say, 2), they'd be smaller but potentially miss important pages, causing page faults.

The working set model leads to a fundamental principle for memory management, often called the Working Set Principle or Denning's Principle:

A process should be allocated frames at least equal to its working set size. If the sum of all processes' working set sizes exceeds total available frames, then some processes must be suspended (not all can run efficiently simultaneously).

This principle has profound implications for operating system design.

The Working Set Balance Equation:

Let WSS_i denote the working set size of process i at a given moment, and let M denote total available frames. The system is in balance when:

∑ WSS_i ≤ M (for all currently running processes)

When this inequality is satisfied, each process can hold its entire working set in memory, page faults are minimal (only when transitioning between phases), and CPU utilization is high.

When the inequality is violated:

∑ WSS_i > M (system is overcommitted)

Some processes cannot hold their working sets, leading to:

• Elevated page fault rates
• Processes interfering with each other's memory
• Potential thrashing if the imbalance is severe

The OS must respond by suspending one or more processes (moving them entirely out of memory) until balance is restored.

The window size Δ is the critical parameter of the working set model. Its selection represents a fundamental tradeoff between responsiveness and stability.

Effects of Different Δ Values:

The Ideal Δ:

The ideal window size is one that:

1. Captures full locality regions — Large enough to include all pages in the current phase's working set
2. Excludes stale pages — Small enough to drop pages from previous phases that are no longer needed
3. Adapts to program behavior — What's ideal may differ between programs or even between phases of the same program

Practical Considerations:

In practice, Δ is typically:

• Measured in page references (logical time) rather than wall-clock time
• Set system-wide (same Δ for all processes) for simplicity
• Chosen empirically based on workload characteristics
• Ranges from thousands to millions of references

Common values in real systems:

• Δ ≈ 10,000 references — Responsive, good for interactive workloads
• Δ ≈ 100,000 references — Balanced, suitable for mixed workloads
• Δ ≈ 1,000,000 references — Conservative, good for batch processing

Students often confuse the working set model with the LRU (Least Recently Used) page replacement algorithm. While both leverage the principle of locality, they serve fundamentally different purposes and operate at different levels.

Key Distinctions:

Complementary, Not Competing:

Working set and LRU work at different levels of the memory management hierarchy:

1. Working Set (Allocation): "Process P needs 15 frames to hold its working set"
2. LRU (Replacement): "Process P needs a frame; evict its least recently used page"

A well-designed system uses both:

• The working set model guides how many frames each process receives
• LRU (or an approximation) determines which page to evict when frames must be reclaimed

The Relationship:

Interestingly, if you use working set-based allocation and need to evict a page, the page that will leave the working set next (under LRU ordering) is exactly the least recently used page. This means:

• Working set allocation with window Δ
• Plus LRU replacement when frames needed
• Equals a coherent policy: keep pages used within last Δ references

The working set model can be seen as a way to dynamically adjust allocation so that LRU replacement rarely needs to evict pages that will be used again soon.

We have established the theoretical foundation of the working set model—one of the most influential concepts in operating systems memory management. Let's consolidate the key insights:

What's Next:

In the next page, we'll explore the working set window in greater depth—examining how the window parameter affects system behavior, how to track working sets in practice, and the implementation challenges that led to approximate approaches.