Counting-Based Algorithms
What you'll learn: How page replacement strategies can use access frequency counts instead of recency to decide which pages to evict.
The Core Idea
While algorithms like LRU track when pages were last used, counting-based algorithms track how often pages are accessed. They maintain a counter for each page that increments with every reference, then use these counts to make replacement decisions.
Least Frequently Used (LFU)
LFU replaces the page with the smallest counter value—the one that's been accessed the fewest times.
Analogy: Imagine a library removing the books that have been checked out least often. If a book has only been borrowed twice while others have been borrowed dozens of times, it's the first to go.
The problem: A page heavily used early on might accumulate a high count but never be used again—yet LFU keeps it in memory because of its historical frequency.
Most Frequently Used (MFU)
MFU does the opposite—it replaces the page with the highest counter.
Rationale: This counterintuitive approach assumes that pages with low counts were probably just brought in and will be used more soon. Pages with high counts may have already served their purpose.
Reality check: MFU is rarely used in practice because this assumption often doesn't hold true.
Practical Considerations
Both algorithms are computationally expensive—finding the minimum or maximum count on every page fault requires scanning all page counters. Additionally, counters never reset, so they don't adapt well when a program's access patterns change over time (e.g., moving from one phase to another).
Key Takeaway: Counting-based algorithms (LFU/MFU) use access frequency rather than recency for page replacement, but their computational overhead and inability to adapt to changing access patterns limit their practical use compared to LRU-based approaches.