Consider a small two-way set-associative cache memory, consisting of four…
2004
Consider a small two-way set-associative cache memory, consisting of four blocks. For choosing the block to be replaced, use the least recently used (LRU) scheme. The number of cache misses for the following sequence of block addresses is 8, 12, 0, 12, 8
- A.
2
- B.
3
- C.
4
- D.
5
Attempted by 175 students.
Show answer & explanation
Correct answer: C
Solution: Simulate a 4-block two-way set-associative cache using LRU replacement.
Key facts: total blocks = 4, two-way associative ⇒ number of sets = 4 / 2 = 2 sets. Each set holds 2 blocks. Use block_number mod 2 to determine set index. All addresses in the sequence are even, so they all map to the same set (set 0). We therefore simulate a 2-entry (per-set) cache with LRU for that set.
Access 8: miss. Insert 8 into set 0. Cache state for set 0 (MRU → LRU): [8]. Misses = 1.
Access 12: miss. Insert 12 into set 0. Cache state for set 0 (MRU → LRU): [12, 8]. Misses = 2.
Access 0: miss. Set 0 is full (2 ways). Evict the LRU block (8) and insert 0 as MRU. Cache state: [0, 12]. Misses = 3.
Access 12: hit. 12 is present; update LRU so 12 becomes MRU. Cache state: [12, 0]. Misses remain = 3.
Access 8: miss. 8 was previously evicted, so evict the LRU (0) and insert 8 as MRU. Cache state: [8, 12]. Misses = 4.
Total cache misses = 4.
A video solution is available for this question — log in and enroll to watch it.