GATE CS 2009 Q29 — Memory Hierarchy: Cache, Main Memory and Secondary Storage

The cache is $4$-way set associative with $16$ blocks. Therefore, the number of sets is:

Each memory block $B$ maps to a set using the formula: $\text{Set} = B \pmod 4$.

Let us trace the LRU queue for Set 0 (where blocks $0, 4, 8, 216, 48, 32, 92$ map) since the options $8$ and $216$ map here:

1. Request 0: Set 0 $\rightarrow [0]$
2. Request 4: Set 0 $\rightarrow [0, 4]$
3. Request 8: Set 0 $\rightarrow [0, 4, 8]$
4. Request 216: Set 0 $\rightarrow [0, 4, 8, 216]$ (Set is now full)
5. Request 8 (Hit): Set 0 $\rightarrow [0, 4, 216, 8]$ (8 becomes MRU)
6. Request 48 (Miss): Replace LRU block $0$ $\rightarrow [4, 216, 8, 48]$
7. Request 32 (Miss): Replace LRU block $4$ $\rightarrow [216, 8, 48, 32]$
8. Request 92 (Miss): Replace LRU block $216$ $\rightarrow [8, 48, 32, 92]$

At the end of the sequence, block $216$ is evicted from the cache. Tracing Set 1 and Set 3 shows that blocks $3$ and $129$ remain in the cache.