Virtual Memory & Demand Paging — Page Faults, EAT, Copy-on-Write

The Story That Explains Virtual Memory

Introduction to Virtual Memory

Traditional memory management demanded that the entire program fit in physical memory before it could run. This wastes RAM (unused error handlers, rarely triggered code paths) and limits program size to available RAM. Virtual Memory throws that assumption away.

Demand Paging — Only Bring In What's Needed

Demand paging is the concrete technique that makes virtual memory work. Simple rule: a page is loaded into physical memory only when the CPU actually references it. Not before. Not speculatively. Only when demanded.

The Valid/Invalid Bit

Every page table entry gets a new bit: the valid bit (v/i). It doesn't mean "is this a legal address in this process's space" — it means "is this page currently in physical memory."

🎮 Interactive — Detecting a Page Fault

Page table with a mix of valid and invalid entries. Watch how the MMU treats each access.

Page Fault Handling — What the OS Actually Does

When the valid bit is clear, the hardware traps to the OS. The OS then executes a carefully choreographed sequence to bring the missing page into memory and restart the instruction.

# Page fault service routine (simplified from Galvin)

def page_fault_handler(faulting_address):
    # Step 1: check if reference is legal
    if not in_process_address_space(faulting_address):
        terminate_process("SIGSEGV")
        return

    # Step 2: locate the page on the backing store (disk)
    disk_location = find_page_on_disk(faulting_address)

    # Step 3: find a free frame in physical memory
    frame = get_free_frame()
    if frame is None:
        frame = page_replacement()      # evict a victim first

    # Step 4: read the page from disk into the frame
    disk_read(disk_location, frame)  # this is slow — millions of cycles

    # Step 5: update the page table
    p = faulting_address / PAGE_SIZE
    PageTable[p].frame = frame
    PageTable[p].valid = True

    # Step 6: restart the faulted instruction
    restart_instruction()

🎮 Interactive — Page Fault Handling, Step by Step

Pure Demand Paging vs Prepaging

Effective Access Time (EAT) for Demand Paging

With demand paging, the vast majority of accesses hit RAM at normal speed (memory access time ma). Occasionally a page fault occurs and costs the huge disk service time (millions of times slower).

Numerical Problem 1 — Compute Effective Access Time

Given

Part (a) — Fault Rate = 0.001 (one in 1000)

EAT = 0.999 × 200 + 0.001 × 8 000 000
    = 199.8 + 8000
    = 8199.8 ns
    ≈ 8.2 μs

Slowdown = 8199.8 / 200 ≈ 41×

Part (b) — Fault Rate = 0.0001 (one in 10 000)

EAT = 0.9999 × 200 + 0.0001 × 8 000 000
    = 199.98 + 800
    = 999.98 ns ≈ 1 μs

Slowdown ≈ 5×

Part (c) — What Fault Rate Keeps Slowdown Under 10%?

We want EAT ≤ 1.1 × ma = 220 ns:

EAT ≤ 220
(1 − p) × 200 + p × 8 000 000 ≤ 220
200 − 200p + 8 000 000p ≤ 220
7 999 800p ≤ 20
       p ≤ 20 / 7 999 800
       p ≤ 2.5 × 10⁻⁶
       p ≤ 1 in 400 000 accesses

Numerical Problem 2 — Address Translation with Page Faults (Interactive)

Setup: Page size = 1024 bytes. Process has 8 pages logically. Page table below (some pages are in RAM, some are still on disk):

Copy-on-Write — A Beautiful Optimisation

When a process forks (creates a child), the child normally gets an identical copy of the parent's address space. Naively, this means duplicating potentially gigabytes of memory — even if the child immediately calls exec() and throws it all away.

Real-World Applications

Golden Rules — Virtual Memory & Demand Paging