Demand Paging

Introduction

Why load an entire program into memory when you might only use a small fraction of it? Microsoft Word has features for mail merge, equation editing, and macro programming that most users never touch. Loading all that code into RAM wastes precious memory. Demand paging solves this by loading pages only when they are actually accessed — a lazy approach that says "do not bring it in until someone asks for it."

Demand paging is the implementation strategy behind virtual memory. Instead of loading all pages of a process into RAM at startup, pages are loaded on demand — only when the process actually references them. This means a process can start executing with very few (or even zero) pages in memory.

How Demand Paging Works

Each page table entry has a valid-invalid bit:

• Valid (v): Page is in physical memory — access it normally
• Invalid (i): Page is NOT in memory (either on disk or does not exist)

When a process starts, all pages are marked invalid. As the process executes and accesses different pages, they are brought in one by one through page faults.

Page Fault Handling — Step by Step

Critical Detail: Instruction Restart

The CPU must be able to restart the exact instruction that caused the page fault. This is non-trivial for complex instructions (like block move in x86 that spans page boundaries). The hardware must save enough state to allow transparent restart after the page is loaded.

Pure Demand Paging

In pure demand paging, NO pages are loaded at process startup. The process begins with an empty page table (all invalid). The very first instruction causes a page fault, loading the first code page. Each subsequent page is loaded only as the process touches it.

While this starts with many faults, the locality principle means the page fault rate drops quickly as the working set is established.

Performance of Demand Paging

The critical formula:

For acceptable performance (less than 10% degradation):

This shows why page replacement algorithms and locality are so important — the fault rate must be astronomically low.

Prepaging (Anticipatory Paging)

Pure demand paging suffers from high initial fault rates. Prepaging loads pages that are likely to be needed soon, before they are actually referenced:

• Load multiple contiguous pages when one faults (spatial locality)
• When a swapped-out process resumes, bring back its entire working set
• Predictive algorithms based on access patterns

The risk: if prepage pages that are not actually used, you waste I/O bandwidth and memory.

Handling Page Faults with No Free Frames

When a page fault occurs but all frames are occupied, the OS must evict a page to make room. This is where page replacement algorithms come in (FIFO, LRU, Optimal — covered separately). The evicted page is written to disk only if it has been modified (dirty bit = 1); otherwise, it is simply discarded.

Real-World Analogy

Demand paging is like a just-in-time manufacturing system. A factory does not stock every possible part in its workshop (that would require a warehouse-sized workshop). Instead, parts are ordered from the warehouse only when needed for the current assembly step. Most of the time, the needed parts are already on the workbench (in RAM — TLB hit). Occasionally, a part must be fetched from the warehouse (page fault — slow but tolerable if rare).

Key Takeaways

• Demand paging loads pages only when accessed, not at process startup
• Page faults trigger when accessing pages not currently in RAM (valid bit = invalid)
• Page fault handling involves disk I/O (~8ms), making faults extremely expensive
• For acceptable performance, page fault rate must be below 1 in 800,000 accesses
• Pure demand paging starts with zero pages loaded — high initial faults but stabilizes quickly
• Prepaging anticipates needed pages to reduce initial fault bursts
• The principle of locality keeps page faults rare in normal program execution