Demand Paging

What demand paging is

Demand paging is the lazy loading strategy for virtual memory. Pages are not loaded into physical memory until they are actually referenced (demanded) by the CPU. The alternative — loading all pages at programme start — wastes time loading code that may never execute (error handlers, rarely-taken branches) and wastes memory on data that may never be touched.

In a demand-paged system, the page table starts with every entry marked not present (P = 0). When the CPU accesses a page for the first time, the MMU raises a page fault. The kernel’s page-fault handler:

1. Checks whether the faulting address is valid (within the process’s virtual address space). If not, the process is terminated with SIGSEGV.
2. Finds a free frame from the free-frame list.
3. Reads the page from disk (from the executable file for code, from swap for previously-evicted data, or allocates a zero-filled page for the heap/stack).
4. Updates the page table to point the faulting page to the newly-allocated frame, with P = 1 and appropriate permissions.
5. Restarts the faulting instruction. This time, the translation succeeds and the instruction completes normally.

The process is unaware that the fault occurred (beyond the timing delay of disk I/O).

Pure demand paging vs prepaging

• Pure demand paging: the process starts with zero pages in memory. Every page faults in. The initial flurry of page faults (cold-start or working-set build-up) can cause a burst of disk I/O.
• Prepaging: the OS guesses which pages will be needed and brings them in before they are demanded. Prepaging reduces the initial page-fault burst but risks wasting I/O on pages that are never used.

Most systems use a hybrid: the loader brings in the first few pages of code (entry point, global constructors) and the rest is demand-paged.

Page-fault handling steps (detailed)

1. Trap: The MMU detects that the P bit is 0 on the PTE for the faulting virtual address.
2. State save: The CPU saves the faulting instruction’s address and the virtual address (in CR2 on x86) and enters the kernel.
3. Validation: The kernel checks that the virtual address belongs to a valid region of the process’s address space. If it’s a wild pointer, the kernel sends SIGSEGV and does not return to the instruction.
4. Frame allocation: If the free-frame list is empty, the kernel must evict a page (page replacement). It selects a victim frame, writes it to disk if dirty, and reclaims it.
5. Disk I/O: The kernel issues a disk read to bring the required page into the frame. The process blocks (or another process runs) during this I/O.
6. Page-table update: The kernel writes the frame number into the PTE, sets P = 1, and sets appropriate permission bits.
7. TLB invalidation: If the old PTE was cached in the TLB (stale not-present), the kernel invalidates that TLB entry.
8. Return: The kernel restores the saved state and resumes the faulting instruction.

Modified (dirty) pages

When the page-fault handler reclaims a frame, it checks the D (Dirty) bit of the evicted page:

• D = 0 (clean): the page has not been modified since it was brought in. Its contents match the copy on disk (executable code, or a previously-loaded data page that was never written). The frame can be reused immediately — no disk write needed.
• D = 1 (dirty): the page has been written. Its contents must be written back to the swap area or file before the frame can be reused. This adds a full disk write to the page-fault service time.

The proportion of dirty pages is one of the most important factors in page-fault handling cost. Clean pages are free to evict; dirty pages are expensive.

EAT with demand paging

The Effective Access Time formula from the paging notes extends naturally to demand paging: the page-fault service time replaces the page-table-walk time:

$\text{EAT} = (1 - p) \times T_\text{mem} + p \times T_\text{page-fault}$

where $p$ is the page-fault rate and $T_\text{page-fault}$ includes disk seek, transfer, and any eviction-write time. For a disk with 8 ms average service time and 80 ns memory: $p$ must be less than $\frac{1}{400{,}000}$ to keep EAT under 100 ns (as worked in the paging examples note).

Summary

• Demand paging loads pages lazily, reducing memory waste and start-up latency.
• The first access to each page triggers a page fault; the kernel brings the page in, updates the page table, and resumes.
• Clean pages are free to evict; dirty pages require a disk write first.
• The page-fault rate must be vanishingly small for demand paging to be viable.