LRU Implementation Techniques
What You'll Learn
You'll discover the practical hardware and software methods used to implement the LRU (Least Recently Used) page replacement algorithm in real operating systems.
The Challenge
In the previous lesson, you learned that LRU is a near-optimal page replacement strategy—it evicts the page that hasn't been used for the longest time. But there's a catch: how do you actually track which page was least recently used? In a system with thousands of pages, this becomes a serious engineering challenge.
Implementation Approaches
Hardware Counters
One approach uses a counter that the CPU increments on every memory access. Each page table entry stores the counter's value when that page was last referenced. When a page fault occurs, the OS scans all entries and evicts the page with the smallest (oldest) counter value.
Drawback: Requires special hardware and scanning thousands of entries is slow.
Stack-Based Approach
Imagine maintaining a stack of page numbers. Whenever a page is referenced, you remove it from its current position and push it to the top. The least recently used page is always at the bottom.
Drawback: Updating the stack on every memory reference requires expensive pointer manipulation—often impractical in software.
Reference Bit Approximations
Most real systems use cheaper approximations. Hardware sets a reference bit in each page table entry when accessed. The OS periodically examines and clears these bits to build a usage history, approximating LRU without perfect tracking.
Analogy
Think of organizing books: true LRU would mean rearranging your entire bookshelf every time you touch a book. Instead, you might just mark which books you've opened this week—close enough for practical purposes.
Key Takeaway:
Perfect LRU requires expensive hardware counters or stack updates on every memory access; real systems use approximations like reference bits for practical performance.