Skip to content
Tutorials Center
My learning

Topics

Lesson 42 of 66 ยท Virtual Memory

Virtual Memory, Demand Paging and Page Fault Handling

Understand virtual memory, demand paging, what happens on a page fault, how page faults hurt effective access time, and why locality of reference makes it all work.

Everything so far assumed that a process must be entirely in memory to run. That is wasteful: most programs never use all their code (error handlers, rarely used features), arrays are declared larger than needed, and a program that is bigger than RAM could not run at all.

Virtual memory removes the requirement. Only the pieces of a process that are actually needed live in RAM; the rest stay on disk. The program sees a large, private, continuous virtual address space, often far larger than the physical memory. Benefits:

  • A program can be bigger than physical memory.
  • More programs fit in memory at once, so the CPU is used better.
  • Starting a program is fast: only its first pages need to be loaded.
  • Processes can share memory and files easily (see copy-on-write and memory mapping).

Demand paging

The usual implementation is demand paging: a page is brought into memory only when it is first used, like loading a book chapter only when you open it. Pages that have never been touched never leave the disk. A system that starts a process with no pages in memory at all and loads each on first access is doing pure demand paging.

The page table's valid bit drives it:

  • valid (1): the page is in memory; the entry holds its frame.
  • invalid (0): either the page is not part of the process's address space at all (an illegal access), or it is legal but currently on disk.

Touching a page whose bit is 0 makes the hardware raise a page fault, a trap into the operating system.

Handling a page fault

flowchart TD
    A["1. CPU references an address"] --> B{"2. Valid bit?"}
    B -- 1 --> OK["Access proceeds"]
    B -- 0 --> F["3. Trap to the OS (page fault)"]
    F --> C{"4. Legal address?"}
    C -- no --> K["Terminate the process (segmentation fault)"]
    C -- yes --> D["5. Find a free frame (replace a page if none)"]
    D --> E["6. Read the page from disk into the frame"]
    E --> G["7. Update the page table: frame, valid = 1"]
    G --> H["8. Restart the faulting instruction"]

The faulting instruction is restarted from the beginning, as if nothing had happened.

Details:

  1. The hardware traps; the OS saves the process state.
  2. The OS checks an internal table to decide: invalid reference (kill the process) or a page not yet loaded.
  3. It finds a free frame from the free-frame list. If there is none, it uses page replacement to evict a victim page (writing it to disk first if dirty).
  4. It schedules a disk read for the page. While waiting, another process runs.
  5. When the read finishes, it updates the page table and the OS's tables.
  6. It puts the process back on the ready queue. When scheduled, it restarts the instruction that faulted.

Instruction restart can be tricky for instructions that touch several addresses (a block-copy instruction may fault halfway). Hardware solves it by checking all addresses first or by saving enough state to resume.

Not every page fault is a disk read

Kind Cause Cost
Minor (soft) Page is in memory but not mapped yet (e.g. shared library already loaded by another process, or just allocated zero page) Microseconds
Major (hard) Page must be read from disk or SSD Milliseconds (spinning disk) or about 100 microseconds (SSD)
Invalid Illegal address Process receives a signal and dies

What a page fault costs

Let p be the page-fault rate (probability that a memory access faults), m the memory access time and f the fault service time.

EAT = (1 - p) x m + p x f

Suppose m = 200 ns and a fault costs 8 ms (a hard disk): f = 8,000,000 ns. Then EAT = 200 + 7,999,800 x p ns. If one access in 1,000 faults, p = 0.001 and EAT is about 8,200 ns, 40 times slower. To slow the program by less than 10% (EAT under 220 ns), p must be below 0.0000025: fewer than one fault per 400,000 accesses.

Python How rare must page faults be?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Only an extremely low fault rate keeps a demand-paged system fast, and that is only possible because of locality.

Why it works: locality of reference

Programs do not touch memory at random. They show:

  • Temporal locality: an address used now will probably be used again soon (loop counters, hot functions).
  • Spatial locality: addresses near a recently used address will probably be used soon (arrays, sequential instructions).

At any moment a program needs only a small working set of pages. Once those are loaded, faults become rare. We simulate a demand-paged process with 6 frames and a trace that moves between phases.

Python Watching faults happen on demand

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The faults bunch up at the beginning of each phase while its pages are being loaded, then disappear. The program without locality faults constantly. Programs written with locality in mind (traversing a 2-D array row by row rather than column by column, for instance) run much faster for exactly this reason.

  • Pre-paging brings in pages the process is likely to need before it asks (for example the pages following the one that just faulted), reducing the number of faults at the cost of possibly wasted work.
  • Page-fault frequency and working-set methods decide how many frames each process deserves (thrashing lesson).
  • Swap space is the disk area used for pages that have no file behind them (heap, stack). Code pages can be read straight from the executable file and simply discarded when evicted, since a copy exists.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is demand paging?

    Pages stay on disk until a reference to them causes a page fault.
  2. 2. What does a page fault trigger?

    The MMU raises a trap, and the kernel's page-fault handler decides what to do.
  3. 3. After the OS loads the missing page, what happens to the faulting instruction?

    The instruction is re-executed from the start; this time the page is present.
  4. 4. m = 100 ns, fault service time 10 ms, fault rate 1 in 100,000 accesses. What is the EAT, roughly?

    EAT = 0.99999 x 100 + 0.00001 x 10,000,000 = about 100 + 100 = 200 ns: even a rare fault can double the average time.
  5. 5. Why does demand paging work in practice?

    Temporal and spatial locality keep the number of distinct pages needed at any moment small.

Summary

  • Virtual memory lets programs be larger than RAM and run with only part of their pages resident.
  • Demand paging loads a page on first use; the valid bit marks pages not in memory, and touching one causes a page fault.
  • The handler checks legality, finds a frame (replacing a page if needed), reads the page, updates the table and restarts the instruction.
  • EAT = (1 - p) m + p f: faults must be extremely rare to avoid a big slowdown.
  • Locality of reference is what keeps real fault rates low.

Next: Page Replacement Algorithms