GATE CS 2026 Set 2 Q42 — Memory Hierarchy: Cache, Main Memory and Secondary Storage

To determine the cache hit/miss behavior, we first analyze how the 24-bit physical address is split into Tag, Index, and Offset fields:

• Physical Address Space: $16\text{ MB} = 2^{24}\text{ bytes} \implies 24\text{ bits}$
• Block Size: $16\text{ bytes} = 2^4\text{ bytes} \implies 4\text{ bits}$ Offset (last hex digit)
• Number of Cache Blocks: $\frac{4\text{ KB}}{16\text{ bytes}} = 256 = 2^8 \implies 8\text{ bits}$ Index (middle 2 hex digits)
• Tag Size: $24 - 8 - 4 = 12\text{ bits}$ Tag (first 3 hex digits)

Using this mapping, we extract the fields for each address:

Note that P and R reside in the exact same cache block (same Tag 0x845 and Index 0xB3), while S maps to the same index 0xB3 but with a different Tag 0x846. Q maps to a different index 0xB2.

Let us trace the access sequence $\text{P, Q, R, S, P, Q, R, S, } \dots$

• Iteration 1:
  • P (Index 0xB3): Miss (cold). Block 0x845B3 is loaded.
  • Q (Index 0xB2): Miss (cold). Block 0x845B2 is loaded.
  • R (Index 0xB3): Hit (since block 0x845B3 is already in index 0xB3).
  • S (Index 0xB3): Miss (conflict). Block 0x846B3 replaces block 0x845B3.
• Iteration 2 to 10:
  • P (Index 0xB3): Miss (conflict with S). Block 0x845B3 is loaded.
  • Q (Index 0xB2): Hit (block 0x845B2 remains undisturbed).
  • R (Index 0xB3): Hit (block 0x845B3 was just loaded by P).
  • S (Index 0xB3): Miss (conflict with P/R). Block 0x846B3 is loaded.

Thus:

• A is True: Every access to $\text{P}$ results in a cache miss.
• B is True: Every access to $\text{R}$ results in a cache hit.
• C is False: Only the first access to $\text{Q}$ is a miss; the remaining 9 are hits.
• D is False: Every access to $\text{S}$ results in a cache miss.