Course contentsShow
← Computer Science
Lesson 1371 of 2,87231. Memory ManagementFree lesson

LRU Implementation Techniques

Hardware counters, stack, and other practical methods for implementing LRU replacement.

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.