Consider 4-way set associative cache (initially empty) with total cache
Duration: 4 min
2009
Consider a 4-way set associative cache (initially empty) with total 16 cache blocks. The main memory consists of 256 blocks and the request for memory blocks is in the following order: 0, 255, 1, 4, 3, 8, 133, 159, 216, 129, 63, 8, 48, 32, 73, 92, 155. Which one of the following memory block will NOT be in cache if LRU replacement policy is used?
- A.
3
- B.
8
- C.
129
- D.
216
Attempted by 179 students.
Show answer & explanation
Correct answer: D
Key insight: A 4-way set associative cache with 16 blocks has 4 sets (16/4 = 4). A block maps to set index = block number mod 4. Each set holds up to 4 blocks and uses LRU replacement within the set.
Quick mapping of the given references (only final results summarized):
Set 0 (blocks with index 0): final contents are 92, 32, 48, 8 (most-recently-used to least-recently-used).
Set 1 (blocks with index 1): final contents are 73, 129, 133, 1 (most-recently-used to least-recently-used).
Set 2 (blocks with index 2): no blocks were loaded into this set during the sequence; it remains empty.
Set 3 (blocks with index 3): final contents are 155, 63, 159, 3 (most-recently-used to least-recently-used).
Why block 216 is not in the cache:
Block 216 maps to set 0 (216 mod 4 = 0) and was loaded into set 0 early in the sequence.
Later references filled set 0, and when block 92 was referenced, set 0 was full and LRU eviction removed block 216.
As a result, block 216 is not present in the final cache contents; the other candidate blocks (3, 8, 129) do remain in the cache.
A video solution is available for this question — log in and enroll to watch it.