Least Recently Used (LRU)
What you'll learn: How the LRU page replacement algorithm evicts the page that hasn't been accessed for the longest time.
The Core Idea
When memory is full and a page fault occurs, the operating system must choose which page to evict to make room for the new page. Least Recently Used (LRU) makes this decision by tracking when each page was last accessed and replacing the one with the oldest "last used" timestamp.
The intuition is simple: if a page hasn't been used recently, it's probably less likely to be needed soon compared to pages that were accessed more recently. This is based on the principle of temporal locality—programs tend to reuse recently-accessed data.
How It Works
Imagine a bookshelf where you always place the book you just read at the front. When you need to remove a book to make space, you pick the one farthest back—the one you read longest ago.
Similarly, LRU maintains a record of page access times. When eviction is needed:
- Examine all pages currently in memory
- Find the page with the oldest "last accessed" time
- Replace that page with the new one
Example
Suppose you have 3 frames and reference this page sequence: 7, 0, 1, 2, 0, 3
- Load 7, 0, 1 (three page faults, frames fill)
- Access 2: must evict. Page 7 was used longest ago → evict 7
- Access 0: already in memory, update its "last used" time
- Access 3: must evict. Page 1 was used longest ago → evict 1
LRU typically performs much better than FIFO and approaches the theoretical optimum of OPT, though it requires tracking access history.
Key Takeaway: LRU replaces the page that has gone the longest time without being accessed, leveraging temporal locality to minimize future page faults.