Which options are correct in GATE CS 2026 Set-2 Q52 on cache hit/miss analysis?

The correct options are A and B. P, R, and S all map to cache line 179. In the access sequence P→Q→R→S: R always hits (P loads its block just before R is accessed), P always misses (S evicts its block every cycle), Q hits after the first miss, and S always misses (P evicts its block before each S access). The website answer of A, B, D is incorrect — D is false because S always misses.

Why do P, R, and S all map to the same cache line?

Cache line = floor(address / block_size) mod number_of_lines. With block size = 16 and 256 lines: P (0x845B32) → block 0x845B3 → line 179; R (0x845B36) → block 0x845B3 → line 179 (same block as P); S (0x846B32) → block 0x846B3 → line 179 (different block, same line). This causes conflict misses between P/R and S.

Why does R always result in a cache hit despite the conflict?

R shares the same memory block as P (both in block 0x845B3). In the access order P→Q→R→S, P is always accessed immediately before R. When P is accessed, it loads block 0x845B3 into cache line 179. When R is then accessed, it finds its block already in line 179 — guaranteed hit every time, including the very first access.

Direct Mapped Cache Hit Miss Analysis P Q R S | GATE CS 2026 Set-2 Q52

Computer Sciences > GATE 2026 SET-2 > Computer Organization

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=210 and 1M=220

Every access to P results in a cache miss

Every access to R results in a cache hit

Every access to Q results in a cache miss

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

Correct : a,b

The correct answers are Option A and Option B.
Cache configuration: Cache = 4 KB, block size = 16 bytes → 256 cache lines. Address split: [Tag: 12 bits | Index: 8 bits | Offset: 4 bits]. Cache line = lower 8 bits of block address = floor(address / 16) mod 256.
Cache line mapping: P (0x845B32) → block 0x845B3 → line 179. Q (0x845B26) → block 0x845B2 → line 178. R (0x845B36) → block 0x845B3 → line 179 (same block as P). S (0x846B32) → block 0x846B3 → line 179 (same line as P and R, different block).
Access trace — Round 1 (P→Q→R→S): P hits empty cache → MISS, loads block 0x845B3 into line 179. Q hits empty line 178 → MISS, loads block 0x845B2. R checks line 179 which has P's block → HIT. S checks line 179 which has P's block, tag mismatch → MISS, evicts P/R's block, loads block 0x846B3.
Round 2+ onwards: P checks line 179 which has S's block → MISS, loads block 0x845B3 back. Q checks line 178 still intact → HIT. R checks line 179 which just loaded P's block → HIT. S checks line 179 which has P's block → MISS again.
Option A — Every access to P is a miss: P always finds S's block in line 179 → TRUE. Correct.
Option B — Every access to R is a hit: R always finds P's freshly loaded block in line 179 → TRUE. Correct.
Option C — Every access to Q is a miss: Q misses only on first access; all subsequent accesses hit since nothing evicts line 178 → FALSE. Incorrect.
Option D — All accesses to S after the first result in hits: P evicts S's block every round before S is accessed again → S always misses → FALSE. Incorrect.

Similar Questions

Related Topics

Similar Questions

Related Topics

Question Options

Sign in to ExamPrev