counting-based replacement

Instead of asking 'when was this page last used?' (recency), counting-based schemes ask 'how often has this page been used?' (frequency). Each page keeps a counter of how many times it has been referenced, and the replacement decision is based on those counts. There are two opposite flavours built on the same counter: LFU (least-frequently-used) and MFU (most-frequently-used).

LFU evicts the page with the smallest reference count, on the reasoning that a rarely-used page probably is not very important and can go. MFU does the opposite — it evicts the page with the largest count — on the reasoning that a page used many times has had its turn and is likely done, while a page with a small count was probably just brought in and still needs to be used. Each policy keeps a per-page counter that the OS increments on every reference (or estimates from the reference bit) and scans for the minimum or maximum when choosing a victim.

Why it matters and why it is rarely the main choice: both LFU and MFU are intuitive but neither approximates optimal especially well, and both are clumsy on real workloads. LFU's classic flaw is the page that was hammered during startup: its count is sky-high, so LFU clings to it long after the program has moved on. A common patch is to age the counts (shift them down over time) so old popularity fades. Because of these weaknesses, counting-based replacement is uncommon in practice — most systems prefer recency-based approximations like the clock algorithm — but LFU-style frequency counting is genuinely useful elsewhere, for example in cache eviction policies.