Coursify

Cache Replacement Algorithms in Memory Management

Cache Replacement Algorithms in Memory Management

Verified Sources
Nov 3, 2026

Cache replacement algorithms decide which cached memory block (or page) to evict when the cache is full and a new block must be brought in. This decision directly affects the cache miss rate and therefore the effective performance of memory systems (e.g., CPU caches, OS page caches, and virtual memory paging). Common algorithms include LRU , FIFO , LFU , Random , and Clock.2

Below is a structured explanation of major replacement policies, their mechanics, properties, trade-offs, and typical approximations used in real systems.

Footnotes

  1. Least Frequently Used (LFU) page replacement — Wikipedia - Describes LFU concepts and common implementation concerns. ↩

  2. Cache replacement — Wikipedia - Overview of multiple replacement policies including FIFO, LFU, random, and related behavior. ↩

Cache Replacement (LRU, FIFO, OPT) - Core Concepts

Key terms and model (used across algorithms)

To reason about replacement algorithms, systems are often modeled with:

  • Cache capacity CC
  • Reference string r1,r2,…,rnr_1, r_2, \dots, r_n
  • Cache hit and cache miss
  • Victim selection

Two important baselines:

  • OPT (Belady’s optimal) gives the theoretical minimum possible misses for a given trace.
  • Practical algorithms approximate OPT with varying costs.

Footnotes

  1. Optimal page replacement algorithm — Wikipedia - Defines OPT/Belady’s optimal and its benchmark role. ↩

1On a miss with full cache: which resident item should be evicted?

Replacement Policy Landscape (from theory to practice)

OPT (Belady)

Theoretical baseline

Uses future knowledge; lower bound on misses."

Footnotes

  1. Optimal page replacement algorithm — Wikipedia - Defines OPT/Belady’s optimal and its benchmark role. ↩

LRU and approximations

Recency-based family

LRU evicts least recently used; approximated by Clock/Second-Chance in hardware/OS."

Footnotes

  1. Clock page replacement — Wikipedia - Explains Clock/second-chance approach and reference-bit approximation to LRU. ↩

FIFO

Age-based family

Evicts oldest insertion; can violate desirable properties (e.g., Belady’s anomaly)."

Footnotes

  1. Cache replacement — Wikipedia - Overview of multiple replacement policies including FIFO, LFU, random, and related behavior. ↩

LFU

Frequency-based family

Evicts least frequently referenced; needs counters and tie-breaking."

Footnotes

  1. Least Frequently Used (LFU) page replacement — Wikipedia - Describes LFU concepts and common implementation concerns. ↩

Random

Low-overhead baseline

Very simple victim selection; predictable worst-case guarantees depend on model."

Footnotes

  1. Cache replacement — Wikipedia - Overview of multiple replacement policies including FIFO, LFU, random, and related behavior. ↩

1) OPT (Optimal / Belady’s algorithm) — “future knowledge”

OPT (Belady’s optimal) chooses, on each eviction, the resident item whose next access occurs farthest in the future (or is never accessed again). This produces the fewest misses among all possible policies for a fixed reference string.

Why it matters: OPT is a benchmark. Many analyses compare real algorithms to OPT to understand how close they can get.

Footnotes

  1. Optimal page replacement algorithm — Wikipedia - Defines OPT/Belady’s optimal and its benchmark role. ↩

2) LRU — evict least recently used

LRU evicts the block with the oldest last access time. Intuition: items used recently are likely to be used again.

A practical hardware view maintains an ordering of “most recently used” items; conceptually, LRU is implemented with:

  • A timestamp per item, or
  • A stack/list ordered by recent touches.

Property (stack behavior): LRU has strong theoretical structure (often described via a “stack property”), which implies monotonic behavior of miss counts across cache sizes in many standard models.

Cost: exact LRU requires updates on every access (time/memory overhead).

Footnotes

  1. Clock page replacement — Wikipedia - Explains Clock/second-chance approach and reference-bit approximation to LRU. ↩

Use LRU as a recency baseline

If you need an algorithm that strongly reflects locality of reference, LRU (or close approximations) are often a good starting point—then evaluate overhead.

3) Clock / Second-Chance — approximate LRU (lower overhead)

Clock approximates LRU using:

  • a circular list of cache “frames”
  • a reference bit RR per frame indicating whether the item was accessed recently
  • a rotating hand (pointer) that scans frames on eviction

A common “second-chance” form:

  1. When scanning for a victim, if a frame’s reference bit is set, clear it and give that frame a “second chance”.
  2. If you find a frame with R=0R=0, evict it.

This mimics LRU behavior but avoids per-access reordering, replacing it with cheaper periodic scanning.

Cost trade-off: update is cheap (set reference bit on access), victim selection cost depends on how many frames have R=1R=1.

Footnotes

  1. Clock page replacement — Wikipedia - Explains Clock/second-chance approach and reference-bit approximation to LRU. ↩

4) FIFO — evict the oldest inserted

FIFO evicts the item that entered the cache first, regardless of subsequent accesses.

Pros

  • Simplicity: maintain a queue of insertion order.
  • Low bookkeeping overhead.

Cons / known phenomenon: FIFO can exhibit Belady’s anomaly, where increasing cache capacity can increase miss count for some reference strings.

Footnotes

  1. Cache replacement — Wikipedia - Overview of multiple replacement policies including FIFO, LFU, random, and related behavior. ↩

5) LFU — evict least frequently used

LFU evicts the item with the smallest access count over some window/history.

Mechanics

  • Keep a counter per item.
  • On hit, increment counter.
  • On miss with full cache, evict the minimum counter; tie-breakers can use recency or insertion time.

Cost: counters require updates on every hit; large counters can be expensive, so implementations often:

  • use approximate counters,
  • apply decay (aging) to prevent “frequency forever” effects.

LFU is designed for workload patterns where frequency locality dominates over recency.

LFU needs aging to avoid stale frequency

Pure LFU can keep ancient “popular” items forever even if the workload shifts. Many real LFU variants add decay/aging.

6) Random — evict a random cache line

Random chooses a random resident item to evict on misses.

Pros

  • Minimal metadata: no recency/frequency tracking.
  • Often simple to implement and sometimes performs surprisingly well in practice under certain assumptions.

Cons

  • No direct use of locality information.
  • The miss behavior depends strongly on workload; compared to informed policies, it may be worse in many scenarios.

Comparison of replacement algorithms

The following comparison focuses on conceptual behavior and implementation overhead.

AlgorithmUses recency?Uses frequency?Requires ordering/updates on access?Main advantageMain risk
OPTYes (via future next-use)IndirectImpossible in practiceTheoretical minimum missesRequires future knowledge
LRUYesNoYes (for exact LRU)Captures temporal localityHigh overhead for exact tracking
Clock / Second-ChanceApprox recencyNoLow (set/clear reference bits)Cheaper than exact LRUCan be less accurate under some patterns
FIFONoNoLowSimple queue-based evictionCan show Belady’s anomaly
LFUNoYesYes (counter updates)Captures frequency localityCan require aging/decay to adapt
RandomNoNoVery lowMinimal metadataIgnores locality

Footnotes

  1. Optimal page replacement algorithm — Wikipedia - Defines OPT/Belady’s optimal and its benchmark role. ↩

  2. Clock page replacement — Wikipedia - Explains Clock/second-chance approach and reference-bit approximation to LRU. ↩ ↩2

  3. Cache replacement — Wikipedia - Overview of multiple replacement policies including FIFO, LFU, random, and related behavior. ↩

  4. Least Frequently Used (LFU) page replacement — Wikipedia - Describes LFU concepts and common implementation concerns. ↩

How a cache replacement decision is made (generic pipeline)

  1. 1
    Step 1

    If the requested block is already resident, return it and record any policy metadata (e.g., update recency bit/counter).

  2. 2
    Step 2

    If the cache has free frames, insert the requested block without eviction.

  3. 3
    Step 3

    Invoke the replacement policy to select a victim resident block.

  4. 4
    Step 4

    Remove the victim, bring in the requested block, and initialize any metadata (e.g., set reference bit).

  5. 5
    Step 5

    Continue to process the next access in the reference string; the policy’s behavior is determined by its metadata updates.

Frequently misunderstood points

Qualitative overhead vs locality awareness (conceptual)

Higher = more metadata/complexity; locality awareness reflects how strongly the policy uses recency/frequency signals.

Cache Replacement Algorithms (Self-check)

1 / 5
Question · Term

What does OPT evict on each miss?

Click to reveal
Answer · Definition

Evicts the resident item whose next access occurs farthest in the future (or never).

Knowledge Check

Question 1 of 4
Q1Single choice

Which policy is guaranteed to produce the minimum number of cache misses for a fixed reference string?

Knowledge Check

Question 1 of 1
Q1Single choice

Which algorithm evicts a randomly chosen resident cache line on a miss?

Knowledge Check

Question 1 of 1
Q1Single choice

In the generic miss path, a replacement policy is invoked when:

Explore Related Topics

1

Page Replacement Analysis: FIFO vs LRU for a 4-Frame Reference String

The page‑replacement analysis compares FIFO and LRU for the reference string 1,3,4,4,3,2,1,7,5,6,4,2,1,21,3,4,4,3,2,1,7,5,6,4,2,1,2 using four frames, showing that LRU incurs fewer faults.

  • FIFO simulation results in 1010 page faults.
  • LRU simulation results in 99 page faults.
  • LRU is superior here because it evicts the least recently used page, better exploiting temporal locality.
  • FIFO evicts the oldest loaded page, which can discard recently used pages and lead to higher fault rates.
  • This example illustrates why LRU often outperforms FIFO, though FIFO’s simplicity can cause anomalies such as Belady’s.
2

Page Faults and Page Replacement in Virtual Memory Systems

3

Swapping in Memory Management: Concept, Mechanisms, and Performance Trade-offs

Browse all research articles