Cache Memory: Why FIFO and LRU Are Replacement Algorithms

Verified Sources

Nov 4, 2026

In CPU cache memory management, FIFO and LRU determine which cache block to evict when the cache is full. Therefore, they are examples of replacement algorithms (option (iii)), not mapping, addressing, or write policies.

A cache has to decide (1) where a memory block could go (mapping), (2) how it’s located/identified (addressing/tag use), (3) what to remove on a miss when space is needed (replacement), and (4) what to do on writes (write policies). FIFO/LRU belong to the third decision point.

Key terms you’ll use repeatedly: replacement algorithm , cache line , cache miss , eviction.

Cache Replacement Policies (FIFO vs LRU) - Educational Overview

Mapping vs Replacement vs Write Policies (the conceptual separation)

mapping technique (e.g., direct-mapped, set-associative) controls candidate placement.
replacement algorithm controls removal on overflow.
write policy controls behavior on writes (e.g., write-through/write-back).

FIFO and LRU are explicitly defined as policies for choosing the eviction victim—so they are replacement algorithms.

Reasoning to Classify FIFO and LRU

1
Step 1
On a cache miss, the cache may need to insert the requested block; if the cache (or set) is full, it must evict one existing block.
2
Step 2
FIFO/LRU specify which existing block is removed to free space—this is eviction.
3
Step 3
Because FIFO/LRU govern eviction, they are replacement algorithms.
4
Step 4
They do not define placement (mapping), nor how addresses are decomposed (addressing), nor store propagation behavior (write policies).

Category Matching for FIFO and LRU

FIFO/LRU control eviction on misses, so they belong under replacement.

Pro Tip: Use the keyword “evict”

If the policy answers “which block do we evict when the cache is full?”, it’s a replacement algorithm (FIFO/LRU).

Common confusion: Write vs Replace

Write policies (write-through/write-back, write-allocate/no-write-allocate) only talk about store behavior, not eviction on load misses. FIFO/LRU are about eviction.

Quick Multiple-Choice Logic

Where FIFO/LRU Fit in Cache Operation

CPU requests data

1. Reference

CPU issues load/store with a memory address."

Check cache

2. Lookup

Compare tags; if present, serve data."

Cache miss occurs

3. Miss?

Cache needs to bring in the requested block."

Replacement decision

4. Space needed

If full, FIFO or LRU selects an eviction victim."

FIFO/LRU Classification Flashcards

1 / 4

Question · Term

FIFO in cache is best described as…

Click to reveal

Answer · Definition

A replacement algorithm.

Knowledge Check

Question 1 of 3

Q1Single choice

In cache memory, FIFO and LRU are examples of:

(i) Mapping techniques

(ii) Addressing techniques

(iii) Replacement algorithms

(iv) Write policies

Explore Related Topics

Locality of Reference: Short Notes for Memory Hierarchies and Cache Performance

Virtual-to-Physical Address Mapping and Cache Write Methods

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,2$ using four frames, showing that LRU incurs fewer faults.

FIFO simulation results in $10$ page faults.
LRU simulation results in $9$ 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.

Browse all research articles