Demand Paging and Segmentation

When you launch a modern web browser, it springs to life in under a second despite being hundreds of megabytes in size. When you open a 10 GB video file in an editor, it appears instantly rather than making you wait for the entire file to load. These experiences—so fundamental to modern computing that we take them for granted—are enabled by demand paging (and historically, demand segmentation).

Demand paging is the mechanism that makes virtual memory practical. Rather than loading an entire program and all its data into memory before execution can begin, the operating system loads pages on demand—only when they're actually accessed. This lazy loading strategy is the key that unlocks virtual memory's power to exceed physical memory limits while providing responsive program startup.

This page provides a comprehensive examination of demand paging and its segmentation counterpart, covering the mechanisms, variants, design decisions, and practical implications that every systems engineer should understand.

Demand loading is a resource management strategy based on a simple principle: don't load something until you actually need it. This principle applies broadly in computing (lazy evaluation, just-in-time compilation), but in memory management, it takes a specific form.

The alternative: Eager loading

Eager (or anticipatory) loading means loading all resources before they're used. For memory, this would mean:

1. When a program starts, load every page of the executable
2. Load every page of every shared library
3. Pre-allocate and zero all heap space the program might use
4. Pre-extend the stack to its maximum size

This approach is simple but wasteful—most programs never touch the majority of their address space.

The demand paging strategy:

Demand paging makes the opposite choice:

1. When a program starts, create page table entries for its entire virtual address space, but mark them as not present (not in physical memory)
2. Load zero or minimal pages initially
3. When the program accesses any address, check if that page is present
4. If not present, trigger a page fault and load the page from its backing store
5. Resume execution after the page is loaded

This strategy trades consistent performance for better average-case performance and dramatically lower memory usage.

Let's trace through exactly what happens when a process accesses a page that isn't currently in physical memory. This is the core mechanism of demand paging.

Prerequisites for demand paging:

1. Valid-invalid bit (present bit) — Each page table entry has a bit indicating whether the page is in physical memory
2. Page fault exception — The CPU generates an exception when accessing a non-present page
3. Backing store — A place to store pages not currently in RAM (swap, executable file, etc.)
4. Restartable instructions — The CPU must be able to restart the faulting instruction after the fault is handled

The valid-invalid bit (also called the present bit) is a single bit in each page table entry that indicates whether the page is currently in physical memory. It's the fundamental trigger for demand paging.

Terminology clarification:

Different systems use different terms:

• Intel x86: Present bit (P bit) — 1 if page is in RAM
• Academic texts: Valid-invalid bit — 1 = valid (in RAM), 0 = invalid (not in RAM)
• Some texts: Resident bit — whether page is resident in memory

These all refer to the same concept: does the page table entry point to a physical frame that currently holds this page's data?

What happens when P = 0:

When the CPU's MMU encounters a page table entry with P = 0 during address translation:

1. Hardware stops the translation — Can't proceed without a valid frame number
2. Page fault exception generated — CPU raises exception #14 (Page Fault) on x86
3. Faulting address saved — The address that caused the fault is stored in CR2
4. Error code pushed — Indicates read/write, user/supervisor, cause
5. Control transfers to OS — Kernel page fault handler takes over

Why P = 0 is not always an error:

A page with P = 0 might be:

• A valid page that's been swapped out (demand paging in action)
• A valid page that's never been loaded yet (first access)
• A copy-on-write page waiting for its first write
• A truly invalid page (bad pointer, stack overflow into guard page)

The OS must examine its own data structures to determine which case applies.

Pure demand paging is the extreme form of lazy loading: no pages are loaded until they generate a fault. When a process starts under pure demand paging, it has zero pages in memory—even the first instruction of the program must be faulted in.

How pure demand paging works at startup:

Advantages of pure demand paging:

• Minimum startup delay — Process begins immediately, no waiting for loading
• Minimum memory usage — Only accessed pages ever load
• Maximum sharing opportunity — Pages only brought in when needed, can check if already in cache

Disadvantages of pure demand paging:

• High initial fault rate — First access to every page faults, causing I/O
• Poor initial performance — Early execution is slow due to fault storms
• I/O overhead — Many small I/O operations instead of fewer large ones

When pure demand paging makes sense:

• Memory is extremely constrained
• Programs are short-lived and may not use much memory
• System prioritizes fast startup over initial runtime performance

Pure demand paging, while theoretically elegant, is rarely used in practice. Real systems employ various optimizations to reduce the initial fault storm while retaining demand paging's benefits.

Prepaging (Anticipatory Paging):

Prepaging loads some pages before they're accessed, anticipating that they'll be needed soon. This trades some memory usage for reduced fault rate.

Clustered paging (fault clustering):

When a page fault occurs, the OS loads not just the faulted page but also several adjacent pages. The rationale: if a program is accessing page N, it likely will access pages N+1, N+2, etc. (spatial locality).

Linux's readahead mechanism is a form of clustered paging for file-backed pages:

Default cluster size: 128-256 KB (32-64 pages for 4K pages)
Adaptive: Increases cluster size if sequential access detected
Benefit: Single I/O operation loads many pages
Risk: Wastes memory if prediction wrong

Working set prepaging:

Some systems track each process's working set and save it when the process is swapped out or hibernated. On resume, the entire working set is preloaded, eliminating the warm-up period.

Windows SuperFetch/Prefetch and macOS's similar features use this approach:

• Monitor page access patterns over time
• At boot/app launch, prefetch predicted pages
• Can dramatically reduce perceived startup time

While demand paging is the dominant technique today, an alternative approach—demand segmentation—played an important historical role and still informs understanding of virtual memory.

What is demand segmentation?

Demand segmentation applies the lazy loading principle to segments rather than pages. Instead of dividing memory into fixed-size pages, segmentation divides it into variable-size logical units (code segment, data segment, stack segment, etc.).

Under demand segmentation:

• Entire segments are loaded as units
• If a segment isn't resident and is accessed, a segment fault occurs
• The entire segment is loaded from disk
• Segments can be swapped out as units

Why demand paging won:

Demand paging has largely replaced demand segmentation for several reasons:

1. Finer granularity — Loading one 4 KB page is faster than loading a 100 KB segment
2. No external fragmentation — Fixed-size pages fit neatly into fixed-size frames
3. Better memory utilization — Can evict cold parts of a segment while keeping hot parts
4. Simpler implementation — Fixed-size units simplify allocation, replacement, and hardware

Where segmentation still matters:

While pure demand segmentation is obsolete, segmentation concepts persist:

• x86 uses segments for memory protection (though with flat memory model)
• Process address space is still conceptually divided into segments (text, data, stack)
• Some systems combine segmentation and paging (segmented paging)
• Intel's MPX (Memory Protection Extensions) used segment-like bounds checking

Not all page faults are equal. Understanding the different types helps in performance analysis and system tuning.

Classification by severity:

Minor (soft) faults:

A minor fault occurs when the page exists in physical memory (perhaps in the page cache or another process's mapping) but isn't yet mapped in the faulting process's page table. The handler just needs to update the page table—no disk I/O required.

Common causes:

• First access to a demand-zero page (allocate frame, zero it, map it)
• Accessing a shared library page that's already in the page cache
• Copy-on-write: accessing a shared page with write intent (copy then map)

Major (hard) faults:

A major fault requires disk I/O to bring the page into memory. This is the expensive case—potentially 10,000× slower than a minor fault.

Common causes:

• First access to a file-backed page (read from file)
• Accessing a page that was swapped out (read from swap)
• Accessing code in an executable that wasn't yet loaded

Monitoring page faults: