Consider a Direct Mapped Cache with 8 cache blocks (numbered 0 to 7). If the memory block requests are in the following order:
3, 5, 2, 5, 8, 63, 9, 16, 20, 17, 25, 18, 30, 24, 2, 63, 5, 82, 17, 24
Which of the following memory blocks will NOT be present in the cache at the end of the sequence?
A. 3 B. 18 C. 20 D. 30
GATE 2007 · Computer Organization and Architecture · Cache Memory · medium
Answer: Block 18 is NOT present in the cache at the end of the sequence (it was evicted by block 82 which maps to the same slot). Answer: B. 18
Map all referenced blocks to their cache slots: Block 3: 3 mod 8 = 3 → slot 3
Block 5: 5 mod 8 = 5 → slot 5
Block 2: 2 mod 8 = 2 → slot 2
Block 8: 8 mod 8 = 0 → slot 0
Block 63: 63 mod 8 = 7 → slot 7
Block 9: 9 mod 8 = 1 → slot 1
Block 16: 16 mod 8 = 0 → slot 0
Block 20: 20 mod 8 = 4 → slot 4
Block 17: 17 mod 8 = 1 → slot 1
Block 25: 25 mod 8 = 1 → slot 1
Block 18: 18 mod 8 = 2 → slot 2
Block 30: 30 mod 8 = 6 → slot 6
Block 24: 24 mod 8 = 0 → slot 0
Block 2: 2 mod 8 = 2 → slot 2 (again)
Block 63: 63 mod 8 = 7 → slot 7 (again)
Block 5: 5 mod 8 = 5 → slot 5 (again)
Block 82: 82 mod 8 = 2 → slot 2
Block 17: 17 mod 8 = 1 → slot 1 (again)
Block 24: 24 mod 8 = 0 → slot 0 (again)
Find the last block loaded into each slot (scan sequence right to left): Processing sequence from right (last) to left (first), first occurrence for each slot wins:
Sequence (with positions): ...82(pos18,slot2), 17(pos19,slot1), 24(pos20,slot0)
Slot 0: last reference is block 24 (position 20) → Slot 0 = 24
Slot 1: last reference is block 17 (position 19) → Slot 1 = 17
Slot 2: last reference is block 82 (position 18) → Slot 2 = 82 [block 18 was earlier at pos12, block 2 even earlier, then 82 is latest]
Slot 3: last (and only) reference is block 3 (position 1). But wait — is there any other block with mod 8 = 3? Check: 11 mod 8=3? No 11 in sequence. 19 mod 8=3? No 19. 27 mod 8=3? No. So Slot 3 = 3? But then the answer wouldn't be A.
Wait — let me recheck: sequence is 3,5,2,5,8,63,9,16,20,17,25,18,30,24,2,63,5,82,17,24
Blocks mapping to slot 3 (mod 8 = 3): 3(pos1), 11, 19, 27, 35, 43, 51, 59, 67, 75, 82 mod 8=2 (not 3)...
82 mod 8: 82 = 10×8 + 2 → 82 mod 8 = 2. So 82 → slot 2.
Is block 3 still the last one in slot 3? Let me check all 20 items for mod=3:
3 mod 8=3 ✓, 5 mod 8=5, 2 mod 8=2, 5 mod 8=5, 8 mod 8=0, 63 mod 8=7, 9 mod 8=1, 16 mod 8=0, 20 mod 8=4, 17 mod 8=1, 25 mod 8=1, 18 mod 8=2, 30 mod 8=6, 24 mod 8=0, 2 mod 8=2, 63 mod 8=7, 5 mod 8=5, 82 mod 8=2, 17 mod 8=1, 24 mod 8=0.
Only block 3 maps to slot 3! So final Slot 3 = 3.
Final cache: Slot0=24, Slot1=17, Slot2=82, Slot3=3, Slot4=20, Slot5=5, Slot6=30, Slot7=63.
Now check the options:
A. Block 3 → in Slot 3 ✓ (IS present)
B. Block 18 → Slot 2, but last block in Slot 2 is 82, so 18 is NOT present.
C. Block 20 → Slot 4, only block mapping to slot 4 is 20 → IS present.
D. Block 30 → Slot 6, only block mapping to slot 6 is 30 → IS present.
So the block NOT present is Block 18 (it was overwritten by block 82).
Answer should be B. 18.
But wait, the image shows the sequence ending at the page boundary. Let me verify by checking the image shows: 3,5,2,5,8,63,9,16,20,17,25,18,30,24,2,63,5,82,17,24 — Yes.
Block 18 → Slot 2: sequence for slot 2 is: 2(pos3), 18(pos12), 2(pos15), 82(pos18). Last = 82. So block 18 is NOT present.
Actual answer = B. 18.