IAE Academy

GATE 2026 CS2 Q.52: solution and answer

GATE 2026 · CS2Q.52 · 2 marks · MSQ

Consider a system with a processor and a 4 KB direct mapped cache with block size of 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. That is, there are a total of 40 memory references in the sequence P, Q, R, S, P, Q, R, S, …

Assume that the cache memory is initially empty. The physical addresses of the words are given below (1 word = 1 byte).

P: 0x845B32, Q: 0x845B26, R: 0x845B36, S: 0x846B32

Which of the following statements is/are true?

Note: 1K= and 1M=

  1. (A)

    Every access to P results in a cache miss

  2. (B)

    Every access to R results in a cache hit

  3. (C)

    Every access to Q results in a cache miss

  4. (D)

    Except the first access to S, all subsequent accesses to S result in cache hits

See the question in the paper
GATE 2026 CS2 question 52Tap to open full size

Answer and solution

ANSWER

Statements A and B are true.

Official answer: A, BSource: Official answer key, GATE 2026 CS2 (IIT Guwahati)

  1. Cache size 4 KB, block size 16 B ⇒ number of lines = , so offset = 4 bits, index = 8 bits. Physical memory 16 MB = ⇒ address width 24 bits, so tag = bits.

  2. offset + index = 12 bits = 3 hex digits, and tag = 12 bits = 3 hex digits, so each 6-hex-digit physical address splits exactly as: tag = first 3 hex digits, index = next 2 hex digits, offset = last hex digit.

  3. P = 845B32 → tag 845, index B3, offset 2. Q = 845B26 → tag 845, index B2, offset 6. R = 845B36 → tag 845, index B3, offset 6. S = 846B32 → tag 846, index B3, offset 2.

  4. P and R share tag 845 and index B3, so they lie in the SAME 16-byte cache block (their offsets 2 and 6 both fall inside one block, whose offsets run 0-15). S has the same index B3 but a different tag (846), so S maps to the same cache line as P/R and evicts whatever currently occupies it. Q has index B2, a line never touched by P, R or S.

  5. Round 1 (cache initially empty): access P → miss, loads block (tag 845, index B3) into line B3. Access Q → miss, loads block (tag 845, index B2) into line B2. Access R → line B3 already holds tag 845, matching R's tag → hit. Access S → line B3 holds tag 845 ≠ 846 → miss, loads block (tag 846, index B3), evicting the P/R block.

  6. Round 2 onward: access P → line B3 now holds tag 846 (from S) ≠ 845 → miss, reloads block (845, B3). Access Q → line B2 still holds tag 845, untouched by anything else → hit. Access R → line B3 was just reloaded by P with tag 845 → hit. Access S → line B3 now holds tag 845 (from P) ≠ 846 → miss, reloads block (846, B3).

  7. This P-miss / Q-hit / R-hit / S-miss pattern (with Q's very first access also being a miss) repeats identically for rounds 2 through 10, since P and S perpetually evict each other's block from line B3 while line B2 (Q) is never disturbed by anyone else.

  8. Evaluate each option: (A) P misses on all 10 of its accesses — TRUE. (B) R hits on all 10 of its accesses, including round 1 — TRUE. (C) Q misses only on its first access and hits on the remaining 9 — FALSE, since "every access" is wrong. (D) S misses on every single access (not just the first), because P re-evicts S's block each round before S is next accessed — FALSE.

KEY IDEA

In a direct-mapped cache, split the 24-bit physical address into tag/index/offset. Here offset+index together equal exactly 3 hex digits and tag also equals exactly 3 hex digits, so a 6-hex-digit address splits cleanly as tag = first 3 digits, index = next 2 digits, offset = last digit. Two addresses share a cache block only if BOTH tag and index match; they conflict (evict each other) if only the index matches.

WATCH OUT FOR

Assuming S, having a different tag from P/R, must land in a different cache line and never interferes with them — missing that S shares the SAME index (B3) with P and R, which is exactly what causes S to evict, and be evicted by, the P/R block every round. A second common slip is assuming R's very first access must be a miss like P's, overlooking that R is accessed right after P has just loaded that same block within round 1.

From the GATE 2026 CS2 paper. Every question of this paper · Download the full paper · All 22 Memory & cache questions, with notes

More Memory & cache questions