When Memory is Full
With virtual memory, the OS periodically needs to free up physical memory by evicting pages. When a new page needs to be loaded but all frames are occupied, the OS must choose which existing page to remove and replace with the new one. This decision is made by a page replacement algorithm.
The goal is simple: choose the page that will be needed furthest in the future (or won't be needed at all), so that future page faults are minimized. Different algorithms approach this goal in different ways.
First-In, First-Out (FIFO)
FIFO replaces the oldest page in memory — the one that was loaded first. It's the simplest algorithm to implement: just maintain a queue of pages and evict the one at the front.
The problem: The oldest page might still be heavily used. A page that was loaded at startup and is accessed constantly would be evicted just because it's old. FIFO can perform surprisingly poorly — it's not uncommon for FIFO to have more page faults than simpler algorithms.
FIFO is mostly useful as a baseline for comparison. Real systems rarely use it alone.
Least Recently Used (LRU)
LRU replaces the page that hasn't been used for the longest time. The logic is simple: if a page hasn't been accessed recently, it's less likely to be accessed soon. Pages that were recently used are probably still needed.
Think of it like cleaning out your closet. You're more likely to donate clothes you haven't worn in months than the shirt you wore yesterday. LRU applies the same principle to memory pages.
The challenge: Implementing LRU exactly is expensive. To know which page was used least recently, the OS would need to track every memory access, which is impractical. Instead, systems use approximations like the clock algorithm (also called the second-chance algorithm), which approximates LRU with much less overhead.
LRU is the gold standard — most modern operating systems use LRU or LRU-approximation algorithms.
Optimal Algorithm (Belady's Algorithm)
The optimal algorithm replaces the page that won't be used for the longest time in the future. It's theoretically perfect — it produces the fewest possible page faults.
The catch? It's impossible to implement in practice because you'd need to know the future. How can the OS know which page won't be needed for the longest time? It can't.
The optimal algorithm is useful as a benchmark. When evaluating other algorithms, we compare their performance against the optimal to see how close we can get. No practical algorithm can beat it, but some come impressively close.
Least Frequently Used (LFU)
LFU replaces the page that has been accessed the fewest number of times. It keeps a counter for each page and evicts the one with the lowest count.
The problem: A page might have been accessed many times in the past but hasn't been used recently. LFU would keep it because of its high count, even though it's no longer needed. This is the opposite of LRU's strength.
LFU is less common than LRU in practice, but it's useful in specific scenarios where access patterns are consistent over time.