LRU Page Replacement Algorithm

Introduction

LRU page replacement stands for Least Recently Used. It is a page replacement algorithm used when RAM is full and a new page must be loaded by removing one existing page.

The main question is simple: among all pages currently in memory, which page should leave? LRU answers by evicting the page that has not been used for the longest time in the past.

LRU Page Replacement Meaning

LRU removes the least recently used page. In other words, it chooses the page whose last access is oldest among the pages currently present in RAM.

LRU is based on temporal locality. Temporal locality means that recently used pages are likely to be used again soon, so LRU tries to keep recently accessed pages in memory.

How LRU Works

LRU updates recency on every page access. This is the most important rule of the algorithm.

• If the page is already in RAM: It is a hit, and its recency is updated.

• If the page is absent and a free frame exists: The page is loaded, and it becomes recently used.

• If the page is absent and frames are full: The page whose last use is oldest is evicted, and the new page becomes recently used.

The key warning is to look at last use, not loading time. A page may have entered memory early, but if it was accessed recently, LRU should not treat it as the victim.

LRU Worked Example

Consider this setup:

• Reference string: 1, 2, 3, 2, 4, 1, 2, 5

• Number of frames: 3

• Initial memory: Empty

The frame table below shows the pages after each access. Recency is tracked by last use, even when the visible frame order does not physically shift in RAM.

At step 5, page 4 is not present and all frames are full. Among 1, 2, and 3, page 1 has the oldest last use, so it is evicted.

At step 6, page 1 causes another fault. Among 4, 2, and 3, page 3 is least recently used, so page 3 is replaced.

For the given reference string, there are 6 page faults and 2 page hits out of 8 total page references. Therefore, the page fault rate is 6 / 8.

Stack Property and Belady’s Anomaly

LRU has the stack property. This means the pages present with N frames are contained within the pages present with N + 1 frames for the same reference string.

Because of this property, giving LRU more frames cannot increase the number of page faults. This is why LRU does not suffer from Belady’s anomaly.

Belady’s anomaly means that increasing the number of frames can increase page faults in some algorithms, such as FIFO. LRU avoids this because its recency-based stack order preserves containment as frame count grows.

LRU vs FIFO

LRU and FIFO may look similar in frame tables, but their logic is different. FIFO uses loading order, while LRU uses recent access history.

This is the core difference: in LRU, hits matter. If a hit does not update recency, the method is not truly LRU.

LRU Implementation Cost

Exact LRU needs recency information on every memory access. This creates overhead because memory references happen extremely frequently. Common exact LRU approaches include:

• Timestamp method: Store the last access time for each page and evict the page with the oldest timestamp.

• Stack or list method: Move the accessed page to the most recently used position on every access.

• Metadata update: Maintain extra information whenever a page is referenced.

These methods are expensive at system scale. Updating timestamps or list positions for every memory access can add too much overhead.

How Real Systems Approximate LRU

Because exact LRU is costly, real operating systems often use approximations instead of pure LRU. These methods try to capture recent usage without updating heavy metadata on every access.

• Reference bits: Hardware-supported bits indicate whether a page was accessed recently.

• Aging: Counters are shifted or decayed over time so recent use has more weight.

• Clock or Second Chance: A circular scan uses reference bits to give recently used pages another chance.

The goal is to get behavior close to LRU while keeping implementation overhead practical.

Summary

LRU page replacement evicts the page that was least recently used when a page fault occurs and all frames are full. It works well because programs often show temporal locality, where recently used pages are likely to be used again soon.

Unlike FIFO, LRU updates recency on every access, including hits. It has the stack property, so it does not suffer from Belady’s anomaly, but exact LRU is expensive and is usually approximated in real systems.