Virtual Memory and Page Replacement Algorithms

1. Overview

A. Definition

Virtual memory is an operating-system memory-management technique that gives each process a contiguous, independent address space (virtual address space) decoupled from the size of physical memory, keeping only the portions actually needed for execution resident in physical memory. Its core enabling mechanism is demand paging, and the rule that decides which page to evict when physical memory is full is the page replacement algorithm.

The fundamental idea of virtual memory springs from the observation that "a program need not reside in memory in its entirety at once." Most programs intensively reference only a subset of their code and data at any given moment (locality), so the system works correctly even if only the executing portion stays in physical memory while the rest remains on disk (the swap area). The OS builds this illusion through the MMU (Memory Management Unit) and page tables that translate virtual addresses into physical addresses, and the programmer can work with a large address space with almost no awareness of physical memory capacity.

B. Background and necessity

In early systems, a program could run only if it was loaded into physical memory in full. This constraint produced two severe problems. First, a program larger than physical memory could not run at all, and developers hand-crafted overlays to swap code fragments in and out. Second, the degree of multiprogramming was bound to physical memory capacity, limiting the number of processes that could run concurrently. By "loading only the parts actually needed," virtual memory relieved both constraints at once, making possible both the execution of programs exceeding physical memory and a high degree of multiprogramming.

Above all, virtual memory simplified the programming model itself. Developers can code assuming a clean, contiguous address space starting at address 0, without any concern for where in physical memory their program is loaded or how it shares space with other programs. This is because hardware and the OS handle relocation and protection transparently; without this abstraction, the complexity of compilers, linkers, and loaders would be incomparably greater than it is today.

The necessity has only grown. On a single server hundreds of containers and processes run concurrently, each using several GB of virtual address space while its actual resident set (RSS) is only a fraction of that. Without virtual memory, such dense resource sharing based on overcommit would be impossible. Moreover, the isolation of virtual address spaces becomes the foundation of inter-process protection (one process cannot intrude on another's memory), and core features of modern operating systems—memory sharing of shared libraries, mmap-based file mapping, and Copy-on-Write—all stand on virtual memory.

C. Characteristics

Virtual memory has several essential characteristics. First, transparency: an application need not know that it is being demand-paged. Second, dependence on locality: the performance of virtual memory improves sharply the better the temporal and spatial locality of references is, and collapses when locality breaks down. Third, a tight coupling with disk I/O: when a page fault occurs, a disk access of tens of microseconds to several milliseconds intervenes, incurring latency equivalent to thousands to tens of thousands of CPU cycles. It is precisely this enormous cost gap that makes the quality of the replacement algorithm in lowering the page-fault rate decisive for system performance.

These characteristics stem from the fact that virtual memory is one tier of the memory hierarchy. In the hierarchy running register–cache–main memory–secondary storage, virtual memory corresponds to a mechanism that "uses main memory as a cache for secondary storage." Just as a CPU cache automatically promotes and demotes blocks of main memory, virtual memory promotes pages of the disk into memory, and the notions of locality, replacement, and consistency from caching are reproduced at the page level. The decisive difference is that, because the miss (fault) cost is thousands of times greater than a cache miss, software (the OS) intervenes with sophisticated policy, unlike a cache that is handled entirely by hardware.

2. How Virtual Memory Works

Virtual memory divides into the process of translating virtual addresses into physical addresses and the process of fetching a page from disk when the referenced page is not in physical memory. Below is the overall structure diagram of address translation and demand paging.

flowchart TD
    CPU["CPU: generate virtual address"] --> TLB{"TLB lookup"}
    TLB -->|"hit"| PA["compute physical address"]
    TLB -->|"miss"| PT["page table lookup"]
    PT --> V{"valid bit?"}
    V -->|"1 (resident)"| PA
    V -->|"0 (on disk)"| PF["page fault raised"]
    PF --> OS["OS fault handler"]
    OS --> FREE{"free frame exists?"}
    FREE -->|"yes"| LOAD["load page from disk"]
    FREE -->|"no"| REPL["page replacement algorithm<br/>select victim page"]
    REPL --> DIRTY{"dirty bit?"}
    DIRTY -->|"1"| WB["write back changes to disk"]
    DIRTY -->|"0"| LOAD
    WB --> LOAD
    LOAD --> UPD["update page table and TLB"]
    UPD --> PA
    PA --> MEM["memory access complete"]

The first gateway of address translation is the TLB (Translation Lookaside Buffer). It caches recently used virtual-to-physical translations to complete most accesses in a few cycles, and only on a TLB miss does the slow page-table walk occur (several memory accesses in a hierarchical table). Each page-table entry holds, along with the frame number, the valid bit (resident or not), dirty bit, reference bit, and protection bits, which form the basis for decisions by the replacement algorithm and the protection mechanism.

Address translation hides an important design variable: page size. A small page reduces internal fragmentation but increases the number of page-table entries and TLB pressure, while a large page improves table and TLB efficiency but increases the loss of "loading unneeded regions along with it" and internal fragmentation. That general-purpose operating systems have long kept 4KB as the default is the historical balance point of this trade-off, and the huge pages discussed in Section 5 are a choice to deliberately break this default for specific workloads so as to maximize TLB efficiency.

A. Demand paging and page-fault handling

Demand paging loads a page only at the moment it is referenced. When a page whose valid bit is 0 is referenced, the hardware traps and raises a page fault, and the OS handler processes it in the order ①validate the address → ②secure a free frame (replace if none) → ③load the page from disk → ④update the page table and TLB → ⑤re-execute the faulting instruction. At this point, if the victim page's dirty bit is 1 it must first be written back to disk, requiring two disk I/Os, whereas if it is 0 the write can be skipped—the reason a "clean page" is preferred when selecting a replacement target.

B. Core features virtual memory underpins — CoW and memory mapping

Virtual memory is not merely a device that "expands memory"; it is the foundation on which many core features of modern operating systems stand. A prime example is Copy-on-Write. Because immediately duplicating the parent's entire memory when creating a child via fork() would be enormously costly, the OS lets the two processes share the same physical frame read-only and copies that page only the instant one side attempts a write. This lazy copy cannot be implemented without the translation layer (the page table's protection bits) and the page-fault mechanism, and it eliminates nearly all unnecessary copying in the common pattern of exec right after fork.

Another is memory mapping (mmap). When a file is mapped into the virtual address space, the file is handled by pointer access alone without read/write system calls, the kernel loads only the needed blocks via demand paging, and changes are written back lazily. Multiple processes sharing one copy of physical code for a shared library, and mapping a new heap page onto a shared zero-filled frame via demand zeroing while allocating an actual frame only at write time, all follow the same principle. In this way virtual memory raises system efficiency along three axes: protection, sharing, and lazy allocation.

C. Effective access time and performance sensitivity

The performance of demand paging is quantified by the effective access time (EAT). If the page-fault rate is p, memory access time is ma, and fault-handling time is pft, then EAT = (1-p)×ma + p×pft. For example, with ma=100ns and pft=8ms (8,000,000ns), even a fault rate of just 0.1% (p=0.001) makes EAT ≈ 100×0.999 + 8,000,000×0.001 ≈ 8,100ns, soaring to about 80× the fault-free case. The calculation shows that to keep the performance degradation within 10%, the fault rate must be held below about 1/800,000. This extreme sensitivity shows numerically why a replacement algorithm that "minimizes faults" and securing locality are a matter of life and death.

3. Page Replacement Algorithms

To bring in a new page when physical memory is full, one existing page must be evicted. The goal is to minimize the fault rate by keeping pages that will soon be used again and evicting pages that will not be used for a while. Below is the decision flow of the representative algorithms.

flowchart LR
    REQ["page replacement needed"] --> OPT["OPT: evict the page<br/>unused for the longest future"]
    REQ --> FIFO["FIFO: evict the page<br/>that entered earliest"]
    REQ --> LRU["LRU: evict the page<br/>least recently referenced"]
    REQ --> CLOCK["Clock (second chance):<br/>evict reference bit 0"]
    OPT -.->|"not implementable, theoretical lower bound"| BENCH["performance baseline"]
    FIFO -.->|"Belady anomaly possible"| SIMPLE["simple but inefficient"]
    LRU -.->|"reflects locality, implementation cost"| GOOD["near-optimal approximation"]
    CLOCK -.->|"LRU approximation, low cost"| REAL["adopted in practice"]

A. OPT (optimal replacement) and the theoretical lower bound

OPT (Optimal, Belady's algorithm) evicts "the page that will not be referenced for the longest time ahead." Since it must know the future reference string, it cannot actually be implemented, but it provides the theoretical lower bound on the achievable minimum number of faults and is used as a yardstick for evaluating other algorithms. For instance, running the reference string 7 0 1 2 0 3 0 4 2 3 0 3 2 with 3 frames, OPT is handled with fewer faults than FIFO or LRU, and how closely a practical algorithm approaches OPT becomes the measure of design quality.

B. FIFO and Belady's anomaly

FIFO evicts the page loaded earliest. Its implementation is simple, but it has the blind spot of evicting even "a page that arrived long ago yet is still in constant use." More fatal is Belady's Anomaly, the counterintuitive phenomenon—appearing in FIFO—in which increasing the number of frames actually increases faults. The reference string 1 2 3 4 1 2 5 1 2 3 4 5 is the classic counterexample, producing more faults with 4 frames than with 3. This shows that FIFO reflects no locality at all, and the anomaly does not occur in LRU or OPT, which have the stack-algorithm property.

C. LRU and its approximations

LRU (Least Recently Used) evicts "the page least recently referenced." Grounded in the locality assumption that past reference patterns continue into the near future, it delivers performance close to OPT, but exact LRU must update a timestamp on every reference or maintain a reference-order list, so its hardware cost is high. Reality therefore uses approximations. A prime example is the Clock (second-chance) algorithm, which arranges frames in a circle and inspects the reference bit—if 1, it clears it to 0 and moves on (one more chance); if it meets 0, it evicts. The enhanced Clock, which also inspects the dirty bit, preferentially evicts "not referenced + clean" pages, saving even the write-back. Real operating systems such as Linux and Windows use variants of this Clock family combined with multi-level LRU lists (active/inactive) and aging.

The table below compares the representative algorithms by performance, cost, and characteristics. Since a table alone does not reveal the "why," the cause of the differences must be read along with it.

Algorithm	Eviction criterion	Fault performance	Implementation cost	Belady anomaly	Practical adoption
OPT	longest future unused	optimal (lower bound)	not implementable	none	for benchmarking
FIFO	load order	poor	very low	occurs	rarely used
LRU	least recently used	excellent	high (HW)	none	approximations only
Clock	reference-bit sweep	good (LRU approx.)	low	none (approx.)	widely used
LFU	least reference frequency	situation-dependent	medium	possible	limited (caches etc.)

The root of the performance differences lies in "how well the future is predicted." FIFO looks only at the load time and ignores usage patterns, so it has no predictive power; LRU approximates the future with the locality that "if used recently, it will be used again soon," so it is strong. Clock cheaply mimics LRU's predictive power with a single reference bit, striking the balance point of performance and cost, which is why it dominates practice. LFU is strong on long-term popular pages, but suffers from a cache-pollution problem where a page used heavily in a burst early on then abandoned stays entrenched because of its high frequency count, so it must be used together with aging.

D. A numerical comparison — same reference string, different results

To feel the difference between the algorithms, it is effective to count the number of faults directly under identical conditions. Assume 3 frames and the reference string 2 3 2 1 5 2 4 5 3 2 5 2. FIFO, looking only at load order, carelessly evicts a page (2) that will be used again later, raising faults; LRU preserves the recently referenced 2 and 5, reducing faults; and OPT, knowing the future, evicts the page to be used last, yielding the minimum faults. In general, for this reference string the fault count appears in the order OPT < LRU ≤ FIFO, reproducing the textbook ranking in which LRU is close to the lower bound set by OPT and FIFO lags most. The key point is that even at the same memory capacity (number of frames), the replacement policy alone can greatly change the fault rate, and combined with the EAT sensitivity of Section 2, this difference in fault count can be amplified into a tens-of-times difference in perceived performance.

This ranking is not always fixed. If the reference string lacks clear locality and is close to random, no algorithm comes near OPT, and cases arise where FIFO happens to resemble LRU or is overtaken by Belady's anomaly. That is, the superiority of a replacement algorithm depends on the reference pattern, so as a principle the designer measures the fault rate against the real trace of the target workload to choose the policy.

Practical replacement policy goes a step further and also considers scan resistance. A job that sequentially reads a large file only once pushes a vast number of pages to the top of the LRU and drives out the frequently used pages; to prevent this, Linux has a two-stage promotion structure that does not immediately promote a newly arrived page to active but promotes it only after confirming re-reference on the inactive list. Database buffer-pool policies such as LRU-K, 2Q, and ARC are products of the same concern, separating "used once" from "used many times" so that a sequential scan cannot pollute the cache.

4. Frame Allocation and Thrashing — why replacement alone is not enough

A. Frame allocation policy

No matter how good the replacement algorithm is, if the number of frames given to a process is smaller than its working set, faults explode. Frame allocation divides into fixed allocation (equal, proportional) and variable allocation, and is also distinguished into local replacement, which confines the replacement scope to the process's own frames, and global replacement, which takes from the whole. Global replacement can concentrate frames on active processes, but one process's faults can snatch another's frames and cause a cascading performance drop.

The choice of allocation scheme lays bare the tension between fairness and efficiency. Equal allocation gives every process the same number of frames and is simple, but a small process has frames to spare while a large one runs short. Proportional allocation divides frames in proportion to virtual-address-space size and mitigates this, but falls into the trap that "being large does not mean being actively used." Modern operating systems therefore take variable allocation + global replacement, adjusting in real time by observing fault behavior, while placing an upper bound such as a cgroup memory limit so that one process's runaway does not drag down the whole.

B. Thrashing and the working-set model

The extreme of this problem is thrashing. Raising the degree of multiprogramming excessively shrinks each process's frames below its working set, reaching a state where the CPU does no work and clings only to page replacement (disk I/O). Here, adding more processes to raise CPU utilization falls into a vicious cycle that accelerates thrashing. The remedy is the Working Set Model, which treats the set of pages (WS) referenced in the most recent time window Δ as the frames a process needs, and adjusts the degree of multiprogramming so that the sum of all processes' WS sizes does not exceed the physical frames. Another approach, PFF (Page Fault Frequency), gives more frames when the fault rate exceeds an upper bound and reclaims them when it drops below a lower bound, controlling the fault rate to a target band. (※ For details on thrashing see [[thrashing]], and for memory-partitioning schemes see [[paging-vs-segmentation]].)

As a concrete case, on a memory-tight Linux server, when memory pressure grows, kswapd incessantly reclaims pages and disk swap I/O soars, the si/so columns of vmstat spike, and the system effectively stalls—a scene in which the textbook's thrashing is reproduced verbatim in the operational field. This is precisely why many organizations limit swap on such services or design cgroup memory limits and OOM policies together.

5. Advanced — Virtual Memory in Modern Operating Systems and Hardware

A. Extension of page tables and the TLB

The classical theory still holds, but modern systems have greatly extended virtual memory in step with scale and hardware advances. First, multi-level and inverted page tables. Handling a 64-bit address space with a linear page table makes the table itself unrealistically large, so x86-64 uses 4–5-level hierarchical page tables and places a multi-level TLB and table caches to reduce the cost of table walks. Second, huge pages (2MB, 1GB), which enlarge the page size so that a single TLB entry covers a wide region, raising the TLB hit rate and reducing the number of table walks—cases of performance improved by several to tens of percent are reported in databases, large JVM heaps, and virtualization. Third, virtualization's nested paging (EPT/NPT), in which hardware handles the two-stage translation of guest virtual → guest physical → host physical, removing the overhead of software shadow page tables.

The hidden cost of this extension is the latency of address translation itself. On a TLB miss in a 5-level page table, up to five memory accesses are needed, and in nested paging a host translation also intervenes at each level, so in the worst case up to 24 memory accesses can occur. Hardware therefore places a dedicated page-walk cache that caches the upper levels of the page table, while software raises the TLB hit rate through huge pages and memory-access locality to offset this cost—that is, the extension of "enlarging the page table" and the optimization of "speeding up translation" always proceed in tandem.

Huge pages are not free. There are reports of cases where transparent huge pages (THP) excessively preempt memory, or the memory compaction latency of the kernel gathering small pages to secure a huge page worsens tail latency. Many vendors therefore recommend, in database operation, turning THP off and using only explicit huge pages via hugetlbfs—a real example showing that even the decision to turn a single hardware feature on or off can backfire without workload characteristics and measurement.

B. Tiered memory and the evolution of reclamation policy

Recent trends are also active. CXL-based memory expansion and tiered memory tier DRAM and slow remote memory, with the OS automatically promoting and demoting hot and cold pages—which is essentially "multi-tiering of page replacement" (related: [[cxl]]). Linux's MGLRU (Multi-Gen LRU) is a representative improvement since 2022 that extends the traditional two-stage active/inactive LRU into multiple generations, raising the accuracy and efficiency of reclamation decisions on large memory. In addition, Copy-on-Write, demand zeroing, and memory compression (zswap/zram) are all techniques that save physical memory at the virtual-memory layer, raising the density of container-dense environments.

Memory compression in particular is drawing attention as an alternative to disk swap. Instead of evicting cold pages to slow disk, compressing them with the CPU and keeping them in memory (zram, zswap) can expand effective memory without disk I/O. The secret to Android keeping many apps in the background on limited RAM is precisely zram, and on Kubernetes nodes too, operations that enable compressed swap to reduce OOM kills are increasing. This shows that virtual memory's essential question—"where and in what form to place a page"—is expanding to diverse backing stores: disk, compression, and remote memory.

6. Considerations and Implications (professional-engineer perspective)

Application strategy — per-workload policy selection: latency-sensitive services (web, DB) should suppress swap and secure huge pages and sufficient working-set frames to structurally block faults, while batch and analytics workloads should raise density by exploiting memory overcommit and tiered memory—memory policy fit to purpose must be designed separately. There is no single optimal setting, and reference-locality analysis must come first.
Managing trade-offs: page size is a balance of internal fragmentation (large) and TLB efficiency (large), overcommit is a balance of density (high) and OOM risk (high), and global/local replacement is a balance of overall efficiency and inter-process isolation. The capacity to quantitatively measure these conflicts via vmstat, perf, and fault rate and tune them is required.
Institutionalizing observation and verification: virtual-memory quality shows not in averages but in the distribution of fault rate, swap I/O, TLB miss rate, and major faults, so without an observation system that measures these continuously, links them to SLOs, and gives early warning of thrashing signs, performance tuning loses its basis.
Linkage with capacity planning: virtual memory allows using more than physical memory, but that does not mean infinite memory. The instant the sum of working sets exceeds physical memory, performance collapses nonlinearly, so in server and container capacity planning a design principle is needed that allocates memory on the basis of measured demand grounded in RSS and working set and uses swap only as a safety net.
Linkage with security and isolation: virtual-address isolation is the foundation of process protection, but speculative-execution side channels such as Meltdown and Spectre exploited the address-translation and TLB paths (related: [[speculative-execution-branch-prediction]]). Since mitigations such as kernel page-table isolation (KPTI) sacrifice performance, memory-management design must now also address the security–performance trade-off.
Securing locality as a design principle: no matter how refined the replacement algorithm, faults cannot be prevented if the program's own reference locality is poor. Application-level locality optimization—the memory layout of data structures (array vs. linked list), the access order of loops (row-major vs. column-major), data-oriented design—must pair with OS memory management for performance to be complete, and the professional engineer must be able to survey both the lower mechanism and the upper design together.
Outlook and related technologies: CXL tiered memory, MGLRU, and memory compression converge toward "managing a slow, large-capacity tier with a replacement policy," and going forward virtual memory will evolve beyond DRAM into a data-placement engine governing the entire heterogeneous memory hierarchy. Directly bordering cloud resource management ([[finops]]) and container density, understanding OS memory principles becomes the foundation of infrastructure cost optimization.

References

Operating System Concepts (Silberschatz et al.), "Virtual Memory" chapter
Arpaci-Dusseau, "Operating Systems: Three Easy Pieces" — Paging/Swapping/Policy — https://pages.cs.wisc.edu/~remzi/OSTEP/
Linux Kernel Documentation, "Multi-Gen LRU" — https://docs.kernel.org/admin-guide/mm/multigen_lru.html
Denning, P., "The Working Set Model for Program Behavior" (CACM, 1968) — the original source of the working-set model

In one line: Virtual memory is a technique that loads only the needed pages via demand paging to provide an address space transcending physical memory and process isolation; because it is extremely sensitive to the fault rate, it blocks thrashing with replacement algorithms such as OPT, FIFO, LRU, and Clock and with working-set-based frame allocation, and in the modern era it is extending to huge pages, nested paging, MGLRU, and CXL tiered memory.