--- title: "Need for replacement algorithm in cache" subject: "Computer Organization and Architecture" chapter: 6 key: "semester_5/computer_organization_and_architecture:replacement-why" source: https://www.bctengineer.com/q/semester_5/computer_organization_and_architecture/replacement-why site: BCT Engineering --- # Need for replacement algorithm in cache Computer Organization and Architecture · Chapter 6: Memory System - Asked in: 2067 Asar (old course), 8 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-why - Whole chapter: https://www.bctengineer.com/md/semester_5/computer_organization_and_architecture/chapter-6 ## Question Why is a replacement algorithm used when designing the cache? Explain with example. ## Short answer When a set is full in associative or set-associative mapping, a new block must replace an existing one on a miss. The replacement algorithm (LRU, FIFO, etc.) selects the block to evict, aiming to keep frequently/recently used data for high hit ratio. Direct mapping needs no algorithm. ## Answer The cache holds only a few of the many blocks of main memory. In associative and set associative mapping, a new block may be placed in any line of the cache or the set. When all these lines are full and a miss occurs, one block must be removed to make room. The replacement algorithm chooses that block. It is needed so that the cache keeps taking new blocks while keeping the most useful ones, which keeps the hit ratio high. (In direct mapping the line is fixed, so no algorithm is needed.) #### Replacement algorithms - **LRU:** removes the block unused for the longest time. - **FIFO:** removes the oldest block. - **LFU:** removes the block with the fewest accesses. - **Random:** removes a random line. #### Example: cache with 3 lines, references 1, 2, 3, 1, 4, 1, 2 ```text Ref FIFO cache Result LRU cache Result 1 [1] miss [1] miss 2 [1, 2] miss [1, 2] miss 3 [1, 2, 3] miss [1, 2, 3] miss 1 [1, 2, 3] hit [2, 3, 1] hit 4 [2, 3, 4] miss [3, 1, 4] miss 1 [3, 4, 1] miss [3, 4, 1] hit 2 [4, 1, 2] miss [4, 1, 2] miss ``` FIFO gets 1 hit and LRU gets 2 hits out of 7 references. At reference 4 the cache is full, so a block must be replaced. FIFO removes 1 (loaded first) even though it was just used, and later has to fetch 1 again. LRU removes 2 (least recently used) and keeps 1, so it gets an extra hit. The replacement algorithm therefore decides how many misses follow. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. When is a replacement algorithm needed? A. On a hit B. On a miss when all candidate lines are full C. Never D. Direct mapping Answer: B. One block must be removed. (Key point: Why) 2. In the 3-line example, which block does FIFO remove at reference 4? A. 2 B. 1 C. 3 D. 4 Answer: B. Block 1 was loaded first. (Key point: FIFO vs LRU) 3. Which does LRU remove at reference 4? A. 1 B. 2 C. 3 D. None Answer: B. 2 is least recently used. (Key point: LRU) 4. Hits for FIFO and LRU out of 7? A. 1 and 2 B. 2 and 1 C. 3 and 3 D. 0 and 1 Answer: A. FIFO 1, LRU 2. (Key point: Hits) ## Related in Computer Organization and Architecture - [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 - [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 - [LRU replacement with hit and miss](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Alru-replacement) — Computer Organization and Architecture, chapter 6 - [Direct mapping with 32-block memory, 8-block cache](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Adirect-mapping-example) — Computer Organization and Architecture, chapter 6, asked 3× - [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× - [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 - [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 - [Cache replacement policies](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Acache-replacement-policies) — Embedded System, chapter 4 - [Replacement strategy for four-year need](https://www.bctengineer.com/question.md?key=semester_6%2Fengineering_economics%3Areplace-machine-aec-four-years) — Engineering Economics, chapter 5 - [Election algorithm need and example](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aelection-scenario) — Distributed System, chapter 6, asked 2×