---
title: "Cache replacement policies"
subject: "Embedded System"
chapter: 4
key: "semester_6/embedded_system:cache-replacement-policies"
source: https://www.bctengineer.com/q/semester_6/embedded_system/cache-replacement-policies
site: BCT Engineering
---

# Cache replacement policies

Embedded System · Chapter 4: Memory

- Asked in: 2071 Magh, 3 marks
- Video: [Cache Memory. Lec 3: Cache Replacement Policies (Random, FIFO, LRU, PLRU & LFU) | COA Module 7.4](https://www.youtube.com/watch?v=SEgeCPAk2yQ) — Batchmate
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_6/embedded_system/cache-replacement-policies
- Whole chapter: https://www.bctengineer.com/md/semester_6/embedded_system/chapter-4

## Question

Write the cache replacement policies.

## Short answer

Common cache replacement policies include: random (choose any block), FIFO (evict the oldest-loaded), LRU (evict the least recently used), and LFU (evict the least frequently used). LRU typically yields the best hit rate but needs tracking circuitry. Direct-mapped caches require no policy.

## Answer

When a miss occurs and the cache (or the set) is full, a block must be evicted. The common replacement policies are:

1. **Random:** pick a line at random. Simple and cheap, but may remove a frequently used block.
2. **FIFO (first in, first out):** evict the block that has been in the cache the longest. Easy, but ignores how often the block is used.
3. **LRU (least recently used):** evict the block not used for the longest time, using locality of reference. Best hit ratio, but needs usage-tracking hardware.
4. **LFU (least frequently used):** evict the block with the fewest accesses, using counters.

Direct-mapped caches need no policy, since each block has only one possible line.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. Which policy evicts the block that has not been used for the longest time?
   A. FIFO
   B. LRU
   C. LFU
   D. Random
   Answer: B. LRU uses locality of reference and removes the least recently used block. (Key point: LRU)

2. What is the main weakness of FIFO replacement?
   A. It needs usage counters
   B. It picks blocks at random
   C. It ignores how often or how recently a block is used
   D. It only works for direct-mapped caches
   Answer: C. FIFO evicts the oldest-loaded block regardless of usage, so a heavily used block may be removed. (Key point: FIFO weakness)

3. Why does a direct-mapped cache need no replacement policy?
   A. It never has misses
   B. Each block has only one possible line
   C. It uses write-through
   D. It always uses LRU internally
   Answer: B. With only one possible line per block, there is no choice of victim. (Key point: Direct-mapped caches)

4. LFU chooses which block to evict?
   A. The one with the fewest accesses
   B. The oldest loaded
   C. A random one
   D. The one most recently used
   Answer: A. LFU uses counters and evicts the block with the fewest accesses. (Key point: LFU)

## Related in Embedded System

- [Cache write policy and replacement algorithm](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Acache-write-policy-replacement) — Embedded System, chapter 4

## Related in other subjects

- [Need for replacement algorithm in cache](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Areplacement-why) — Computer Organization and Architecture, chapter 6