Page replacement policies: what does the Least Recently Used (LRU) algorithm select when choosing a page to evict from memory?

Introduction / Context:
When physical memory fills up, a virtual memory system must choose which page to evict. The replacement policy impacts hit rates and overall performance. LRU is a widely taught policy that approximates the ideal of keeping the working set in memory by favoring pages that were used most recently and discarding those that have been idle the longest.

Given Data / Assumptions:

• LRU tracks recency of access for each page.
• The policy removes the page that is least recently referenced.
• We ignore implementation approximations and focus on the principle.

Concept / Approach:

The working set model suggests that the near future usage correlates with recent past usage. LRU embodies this by selecting for eviction the page with the oldest access timestamp. Real systems approximate LRU using counters, stacks, clock algorithms, or reference bits due to overhead constraints.

Step-by-Step Solution:

Verification / Alternative check:

Performance studies show LRU tends to outperform FIFO on many workloads because it avoids Belady anomalies typical of FIFO and aligns with temporal locality.

Why Other Options Are Wrong:

• used recently: that would be MRU, not LRU.
• least used recently: ambiguous wording; LRU is specifically least recently used, which matches not been used recently more clearly.
• first page in a given area: FIFO behavior, not LRU.

Common Pitfalls:

• Confusing frequency based policies (LFU) with recency based policies (LRU).
• Overlooking that implementations are approximations due to cost.

Final Answer:

pages out pages that have not been used recently.