Project ForgeConsider 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 blocks will NOT be in cache if LRU replacement policy is used?
- A3
- B8
- C129
- 216
Explanation
With 16 blocks / 4-way = 4 sets, mapping by (block mod 4): Set 0 gets 0,4,8,216,8(hit),48,32,92 in order — tracing LRU eviction through this sequence with only 4 ways evicts 0, then 4, then 216 (in that order) as 48,32,92 arrive, leaving {8,48,32,92} at the end — so 216 is evicted and NOT in the final cache. Set 1 (1,133,129,73) has exactly 4 distinct blocks, all fit with no eviction. Set 3 (255,3,159,63,155) evicts 255, not 3. So only 216 among the given options ends up evicted.
Source: GATE CS 2009 (2009)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.