LFU and MFU Page Replacement

Introduction

LFU and MFU are page replacement algorithms based on frequency. Frequency means how many times a page has been used after being loaded into physical RAM.

These algorithms are used when a page fault occurs and all frames are full. LFU removes the page with the lowest count, while MFU removes the page with the highest count.

LFU and MFU Meaning

LFU stands for Least Frequently Used. It assumes that a page used very few times may be less important, so it evicts the page with the lowest access count.

MFU stands for Most Frequently Used. It assumes that a page used many times may have already completed its active phase, so it evicts the page with the highest access count.

Both algorithms use access count, but they choose opposite victims.

Why Frequency Can Mislead

Frequency counts can become stale. A page may be used many times early in execution and then never used again, but its count remains high. This creates a problem for LFU. A page with an old high count may stay protected even when it is no longer useful. The algorithm may keep it in RAM because the counter still looks strong.

MFU has the opposite risk. A page with a high count may still be actively useful, such as a loop page being accessed repeatedly. Evicting it only because it has the highest count can cause unnecessary future page faults.

Aging is often used to reduce this problem. In aging, old counts gradually lose importance so the replacement decision can reflect more recent behavior.

LFU Worked Example

Consider this setup:

• Reference string: 1, 2, 3, 2, 4, 1, 2, 5

• Number of frames: 3

• Initial memory: Empty

• Tie rule: FIFO among pages with the same count

In LFU, the page with the lowest count is evicted when all frames are full.

For this LFU trace, page faults are 6 and page hits are 2. Page 2 is protected because its count increases on hits, while pages with lower counts become better victims.

MFU Worked Example

Now use the same setup for MFU:

• Reference string: 1, 2, 3, 2, 4, 1, 2, 5

• Number of frames: 3

• Initial memory: Empty

• Tie rule: FIFO among pages with the same highest count

In MFU, the page with the highest count is evicted when all frames are full.

For this MFU trace, page faults are 6 and page hits are 2. MFU removes the most frequently used page, which can be useful only when high frequency suggests that the page’s active phase is over.

LFU vs MFU

Both algorithms depend on frequency, but frequency alone does not always represent current usefulness. That is why aging and tie-breaking rules matter.

Why LFU and MFU Are Less Central

FIFO, Optimal, LRU, and Clock are more central in operating system discussions because they are simpler, ideal for benchmarking, locality-based, or practical to approximate.

LFU and MFU are still useful for understanding how frequency affects replacement decisions. They show that counting page uses can be helpful, but also that old counts may become misleading. In practice, frequency-based ideas are more useful when combined with aging or other signals instead of using raw lifetime counts alone.

Summary

LFU and MFU are frequency-based page replacement algorithms. LFU evicts the page with the lowest access count, while MFU evicts the page with the highest access count when a page fault occurs and all frames are full.

Both algorithms show that frequency can be useful, but also risky. Counts can become stale, tie rules affect results, and real systems usually need aging or other practical approximations to make frequency-based decisions more adaptive.