What is the LFU Page Replacement Algorithm?
Learn how LFU page replacement works, its stale-favorite weakness, and how it compares to LRU and clock, with OS interview questions.
Expected Interview Answer
Least Frequently Used (LFU) page replacement evicts the page with the smallest access count, on the assumption that pages referenced rarely overall are less valuable to keep resident than pages referenced often, regardless of how recently each was last touched.
LFU maintains a reference counter per resident page that increments on every access, and when a victim must be chosen, the page with the lowest count is evicted, with ties usually broken by some secondary rule such as oldest load time. This differs fundamentally from LRU, which only cares about the single most recent access: LFU accumulates a full history of usage frequency, which can better identify pages that are genuinely “hot” across a long window rather than just recently touched once. The classic failure mode is the “cache pollution” or stale-favorite problem — a page that was extremely popular early on accumulates a high count and then becomes nearly impossible to evict even after it stops being used, since new pages start at count 1 and can never catch up quickly. Practical LFU implementations mitigate this by aging or periodically decaying counters so that old popularity does not permanently entrench a now-cold page, and pure LFU is rarely used for OS page replacement in practice — it appears far more often in application-level or web caching systems where frequency skew is stronger and more persistent.
- Captures long-term popularity rather than just the last access
- Resistant to one-off scans that would fool a pure recency-based algorithm
- Useful mental model contrasting frequency-based vs. recency-based eviction
- Widely used in application caches (CDNs, DB buffer pools) even where less common in raw OS paging
AI Mentor Explanation
LFU is like a coach keeping a running tally of how many times each player has been picked across the whole season and dropping whichever player has the lowest total picks, even if that player featured in yesterday’s match. A veteran picked constantly all season keeps a high count and stays, while a bench player who played once weeks ago and once yesterday still has a low total and gets cut. The danger is a star from early in the season who got injured: their old high pick-count keeps them “protected” long after they stopped playing, unlike a frequency-decaying system that would eventually let them go.
Step-by-Step Explanation
Step 1
Access increments counter
Every reference to a resident page increments its per-page frequency counter, either exactly or approximately.
Step 2
Fault requires a victim
A page fault occurs with no free frame available, forcing a replacement decision.
Step 3
Scan for minimum count
The algorithm finds the resident page with the lowest access count; ties are broken by a secondary rule like oldest load time.
Step 4
Evict and reset
The lowest-count page is evicted, and the newly loaded page typically starts its own counter at 1 (or an aged baseline).
What Interviewer Expects
- A definition tied to cumulative access frequency, not recency of last touch
- Clear contrast with LRU: total count over time vs. single most-recent access
- Awareness of the stale-favorite / cache-pollution problem for old popular pages
- Knowledge that aging/decay mitigates stale favorites, and that LFU is more common in application caches than raw OS paging
Common Mistakes
- Confusing LFU with LRU (frequency count vs. recency of last access)
- Not identifying the stale-favorite problem as LFU’s key weakness
- Assuming LFU is the default OS page-replacement algorithm (it is much more common in web/DB caches)
- Forgetting that a fresh page always starts at a low count and needs time to prove usefulness
Best Answer (HR Friendly)
“LFU page replacement keeps a running tally of how many times each page has been used and evicts whichever page has the lowest total count, treating overall popularity as more important than how recently something was touched. Its weakness is that a page can become popular early on, rack up a big count, and then stay resident for a long time even after nobody uses it anymore, unless the system periodically ages those counts down, which is why LFU shows up more in web and database caching than in classic OS page replacement.”
Code Example
struct frame { int page_id; long freq; };
struct frame frames[NUM_FRAMES];
void on_page_access(int frame_idx) {
frames[frame_idx].freq++; /* bump frequency on every reference */
}
int lfu_evict(void) {
int victim = 0;
for (int i = 1; i < NUM_FRAMES; i++) {
if (frames[i].freq < frames[victim].freq) {
victim = i; /* track lowest-frequency page */
}
}
frames[victim].freq = 1; /* new page starts fresh */
return victim;
}Follow-up Questions
- What is the “stale favorite” or cache-pollution problem in LFU, and how does aging fix it?
- How does LFU differ from LRU in what history it tracks?
- Why is LFU used more often in web/database caching than in raw OS page replacement?
- How would you break a tie when two pages have the same frequency count?
MCQ Practice
1. LFU page replacement evicts the page with?
LFU tracks a cumulative access counter per page and evicts whichever resident page has been referenced the fewest times overall.
2. What is the classic weakness of pure LFU?
Because counts accumulate indefinitely, an old but no-longer-used page can retain a high count that keeps it resident, a problem usually fixed with counter aging or decay.
3. How does LFU fundamentally differ from LRU?
LRU cares only about the single most recent touch, while LFU accumulates a full count of how many times a page has been referenced.
Flash Cards
What does LFU evict? — The resident page with the lowest cumulative access frequency.
How does LFU differ from LRU? — LFU tracks total access count over time; LRU tracks only the single most recent access.
What is LFU’s classic weakness? — The stale-favorite problem — an old, once-popular page keeps a high count and resists eviction after going cold.
How is the stale-favorite problem mitigated? — By periodically aging or decaying frequency counters so old popularity does not permanently entrench a page.