What is the LRU Page Replacement Algorithm?
Learn how LRU page replacement works, why exact LRU is costly, and how the clock algorithm approximates it, with OS interview questions.
Expected Interview Answer
Least Recently Used (LRU) page replacement evicts the page that has gone the longest without being referenced, on the assumption that pages accessed far in the past are least likely to be needed again soon.
LRU approximates the theoretically optimal algorithm by using recency of access as a proxy for future use, exploiting temporal locality in real workloads. An exact implementation needs a timestamp or ordered structure — a counter updated on every reference, or a doubly linked list reordered on each access so the tail is always the least-recently-used page — both of which add overhead on every memory access. Because true per-access bookkeeping is expensive in hardware, most operating systems approximate LRU with a reference bit and a clock (second-chance) algorithm that periodically sweeps and clears bits instead of maintaining an exact order. LRU performs well for workloads with strong temporal locality but can still suffer from Belady’s anomaly-free behavior yet degrade badly on sequential scanning patterns that touch every page exactly once, since recency carries no predictive value there.
- Exploits temporal locality present in most real workloads
- Never suffers from Belady’s anomaly, unlike FIFO
- Forms the theoretical basis for practical approximations like clock
- Well understood, making it a strong interview baseline for comparisons
AI Mentor Explanation
LRU is like a coach trimming the practice squad by dropping whichever player has gone the longest without being called into a net session, because a player untouched for weeks is judged least likely to be needed next week. Every time a player is used in a drill, they move to the front of the availability list, pushing stale players toward the cut line. This mirrors how LRU tracks recency of access rather than raw arrival order. A player who was excellent last season but has not practiced recently still gets cut first, just as an old but recently unused page gets evicted.
Step-by-Step Explanation
Step 1
Reference occurs
A page is accessed, and its position in the recency-ordering structure (list or counter) is updated to “most recently used”.
Step 2
Fault triggers eviction
When a page fault occurs and no free frame exists, the replacement algorithm must select a victim.
Step 3
Locate least-recent page
The page at the tail of the recency list (or with the oldest timestamp) is chosen as the victim.
Step 4
Evict and load
The victim page is written back if dirty, the new page is loaded into its frame, and it becomes the new “most recently used” entry.
What Interviewer Expects
- A definition tied to recency of access, not frequency or arrival order
- Awareness that exact LRU needs a linked list or counter with per-access overhead
- Knowledge that clock/second-chance is the practical hardware approximation
- Recognition of the sequential-scan worst case where recency is not predictive
Common Mistakes
- Confusing LRU with FIFO (arrival order instead of access recency)
- Claiming LRU is immune to Belady’s anomaly by definition without knowing why (it is a stack algorithm)
- Not knowing that exact LRU is expensive and is usually approximated
- Forgetting the sequential-scan worst case where LRU underperforms
Best Answer (HR Friendly)
“LRU page replacement means the operating system throws out whichever page has not been used in the longest time, betting that pages we have not touched recently are the ones we are least likely to need again soon. It works well because most programs reuse recently touched data, but tracking exact recency is expensive, so real systems approximate it with simpler bookkeeping like a reference bit swept periodically.”
Code Example
struct page_node {
int page_id;
struct page_node *prev, *next;
};
struct page_node *mru_head, *lru_tail; /* head = most recent, tail = least recent */
void touch_page(struct page_node *p) {
unlink(p); /* remove from current position */
push_front(&mru_head, p); /* move to most-recently-used end */
}
int evict_victim(void) {
struct page_node *victim = lru_tail; /* least recently used */
int id = victim->page_id;
unlink(victim);
free(victim);
return id;
}Follow-up Questions
- Why is exact LRU expensive to implement in hardware?
- How does the clock (second-chance) algorithm approximate LRU?
- What is a stack algorithm, and why does that property mean LRU avoids Belady’s anomaly?
- In what access pattern does LRU perform worse than FIFO?
MCQ Practice
1. LRU page replacement evicts the page that is?
LRU tracks recency of access and evicts whichever page has gone the longest without being referenced.
2. Why do real operating systems rarely implement exact LRU?
Exact LRU needs a timestamp or list update on every single memory access, which is too costly at hardware speed, so it is approximated (e.g., clock algorithm).
3. LRU is classified as a “stack algorithm” because?
Stack algorithms guarantee monotonic containment of resident sets as frame count increases, which is why LRU never exhibits Belady’s anomaly.
Flash Cards
What does LRU evict? — The page that has gone the longest without being referenced.
Why is exact LRU costly? — It requires updating recency order (list or timestamp) on every memory access.
How is LRU approximated in practice? — With the clock (second-chance) algorithm using reference bits swept periodically.
Does LRU suffer from Belady’s anomaly? — No — it is a stack algorithm, so adding frames never increases faults.