1. The Virtual Memory Abstraction: Demand Paging

1.1 Physical Frames and Virtual Pages

Operating systems split physical RAM into fixed-size blocks called frames, and virtual address spaces into blocks of the same size called pages (typically 4KB in size). When a process executes, the kernel maps virtual pages to physical frames using a page table. Under Demand Paging, pages are only loaded into RAM when they are referenced by an active thread. This saves physical memory when processes only execute subset instructions.

However, if the process working set (the set of pages actively used in a time window) exceeds the allocated physical frames, the system must continually evict pages to load new ones. Choosing which page to evict is the responsibility of the OS page replacement policy.

1.2 Paging vs Segmentation

Paging uses fixed-size memory blocks to prevent external fragmentation. Segmentation uses variable-size blocks matching logical code structures, requiring compaction under fragmentation.

Common Misconception — Paging eliminates memory fragmentation: A common developer misconception is that paging completely eliminates memory fragmentation. While paging eliminates external fragmentation (since any page can fit into any physical frame), it still suffers from internal fragmentation. If a process requires only 1 byte of memory but is allocated a full 4KB page, the remaining 4095 bytes are wasted.

2. Anatomy of a Page Fault

2.1 The Interrupt Pipeline

When a CPU instruction references a virtual address, the Memory Management Unit (MMU) translates it using the page table. If the page's valid bit is set to 0, it means the page is not in physical RAM. This triggers a page fault interrupt. The CPU halts the process execution, switches to kernel mode, and transfers control to the OS page fault handler.

The handler locates the target page on disk, finds an empty physical frame in RAM, reads the page bytes into the frame, updates the page table mapping, and resumes the process instruction. If no physical frames are empty, the handler must run a page replacement algorithm to evict an active frame first.

Mermaid Diagram: The hardware and kernel interrupt path when a process references a page that is not present in RAM.

3. The First-In-First-Out (FIFO) Algorithm and Belady's Anomaly

3.1 Evicting the Oldest Page

The First-In-First-Out (FIFO) algorithm is the simplest page replacement policy. The OS maintains a queue of all page frames currently loaded in RAM. When a page must be replaced, the page at the head of the queue (the oldest page loaded) is evicted, and the new page is added to the tail of the queue.

While simple to implement (requiring only a FIFO queue structure), FIFO ignores page access patterns. It often evicts heavily used global library pages simply because they were loaded first, leading to immediate page faults on subsequent instructions.

4. The Least Recently Used (LRU) Algorithm

4.1 Exploiting Temporal Locality

The Least Recently Used (LRU) algorithm approximates optimal replacement by assuming that page access patterns exhibit strong temporal locality: pages that have been referenced recently are highly likely to be referenced again in the near future. When a page must be replaced, LRU evicts the page that has not been referenced for the longest period of time.

While highly efficient, implementing true LRU in hardware or software is expensive. It requires tracking reference timestamps on every memory instruction, which introduces overhead to the critical path of CPU cache access.

5. The Clock (Second Chance) Algorithm

5.1 Approximating LRU with Low Overhead

To avoid the overhead of tracking timestamps, modern operating systems approximate LRU using the Clock (Second Chance) algorithm. The OS structures page frames in a circular queue, resembling a clock face. A clock hand points to the next frame to evaluate. Each page frame has an associated **reference bit** set to 1 by the MMU hardware whenever the page is read or written.

When a page fault occurs, the clock hand sweeps clockwise. If the referenced page frame has a reference bit of 1, the hand resets the bit to 0 and gives the page a "second chance," moving to the next frame. If the reference bit is 0, that page is chosen for eviction, and the clock hand moves past it.

5.2 Clock Hand Sweeping Arithmetic and the Two-Pass Dirty Bit Extension

The Clock algorithm traverses physical memory frames using modular pointer indexing. Let $N$ be the number of physical frames allocated to the process, let $idx$ be the index of the clock hand, and let $R[i]$ and $D[i]$ represent the reference and dirty bits for frame $i$ respectively. During a page replacement sweep, the hand index updates sequentially:

In its basic form, the algorithm only checks the reference bit $R[idx]$. If $R[idx] == 1$, the engine sets $R[idx] \leftarrow 0$ and increments the pointer. If $R[idx] == 0$, the page at $idx$ is selected for eviction.

To minimize slow disk writebacks, modern operating systems (like Linux) utilize a **Two-Pass (Dirty Bit) Clock Algorithm**. This extension evaluates the pair $(R, D)$ to prioritize evicting clean pages that require zero disk write latency. The clock hand performs up to four sweep sweeps with different search criteria:

• **Pass 1**: Search for a frame with $(R=0, D=0)$. During this sweep, do not modify any reference bits. If found, evict immediately.
• **Pass 2**: If Pass 1 fails, search for a frame with $(R=0, D=1)$. During this sweep, set the reference bit $R \leftarrow 0$ for all visited frames. If found, write to disk and evict.
• **Pass 3**: If Pass 2 fails, repeat Pass 1. Since reference bits were cleared during Pass 2, a frame with $(R=0, D=0)$ is guaranteed to be found.

This priority model ensures that pages that are both unreferenced and clean are evicted first, dramatically reducing disk write queues. Below is a comparison table of Clock sweep states:

Pitfall — Over-sweeping the clock hand: If all pages in memory are actively referenced ($R=1$ for all frames), the clock hand must sweep the entire circular queue once, clearing all reference bits to $0$, before evicting the first page. This makes the replacement search latency $O(N)$ instead of $O(1)$. If this occurs frequently, it indicates that the process needs more physical RAM allocation.

6. The Optimal (MIN) Algorithm

6.1 The Theoretical Limit

The Optimal (MIN) algorithm replaces the page that will not be used for the longest period of time in the future. This algorithm guarantees the lowest possible page fault rate for a given number of frames.

However, because the operating system cannot predict the future execution path of arbitrary programs, the optimal algorithm cannot be implemented in practice. It is used exclusively as a theoretical benchmark during offline analysis to evaluate the efficiency of real-world algorithms.

7. Advanced: Page Table Reference Bits and Hardware Assistance

7.1 Hardware-Software Interface

The MMU hardware interacts with the OS kernel by updating bits inside the page table entry (PTE). The most important bits are: (1) **Reference Bit**: set to 1 by the hardware when a page is accessed. (2) **Dirty Bit**: set to 1 by the hardware when a page is written to. If a dirty page is evicted, it must be written back to disk first, which is slower than evicting a clean page.

The OS periodically clears the reference bits to track which pages are actively used in the current time window, allowing the scheduler to detect inactive processes.

7.2 Translation Lookaside Buffer (TLB) and Effective Memory Access Time (EMAT)

To speed up address translation, the CPU utilizes a small, high-speed hardware cache called the **Translation Lookaside Buffer (TLB)**. The TLB caches recent virtual-to-physical address mappings. When the CPU references a memory address, it first queries the TLB. A TLB hit resolves the translation in less than $1$ nanosecond, bypassing page table lookups.

If the mapping is missing (a TLB miss), the MMU must perform a multi-level page table walk, traversing up to 4 or 5 levels of page directories in physical memory. Let $h$ be the TLB hit ratio, let $c_{\text{TLB}}$ be the TLB lookup latency (typically $\approx 1$ ns), let $m$ be the physical memory access latency (typically $\approx 100$ ns), let $p$ be the page fault rate, and let $S_{\text{fault}}$ be the page fault service latency (typically $\approx 8$ milliseconds). The **Effective Memory Access Time (EMAT)** is calculated as:

Where $k$ represents the number of page table levels traversed during a page walk (e.g. $k=4$ in x86-64 paging systems). Because $S_{\text{fault}}$ is measured in milliseconds, even a tiny page fault rate (such as $p = 0.001$, or 0.1%) will cause EMAT to balloon by thousands of percentage points, introducing visible system lag:

When the page replacement algorithm evicts a page, the OS kernel must invalid the mapping in the page tables. Crucially, the OS must also flush the obsolete translation from the TLB caches of all CPU cores. In multi-core systems, this is coordinated via an inter-processor interrupt (IPI) sequence known as a **TLB Shootdown**. Below is a comparison table of address translation latency stages:

Pitfall — Thrashing via context switches: When EMAT increases due to page faults, the OS scheduler attempts to mask the latency by switching to another thread. However, if that thread also page faults, the system enters a thrashing loop, spending all its time performing context switches and TLB shootdowns without executing progress.

8. Advanced: Comparison of Page Eviction Profiles

8.1 Eviction Strategy Matrix

The table below compares the implementation complexity, performance, and hardware requirements of different page replacement algorithms:

Pitfall — Overlooking dirty page writeback delays: Evicting a dirty page (modified since loaded) is twice as slow as evicting a clean page because the dirty page must be written to disk. Real-world Clock algorithms track dirty bits and prioritize evicting clean pages first, avoiding disk write bottlenecks.

9. Complete LRU Cache / Page Frame Simulator Implementation

9.1 The JavaScript Code

The following JavaScript class implements an LRU page simulator, combining a hash map and a doubly-linked list to achieve $O(1)$ page lookups and evictions:

10. Interactive: Page Replacement Simulator

Click "Reference Page" to access page frames sequentially. Watch how the replacement algorithm evicts old pages to load new ones:

Page Faults vs Frames Allocated (Belady's Anomaly)

The chart below compares the total page fault counts for FIFO and LRU algorithms as the number of allocated physical frames increases, illustrating Belady's Anomaly under FIFO:

12. Frequently Asked Questions