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

# Mapping function and replacement algorithm

Computer Organization and Architecture · Chapter 6: Memory System

- Asked in: 2069 Asar, 2+6 marks
- Video: [Cache Memory ||Direct Mapping|Associative Mapping-Set Associative-Computer Organization Architecture](https://www.youtube.com/watch?v=beqOrVgxsA0) — Sudhakar Atchala
- 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/mapping-replacement
- Whole chapter: https://www.bctengineer.com/md/semester_5/computer_organization_and_architecture/chapter-6

## Question

What do you mean by mapping function? Why is a replacement algorithm used in associative and set associative mapping? Explain with example.

## Short answer

Mapping function decides cache placement (direct, associative, set associative). Replacement algorithms like LRU, FIFO are required for associative and set associative caches when all candidate lines are full; direct mapping has no choice. Example: In a 2-way set with A and B, a miss for C may evict the least recently used block (A).

## Answer

#### Mapping function
The mapping function decides in which cache line a block of main memory is placed, because the cache has far fewer lines than main memory has blocks. The three functions are direct, associative and set associative mapping.

#### Why a replacement algorithm is used
In associative and set associative mapping a block may be placed in more than one line (any line of the cache or of the set). When a miss occurs and all candidate lines are already filled, the hardware must pick one line to be overwritten. A replacement algorithm makes that choice. In direct mapping there is only one possible line, so no choice (and no algorithm) is needed.

#### Common algorithms
- **LRU:** removes the block unused for the longest time (best hit ratio).
- **FIFO:** removes the block that has been in the cache longest.
- **LFU:** removes the block with fewest references.
- **Random:** removes any line; cheap and fairly good.

#### Example
A 2-way set has blocks A and B (A used earlier). Block C maps to this set and misses. The set is full, so one of A or B must go. FIFO or LRU removes A (assuming A was the oldest and the least recently used), then the set holds B and C. If a later request is for A, it is a miss and a block is replaced again.

Using the 4-line cache LRU sequence 2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2 gives 6 hits and 6 misses; block 3 is evicted at the reference to 4 because it is the least recently used.

## Check yourself

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

1. What does a mapping function decide?
   A. Which CPU instruction runs
   B. In which cache line a main-memory block is placed
   C. The disk speed
   D. The word size
   Answer: B. Cache has far fewer lines than memory blocks, so a rule is needed to place blocks. (Key point: Mapping function)

2. Why is a replacement algorithm needed in associative and set associative mapping?
   A. A block can go to more than one line, so a victim must be chosen when all are full
   B. Tags are too short
   C. The block has only one possible line
   D. The CPU is slow
   Answer: A. Several candidate lines exist, so the hardware must choose one. (Key point: Need for replacement)

3. Why does direct mapping not need one?
   A. It has bigger cache
   B. Each block has only one possible line, which is overwritten
   C. It uses LRU internally
   D. It never has misses
   Answer: B. There is no choice of victim. (Key point: Direct mapping)

## Related in Computer Organization and Architecture

- [Replacement algorithm in associative mapping](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Areplacement-assoc) — Computer Organization and Architecture, chapter 6
- [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×
- [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 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
- [Write policy; direct vs associative mapping](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Awp-direct-vs-assoc) — 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×

## 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