Demand Paging

In our exploration of lazy loading, we established that loading pages only when needed is generally beneficial. But how far should we take this principle? Pure demand paging represents the extreme interpretation: load absolutely nothing until the CPU explicitly generates a memory reference that requires a page.

Under pure demand paging, a process begins execution with zero pages in memory. Not a single byte of code, not a single byte of data. The very first instruction the CPU attempts to execute causes a page fault. That page is loaded, and execution continues—only to likely fault again for data or stack accesses. Gradually, as the program runs, the pages it actually uses accumulate in memory.

This approach embodies a philosophical commitment: never do work that might not be needed. It's the logical conclusion of lazy loading, but like many extremes, it comes with trade-offs that make it more of a conceptual ideal than a universally optimal strategy.

Pure demand paging is a memory management strategy with a simple rule: never load a page into memory until a CPU access explicitly requires it. No speculation, no prefetching, no read-ahead—just reactive loading in response to faults.

Formal Definition:

For all pages P in process address space:
  load(P) occurs if and only if
    ∃ instruction I where I accesses address A ∧ A ∈ P ∧ P ∉ RAM

In plain terms: a page is loaded if and only if an instruction tries to access an address within that page and the page isn't already in physical memory.

Characteristics of Pure Demand Paging:

Comparison: Pure vs. Modified Demand Paging

The most distinctive aspect of pure demand paging is how processes start. Let's trace through the startup sequence in detail.

The exec() Sequence:

When a process calls exec() to load a new program:

1. Kernel parses executable header - Determines code, data, BSS sections without loading them
2. Creates empty page table - All entries set to not-present
3. Sets up VMAs - Records which address ranges map to which file regions
4. Sets instruction pointer - Points to program entry (e.g., _start)
5. Returns to user mode - Execution 'begins' with zero pages loaded

The First Fault Cascade:

Time →

0 ms:   CPU jumps to entry point address (e.g., 0x401000)
        → Page fault #1: Code page containing entry point
        → Load page from executable file
        → ~10 ms for SSD, longer for HDD

10 ms:  First instruction executes (e.g., PUSH RBP)
        → Page fault #2: Stack page
        → Allocate zero-filled frame
        → ~1 ms (minor fault)

11 ms:  Next instruction accesses global data
        → Page fault #3: Data page
        → Load page from executable file
        → ~10 ms

21 ms:  Program calls a library function (printf)
        → Page fault #4: PLT/GOT page
        → ~10 ms

31 ms:  Library code executes
        → Page fault #5: libc code page
        → ~10 ms

...and so on for every new page touched

A simple "Hello, World" program under pure demand paging might experience 10-20 page faults before producing any output. Larger programs can experience hundreds or thousands of faults during initialization.

After the startup storm of page faults, the process enters a steadier state as its working set becomes established in memory. Pure demand paging has interesting implications for this phase.

Working Set Definition:

The working set W(t, Δ) is the set of pages referenced during the time interval [t - Δ, t]. Under pure demand paging, the physical pages present in memory are exactly those that have been accessed (minus any that were evicted due to memory pressure).

Working Set Building Phase:

Fault Rate Over Time (pure demand paging):

     Faults/sec
          ▲
     1000 │▓▓
          │▓▓▓▓
      500 │▓▓▓▓▓▓▓
          │▓▓▓▓▓▓▓▓▓▓
      100 │▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
          │               ▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓───────
       10 │                                                    Steady state
          │                                                    (new pages rare)
        0 └────────────────────────────────────────────────────────────▶
               1s    5s    10s         30s              Time
          ←───────────────────→ Working set establishment

Phase 1: High Fault Rate (0-10s)

• Every new code path or data structure causes faults
• Dominated by major faults (disk I/O)
• Application feels sluggish

Phase 2: Decreasing Fault Rate (10-30s)

• Core working set established
• Fewer new pages touched
• Major faults become rare

Phase 3: Steady State (30s+)

• Working set stable in memory
• Only occasional faults for rarely-used code
• Application runs at near-native speed

Locality Determines Steady-State Behavior:

Programs with good locality stabilize quickly:

• Text editors: Working set established in seconds
• Compilers: Working set per compilation phase, then stable
• Web servers: Working set per request type, frequently accessed

Programs with poor locality never stabilize:

• Database scans: Touch different pages continuously
• Virtual machines: Guest OS has unpredictable access patterns
• Machine learning: Training data access may span huge datasets

Pure demand paging achieves optimal memory utilization in a specific sense: it never loads pages that aren't accessed. Let's analyze this efficiency in detail.

Memory Efficiency Theorem:

Under pure demand paging with no eviction (unlimited memory):

|Pages in Memory| = |Unique Pages Accessed|

This is optimal because any page loaded was definitively needed. No memory is wasted on speculative loads that turn out to be unnecessary.

Comparison with Eager Loading:

Memory Savings Calculation:

For a typical office suite:

• Executable + libraries: 500 MB
• Typical usage touches: 50 MB
• Memory usage ratio: 50/500 = 10%

With eager loading: 500 MB per instance With pure demand: 50 MB per instance

If running 3 instances:

• Eager: 1500 MB (with sharing: ~600 MB if code shared)
• Pure demand: 150 MB (or less with code sharing)

The cost of this efficiency: Startup time and initial response latency.

When Memory Efficiency Matters Most:

Pure demand paging has distinctive I/O characteristics that significantly impact performance, particularly on mechanical storage.

I/O Pattern Under Pure Demand Paging:

• Random access pattern: Pages may be loaded from anywhere in the file
• Small transfer size: Each fault loads one page (typically 4 KB)
• Serial dependencies: Cannot start loading next page until current instruction restarts
• No aggregation: Each page is a separate I/O operation

Comparison of I/O Patterns:

The HDD Problem:

Mechanical hard drives have a significant random access penalty:

HDD Performance:
- Sequential read: ~100-150 MB/s
- Random read (4 KB): ~100 IOPS → 400 KB/s

Loading 10 MB of random pages:
- Sequential: 10 MB / 100 MB/s = 100 ms
- Random 4 KB: 2500 IOPS / 100 IOPS = 25 seconds (!)

Pure demand paging on HDDs can be 250x slower than sequential loading for random access patterns. This is why read-ahead is so important for HDD-based systems.

SSD Improvements:

SSD Performance:
- Sequential read: ~500-3000 MB/s (NVMe)
- Random read (4 KB): ~50,000-500,000 IOPS → 200-2000 MB/s

Loading 10 MB of random pages:
- Random 4 KB: 2500 pages / 100,000 IOPS = 25 ms

SSDs make pure demand paging far more practical, but read-ahead still helps by exploiting the even higher sequential throughput.

Despite its drawbacks, there are scenarios where the pure demand paging approach (or something close to it) is optimal.

Scenario 1: Large Programs with Small Working Sets

Consider an IDE with 100 MB of code but only 10 MB active at any time:

• Eager loading: 100 MB always occupied
• Pure demand: 10 MB after warmup
• Benefit: 90 MB saved for other processes

The key insight: if usage is sparse relative to size, demand paging wins.

Scenario 2: Rarely-Run Utilities

Command-line tool invoked once:

Eager loading:
  Load 5 MB          →  500 ms
  Execute               10 ms
  Exit                      -
  Total:                 510 ms (5 MB loaded, ~1 MB used)

Pure demand:
  Load ~1 MB pages  →  100 ms
  Execute               10 ms
  Exit                      -
  Total:                 110 ms (1 MB loaded)

For short-lived processes, pure demand paging can actually be faster because it loads less data.

Scenario 3: Fork and Exec Patterns

Traditional Unix pattern:
  fork()   → Create child with copy of parent
  exec()   → Replace child with new program

With pure demand paging:
  fork():
    - No copying! Just create page table with COW
    - Instantaneous (no memory touched)
  
  exec():
    - Discard all COW references
    - Set up new page table (everything non-present)
    - Child's parent-inherited pages were never loaded

Pure demand paging + COW makes fork+exec extremely efficient. The child never pays for pages it will immediately discard.

There are equally important scenarios where pure demand paging performs poorly, and practical systems must use alternatives.

Scenario 1: Long-Running Startup-Intensive Applications

Web browser startup:

  Pure demand paging:
    1000+ page faults during initialization
    User stares at blank window for 5+ seconds
    Every click during warmup causes new faults
    
  With prefetching:
    Predict common startup pages
    Stream 50 MB during splash screen display
    Application responsive in 1-2 seconds

Scenario 2: Predictable Access Patterns

Sequential file processing:

  Pure demand paging:
    Read page 0: fault, load, process
    Read page 1: fault, load, process
    Read page 2: fault, load, process
    ... (one fault per page, I/O latency on each)
    
  With read-ahead:
    Read page 0: fault, load pages 0-15, process page 0
    Read page 1: already loaded, process immediately
    Read pages 2-15: already loaded
    Read page 16: fault, load pages 16-31
    ... (one fault per 16 pages)

Sequential access with read-ahead is an order of magnitude faster.

Scenario 3: Real-Time Audio/Video Processing

Audio processing requirements:
- Buffer size: 128 samples
- Sample rate: 48 kHz
- Deadline: 128/48000 = 2.7 ms per buffer

Page fault during processing:
- SSD latency: 50-200 μs (acceptable... barely)
- HDD latency: 5-15 ms (BUFFER UNDERRUN! Audio glitch!)

Solution: Wire pages in memory (mlock) to prevent any faults

Real-time systems cannot tolerate the unpredictability of demand faults.

No production operating system uses pure demand paging exactly as described. However, understanding the pure model helps us appreciate what optimizations real systems add.

Linux Approach:

Linux uses demand paging as the foundation but adds significant optimizations:

• Read-ahead: When a page fault occurs, the fault handler may initiate async loading of adjacent pages
• Fault-around: Map additional pages that are already in page cache, even if not faulted
• madvise hints: Applications can request specific prefetching behavior
• Page cache prefetch: Background readahead based on detected patterns

Windows Approach:

Windows uses a more aggressive prefetching strategy:

• Prefetcher: Monitors access patterns, preloads at application startup
• SuperFetch: Machine learning to predict and preload pages
• Working set estimation: Proactive working set establishment
• Boot optimization: Prefetch files accessed during boot

Pure demand paging represents one extreme on a spectrum of paging strategies. Understanding its trade-offs helps us make informed decisions.

The Core Trade-off:

         Memory Efficiency ◄─────────────────────► Startup Performance
                ▲                                          ▲
                │                                          │
        Pure Demand                               Eager Loading
           Paging                                   + Prefetch

Each position on this spectrum has costs and benefits:

Decision Framework:

Choose more toward pure demand when:

• Memory is severely constrained
• Process lifetime is short
• Working set is small relative to executable size
• Storage is fast (NVMe SSD, RAM disk)
• Multiple short-lived processes compete for memory

Choose more toward prefetching when:

• Fast startup is critical for user experience
• Access patterns are predictable
• Working set is close to executable size
• Storage is slow (HDD)
• Long-running processes that will access most pages anyway

Choose wired pages when:

• Real-time guarantees required
• Latency variance is unacceptable
• Failed page fault would be catastrophic

We've examined pure demand paging—the extreme lazy loading strategy. Let's consolidate the key insights:

What's Next:

Having explored the extreme of pure demand paging, we'll now examine its counterweight: prepaging. Prepaging attempts to preemptively load pages before they're needed, trading memory efficiency for reduced fault rates and faster initial performance. Understanding both extremes helps us appreciate the practical middle ground that real systems occupy.