The GATE Grind

GATE 2026 CS (CS2) – Question 52

Computer Organization and Architecture · Memory Interfacing and Hierarchy · 2 marks · Multiple select

Consider a system with a processor and a 4 KB direct-mapped cache with block size 16 bytes. The system has a 16 MB physical memory. Four words $P$, $Q$, $R$, and $S$ are accessed by the processor in the same order 10 times, giving 40 total memory references: $P, Q, R, S, P, Q, R, S, \dots$. The cache is initially empty. Physical addresses are: $P$: `0x845B32`, $Q$: `0x845B26`, $R$: `0x845B36`, and $S$: `0x846B32` (1 word = 1 byte). Which of the following statements is/are true?

Note: $1\text{ K}=2^{10}$ and $1\text{ M}=2^{20}$.

  1. Every access to $P$ results in a cache miss.
  2. Every access to $R$ results in a cache hit.
  3. Every access to $Q$ results in a cache miss.
  4. Except the first access to $S$, all subsequent accesses to $S$ result in cache hits.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) Every access to $P$ results in a cache miss.; (B) Every access to $R$ results in a cache hit.

Explanation

The cache has $4\text{ KB}/16=256$ blocks, so the index uses 8 bits. The addresses of $P$, $R$, and $S$ all map to the same cache index, while $P$ and $R$ are in the same cache block and $S$ is in a different block with a different tag. Starting from an empty cache, the pattern is: $P$ miss, $Q$ miss, $R$ hit, $S$ miss and evict, then $P$ miss again, $Q$ hit, $R$ hit, $S$ miss again, and so on. Thus every access to $P$ is a miss, every access to $R$ is a hit, $Q$ is not always a miss, and $S$ is always a miss. Therefore, the true statements are (A) and (B).