Page Replacement Algorithms in Virtual Memory Systems

Core strategies and characteristics

Replacement policies balance two main factors: accuracy in predicting future use and implementation cost. Good algorithms exploit temporal and spatial locality: recently or frequently used pages tend to be used again soon. Important characteristics include eviction granularity, handling of dirty pages that require writes, whether replacement is global or local, and the runtime or memory overhead of tracking usage.

Common algorithms

• Optimal (Belady's algorithm) — theoretical minimum faults by evicting the page used farthest in the future; impractical but useful as a benchmark.
• FIFO (First-In, First-Out) — evicts the oldest loaded page; simple but can suffer anomalies where more frames give worse performance.
• LRU (Least Recently Used) — evicts the page not used for the longest time; approximates optimal behavior but can be expensive to implement exactly.
• Clock / Second-Chance — an efficient approximation to LRU using a circular buffer and a single use bit, widely used in real kernels.
• LFU (Least Frequently Used) and Working Set — track long-term frequency or the recent active set; useful for different workload patterns.

History and development

Page replacement emerged with time-sharing systems in the 1960s as virtual memory became practical. Early research highlighted fundamental results, such as comparisons between FIFO and optimal behavior and phenomena like Belady's anomaly. Over time, designs have favored approximations that reduce hardware and software cost while preserving most benefits, leading to hybrids and adaptive schemes in modern systems.

Uses, trade-offs, and practical considerations

Choice of policy matters for general-purpose operating systems, databases, virtual machines, and embedded platforms. Systems may prefer low-overhead approximations (e.g., Clock) for predictable performance or more sophisticated tracking for workloads with strong locality. Tuning also involves frame allocation (global vs local), prefetching (pre-paging), and write policies for dirty pages. Understanding the workload pattern is key: sequential scans, random accesses, and interactive programs each favor different approaches.

Notable distinctions and facts

Some important distinctions include the difference between demand paging and pre-paging, and between write-back and write-through strategies for modified pages. Modern kernels often combine several techniques and heuristics to adapt to changing workloads, and designers measure algorithms against empirical traces in addition to theoretical bounds. For further technical details and implementation examples, consult operating system texts and kernel documentation linked from reputable sources.

Related links: OS concepts, virtual memory overview, backing storage, swap files, algorithmic foundations.