Consider a small 2-way set-associative cache memory consisting of four blocks.…
2007
Consider a small 2-way set-associative cache memory consisting of four blocks. Use the least recently used (LRU) policy to choose the block to be replaced. What is the number of cache misses for the following sequence of block addresses: 8, 12, 0, 12, 8?
Answer: C. 4 — ConceptIn a k-way set-associative cache, each set holds k blocks. A block address maps to one set, and LRU replaces the block in that set whose most recent…
- A.
2
- B.
3
- C.
4
- D.
5
Attempted by 308 students.
Show answer & explanation
Correct answer: C
Concept
In a k-way set-associative cache, each set holds k blocks. A block address maps to one set, and LRU replaces the block in that set whose most recent access is the oldest. A cache miss occurs when the requested block is absent from its mapped set.
Application
Four blocks with 2-way associativity give 4 / 2 = 2 sets. Using the block-address convention, the set index is the block address modulo 2; therefore 8, 12, and 0 all map to set 0.
Access 8: set 0 is empty, so this is a miss. The set now contains [8].
Access 12: 12 is absent, so this is a miss. The set now contains [8, 12], with 8 least recently used.
Access 0: 0 is absent, so this is a miss. The full set evicts 8 under LRU and becomes [12, 0].
Access 12: 12 is present, so this is a hit. Recency changes, making 0 the least recently used block.
Access 8: 8 was evicted and is absent, so this is a miss. The full set evicts 0.
Cross-check
The only hit is the second access to 12. Thus the five accesses contain one hit and 5 - 1 = 4 misses, so the number of cache misses is 4.