--- title: "LRU replacement with hit and miss" subject: "Computer Organization and Architecture" chapter: 6 key: "semester_5/computer_organization_and_architecture:lru-replacement" source: https://www.bctengineer.com/q/semester_5/computer_organization_and_architecture/lru-replacement site: BCT Engineering --- # LRU replacement with hit and miss Computer Organization and Architecture · Chapter 6: Memory System - Asked in: 2078 Bhadra, 8 marks - Video: [L-3.13: LRU (Least Recently Used) Cache Replacement Algorithm | Computer Organisation & Architecture](https://www.youtube.com/watch?v=w32d1lD0Jb0) — 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/lru-replacement - Whole chapter: https://www.bctengineer.com/md/semester_5/computer_organization_and_architecture/chapter-6 ## Question Explain the Least Recently Used (LRU) replacement algorithm in case of hit and miss with suitable example. ## Short answer LRU replaces the least recently used block. On a hit, the accessed block becomes most recent. On a miss with a free line, the new block is loaded as most recent. On a miss with a full cache, the least recent block is evicted. Example: 4-block cache with reference string 2,3,2,1,5,2,4,5,3,2,5,2 yields 6 hits, 6 misses, hit ratio 0.5. ## Answer **LRU (Least Recently Used)** replaces the cache block that has not been used for the longest time. It uses temporal locality: a block used recently is likely to be used again soon. The hardware keeps an age (or use) counter for each line; on each access the age of the used line is reset and others are increased. - **Hit:** the block is in the cache; no replacement. The block becomes the most recently used. - **Miss with free line:** the block is loaded into a free line and becomes the most recently used. - **Miss with cache full:** the least recently used block is removed and the new block is loaded. #### Example: cache of 4 blocks, reference string 2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2 ```text Ref Result Cache (most recent first) 2 Miss [2] 3 Miss [3, 2] 2 Hit [2, 3] 1 Miss [1, 2, 3] 5 Miss [5, 1, 2, 3] 2 Hit [2, 5, 1, 3] 4 Miss (evict 3) [4, 2, 5, 1] 5 Hit [5, 4, 2, 1] 3 Miss (evict 1) [3, 5, 4, 2] 2 Hit [2, 3, 5, 4] 5 Hit [5, 2, 3, 4] 2 Hit [2, 5, 3, 4] ``` Hits = 6, misses = 6, hit ratio = 6/12 = 0.50. When 4 was referenced the cache was full and the least recently used block was 3, so 3 was evicted; when 3 came back, block 1 was the least recently used, so 1 was evicted. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What happens on a hit in LRU? A. Block is replaced B. No replacement; the block becomes most recently used C. Oldest block removed D. Cache cleared Answer: B. A hit just updates recency. (Key point: Hit) 2. On a miss with a free line? A. LRU block evicted B. Block loaded into free line, becomes most recent C. Request ignored D. Random block evicted Answer: B. No eviction is needed. (Key point: Miss with free line) 3. In the example, which block is evicted when 3 returns after 4 and 5? A. Block 2 B. Block 5 C. Block 1 D. Block 4 Answer: C. Cache is [5,4,2,1] most recent first, so 1 is LRU. (Key point: Eviction) 4. How many hits and misses in the example? A. 4 hits, 8 misses B. 6 hits, 6 misses C. 8 hits, 4 misses D. 5 hits, 7 misses Answer: B. Hit ratio 6/12 = 0.50. (Key point: Counts) ## Related in Computer Organization and Architecture - [Memory characteristics and LRU replacement](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Amemory-char-lru) — Computer Organization and Architecture, chapter 6 - [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 - [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 - [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× - [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 - [LRU algorithm; page faults on string](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Alru-page-faults-ref-string) — Operating System, chapter 4 - [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 - [Hits and faults: FIFO, LRU, Optimal](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Ahits-faults-fifo-lru-optimal-3frames) — Operating System, chapter 4 - [Page faults: LRU, FIFO, Optimum](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Apage-faults-lru-fifo-optimum) — Operating System, chapter 4