Page Faults and Page Replacement in Virtual Memory Systems

Verified Sources

Nov 4, 2026

A page fault occurs when the CPU attempts to access a virtual memory page whose contents are not present (or not valid) in main memory, so the operating system must handle the missing page before the access can complete. In demand paging, the OS typically delays bringing pages into RAM until they are actually needed, and a page fault is the mechanism that triggers this on-demand transfer from secondary storage into memory.

At a systems level, a page fault indicates that the address translation for the requested virtual page cannot be satisfied by the current page table state (e.g., the entry is invalid/not-present), so the OS must (1) locate the needed page (from a file-backed mapping or swap), (2) load it into a physical frame (possibly evicting another page if memory is full), (3) update the page table, and (4) resume the faulting instruction.

The “significance” of a page fault therefore has two intertwined meanings:

Correctness: it enables the required page to be brought into memory so the program can proceed.
Performance: it reveals a miss in RAM—latency can be much higher because disk (or other backing store) I/O may be required.

Merely having any page fault does not mean “the OS is slow”; page faults are an expected part of virtual memory. However, frequent page faults can indicate a working set larger than available frames or poor locality, leading to heavy paging activity.

Key page-fault and replacement terms

virtual memory
demand paging
page table
working set
page replacement

Note: Below, the replacement algorithms differ in how they choose the evicted “victim” page when the resident set is full.

Virtual Memory & Page Faults (Demand Paging Overview)

How a Page Fault Is Handled (High-Level Algorithm)

1
Step 1
The MMU determines the referenced page is not valid/present, triggering a page-fault exception.
2
Step 2
The OS saves process state and enters the page-fault handler with the faulting address.
3
Step 3
If the faulting page is file-backed, the OS prepares to read it from the mapped file; otherwise it may come from swap.
4
Step 4
If there is a free frame, use it; otherwise invoke the configured page replacement algorithm to pick a victim.
5
Step 5
If the victim page is dirty, the OS writes it back to its backing store before reuse.
6
Step 6
Bring the required page into the selected physical frame.
7
Step 7
Mark the page-table entry as present/valid, then restart the faulting instruction.

What does a page fault signify in terms of locality?

A page fault generally signifies a lack of the needed page in RAM at the moment of reference. More concretely, page faults track the relationship between:

Temporal locality: recently used pages are likely to be used again.
Spatial locality: nearby pages might soon be referenced.
Frame availability: if the number of frames is smaller than the process’s working set, faults increase.

To reason about page replacement algorithms, it helps to view memory frames as holding a set of resident pages, and each page fault occurs when the referenced page is not in that set. Replacement determines which resident page is removed to make room.

Practical interpretation

A page fault is often a feature of demand paging: it trades upfront loading for on-demand loading. The goal is to avoid loading pages that a process never touches.

Performance trap: thrashing

If available frames are far less than the working set size, the process may fault continuously—leading to thrashing (most time spent paging rather than computing).

Core page replacement algorithms (victim selection when RAM is full)

When memory frames are all occupied and a new page must be loaded, the OS must evict one existing page. Different algorithms implement different heuristics for “which page is least worth keeping.”

We’ll cover four major families:

Optimal (OPT)
FIFO
LRU
CLOCK

Also common variants include Second-Chance and working-set inspired strategies, but OPT/FIFO/LRU/CLOCK form the conceptual backbone.

How Replacement Policies Differ Conceptually

Future-aware evictions

OPT (theoretical)

Always evicts the page used farthest in the future."

Past usage evictions

LRU

Evicts the page with the oldest last-use time."

Arrival-order evictions

FIFO / Second-Chance

Evicts based on when pages entered memory (optionally improved by reference checks)."

Approximate LRU in practice

CLOCK

Uses reference bits to approximate recency with low overhead."

Optimal (OPT)

The OPT algorithm evicts the page that will not be used for the longest time in the future. It is optimal (minimum number of faults) among all page replacement algorithms, but it cannot be implemented in practice because it would require perfect knowledge of future references.

FIFO

The FIFO algorithm evicts the page that entered memory earliest. Despite simplicity, FIFO can perform poorly because it ignores both recency and future usefulness. It can also exhibit Belady's anomaly (increasing the number of frames can increase faults for some reference strings), which is a well-known property of FIFO.

LRU

The LRU algorithm evicts the page that has gone unused for the longest time, using “recency” as a proxy for likelihood of near-future reference. Under the stack property intuition, LRU tends to avoid pathological behavior seen in FIFO, and it performs close to OPT on many workloads.

Implementing true LRU exactly requires tracking access history (e.g., via timestamps or linked lists), which can be expensive at large scale, so approximations are often used.

CLOCK (approximate LRU)

CLOCK is a practical approximation to LRU:

Maintain a circular list of frames.
Each frame has a reference bit (often called R-bit).
On reference, set the page’s R-bit to 1.
On replacement, scan frames:
- If a frame has R-bit = 0, evict it.
- If R-bit = 1, clear it and advance the hand. This approximates “evict least recently used” without full historical ordering.

Conceptual Comparison of Victim Selection

Heuristic basis used to choose the evicted page (not measured performance; qualitative).

CLOCK Replacement Procedure (Detailed)

1
Step 1
Frames are arranged in a ring; each frame has a reference bit set when its page is accessed.
2
Step 2
Set the referenced frame's R-bit to 1 (or update it accordingly).
3
Step 3
Begin scanning from the current 'hand' position.
4
Step 4
If R-bit = 0, choose this frame as the victim.
5
Step 5
If R-bit = 1, set it to 0 and advance the hand to the next frame.
6
Step 6
Evict the first frame found with R-bit = 0, load the new page into it, and set its R-bit (typically 1).
7
Step 7
Typically, advance the hand to the next position after installing the new page.

Common Questions and Edge Cases

Knowledge Check

Question 1 of 4

Q1Single choice

A page fault most directly indicates that the referenced page is:

Not currently present (valid) in RAM according to the page table

Always stored in CPU caches

Always caused by memory leaks

Only occurs when the program calls malloc

Explore Related Topics

Virtual Memory, Its Implementation, and the Role of the TLB

Virtual memory abstracts physical RAM by giving each process a large contiguous logical address space, implemented with paging, page tables, and a Translation Lookaside Buffer (TLB) that caches recent translations.

Provides protection, simplifies programming, enables demand paging and sharing of code/pages.
Virtual address = (VPN, offset); physical address = (PFN, offset) with VPN → PFN via TLB or page‑table walk.
Effective access time: $EAT = \alpha (m+\epsilon) + (1-\alpha)(2m+\epsilon)$ , so high TLB hit rate $\alpha$ is critical.
Multi‑level page tables reduce memory use for sparse address spaces.
TLB reach = (entries) × (page size); exceeding it causes TLB thrashing and performance loss.

Cache Memory: Why FIFO and LRU Are Replacement Algorithms

Paging Addressing: Logical vs Physical Bits and Page Table Size

Browse all research articles