Consider a system with a processor and a 4 KB direct mapped cache with block…

2026

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

  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

Attempted by 25 students.

Show answer & explanation

Correct answer: A, B

1. Cache Configuration Analysis

Cache Size = 4 KB = 2^12 bytes. Block Size = 16 bytes = 2^4 bytes. Number of Cache Lines = 2^12 / 2^4 = 2^8 = 256 lines. Index Bits = log2(256) = 8 bits. Offset Bits = log2(16) = 4 bits. Physical Address = 16 MB = 2^24 bits. Tag Bits = 24 - 8 - 4 = 12 bits.

2. Address Breakdown (Tag | Index | Offset)

P: 0x845B32 -> Tag: 0x845 | Index: 0xB3 | Offset: 0x2 Q: 0x845B26 -> Tag: 0x845 | Index: 0xB2 | Offset: 0x6 R: 0x845B36 -> Tag: 0x845 | Index: 0xB3 | Offset: 0x6 S: 0x846B32 -> Tag: 0x846 | Index: 0xB3 | Offset: 0x2

3. Access Sequence Analysis (Initially Empty Cache)

Iteration 1: - P: Miss (Load 0xB3, Tag 0x845) - Q: Miss (Load 0xB2, Tag 0x845) - R: Hit (Index 0xB3, Tag 0x845 matches) - S: Miss (Index 0xB3, Tag 0x846 != 0x845). Evicts P. Iteration 2: - P: Miss (Index 0xB3, Tag 0x845 != 0x846). Evicts S. - Q: Hit (Index 0xB2, Tag 0x845) - R: Hit (Index 0xB3, Tag 0x845) - S: Miss (Index 0xB3, Tag 0x846 != 0x845). Evicts R.

4. Conclusion

P always misses due to conflict with S. Q hits after first access (unique index). R always hits (P loads block before R). S always misses due to conflict with P.

Explore the full course: Gate Guidance By Sanchit Sir