---
title: "Replacement algorithm in associative mapping"
subject: "Computer Organization and Architecture"
chapter: 6
key: "semester_5/computer_organization_and_architecture:replacement-assoc"
source: https://www.bctengineer.com/q/semester_5/computer_organization_and_architecture/replacement-assoc
site: BCT Engineering
---

# Replacement algorithm in associative mapping

Computer Organization and Architecture · Chapter 6: Memory System

- Asked in: 2076 Chaitra, 4 marks
- Video: [L-3.12: Cache Replacement Algorithms in Computer Organisation and Architecture](https://www.youtube.com/watch?v=EXRicJapuOQ) — Gate Smashers
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_5/computer_organization_and_architecture/replacement-assoc
- Whole chapter: https://www.bctengineer.com/md/semester_5/computer_organization_and_architecture/chapter-6

## Question

Why is a replacement algorithm necessary in associative mapping? Justify.

## Short answer

In associative mapping any block can occupy any line, so when the cache is full a miss requires choosing which existing block to replace. A replacement algorithm (e.g., LRU) selects the victim to maximize hit ratio; without it the cache cannot accept new blocks once full. The algorithm is implemented in hardware for nanosecond decisions.

## Answer

In associative mapping a block of main memory may be placed in **any** cache line. The cache is small, so after some time all lines are occupied. When a new block is requested and misses, there is no free line, and the new block is not tied to one fixed line as in direct mapping.

- The hardware must therefore decide which of the existing blocks is to be replaced. This decision is made by a replacement algorithm.
- A good algorithm (LRU, FIFO, LFU, random) removes the block least likely to be needed soon. A bad choice removes a useful block and causes extra misses, which lowers the hit ratio.
- The algorithm is implemented in hardware, as the decision must be made in nanoseconds so that the cache stays fast.

Without such a rule the cache could not continue to take new blocks once it is full.

## Check yourself

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

1. Why is a replacement algorithm needed in associative mapping?
   A. Blocks have a fixed line
   B. When the cache is full a victim must be chosen among all lines
   C. Tags are missing
   D. To increase the tag
   Answer: B. Any line is a candidate, so the choice must be made. (Key point: Why needed)

2. What does a poor algorithm cause?
   A. Fewer misses
   B. Useful block removed, extra misses and lower hit ratio
   C. Bigger cache
   D. Faster writes
   Answer: B. Removing a useful block hurts hit ratio. (Key point: Bad choice)

3. Why is it implemented in hardware?
   A. It is cheaper in software
   B. The decision must be made in nanoseconds to keep the cache fast
   C. It cannot be programmed
   D. For tags
   Answer: B. Speed demands hardware. (Key point: Implementation)

## Related in Computer Organization and Architecture

- [Associative mapping and replacement algorithms](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Aassociative-mapping) — Computer Organization and Architecture, chapter 6, asked 2×
- [Mapping function and replacement algorithm](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Amapping-replacement) — Computer Organization and Architecture, chapter 6
- [Why direct mapping needs no replacement](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Adirect-no-replacement) — Computer Organization and Architecture, chapter 6, asked 2×
- [Set associative mapping](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Aset-assoc-mapping) — Computer Organization and Architecture, chapter 6
- [Associative cache mapping with example](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Aassoc-cache-example) — Computer Organization and Architecture, chapter 6
- [Associative vs set associative mapping](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Aassoc-vs-setassoc) — Computer Organization and Architecture, chapter 6

## Related in other subjects

- [Associative cache mapping](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Aassociative-cache-mapping) — Embedded System, chapter 4, asked 2×
- [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